Who takes which order
A delivery service's control room has n free couriers and n new orders. Each courier must get exactly one order, and each order must go to exactly one courier. For each pair it is known how many metres the courier has to drive to the order by road. How should the orders be assigned so that the couriers together drive as little as possible?
The dispatcher is used to giving each next courier the remaining order nearest to them. In the first sample this costs an extra 400 metres. The tests include real distances along the streets of Almaty.
Input
The first line holds n (1 ≤ n ≤ 16). Then n lines of n integers: the j-th number in the i-th line is how many metres courier i is from order j (0 ≤ number ≤ 106).
Output
One number: the smallest total distance in metres.
Examples
Example 1
2 300 500 400 1000
900
Example 2
4 9016 6428 10241 12160 8299 7953 4572 9492 10458 1812 4409 12842 8032 9107 5887 7446
22846
Limits
- Time · Python
- 2000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Trying all assignments is 16! ≈ 2 · 1013 options. What do you need to know about partly assigned orders to go on? Does it matter who exactly got the orders already given out?
2Hint 2
Give orders to the couriers in turn: the first, the second, the third… Then the set of orders already given out also tells you which courier is next.
3The idea
The state is the mask of orders given out. If the mask has k ones, the orders went to couriers 0, 1, … , k − 1, and the next is courier k. best[mask] is the smallest total distance for such an assignment; a transition gives courier k any free order j: best[mask | 2j] ← best[mask] + cost[k][j]. The answer is best of the full mask. This is bitmask DP, and the courier's number is not needed in the state: the number of ones in the mask gives it.
4Walkthrough
Why this works: for the future couriers only which orders are still free matters, not who took the others and how. Of all the ways to give the orders of a mask to the first k couriers, it is enough to remember the cheapest: any more expensive one with the same remainder can be replaced by it.
Masks are processed in increasing order: a transition only adds a bit, and the mask grows, so by the time a mask is processed all paths into it have been counted. There are 216 = 65,536 states, with at most 16 transitions from each, about a million operations.
The second sample has four couriers and four orders on the real streets of Almaty: the habit “give each the nearest” gives 28,904 metres, and the best assignment 22,846. With sixteen couriers in the tests the habit loses up to a fifth of the distance.
4+Solution
5Complexity
O(2n · n) time and O(2n) memory. For large n this assignment problem is solved by the Hungarian algorithm, published by Harold Kuhn in 1955, which in later versions runs in O(n³). Masks are good while n is up to twenty, and when the problem gets conditions the Hungarian algorithm cannot express: for example, that two couriers must not take orders in the same district.
6Common mistakes
- Each courier gets the nearest free order. Fails the first sample: 300 + 1000 instead of 500 + 400.
- The courier's number in the state. best[mask][i] is correct but n times larger than needed: the courier is determined by the mask anyway.
- Trying permutations. 16! options cannot be tried in any reasonable time.
Algorithms behind it
O(2ⁿ · n²) for the travelling salesman
2 problems
TEC
Technique
Bit tricks
A number as a set of flags: masks, the lowest set bit, counting ones and going through subsets without recursion.
O(1) per operation on a word
1 problem