Contest Duration: - (local time) (180 minutes) Back to Home
Official

## D - Everyone is a winner Editorial by evima

First, for each $$1 \leq i \leq N$$, let $$T_i$$ be the time that elapses before someone solves $$i$$ problems for the first time, assuming that each participant solves the problems in descending order of time required. Then, each participant $$i$$ has to solve the first $$i$$ problems within $$T_i$$ minutes.

We can determine whether the condition can be satisfied by deciding the order each participant solves the problems, as follows.

• For each $$i=N,N-1,\ldots,1$$, in this order, do the following:
• If it is impossible to solve the first $$i$$ problems within $$T_i$$ minutes, declare that it is impossible to satisfy the condition and terminate.
• Otherwise, decide the first $$i$$ problems so that the time needed to solve them is as long as possible while not exceeding $$T_i$$ minutes. If there are multiple such choices, include as many problems requiring $$1$$ minute as possible in the first $$i$$ problems.
• Then, solve the first $$i$$ problems in descending order of time required. Afterward, solve the other $$N-i$$ problems in descending order of time required, too.
• Lastly, for each $$1 \leq j < i$$, update $$T_j \mapsto \min\{T_j, t_{i,j}\}$$, where $$t_{i,j}$$ is the time taken for Participant $$i$$ to solve the first $$j$$ problems.
• If we successfully decide the order every participant solves the problems, declare that it is possible to satisfy the condition and terminate.

In this algorithm, we did not check if $$t_{i,j} \geq T_j$$ for $$i<j \leq N$$. However, this inequality always holds when it takes $$1$$, $$2$$, or $$3$$ minutes to solve a problem. This is because, for each $$2 \leq i \leq N$$, if we have $$T_{i-1}+2 \geq T_i$$ when we have done the operation for $$i$$, we always have $$T_j \leq T_i+2(j-i)$$ ( $$j \geq i$$ ) at that moment. (For a more general setting, our greedy strategy does not work.)

The algorithm takes $$O(N^2)$$ time if we naively update $$T$$, but we can express $$T$$ as a convex polyline consisting of line segments with slopes $$1$$, $$2$$, and $$3$$ (after removing unnecessary parts) to make it work in linear time.

posted:
last update: