Ninja And The Clan

Moderate
0/80
Average time to solve is 24m
profile
Contributed by
0 upvote
Asked in company
Flipkart limited

Problem statement

There are ‘N’ Ninjas in a clan and the clan leader wants to assign ‘N’ tasks to each of the Ninjas. There is a ‘cost’ matrix of size ‘N’ x ‘N’, where ‘COST[i][j]’ denotes the cost of ‘i’th Ninja completing the ‘j’th task. The leader wants to assign the task in such a way that the total cost is minimized.

Note that each task is assigned to a single Ninja, and each Ninja will only be allotted a single task.

EXAMPLE: 
Input: 
'N' = 3
‘COST’ = [[1 2 3],
          [6 5 6],
          [3 8 9]]

Output: 11

A possible assignment is:
Assign task 1 to ninja 3, task 2 to ninja 1 and task 3 to ninja 2, total cost = 3 + 2 + 6 = 11
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', the number of test cases. For each test case

The first line of each test case an integer ‘N’ denoting the number of Ninjas and tasks.
The next ‘N’ lines  contain ‘N’ integers denoting the cost of ith Ninja completing the jth task.
Output format : 
For each test case, print a single integer denoting the minimum cost of the assignment.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= 'T' <= 10
1 <= 'N' <= 18
1 <= 'COST[i][j]' <= 10^5
Time Limit: 1 sec
Sample Input 1 :
2
2
10 13
12 14
3
1 1 1
2 2 1
1 2 1
Sample Output 1 :
24
3
Explanation Of Sample Input 1 :
For the first test case, a possible assignment can be:
Ninja 1 to task 1, Ninja 2 to task 2.

For the second test case, a possible assignment can be:
Ninja 1 to task 2, Ninja 2 to task 3, and Ninja 3 to task 1.
Sample Input 2 :
2
3
2 4 6
8 4 2
8 4 8
5
1 3 5 7 4
3 4 9 10 11
1 2 1 2 1
5 4 8 3 3
6 6 6 6 6
Sample Output 2 :
8
15
Hint

We have two choices for a person to take a task or leave it. so you use Dynamic Programming with BitMask?

Approaches (2)
Brute Force

Approach: 
 

We can generate all permutations of task assignments and for each assignment calculate the cost.

Find the minimum overall (N!) assignments
 

Algorithm :  

 

  • Create and initialize an array ‘ASSIGNMENT’ of size ‘N’ to store the current assignment of the task.
  • Initialize a ‘RES’ variable as ‘0’.
  • Run a for loop from i = 0 to n
    • Set task ‘i’ to person ‘i’
  • For each next lexicographically greater permutation :
    • Create a ‘TOTALCOST’ variable to store the cost of the permutation.
    • Run a for loop from i = 0 to ‘N’
      • Add COST[i][ASSIGNMENT[i]] to ‘TOTALCOST’.
    • ‘RES’ = min(RES, TOTALCOST)
  • return ‘RES’
Time Complexity

O(N!), Where ‘N’ is the number of ninjas and tasks.

There are a total of 'N!' Arrangement, the time complexity will be O(N!)

Space Complexity

O(N), Where ‘N’ is the number of ninjas and tasks.


As we are using the extra ‘assignment’ array of size ‘N’, the space complexity will be O(N)

Code Solution
(100% EXP penalty)
Ninja And The Clan
Full screen
Console