Funcia
Lv.3bitmaskdp

Minimum-Cost Task Assignment (Small)

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

There are N employees and N tasks; cost[i][j] is the cost of employee i doing task j. Assign each employee exactly one task, all tasks different, and return the minimum possible total cost.

Examples

costresult
[[9, 2, 7], [6, 4, 3], [5, 8, 1]]9
[[4]]4
[[1, 2], [1, 100]]3

Example 1 — Employee 0 → task 1 (2), employee 1 → task 0 (6), employee 2 → task 2 (1).

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(cost: int[][]) → int

Constraints

  • 1≤N=1 \le N = cost.length ≤20\le 20, cost[i].length =N= N
  • 0≤0 \le cost[i][j] ≤106\le 10^6

Expected complexity

Time
O(N * 2^N)
Space
O(2^N)

Examples

costExpected
[[9,2,7],[6,4,3],[5,8,1]]9
[[4]]4
[[1,2],[1,100]]3

Hint

Hint

Assign employees in order 0, 1, …; only the set of used tasks matters. With that set as a bitmask mask, the next employee is popcount(mask), and dp[mask | 1<<j] = min(dp[mask] + cost[popcount(mask)][j]) over unused j. Trying all N!N! permutations exceeds the time limit; O(N⋅2N)O(N \cdot 2^N) is enough.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.132548 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance605verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.