Author: Lucian Bicsi
Solved by:
First to solve: CodeBusters
Let's consider the job ids in order from left to right. One may argue that it is always optimal to put the current job id in the run with the smallest id that can be placed. This creates a scenario where the currently placed jobs in run always include the currently placed jobs in run , for all 1 \leq i < k. Intuitively, this allows for the most opportunity for future jobs to be able to be placed somewhere, without violating the current constraints.
We'll prove the greedy using an exchange argument: suppose there exist a solution, and that our approach does not yield a valid solution. Let's choose the solution with the longest common prefix with the greedy solution. Let be the first step where the (incorrect) greedy solution and the correct solution diverge. The correct solution will, then, not place the job in the first available run. Let's try to move it to the smallest run instead. This may create a number of conflicts, but one may prove that one may solve all conflicts with exchanges by induction on the earliest conflict.
Therefore, the solution is to place the -th occurence of job in the -th run. If a solution exists, then this solution is valid. It ultimately turns out that the dependencies are not useful for solving the problem, and they can just be ignored.
It is also, quite possible, that the problem can be solved "by Mistake", as a lot of approaches ultimately lead to something equivalent to the solution described above.
The total complexity is O(m + nk).