Editorial for Valentine's Day '19 S4 - A Greedy Spouse


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Ninjaclasher

This problem was mainly implementation and casework.

For all the subtasks, we have to simulate the procedure that was described in the statement. In particular, we have to sort the tasks, and greedily assign the tasks to the computer.


The first subtask was meant to reward brute force solutions.

Time Complexity: \mathcal{O}(N^3) or \mathcal{O}(N^2)


For the second subtask, note that K = 1. For each task that is used originally, we can remove it, and perform the dynamic programming or greedy algorithm that places the most number of tasks in place of the removed task. A key optimization is to notice that any discarded task that intersects with more than 1 used task can never be added, so these can just be discarded completely. Out of the discarded tasks that are left, we can link each to the used task that it intersects, instead of looping through the discarded tasks every time.

Time Complexity: \mathcal{O}(N \log N)


For the third subtask, K \le 2. Since the K=1 solution is already explained above, we will only explain the K=2 solution here.

Instead of completely removing the tasks that intersect more than 1 used task, we now only remove the tasks that intersect more than 2 used tasks.

There are two cases:

  • The optimal solution consists of removing two used tasks that are not adjacent.
  • The optimal solution consists of removing two used tasks that are adjacent.

For the first case, the solution is exactly the same as above, except instead of keeping the running maximum, we keep track of the running maximum and second maximum.

For the second case, we can remove every adjacent pair of used tasks, and perform the same greedy/DP algorithm as above. However, now, we also need to keep track of the tasks that intersects exactly the two that we are removing, and keep those into account when running the greedy/DP algorithm.

Time Complexity: \mathcal{O}(N \log N)


Comments

There are no comments at the moment.