A few days ago, I published a blog post on Codeforces about how to train for competitive programming: Link
In that post, I mentioned that I planned to regularly publish recommended training problems. Now, here they are!
Please join our Discord server to receive the latest updates: https://discord.gg/DsHSfmVgG
Problem Set Overview
Each release will include $$$5$$$ problems and their editorials. After converting the difficulty of every problem into a Codeforces rating, the problems will be distributed approximately uniformly across the range $$$[1200,2600]$$$.
The problems will be selected from relatively obscure problem series that are not suitable for being worked through indiscriminately from beginning to end. For this reason, some problem statements may not be available in English; you can use an LLM to translate them.
I will try to explain each solution by following the thought process I recommend, as described in the blog mentioned at the beginning. Each paragraph corresponds to one step in the reasoning process.
If you need additional problems, please join the Discord server, you can find the pricing and subscription options in the subscribe-details channel.
If you find any good problems, feel free to submit them by emailing [email protected]
Problem Recommendations
If $$$A \lt B$$$, you can think of each operation as first subtracting $$$A$$$ from every number and then choosing one number and subtracting an additional $$$B-A$$$ from it.
Suppose we first fix the total number of operations as $$$x$$$. For the $$$i$$$-th number, the number of times it needs to be selected can then be calculated as $$$\frac{t_i-Ax}{B-A}$$$. Sum these values and check whether the available total number of selections is sufficient.
The problem can therefore be solved by binary-searching the answer.
If $$$A \gt B$$$, similarly, you can think of each operation as first subtracting $$$A$$$ from every number and then choosing one number and adding $$$A-B$$$ back to it. You only need to calculate the maximum number of times each number can be selected and check whether the combined capacity can accommodate the total number of operations.
Problem 2: Missing Number Queries
Because the possible values of $$$a_i$$$ are exactly $$$[1,N]$$$, in most cases there will be some number that does not appear anywhere in the sequence. If such a number exists, simply use it to answer the query.
If no such number exists, then $$$a_1,\cdots,a_N$$$ must be a permutation.
Based on the analysis above, you first need to maintain the set of numbers that do not appear anywhere in the sequence. Maintain an array cnt, where cnt[x] represents the number of times the value $$$x$$$ appears in the sequence. At the same time, maintain a std::set containing every $$$x$$$ for which cnt[x] is $$$0$$$. A type $$$1$$$ operation modifies two positions in the array. If either affected value changes from having a count of $$$0$$$ to a nonzero count, or from a nonzero count to $$$0$$$, update the set accordingly.
For a type $$$2$$$ operation, if the set is nonempty, return any element from it. If the set is empty, then $$$a_1,\cdots,a_N$$$ must be a permutation. Since every number appears exactly once in a permutation, you can return any number located outside the queried interval.
Bonus: Think about how to implement the Special Judge for this problem.
If every segment has the same MEX, then the MEX of the entire sequence must also be equal to the MEX of those segments. Therefore, the MEX of every segment can only be the MEX of the entire sequence. Let the MEX of the entire sequence be $$$m$$$.
Let $$$dp(i)$$$ denote the number of ways to partition $$$a_1,a_2,\cdots,a_i$$$. If the MEX of $$$[j,i]$$$ is $$$m$$$, then for every $$$j' \le j$$$, the MEX of $$$[j',i]$$$ is also $$$m$$$.
For every $$$i$$$, define $$$l_i$$$ as the largest $$$l$$$ such that the interval $$$[l,i]$$$ contains all the numbers $$$0,1,\cdots,m-1$$$. Every $$$dp(j)$$$ with $$$j \lt l_i$$$ can transition to $$$dp(i)$$$, so once we compute $$$l_i$$$, the problem is solved.
Observe that as $$$i$$$ increases, $$$l_i$$$ never decreases. Therefore, all values of $$$l_i$$$ can be computed using the two-pointer technique.
First, consider which contestants can become $$$b_2$$$. Suppose $$$b_2$$$ defeats $$$b_3$$$ in contest $$$c$$$. If we replace $$$b_2$$$ with a contestant who ranks higher in contest $$$c$$$, the sequence $$$b$$$ remains valid.
Therefore, there are at most $$$m$$$ candidates for $$$b_2$$$: For each of the $$$m$$$ contests, take the highest-ranked contestant among those whom $$$b_1$$$ can defeat. Similarly, for every $$$b_i$$$, it is sufficient to retain only $$$m$$$ candidates.
For problems in which each step has only $$$O(1)$$$ possible states, we often consider binary lifting. Recall that when using binary lifting to find the LCA, each vertex has only one $$$k$$$-th ancestor; when using binary lifting to solve RMQ problems, once the interval length is fixed, each left endpoint corresponds to only one right endpoint.
Let $$$f(k,u,c)$$$ denote the highest-ranked contestant in contest $$$c$$$ among all contestants who can become $$$b_{2^k+1}$$$ when $$$b_1=u$$$. During the transition, $$$b_{2^{k-1}+1}$$$ can only be one of $$$f(k-1,u,1),\cdots,f(k-1,u,m)$$$. We enumerate one value $$$f(k-1,u,i)$$$ as $$$b_{2^{k-1}+1}$$$. Then $$$f(k-1,f(k-1,u,i),c)$$$ becomes a candidate for $$$b_{2^k+1}$$$. Among all the candidates obtained through this enumeration, $$$f(k,u,c)$$$ is the one with the highest ranking.
For each query, follow a process similar to binary lifting for finding the LCA. Initially, set $$$ans=0$$$ and maintain the $$$m$$$ candidates for $$$b_{ans+1}$$$. Enumerate $$$k$$$ from large to small. Use the current $$$m$$$ candidates for $$$b_{ans+1}$$$ and the precomputed values $$$f(k,*,*)$$$ to derive the $$$m$$$ candidates for $$$b_{ans+2^k+1}$$$. These $$$m$$$ candidates allow us to determine how $$$ans+2^k$$$ compares with the actual answer. If $$$ans+2^k$$$ is smaller than the actual answer, add $$$2^k$$$ to $$$ans$$$.
After the dividing, the two subrectangles become independent subproblems. This naturally suggests a straight forward DP: let $$$dp(x_1,y_1,x_2,y_2)$$$ denote the complexity of the subrectangle whose top-left corner is $$$(x_1,y_1)$$$ and whose bottom-right corner is $$$(x_2,y_2)$$$.
By splitting a rectangle into two equal halves each time, we can ensure that the answer does not exceed $$$O(\log n)$$$.
For DP problems in which the answer is small, we can consider including the answer itself in the state. Let $$$dp(c,x_1,y_1,x_2)$$$ denote the maximum possible $$$y$$$-coordinate of the bottom-right corner of a subrectangle whose complexity does not exceed $$$c$$$, whose top-left corner is $$$(x_1,y_1)$$$, and whose bottom-right corner has an $$$x$$$-coordinate of $$$x_2$$$.
Now consider the transitions. A vertical split is straightforward: simply assign the value of $$$dp(c,x_1,dp(c,x_1,y_1,x_2)+1,x_2)$$$ to $$$dp(c+1,x_1,y_1,x_2)$$$.
For a horizontal split, we need to enumerate the position at which the rectangle is divided. Once $$$c,x_1,y_1$$$ are fixed, the optimal splitting point is monotonic with respect to $$$x_2$$$, because keeping the two sides balanced is advantageous.
