Some information about task CAR The final state of the parking center can easily be determined by sorting the input list of car types. This can be done in linear time (O(M+N)). O(N^2) and N*log N methods may be too slow for larger N. A greedy approach to construct successive rounds will work, since in each round it can be guaranteed that at least W-1 cars are put into their final position. Hence, the number of rounds needed by this greedy algorithm is D/(W-1) rounded up, where D is the number of displaced cars in the initial state for the input. In general, finding the minimum number of rounds is NP-complete. Even reducing the number of rounds for the greedy algorithm by just one round is, in general, as hard as finding the minimum (compare to bin packing: you need to find cycles that add up in length to W, for otherwise one worker is not doing useful work). The greedy algorithm can be implemented in O(N+M) space and O(N) time. However, a more naive implementation may use O(N) space and O(N^2) time. The test data has been designed to distinghuish linear solutions from less efficient ones. The 10 test cases have the following characteristics: # N M W Q D Min Max Kind of data -- ----- -- -- ----- ----- --- --- ------------ 1 5 5 2 5 0 1 1 Sorted 2 12 10 5 3 10 1 2 Manually designed 3 30 30 6 6 30 1 1 Manually designed 4 300 50 12 28 293 1 14 Random 5 500 50 27 20 485 3 16 Random 6 20000 50 5 5000 20000 400 400 4000 2-cycles, 4000 3-cycles 7 20000 50 49 417 20000 400 400 400 50-cycles 8 20000 50 2 20000 19595 368 439 Random 9 20000 50 10 2223 443 393 406 Sorted, randomly perturbed 10 20000 50 50 409 19087 345 449 Random where N = number of cars (input) M = number of car types (input) W = number of workers (input) Q = N / (W-1) rounded up D = number of displaced cars Min = minimum number of cars in a type, over all types Max = maximum number of cars in a type, over all types