Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Ninja And The Clan

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

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 )
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
Full screen
Console