Setting Three Contests

Sort the problems of each contest by nondecreasing deadline. If two problems of the same contest appear in the opposite order, swapping them does not change the number of switches and cannot make the earlier deadline finish later. Therefore, the order inside each contest may be fixed, giving three chains.

Let contest $x$ contain $m_x$ problems, and let their preparation times and deadlines in this order be $E_{x,r}$ and $D_{x,r}$. Tighten the deadlines backwards:

$$D_{x,r}\leftarrow\min(D_{x,r},D_{x,r+1}-E_{x,r+1})\qquad(1\leq r<m_x).$$

This does not change feasibility. After problem $r$ of one contest is completed, the later problems $r+1,r+2,\cdots,q$ of that contest still require at least their total preparation time. Hence every schedule feasible for the original deadlines already satisfies all tightened deadlines. The converse is immediate because every tightened deadline is at most the original one.

After tightening,

$$D_{x,r}+E_{x,r+1}\leq D_{x,r+1}.$$

Thus, whenever a state ending with a problem of one contest is feasible, continuing with the next problem of the same contest is always feasible.

Let $P_x[r]=E_{x,1}+E_{x,2}+\cdots+E_{x,r}$. If problems of the three contests have been completed, the last problem belongs to contest , and the number of switches is , then the current time is

$$P_1[a]+P_2[b]+P_3[c]+Ks.$$

Define $\operatorname{dp}_1[a][b][c]$ as the minimum number of switches for such a state, and define the analogous arrays for last contests $2$ and $3$. The direct dynamic programming has $O({}_{}$ states.

The tightened deadlines let us remove one dimension. For fixed $b,c$, as $a$ increases, $\operatorname{dp}_1[a][b][c]$ is impossible up to one position and has one constant value from the first feasible position onward. This follows by induction on the total number of completed problems: a same-contest transition propagates the current value to the right, while a transition from another contest creates one first feasible position and then receives the same propagation.

Store only the following pairs.

• $F_1[b][c]=(a,s)$: the minimum $a$ at which a state ending with contest $1$ first becomes feasible, together with its number of switches .

Suppose $F_1[b][c]=(a,s)$. Extend the current final block of contest $1$ until exactly $q$ problems of contest have been completed, then switch to contest . Completing the next problem of contest is valid exactly when

$$P_1[q]+P_2[b+1]+P_3[c]+K(s+1)\leq D_{2,b+1}.$$

Because $P_1$ is increasing, the valid values of $q$ form either an empty set or one interval $[a,r]$. Find $r$ by binary search. For every in this interval, apply

$$F_2[q][c]\leftarrow\min(F_2[q][c],(b+1,s+1)).$$

The other five transition types are symmetric.

Give a candidate $(h,s)$ the priority $({\rm row}+{\rm column}+h,s)$. The first component is the total number of completed problems represented by the first state of the candidate. Every transition increases this value by at least one, so the currently smallest candidate can never be improved by a future transition. Finalize that state and add its two outgoing interval updates.

Each table $F_x$ receives row intervals from one previous contest and column intervals from the other. The implementation stores each table twice, once in each orientation. Every copy must support interval minimum with a candidate pair, deletion of one finalized position, and retrieval of the globally smallest priority.

Encode a pair lexicographically as one integer. The interval operation becomes range chmin. A segment tree beats structure maintaining the maximum and second maximum handles each update in amortized $O(\log N)$. By additionally maintaining the best position among maximum-valued leaves and the best priority among the remaining leaves, the root directly gives the globally smallest candidate.

The number of finalized states is

$$(m_2+1)(m_3+1)+(m_1+1)(m_3+1)+(m_1+1)(m_2+1)=O(N^2).$$

Each state causes only a constant number of interval updates and point deletions. The total time complexity is $O(N^2\log N)$ and the memory complexity is $O(N^2)$.

Solution written by GPT5.6