Editorial for CPC '21 Contest 1 P6 - AQT's Break Time is Over

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: crackersamdjam

Subtask 1

We can model each student as a 3-dimensional coordinate (a_i, b_i, c_i). We will first "plane sweep" (like line sweep, but in 3 dimensions) through the x dimension in non-increasing order. We sweep with a plane parallel to the yz-plane, having its x-coordinate denote the current A being considered. This means that any coordinate with a_i \le A will get covered. We can treat the remaining points with a_i > A as 2-dimensional coordinates (b_i, c_i). Since we are sweeping in non-increasing order, our algorithm will add new (b_i, c_i) points into consideration and never remove any old points. Let f(y) be the minimum value of C we need to cover all the points if we set B=y at the current moment. When we add a point (b_i, c_i) into consideration, all f(y) with y < b_i will get updated to \max(f(y), c_i). For the first subtask, it is sufficient to loop to update all y < b_i. We can then loop through all y to find the minimum A+y+f(y) (we set B=y and C=f(y)). Our answer is the minimum of all A+y+f(y). This costs \mathcal{O}(N) per point for a total time complexity of \mathcal{O}(N^2).

Subtask 2

Notice that the function f(y) is monotonically non-increasing. Instead of looping to update and query, we can use a data structure such as a segment tree or a balanced binary search tree (BBST). \mathcal{O}(N \log N) segment tree solutions should pass with ease. Some optimization may be required to get BBST solutions or \mathcal{O}(N \log^2 N) solutions to pass.


There are no comments at the moment.