Round #283 (Div. 2) E. Distributing Parts

http://codeforces.com/contest/496/problem/E Greedy Algorithm Sorting songs and actors first by their lower bounds then by their upper bounds in non-decreasing order. For each song j in this order, assign a valid actor \[ ( c_i \leq a_j \: and \: b_j \leq d_i \: with \: k_i ) \] with the minimized \[ b_j \], if we cannot find such actor, the program terminates and outputs “NO”. Finding such actor can be done by two binary searches. Proof of Correctness Theorem 1 The algorithm produces a valid solution if there exists a valid solution. Proof: Suppose there is a valid solution for the sorted songs: For each song \[(a_i, b_i)\], an actor \[(c_i', d_i')\] was assigned for this song. For the first song \[(a_1, b_1)\], let \[(c_i'', d_i'')\] be the actor selected by the greedy algorithm for this song. Now we substitute \[(c_1', d_1')\] with \[(c_1'', d_1'')\] and prove that the solution is still valid. Case 1: i’=i’’ This is trivial. Case 2: \[i' \neq i''\] and the actor \[(c_1'', d_1'')\] will perform less than \[k_1''\] parts for the rest of the songs. The substitution produces a valid solution since there is an extra \[(c_1'', d_1'')\] we can use for \[(a_1, b_1)\] and the rest of assignments remains the same. Case 3:\[i' \neq i''\] and the actor \[(c_1'', d_1'')\] will perform exact \[k_1''\] parts for the rest of the songs. There exists a song \[(a_t, b_t)\] such that the actor \[(c_1'', d_1'')\] will perform on. Therefore, we have \(\begin{cases} c_1'' \leq a_t \leq b_t \leq d_1'', & \mbox{since it is a valid solution} \\ c_1'' \leq a_1 \leq b_1 \leq d_1'', & \mbox{since it is a valid solution} \\c_1' \leq a_1 \leq b_1 \leq d_1', & \mbox{since it is a valid solution} \\ a_1 \leq a_t & \mbox{songs are sorted} \\ d_1'' \leq d_1' & \mbox{this is how the algorithm works} \end{cases}\) \(\Rightarrow c_1' \leq a_t \leq b_t \leq d_1'\) Which implies that after swapping \[ (c_1', d_1')\] with \[(c_1'', d_1'')\], the solution is still valid. Continuing in this fashion and after substituting all original assignments, our greedy solution is a valid solution. Theorem 2 The algorithm produces “NO” if there does not exists a valid solution. Proof: Assume that the algorithm produces a solution if there does not exists a valid solution, then the produced solution must be a valid solution, otherwise our algorithm terminates before producing a solution, which contradicts that a valid solution does not exist in the first place. Combining Theorem 1 and 2 completes the proof of correctness. Time Complexity \[O(n\log n+m\log m+n(\log m)^2)=O(n(\log m)^2)\] if we use two binary searches for each song. There is a slightly better solution in the editorial http://codeforces.com/blog/entry/15208 which combines songs and actors and then sorts them altogether and then uses std::set or other balanced search trees. the time complexity is \[O((n+m)\log (n+m))\] Solution https://github.com/hujiewang/Programming-Contests/blob/master/codeforces/%23283/e.cpp