See here. Monotone cycles of odd length are tileable, which is a stronger condition than the one required in Problem B.

Each value $$$x$$$ is independent of the others; only its own frequency matters.

In a balanced array, value $$$x$$$ must appear either $$$0$$$ times or exactly $$$x$$$ times.

• Each value $$$x$$$ is independent of the others; only its own frequency matters. In particular, for each value, find its frequency $$$f[x]$$$.
• In a balanced array, value $$$x$$$ must appear either $$$0$$$ times or exactly $$$x$$$ times. Specifically, if it appears $$$ \lt x$$$ times at the beginning, you have to delete all its occurrences, otherwise you should keep $$$x$$$ occurrences. Specifically, for each $$$x$$$, add $$$f[x]$$$ to the answer if $$$f[x] \lt x$$$, else add $$$f[x] - x$$$.

Complexity: $$$O(n)$$$ time. Slower solutions (e.g., $$$O(n^2)$$$) are allowed.

350380351

The order of operations does not matter. Only the number of $$$\texttt{4}s$$$ and $$$\texttt{8}s$$$ in the substring matters.

The black cells are the positions we can reach starting from $$$(0, 0)$$$, if we can move orthogonally (using a $$$\texttt{4}$$$) and diagonally (using an $$$\texttt{8}$$$).

A move with an $$$\texttt{8}$$$ is equivalent to two moves with a $$$\texttt{4}$$$, in different directions.

• The order of operations does not matter. So count the number of $$$\texttt{4}s$$$ and $$$\texttt{8}s$$$, and assume there are $$$a$$$ $$$\texttt{4}$$$s and $$$b$$$ $$$\texttt{8}s$$$.
• The grid is symmetrical. We can assume $$$x, y \geq 0$$$ (by making $$$x := |x|$$$, $$$y := |y|$$$).
• The black cells are the positions we can reach starting from $$$(0, 0)$$$, if we can move orthogonally (using a $$$\texttt{4}$$$) and diagonally (using an $$$\texttt{8}$$$).
• In particular, since $$$x, y \geq 0$$$, a $$$\texttt{4}$$$ is a step either up or right while an $$$\texttt{8}$$$ consists of two steps, one up and one right.
• So you make $$$a+2b$$$ steps in total, and only $$$a+b$$$ of them can be in the same direction.
• The necessary and sufficient conditions are
• • $$$a+2b \geq x+y$$$ (you need to be able to perform $$$x+y$$$ steps, either up or right, to reach $$$(x, y)$$$);
• • $$$a+b \geq \max(x, y)$$$ (you need to be able to perform $$$y$$$ steps up and $$$x$$$ steps right).

350380442

For each element, determine whether it belongs to a $$$\texttt{MEX}$$$ constraint, a $$$\min$$$ constraint, both, or none.

If an element belongs to both a $$$\texttt{MEX}$$$ constraint and a $$$\min$$$ constraint, it is useless for both constraints.

If an element only belongs to a $$$\min$$$ constraint, you can set it to $$$k$$$ for convenience.

What's the "fastest" way to satisfy a $$$\texttt{MEX}$$$ constraint? What about several constraints simultaneously?

For each element, determine whether it belongs to a $$$\texttt{MEX}$$$ constraint, a $$$\min$$$ constraint, both, or none.

• If an element is covered by a $$$\min$$$ constraint, it must be $$$\geq k$$$, and ideally it should be $$$= k$$$ (so that the constraint is immediately satisfied).
• If an element is covered by a $$$\texttt{MEX}$$$ constraint, it must be $$$\neq k$$$, and ideally it should be $$$ \lt k$$$ (to make the constraint easier to satisfy).

Then

• If an element is not covered by any constraints, it does not matter, and you can set it to any value.
• If an element belongs to both a $$$\texttt{MEX}$$$ constraint and a $$$\min$$$ constraint, it is useless for both constraints, but you must set it to something both $$$\neq k$$$ and $$$\geq k$$$. For example, you can set it to $$$k+1$$$.
• If an element only belongs to a $$$\min$$$ constraint, it is optimal to set it to $$$k$$$.
• The remaining elements are the ones which are only covered by a $$$\texttt{MEX}$$$ constraint. In order to be satisfied, a $$$\texttt{MEX}$$$ constraint must contain at least $$$k$$$ such elements (because it must contain all the elements between $$$0$$$ and $$$k-1$$$, which would violate a $$$\min$$$ constraint). In particular, assigning $$$i \text{ mod } k$$$ at the $$$i$$$-th such element works (if a $$$\texttt{MEX}$$$ constraint contains $$$k$$$ such elements, their values are $$$[0, 1, \ldots, k-1]$$$, possibly shifted).

Complexity: $$$O(nq)$$$ or $$$O(n+q)$$$ per test case.

Bonus: in the above solution, we assign $$$i \text{ mod } k$$$ to the $$$i$$$-th element only covered by $$$\texttt{MEX}$$$ constraints. However, assigning $$$a_i = i \text{ mod } k$$$ to such elements (where $$$i$$$ is the position in the whole array, instead of the position only considering such elements) also works. Can you prove it?

350380521

The worst case is either $$$x = l$$$ or $$$x = r$$$. So you can assume that $$$x$$$ is either $$$l$$$ or $$$r$$$, but you don't know which one.

There exists an optimal strategy where a prefix of offers (after sorting) is accepted using the third option, and a suffix of elements is accepted using the second option.

There exists an optimal strategy where (in addition to the previous properties) at most one offer is rejected.

The worst case is either $$$x = l$$$ or $$$x = r$$$.
Sketch of proof. After fixing the strategy, the number of coins as a function of $$$x$$$ is a straight line.
Then, in order to test a strategy, it is enough to evaluate it at $$$x = l$$$ and $$$x = r$$$ and pick the minimum.

There exists an optimal strategy where a prefix of elements (after sorting) is red, and a suffix of elements is blue.
Sketch of proof. Use exchange argument. For example, if $$$y \leq z$$$, $$$y$$$ is white and $$$z$$$ is red, then we get $$$x-z$$$ coins. If we make $$$y$$$ red and $$$z$$$ white, we make $$$x-y$$$ coins instead.

There exists an optimal strategy where (in addition to the previous properties) at most one element is white.
Sketch of proof. If $$$x \leq y$$$, and they are both white, we can make $$$x$$$ red and $$$y$$$ blue instead.

• Try all possibilities for the white element. So there are $$$O(n)$$$ candidate strategies.
• We can test a strategy in $$$O(1)$$$: find the number of coins as a function of $$$x$$$ using prefix sums, and evaluate it in $$$l$$$ and $$$r$$$ to check the actual worst case.

Complexity: $$$O(n \log n)$$$

350380713

The order of the elements does not matter.

Solve the problem with $$$k = 1$$$.

Iterate over elements from right to left and find their final value if $$$k = 1$$$.

Find the value of each element over time. Can you calculate the value of some element after a fixed number $$$m$$$ of operations?

Binary search the answer.

The order of the elements does not matter. So let's sort the elements in increasing order. Also, we have the freedom to choose the tiebreaker rule (i.e., which elements are increased by $$$1$$$).

• Assume the process stops when all the elements are distinct (i.e., $$$k = 1$$$). Let's find the configuration $$$b_1, b_2, \ldots, b_n$$$ at that point. If some elements are equal, the rightmost does not increase.
• From right to left, if the initial value is $$$a_i$$$, then $$$b_i$$$ is the smallest $$$x \geq a_i$$$ not present in $$$b$$$ yet.
• If we look at a single element over time, it has values $$$a_i, a_i + 1, \ldots, b_i, b_i, \ldots, b_i$$$.

• The maximum number of occurences of one element does not increase after one operation (if value $$$x$$$ appeared $$$\leq k$$$ times, it produces $$$\leq k-1$$$ copies of $$$x+1$$$, and at most one other copy of $$$x+1$$$ survives).
• So we can binary search the answer. Using the process described earlier, we can retrieve the configuration after $$$m$$$ moves in $$$O(n)$$$.

Complexity: $$$O(n \log n)$$$ time (there also exist "magical" $$$O(n)$$$ solutions!)

350380783

How would you write the checker for this problem? (How to check efficiently whether a submission gets AC or WA)?

After you choose $$$y$$$, calculating the optimal $$$l$$$ is easy. From now, let's denote the operations only using $$$y$$$.

Consider some naive strategies: for example, $$$[1, 2, \ldots, n-1]$$$, or $$$[n-1, n-2, \ldots, 1]$$$. Why are they bad? How to improve them?

You can fix your skill modulo $$$2$$$, then modulo $$$4$$$, then modulo $$$8$$$, etc., but that's still a bit too inefficient.

Try with a different modulo.

As a warm-up, think about how we would write the checker for this problem.

We can store the set of all the possible skills (initially, all integers in $$$[1, n]$$$), and perform operations in $$$O(1)$$$ (we have to remove $$$y$$$ and insert $$$y+l$$$).

As a consequence, the optimal value of $$$l$$$ is the smallest one such that $$$y+l$$$ is already in the set. Since we know how to determine the optimal $$$l$$$ for a fixed $$$y$$$, let's denote the operations only using $$$y$$$.

• Naive strategy 1: use operations $$$1, 2, \ldots, n-1$$$. Unfortunately, they are too "increasing".
• Naive strategy 2: use operations $$$n-1, n-2, \ldots, 1$$$. Unfortunately, they are too long.

Better strategy:

• Fix our skill modulo $$$2$$$ using operations $$$n-1, n-3, n-5, \ldots$$$
• Fix our skill modulo $$$4$$$ using operations $$$n-2, n-6, n-10, \ldots$$$
• $$$\ldots$$$

The cost is $$$O(n \log n)$$$ ($$$\approx \log_2 n$$$ layers, $$$O(n)$$$ per layer). We use very few "increasing" operations ($$$1$$$ per layer): we can try to use more (and maybe use less layers).

Generalization:

• Fix our skill modulo $$$3$$$ using operations $$$n-2, n-5, n-8, \ldots, n-1, n-4, n-7, \ldots$$$
• Fix our skill modulo $$$9$$$ using operations $$$n-6, n-18, n-30, \ldots, n-3, n-12, n-21, \ldots$$$
• $$$\ldots$$$

Now we have $$$\approx \log_3 n$$$ layers and $$$2$$$ "increasing" operations per layer.

If we use modulo $$$m$$$, we have $$$\approx \log_m n$$$ layers, each with cost $$$\approx n$$$, and $$$m-1$$$ "increasing" operations per layer, each with cost $$$1000$$$.

We should choose $$$m \approx \sqrt[3]{n}$$$. So the total cost is around

if $n = 250\,000$.

350380837

Apply prefix XOR. So, instead of information about $$$a_l \oplus a_{l+1} \oplus \ldots \oplus a_r$$$, assume you can ask information about $$$a_l \oplus a_r$$$.

Find whether the highest bit of every $$$a_i$$$ (viewed as $$$30$$$-bit integer) is $$$0$$$ or $$$1$$$. You can assume that $$$a_1$$$ has highest bit $$$0$$$.

You get two blocks. Recurse.

Solve every block in the most efficient way possible.

Apply prefix XOR. So, instead of information about $$$a_l \oplus a_{l+1} \oplus \ldots \oplus a_r$$$, we assume we can ask information about $$$a_l \oplus a_r$$$.

Let's build a trie containing the $$$a_i$$$. Specifically, each node corresponds to a prefix of the binary representation, and contains positions $$$i$$$ such that $$$a_i$$$ has that prefix. It is not possible to recover the $$$a_i$$$ uniquely, but we can set bits to $$$0$$$ without loss of generality if they do not impact any queries. Then, in order to calculate the answer for some $$$(l, r)$$$, we have to find the LCA of the corresponding nodes.

Suppose we are in some node of the trie containing $$$k$$$ values. We want to recurse into two children, depending on the next bit. This is possible by asking the query.

Specifically, suppose that a node contains positions $$$p_1, p_2, \ldots, p_k$$$. In order to recurse, we need to ask queries between some pairs. We choose this pairs greedily, by calculating a minimum spanning tree (the edges have cost $$$\frac{1}{p_j-p_i+1}$$$). It can be also shown that, in the minimum spanning tree, the picked edges contain either $$$p_1$$$ or $$$p_k$$$, which makes the implementation easier.

Empirically, this solution requires around $$$8$$$ robocoins per test case with $$$n = 100$$$.

Bonus: prove the asymptotic behavior of the solution (idea: for each $$$(i, j)$$$, estimate the probability that the query is performed).

350380944

Start with some "easy" pairs $$$(n, m)$$$. Which ones can you solve?

If you have a solution to $$$(n, m)$$$, can you transform it into a solution to $$$(n+1, m+1)$$$?

If you have a solution to $$$(n, m)$$$, can you transform it into a solution to $$$(n+1, m)$$$?

Find small $$$(n, m)$$$ with at least $$$2000$$$ solutions, and propagate these solutions to some bigger pairs.

Now some pairs are missing. They either have small $$$n$$$, or small $$$n-m$$$.

If $$$n-m$$$ is small, what can you say about the amount of $$$p_i = i$$$?

If $$$n-m$$$ is small, then $$$p_n$$$ must be large.

For convenience, let's find "anti-bitonic" permutations instead (decreasing, then increasing). There is a bijection between bitonic and anti-bitonic permutations.

vector<int> f(vector<int> p) {
    int n = p.size();
    reverse(p.begin(), p.end());
    for (auto &u : p) u = n - u + 1;
    return p;
}

We can transform a solution to $$$(n, m)$$$ into a solution to $$$(n+1, m+1)$$$: just append $$$n+1$$$ at the end.

We can also transform a solution to $$$(n, m)$$$ into a solution to $$$(n+1, m)$$$: append $$$n+1$$$ at the end, and swap $$$p_1$$$ with $$$p_1 + 1$$$.

Let's divide into three cases:

1. $$$n \le 18$$$;
2. $$$n \ge 19$$$, $$$n - m \ge 10$$$;
3. $$$n \ge 19$$$, $$$n - m \le 9$$$.

They can be solved as follows.

1. We can find all the anti-bitonic permutations and test them in $$$O(n \cdot 2^n)$$$.
2. First, solve $$$(18, i)$$$ for $$$1 \leq i \leq 8$$$ (for each $$$i$$$, we have $$$\geq 2000$$$ solutions). Transform these solutions into solutions to $$$(n, m)$$$.
3. $$$p_1, p_2, \ldots, p_n$$$ must have at least $$$n-9$$$ cycles, so it must have at least $$$n-18$$$ fixed points (i.e., $$$p_i = i$$$). The permutation structure is $$$[p_1, \ldots, p_1+1, p_1+2, \ldots, n]$$$: the highlighted square has at most $$$1$$$ fixed point, so there are at most $$$n-p_1+1$$$ fixed points. Therefore, $$$p_1 \leq 19$$$, and we can iterate over all such permutations.

350381048

Solve the problem with even $$$m$$$.

Solve the problem with $$$t = 1$$$.

For a fixed $$$n$$$, how do "losing" $$$m$$$ look like?

Let $$$(n, l)$$$ ($$$0 \leq m$$$) be losing if you lose if it's your turn, the current integer is $$$n$$$, and you cannot subtract $$$l$$$.
If $$$(n, l)$$$ is losing, then $$$(n+l, l')$$$ with $$$l' \neq l$$$ is winning. This means that the number of losing $$$l$$$ for a fixed $$$n$$$ is either $$$0$$$, $$$1$$$, or $$$m+1$$$. Let's call $$$n$$$ "good", "neutral", and "evil", respectively.

How do the losing states $$$(n, l)$$$ look like?

Our goal is to solve $$$t = 1$$$ in $$$O(n/m)$$$.

How to determine efficiently whether some $$$n$$$ is good or neutral?

In order to determine whether some $$$n$$$ is good or neutral, you can write a recursive function which terminates in $$$O(1)$$$ on average.

Losing positions.

Let $$$(n, l)$$$ ($$$0 \leq m$$$) be losing if you lose if it's your turn, the current integer is $$$n$$$, and you cannot subtract $$$l$$$ (if $$$l$$$ is $$$0$$$, you can subtract everything).

Evil $$$n$$$.

Let $$$n$$$ be evil if $$$(n, 0)$$$ is losing (i.e., you lose even without constraints on the number you subtract).

Bound on the evil $$$n$$$ (I).

There are $$$O(N/m)$$$ evil $$$n$$$. Specifically, let $$$v_1, v_2, \ldots, v_k$$$ be the evil $$$n \leq N$$$. Then, $$$v_i - v_{i-1} \geq m+1$$$ (otherwise you would be able to move from an evil $$$n$$$ to another, contradiction).

Structure of losing positions and solution in $$$O(t(N+m))$$$.

If $$$(n, l)$$$ is losing, then $$$(n+l, l')$$$ with $$$l' \neq l$$$ is winning. This means that the number of losing $$$l$$$ for a fixed $$$n$$$ is either $$$0$$$, $$$1$$$, or $$$m+1$$$. Let's call $$$n$$$ "good", "neutral", and "evil", respectively.
Note that the losing states are $$$O(N+m)$$$ in total.

Even $$$m$$$.

For even $$$m$$$, only the multiples of $$$m+1$$$ are evil. In order to win, you can ensure that the last two moves have sum $$$m+1$$$. Since $$$m+1$$$ is odd, the last move will never be the same as the second last.

From now, let's only consider odd $$$m$$$.

More structure.

Let $$$f(n)$$$ be the distance from the largest evil $$$n' \leq n$$$.

There are three types of losing states.

• $$$(n, l)$$$ with $$$f(n) = 0$$$.
• $$$(n, f(n))$$$.
• $$$(n, f(n)/2)$$$ with $$$f(n) = m+1$$$.

This is a consequence of the slow solution described above. If $$$s$$$ is evil:

• the losing states $$$(s, l)$$$ propagate to $$$n$$$ in $$$[s+1, s+m]$$$;
• only the losing state $$$(s + \frac{m+1}{2}, \frac{m+1}{2})$$$ can propagate to $$$(s+m+1, \frac{m+1}{2})$$$, and in that case $$$s+m+2$$$ is evil.

So $$$s+m+1$$$ cannot be good (it is either neutral or evil).

Bound on the evil $$$n$$$ (II).

Let $$$v_1, v_2, \ldots, v_k$$$ be the evil $$$n \leq N$$$. Then, $$$m+1 \leq v_i - v_{i-1} \leq m+2$$$.

Our goal.

Let $$$v_1, v_2, \ldots, v_k$$$ be the evil $$$n \leq N$$$. We want to find them in $$$O(k) = O(N/m)$$$. In this way, we can solve the problem for all $$$m$$$ in $$$O(\sum_{1 \leq m \leq M} N/m) = O(N \log M)$$$.

Finding $$$v_{i+1}$$$.

We have $$$v_1, v_2, \ldots, v_i$$$, and we want to find $$$v_{i+1}$$$ in $$$O(1)$$$. It is enough to check whether $$$v_i + m + 1$$$ is evil. It's easier to check whether it is not evil, i.e., whether there exists a winning move.
Let's start from some $$$n$$$ which satisfies $$$v_j \leq n \leq v_{j+1}$$$. A winning move must ensure that the opponent cannot move to an evil state (necessary condition). So there are three candidate winning moves.

• Subtracting $$$n-v_j+1$$$ (so that the opponent is too far from $$$v_{j-1}$$$; this can only work if $$$v_j-v_{j-1} = m+2$$$).
• Subtracting $$$\frac{n-v_j}{2}$$$ (so that the opponent would have to subtract $$$\frac{n-v_j}{2}$$$ again to reach $$$v_j$$$).
• Subtracting $$$\frac{n-v_{j-1}}{2}$$$ (so that the opponent would have to subtract $$$\frac{n-v_{j-1}}{2}$$$ again to reach $$$v_{j-1}$$$).

Finding $$$v_{i+1}$$$ efficiently.

The previous observation provides a recursive function which can call itself up to $$$3$$$ times.
The recursive function answers the question "can we win starting from $$$(n, n-v_j)$$$?" (i.e., it is forbidden to make the move which would win immediately). This is equivalent to "is $$$n$$$ good or neutral?"
We want to make the average number of recursive calls less than $$$1$$$, so that the function terminates in $$$O(1)$$$.

• We do not need the first call, because $$$v_{j-1}+m+1$$$ is neutral (proved before).
• The second call happens with probability $$$\lesssim 1/2$$$ ($$$n-v_j$$$ must be even, and the first case must not apply).
• The third call happens with probability $$$\lesssim 3/8$$$ ($$$n-v_{j-1}$$$ must be even, the first case must not apply, and the second call must not succeed).

So the function calls itself $$$\lesssim 7/8$$$ times on average. This is fast enough for all $$$m$$$ (it can be tested locally).

350381246

Div. 1:

• $$$1^{st}$$$ place: ksun48
• $$$2^{nd}$$$ place: maroonrk
• $$$3^{rd}$$$ place: potato167
• $$$4^{th}$$$ place: turmax
• $$$5^{th}$$$ place: noimi

Div. 2:

• $$$1^{st}$$$ place: Genius_Star_rgw
• $$$2^{nd}$$$ place: Foredawn
• $$$3^{rd}$$$ place: rizynvu
• $$$4^{th}$$$ place: DaydreamWarrior
• $$$5^{th}$$$ place: Phyus003

There are two types of subarrays.

If there exists $$$a_i \geq a_{i+1}$$$, how many times can the subarray appear?

• If there exists an $$$i$$$ such that $$$a_i \geq a_{i+1}$$$, we have $$$a_i = k$$$ for some $$$k$$$, $$$a_{i+1} = 1$$$. The subarray $$$[k, 1]$$$ appears only once on the blackboard (when James writes $$$1, \ldots, k$$$ and then $$$1, \ldots, k+1$$$). Since $$$a_1, a_2, \ldots, a_m$$$ contains $$$[k, 1]$$$, it must appear at most once as well, but the statement guarantees that it appears at least once, so the answer is $$$1$$$.
• Otherwise, the array $$$a_1, a_2, \ldots, a_m$$$ can be rewritten as $$$l, l+1, \ldots, r$$$, and it appears when James writes $$$1, \ldots, r$$$, then when James writes $$$1, \ldots, r+1$$$, ..., then when James writes $$$1, \ldots, n$$$ (so $$$n-r+1$$$ times in total).

Complexity: $$$O(n)$$$

340224512

Suppose you have already calculated where person $$$i-1$$$ goes. Can you calculate fast where person $$$i$$$ goes?

The first $$$i-2$$$ cells visited by people $$$i-1$$$ and $$$i$$$ coincide.

Person $$$i$$$ performs the same commands as person $$$i-1$$$, with the addition of the $$$i$$$-th command.

Now we wonder whether performing the same $$$i-1$$$ commands means that the first $$$i-1$$$ cells visited are the same. This is actually false in general, because after person $$$i-1$$$ performs his commands, he colors a new cell black, and this can change the outcome of the $$$(i-1)$$$-th operation. However, the outcome of the first $$$i-2$$$ commands remains the same, because the new black cell is too far from the positions visited in the first $$$i-2$$$ commands.

So the position visited by person $$$i$$$ after $$$i-2$$$ commands is the same position visited by person $$$i-1$$$ after $$$i-2$$$ commands, and it's enough to simulate the last two commands naively.

Complexity: $$$O(n \log n)$$$ or $$$O(n)$$$

340224365

For a fixed $$$k$$$, find a greedy strategy.

You can calculate the answer with prefix sums.

Consider the following strategy:

• Iterate over events in increasing order.
• In the first $$$k$$$ events, people enter the museum. In the last $$$k$$$ events, people exit. For the other events, if the current number of people is $$$k$$$ a person exits, otherwise a person enters.

This strategy is optimal, because it maximizes the number of people present at any time in the museum.

• After the $$$i$$$-th event with $$$i \leq k$$$, at most $$$i$$$ people can be inside the museum, and in fact we have exactly $$$i$$$.
• A similar argument works for the last $$$k$$$ events (you have to use that at the end the museum is empty).
• For the other events, after the $$$i$$$-th event we know that the parity of the number of people is equal to the parity of $$$i$$$. In fact, the number of people is either $$$k$$$ or $$$k-1$$$, which is the maximum possible number of people $$$\leq k$$$ with the correct parity.

Now we have to calculate the following terms:

• $$$1 \cdot a_1 + 2 \cdot a_2 + \ldots + k \cdot a_k$$$: can be done with prefix sums of $$$i \cdot a_i$$$.
• $$$k \cdot a_{2n-k+1} + (k-1) \cdot a_{2n-k+2} + \ldots + 1 \cdot a_{2n}$$$: can be done with prefix sums of $$$(2n-i+1) \cdot a_i$$$:
• $$$k \cdot (a_{k+2} + a_{k+4} + \ldots + a_{2n-k})$$$, $$$k \cdot (a_{k+2} + a_{k+4} + \ldots + a_{2n-k-1})$$$ and similar: can be done with prefix sums of $$$a_{2i}$$$, and prefix sums of $$$a_{2i+1}$$$.

Alternatively, we can calculate the answer for some $$$k$$$ fast using the answer for $$$k-2$$$ and changing a few terms.

Complexity: $$$O(n)$$$

340224635

Let's ignore the first condition for now.

Some cells are necessarily black.

Then, some cells are necessarily white.

Now what happens with $$$k = 2$$$? You can conclude that some cells in column $$$2$$$ are necessarily white.

Repeat with $$$k = 3$$$, etc.

Once you find all the grids which satisfy the second and the third conditions, iterate over rows in decreasing order.

• $$$(1, 1)$$$ is black, because of the second condition with $$$k = 1$$$.
• Then, $$$(i, 1)$$$ is white for $$$i \geq 2$$$, because of the third condition with $$$k = n$$$.
• Then, either $$$(1, 2)$$$ or $$$(2, 2)$$$ is black, because of the second condition with $$$k = 2$$$.
• Then, $$$(i, 2)$$$ is white for $$$i \geq 3$$$, because of the third condition with $$$k = n-1$$$.
• $$$\ldots$$$

In general, only $$$(i, j)$$$ with $$$i \leq j$$$ can be black. If you repeat the same process starting from $$$(1, n)$$$, you can conclude that only $$$(i, j)$$$ with $$$i \leq n-j+1$$$ can be black.

So, for each column $$$j$$$, there is exactly one black cell $$$(i, j)$$$, with $$$i \leq \min(j, n-j+1)$$$.

Now you can iterate over rows in decreasing order. For each row, you have some number $$$c_i$$$ of available columns, and $$$a_i$$$ columns you must fill, and this can be done in $$$\binom{c_i}{a_i}$$$ ways. You can calculate $$$c_i$$$ from $$$c_{i+1}$$$ by calculating the number of new available columns, and subtracting the $$$a_{i+1}$$$ columns you must fill.

Complexity: $$$O(n \log n)$$$ or $$$O(n)$$$

340224711

Try to come up with a condition for when Alice can choose some subset of items.

Write a dynamic programming $$$O(n^2)$$$ solution based on the condition.

Optimize the solution with data structures like segment trees.

We can assume $$$a_i = i$$$ for all $$$i$$$. Now, if Alice wants to take some subset $$$S$$$, we have the following condition:

• For all $$$x \notin S$$$, $$$y \in S$$$, if $$$x \lt y$$$, then $$$pos_x \lt pos_y$$$, where $$$pos = b^{-1}$$$

Proof: If $$$pos_x \gt pos_y$$$, the item $$$y$$$ cannot be taken before $$$x$$$ because $$$x$$$ comes first in Alice's priority order. And item $$$x$$$ cannot be taken before $$$y$$$ because $$$y$$$ comes first in Bob's priority order.

Now, if the condition is satisfied, infact all subsets are valid. A simple algorithm works, just make Alice take all items in $$$S$$$ in increasing order, and when Alice wants to take some item but it is not the first remaining item according to her priority order, Bob takes items till it becomes first in her priority order.

Now, we can write our dynamic programming solution: $$$dp_{(i, j)} =$$$ maximum sum of items taken by Alice within the first $$$i$$$ items such that $$$max(pos_x)$$$ among Bob's items is $$$j$$$.

Transitions are:

• We are allowed to let Alice take item $$$i + 1$$$ if and only if $$$pos_i \gt j$$$.
• Bob can take item $$$i + 1$$$ without restrictions, and $$$j$$$ gets updated to $$$\max(j, pos_{i + 1})$$$

We then optimize this with storing a segment tree over the states $$$j$$$. The first type of transition is a range add query, the second type of transition can be split into $$$j \lt pos_{i + 1}$$$ and $$$j \gt pos_{i + 1}$$$, in the first case we do nothing, and in the second case we need a range max query.

All of the above operations can be handled with a lazy segment tree. The time complexity is $$$O(n \cdot log(n))$$$.

340224797

Find a characterization for when a position array $$$p$$$ is possible. It helps to think in terms of $$$f_x =$$$ the number of people at coordinate $$$x$$$ instead.

Essentially, an attraction at $$$x$$$ combines the people standing at $$$x - 1, x$$$ and $$$x + 1$$$. Each update unites $$$3$$$ components into one, except for updates at the edge.

Read the hints. We are trying to find a characterization for valid sequences $$$p$$$.

We can prove the following necessary conditions easily by considering what happens when an attraction is placed in different positions,

• There exists $$$1 \le L \le R \le n$$$ such that $$$f_i \ge 1$$$ if and only if $$$L \le i \le R$$$.
• $$$f_i$$$ is odd for all $$$L \lt i \lt R$$$.

Further, these conditions are sufficient, and a simple construction is to do $$$\frac{f_i}{2}$$$ attractions at the position of the centre of the group of people finally at $$$i$$$ (The edges are handled easily). Also, you may have to do some translations at the end, which can be done by attracting at $$$1$$$ or $$$n$$$.

Try to fix $$$L$$$ and $$$R - L + 1$$$, and then calculate the sum under these restrictions.

The middle $$$R - L - 1$$$ variables have to be odd, and the outer $$$2$$$ variables can have any parity. Fix the parity of the outer elements.

Use expected value symmetry arguments to calculate the sum fast.

Assume $$$L = 1$$$ and $$$R = K$$$ ($$$K \gt 1$$$) for now. We have the equation $$$f_1 + f_2 + f_3 + \ldots + f_k = n$$$, and $$$f_i \ge 1$$$ and $$$f_i$$$ odd for $$$i \ne 1$$$ and $$$i \ne k$$$, where $$$f_i =$$$ the number of people finally at $$$i$$$. We want $$$\sum f_i \cdot a_i$$$ over all ways.

Fix parity of $$$f_1, f_k$$$ say $$$x$$$ and $$$y$$$ (let $$$1 \le x, y \le 2$$$), and then let

• $$$f_i = 2 \cdot g_i + 1$$$ for all $$$i \ne 1, i \ne k$$$
• $$$f_1 = 2 \cdot g_1 + x$$$
• $$$f_k = 2 \cdot g_k + y$$$

Let $$$S = n - x - y - (k - 2)$$$. Now, the equation becomes $$$\sum g_i = \frac{S}{2}$$$, and we want $$$\sum 2 \cdot g_i \cdot a_i$$$ over all ways ($$$+$$$ a few more terms arising from the constants $$$1$$$, $$$x$$$ and $$$y$$$).

If $$$S$$$ is odd, no solution. Assume $$$S$$$ even.

Since all $$$g_i$$$ variables are symmetric, we can just say the expected value of $$$g_i$$$ is $$$\frac{S}{2 \cdot k}$$$, and then calculate $$$\sum ways \cdot EV(g_i) \cdot a_i$$$, where $$$ways$$$ is the number of solutions (simple stars and bars).

To solve the full problem, note that it essentially requires you to optimize finding sum of subarrays of size of length $$$k$$$, and this can be done (cleanly) with prefix sums on prefix sums. Also, you need to handle $$$L = R$$$ separately. The final solution is $$$O(n)$$$.

340224836

Assume all elements appear twice, and look for a contradiction.

Split the array into two.

Determine whether each value appear on the left, on the right, or in both.

Continue recursively.

Write a recursive function solve(tl, tr, vals, waste), which means that

• you are looking for the special value in the interval [tl, tr];
• the vector vals contains the values which only appear in [tl, tr];
• the vector waste contains the value which appear both in [tl, tr] and outside it.

At the beginning, call solve(1, 2n - 1, {1, 2, ..., n}, {}). In every call,

• let tm = (tl + tr) / 2, and split the interval [tl, tr] into two intervals [tl, tm] and [tm+1, tr];
• for each value in waste determine the sub-interval containing it (spending $$$1$$$ query);
• for each value in vals determine the sub-intervals containing it (spending at most $$$2$$$ queries).

Now pretend every element appears twice, and calculate the length of [tl, tm] and [tm+1, tr] according to the values they contain. One of the lengths turns out to be wrong, because the interval contains a single element which was counted twice, so you can recurse there.

You visit at most $$$\lceil \log_2 n \rceil$$$ intervals. The total length of the visited intervals is at most $$$4n + \lceil \log_2 n \rceil$$$ (the starting interval has length $$$2n-1$$$ and is halved every time).

For an interval of length $$$l$$$, you ask at most $$$l+1$$$ queries. So you ask at most $$$4n + \lceil 2 \log_2 n \rceil$$$ queries in total.

340224890

For a single value, if it appears twice, how many queries can you spend on average to detect that?

Combine a randomized solution with the solution to 2150E1 - Hidden Single (Version 1).

After the first layer of recursion in the solution to 2150E1 - Hidden Single (Version 1), you have spent around $$$7n/4$$$ queries, and there are around $$$n/4$$$ candidate values which can be the special value.

Consider the following procedure to approximately halve the number of candidates:

• split the array randomly into two halves (subsets);
• for each candidate, determine whether it appears in both halves.

With probability around $$$1/2$$$, the candidate appears in both halves and you use $$$2$$$ queries to detect it. Otherwise, you spend $$$3/2$$$ queries on average. So the average number of queries is approximately the solution to $$$x = 2/2 + (x+3/2)/2$$$, which is $$$7/2$$$. So you spend around $$$21n/8$$$ queries in total. Because of variance, you might end up asking significantly more queries, but with high probability you ask at most $$$900$$$ queries.

Bonus: you can further reduce the number of queries using some minor optimizations. For example, instead of splitting randomly, you can shuffle the array randomly at the beginning, and binary search every candidate. This is better because:

• there is an upper bound on the number of queries you make for each candidate;
• you ask queries on smaller subsets, so the probability of a candidate appearing twice in the same subset is slightly lower;
• you can break earlier if you find the special value.

The model solution based on this approach takes only $$$863$$$ queries on worst case with $$$10^4$$$ tests of size $$$n = 300$$$.

340224967

Use $$$k = 3$$$ for the first operation. Now, you have edges between all vertices at distance $$$1$$$ and $$$2$$$.

Use $$$\frac{D}{2} + 1$$$ for your second operation, where $$$D$$$ is the diameter.

Assume the graph is a tree, otherwise take an arbitrary spanning tree. First operation is $$$k = 3$$$, because that adds edges between all vertices at distance $$$2$$$, and we already have edges of vertices at distance $$$1$$$.

The second operation needs to be at least $$$\frac{D}{2} + 1$$$, where $$$D$$$ is diameter, because otherwise it is impossible to construct a path between the farthest nodes. And infact, it is possible to construct paths of length exactly $$$\frac{D}{2} + 1$$$ between all pairs of vertices, so we choose second operation as this.

The construction is as follows, suppose we want a path between nodes $$$u$$$ and $$$v$$$ (there are simpler constructions, the editorialist describes his). Let $$$c_x$$$ denote the closest node in the diameter to node $$$x$$$.

• $$$dist(u, v) \ge k$$$ : Just take a direct path between $$$u$$$ and $$$v$$$, and skip appropriate number of vertices.

• $$$c_u \ne c_v$$$ : First construct a path from $$$u$$$ to $$$c_u$$$ and similarly, $$$v$$$ to $$$c_v$$$. Now, we need to waste some operations because $$$dist(u, v) \lt k$$$. Assume the diameter is $$$1, 2, \ldots, D$$$ WLOG. Then, we can do the following operation: $$$(c_u, c_u - 2, c_u - 4, c_u - 3, c_u - 1, c_u + 1)$$$ and we successfully wasted $$$4$$$ steps.

This can be easily generalized to all lengths. Because $$$dist(u, v) \lt k$$$ implies $$$dist(c_u, c_v) \lt k$$$, and thus, $$$dist(1, c_u) + dist(c_v, D) \ge k$$$, so it is always possible to waste sufficient number of steps on the paths $$$1$$$ to $$$c_u$$$ and $$$c_v$$$ to $$$D$$$.

• $$$c_u = c_v$$$ : Root the tree at $$$c_u$$$. Assume that $$$u$$$ is an ancestor of $$$v$$$ (if it is not, make it an ancestor by jumping to parent). Either $$$dist(1, u) \ge k$$$ or $$$dist(D, u) \ge k$$$ [due to property of diameter, $$$k = \frac{D}{2} + 1$$$]. Then we can waste the sufficient number of steps on the path from $$$1$$$ to $$$u$$$, or $$$L$$$ to $$$u$$$ whichever one is larger. ($$$1$$$ and $$$D$$$ are diameter endpoints).

The entire solution runs in $$$O(n^3)$$$.

340225230

Let's first solve the following subproblem: given $$$x, y, k,$$$ how can we find the number of binary strings with Longest Nondecreasing Subsequence $$$\geq k$$$?

The answer is if $$$max(x,y)\geq k$$$, the answer is $$$\binom{x+y}{x}$$$. Otherwise, it is $$$\binom{x+y}{k}$$$. The proof for the first case is obvious. In the second case, we can approach it by bijecting it to paths on a grid. We start at the point $$$(0,0)$$$ and we want to get to the point $$$(x,y)$$$ through going East ($$$+1$$$ on $$$x$$$-coordinate) or North ($$$+1$$$ on $$$y$$$-coordinate). We claim that any path $$$p_0=(0,0), p_1,p_2,\ldots,p_{x+y}=(x,y)$$$, where there exists an index $$$i$$$ such that $$$(p_i).x-(p_i).y=y-k$$$ can be bijected to a good binary string. To prove that this is sufficient, note that by taking every occurrence of North on our path in the future, we have a subsequence of size $$$k$$$. To prove that this is necessary, note that if the longest nondecreasing subsequence in the binary string is $$$a$$$ $$$0$$$'s followed by $$$b$$$ $$$1$$$'s, then we can map the point right after $$$a$$$ $$$0$$$'s to the index $$$i$$$. Now, why is this mapping helpful? We can use the reflection technique to count the number of good paths. Let $$$i$$$ be the first occurrence where $$$(p_i).x-(p_i).y=y-k$$$. Now, reflect the remaining part of the path across the line $$$y-x=y-k$$$. Now we have mapped the number of good paths to the number of paths that arrive to the point $$$(x+y-k, k)$$$. This is similar to the proof of the closed form of Catalan numbers. Let this function be $$$f(x,y,k)$$$.

Now, let's solve the above problem again, but we are given a prefix of the binary string. Let $$$Z$$$ be the number of zeroes, $$$L$$$ be the length of the longest nondecreasing subsequence, $$$x$$$ and $$$y$$$ be the number of zeroes and ones to concatenate, and let $$$k$$$ be the target length of longest nondecreasing subsequence. I claim that the number of ways to finish the binary string is $$$\binom{x+y}{x}$$$ if $$$L+y \geq k$$$ or $$$Z+x \geq k$$$, $$$0$$$ if $$$Z+x+y \lt k$$$, and $$$\binom{x+y}{k-Z}$$$ otherwise. The first two cases are relatively simple to show. We can show the last case because the longest nondecreasing subsequence of the entire string must compose entirely of $$$0$$$'s in the prefix (or else $$$L+y\geq k$$$ would be true), so we can simplify this problem to the above problem as we only need a longest nondecreasing subsequence of $$$k-Z$$$ now. Let this function be $$$g(x,y,k,Z)$$$.

Now, to solve the problem, let's enumerate the length of the common prefix of $$$s$$$ and $$$t$$$, and then the index where the first half first has a longest nondecreasing subsequence length of exactly $$$k$$$ (call this index $$$i$$$). If this point is within the prefix, then we can complete the second half of the sequence directly using the formula we obtained above. There are two cases: either $$$t_i=0$$$ or $$$t_i=1$$$. If $$$t_i=0$$$ and $$$i$$$ is the first index where the longest nondecreasing subsequence has length $$$k$$$, then the longest nondecreasing subsequence must compose of only $$$0$$$'s. In this case, the length of the longest nondecreasing subsequence up to index $$$i-1$$$ must be $$$k-1$$$, and the number of zeroes are also fixed — this is also a direct application of the original formula. Otherwise (that is, if $$$t_i=1$$$), let $$$x'$$$ and $$$y'$$$ be the number of zeroes and ones in this half. At index $$$i-1$$$, the length of the longest nondecreasing subsequence should be exactly $$$k-1$$$. We can calculate this by taking the number of binary strings with LNDS length at least $$$k-1$$$, and subtract the number of binary strings with LNDS length at least $$$k$$$. Note that the number of $$$0$$$'s and $$$1$$$'s in the second half is also fixed (call them $$$x"$$$ and $$$y"$$$ respectively), so we can multiply the previous result by the number of binary strings with LNDS at least $$$k$$$. We can write this as getting the sum $$$(g(x',y',k-1,Z)-g(x',y',k,Z))\cdot f(x",y",k)$$$.

This looks like the solution will become $$$O(n^3)$$$ since we have to loop through all possible $$$x'$$$ values. However, let's look at $$$g(x,y,k,Z)$$$ again. It is $$$\binom{x+y}{x}$$$ if $$$y \geq k-C_1$$$ or $$$x \geq k-C_2$$$ (call this case $$$1$$$) for some constants $$$C_1$$$ and $$$C_2$$$, and $$$\binom{x+y}{k-Z}$$$ otherwise (call this case $$$2$$$). Consider $$$g(x',y',k-1,Z)$$$ and $$$g(x',y',k,Z)$$$. When both functions are in case $$$1$$$, we have $$$g(x',y',k-1,Z)-g(x',y',k,Z)=0$$$. When both functions are in case $$$2$$$, the difference is a constant. The only case we have to worry about is when one function is in case $$$1$$$ and the other is in case $$$2$$$. But note the conditions for case $$$1$$$ — it is either if $$$y$$$ is larger than some constant or if $$$x$$$ is larger than some constant. Thus, when $$$g(x',y',k-1,Z)$$$ leaves case $$$1$$$, $$$g(x',y',k-1,Z)$$$ will also leave case $$$1$$$. Similarly, when $$$g(x',y',k,Z)$$$ enters case $$$1$$$ (when $$$y$$$ becomes too large), $$$g(x',y',k-1,Z)$$$ will also enter case $$$1$$$ in the next iteration. So, we only have to calculate these cases for $$$2$$$ values of $$$X$$$. Combining this with some prefix sums of binomial factors (to deal with the $$$f(x",y",k)$$$ portion when $$$g(x',y',k-1,Z)-g(x',y',k,Z)$$$ is constant), we actually avoid running the loop entirely. Thus, we can calculate the answer in $$$O(n^2)$$$.

340578210

Can you reach the score $$$\max(a) + \lceil n/2 \rceil$$$?

Can you reach the score $$$\max(a) + \lceil n/2 \rceil - 1$$$?

The maximum red element is $$$\leq \max(a)$$$, and the maximum number of red elements is $$$\lceil n/2 \rceil$$$. Can you reach the score $$$\max(a) + \lceil n/2 \rceil$$$?

• If $$$n$$$ is even, you always can, by either choosing all the elements in even positions or all the elements in odd positions (at least one of these choices contains $$$\max(a)$$$).
• If $$$n$$$ is odd, you can if and only if there is one occurrence of $$$\max(a)$$$ in an odd position. Otherwise, you can choose even positions and your score is $$$\max(a) + \lceil n/2 \rceil - 1$$$.

Complexity: $$$O(n)$$$

Can you determine fast how many intervals contain point $$$p$$$?

The intervals that contain point $$$p$$$ are the ones with $$$l \leq p$$$ and $$$r \geq p$$$.

Determine how many intervals contain:

• point $$$x_1$$$;
• points $$$x_1 + 1, \ldots, x_2 - 1$$$;
• point $$$x_2$$$;
• $$$\ldots$$$
• point $$$x_n$$$.

First, let's focus on determining how many intervals contain some point $$$x$$$. These intervals are the ones with $$$l \leq x$$$ and $$$x \leq r$$$.

So a point $$$x_i \lt p \lt x_{i+1}$$$ satisfies $$$x_1 \leq p, \ldots, x_i \leq p$$$, and $$$p \leq x_{i+1}, \ldots, p \leq x_n$$$. It means that you have found $$$x_{i+1} - x_i - 1$$$ points contained in exactly $$$i(n-i)$$$ intervals (because there are $$$i$$$ possible left endpoints and $$$n-i$$$ possible right endpoints).

Similarly, the point $$$p = x_i$$$ is contained in $$$i(n-i+1) - 1$$$ intervals (you have to remove interval $$$[x_i, x_i]$$$, which you do not draw).

So you can use a map that stores how many points are contained in exactly $$$x$$$ intervals, and update the map in the positions $$$i(n-i)$$$ and $$$i(n-i+1) - 1$$$.

Complexity: $$$O(n \log n)$$$

The answer is at most $$$n$$$.

Solve the problem with $$$k = 0$$$.

When is the answer $$$n$$$?

If the answer is not $$$n$$$, how can you buy cards?

Note that there are $$$n$$$ types of cards, so the subsets have size at most $$$n$$$, and the answer is at most $$$n$$$.

If $$$k = 0$$$, you can make subsets of size $$$s$$$ if and only if the following conditions are true:

• the number of cards ($$$m$$$) is a multiple of $$$s$$$;
• the maximum number of cards of some type ($$$x$$$) is $$$\leq m/s$$$.

Proof:

• $$$m$$$ is the number of decks times $$$s$$$.
• The number of decks is $$$m/s$$$. Each deck can contain at most $$$1$$$ card of each type, so there are at most $$$m/s$$$ cards of each type in total.
• If the two conditions above hold, you can make a deck containing the $$$s$$$ types of cards with maximum frequency. You can show with some calculations that the conditions still hold after removing these cards. So you can prove by induction that the two conditions are sufficient to make decks of size $$$s$$$.

The same idea is used in problems like 1954D - Colored Balls and abc227_d - Project Planning.

For a generic $$$k$$$, the answer is $$$n$$$ if you can make the number of cards of type $$$1, \ldots, n$$$ equal. Otherwise, for any choice of number of cards to buy, you can buy them without changing $$$x$$$. It means that you need $$$x \cdot s$$$ cards in total:

• if you have less than $$$x \cdot s$$$ cards, you have to check if you can reach $$$x \cdot s$$$ cards by buying at most $$$k$$$ new cards;
• if you already have $$$x \cdot s$$$ or more cards at the beginning, you have to check if you can make $$$m$$$ a multiple of $$$s$$$.

Complexity: $$$O(n)$$$

When is the answer $$$0$$$?

Starting from city $$$x$$$ is equivalent to setting $$$a_x = 1$$$.

At some time $$$t$$$, consider the minimal interval $$$[l, r]$$$ that contains all the cities with $$$a_i \leq t$$$ (let's call it "the minimal interval at time $$$t$$$"). You have to visit all this interval within time $$$t$$$, otherwise there are some cities with $$$a_i \leq t$$$ which you do not visit in time. So if this interval has length $$$ \gt t$$$, you cannot visit it all within time $$$t$$$, and the answer is $$$0$$$.

Otherwise, the answer is at least $$$1$$$. A possible construction is visiting "the minimal interval at time $$$1$$$", then "the minimal interval at time $$$2$$$", ..., then "the minimal interval at time $$$n$$$". Note that, when you visit "the minimal interval at time $$$t$$$", the actual time is equal to the length of the interval, which is $$$\leq t$$$. In this way, at time $$$t$$$ you will have conquered all the cities in the minimal interval at time $$$t$$$, and possibly other cities.

Starting from city $$$x$$$ is equivalent to setting $$$a_x = 1$$$. After this operation, you have to guarantee that, for each $$$i$$$, the minimal interval at time $$$t$$$ is short enough. If this interval is $$$[l, r]$$$ before the operation, it can become either $$$[x, r]$$$ (if $$$x \lt l$$$), or $$$[l, x]$$$ (if $$$x \gt r$$$), or stay the same. In all this cases, the resulting length must be $$$\leq t$$$. With some calculations (e.g., $$$r-x+1 \leq t$$$), you can get than $$$x$$$ must be contained in $$$[r-t+1, l+t-1]$$$. So it's enough to calculate and intersect the intervals obtained at $$$t = 1, \ldots, n$$$, and print the length of the final interval.

You can calculate the minimal intervals by iterating on the cities in increasing order of $$$a_i$$$. Again, if the old interval is $$$[l, r]$$$ and the new city has index $$$x$$$, the new possible intervals are $$$[x, r]$$$, $$$[l, r]$$$, $$$[l, x]$$$.

Another correct solution is to intersect the intervals $$$[i-a_i+1, i+a_i-1]$$$. The proof is contained in the editorial of 2018F3 - Speedbreaker Counting (Hard Version).

Complexity: $$$O(n)$$$

Solve for a fixed final depth of the leaves.

Which nodes are "alive" if all leaves are at depth $$$d$$$ at the end?

If the final depth of the leaves is $$$d$$$, it's optimal to keep in the tree all the nodes at depth $$$d$$$ and all their ancestors. These nodes are the only ones which satisfy the following two conditions:

• their depth ($$$a_i$$$) is $$$\leq d$$$;
• the maximum depth of a node in their subtree ($$$b_i$$$) is $$$\geq d$$$.

So every node is alive in the interval of depths $$$[a_i, b_i]$$$. The optimal $$$d$$$ is the one contained in the maximum number of intervals.

The optimal subsequence must contain at least one occurrence of the maximum.

Iterate over the minimum, in decreasing order.

You have some "connected components". How many elements can you pick from each component? How to make sure you have picked at least one occurrence of the maximum?

The optimal subsequence must contain at least one occurrence of the maximum ($$$r$$$) (suppose it doesn't; then you can just add one occurrence, at the cost of removing at most two elements, and this does not make your score smaller).

Now you can iterate over the minimum value ($$$l$$$), in decreasing order. At any moment, you can pick elements with values $$$[l, r]$$$. Then you have to support queries "insert pick-able element" and "calculate score".

The pick-able elements make some "connected components" of size $$$s$$$, and you can pick $$$\lceil s/2 \rceil$$$ elements. You can maintain the components with a DSU.

You also want to pick an element with value $$$r$$$. For each component, check if it contains $$$r$$$ in a subsequence with maximum size. If this does not happen for any component, your score decreases by $$$1$$$. All this information can be maintained by storing, for each component, if it contains $$$r$$$ in even positions, and if it contains $$$r$$$ in odd positions.

Complexity: $$$O(n \alpha(n))$$$

Solve for a fixed $$$m$$$ (size of the subsets).

$$$m = 1$$$ is easy. Can you do something similar for other $$$m$$$?

Solve for a fixed $$$k$$$ (number of subsets).

If you have a $$$O(n \log n)$$$ solution for a fixed $$$m$$$, note that there exists a faster solution!

Let's write a function max_k(m), which returns the maximum $$$k$$$ such that there exists a partition of $$$k$$$ valid sets containing $$$m$$$ intervals each. max_k works in $$$O(n \log n)$$$ in the following way (using a lazy segment tree):

• (wlog) $$$r_i \leq r_{i+1}$$$;
• for each $$$i$$$ not intersecting the previous subset, add $$$1$$$ on the interval $$$[l[i], r[i]]$$$;
• as soon as a point belongs to $$$m$$$ intervals, they become a subset;
• return the number of subsets.

For a given $$$k$$$, you can binary search the maximum $$$m$$$ such that max_k(m) $$$\geq k$$$ in $$$O(n \log^2 n)$$$.

The problem asks for the maximum $$$mk$$$. Since $$$mk \leq n$$$, for any constant $$$C$$$ either $$$m \leq C$$$ or $$$k \leq n/C$$$. For $$$C = (n \log n)^{1/2}$$$, the total complexity becomes $$$O((n \log n)^{3/2})$$$, which is enough to solve 2018E1 - Complex Segments (Easy Version). You can also find max_k(m) for all $$$m$$$ with a divide and conquer approach, and the complexity becomes $$$O(n \sqrt n \log n)$$$ (see here).

Now let's go back to max_k(m). It turns out you can implement it in $$$O(n \alpha(n))$$$.

First of all, let's make all the endpoints distinct, in such a way that two intervals intersect if and only if they were intersecting before.

Let's maintain a binary string of size $$$n$$$, initially containing only ones, that can support the following queries:

• set bit in position $$$p$$$ to 0;
• find the nearest 1 to the left of position $$$p$$$.

This can be maintained with DSU, where the components are the maximal intervals containing 100...00.

Now let's reuse the previous solution (sweeping $$$r$$$ from left to right), but instead of a segment tree we will maintain a binary string with the following information:

• the positions $$$ \gt r$$$ store 1;
• the positions $$$\leq r$$$ store 1 if and only if the value in that position (in the previous solution) is a suffix max.

So the queries become:

• add $$$1$$$ to $$$[l, r]$$$:
• • $$$r$$$ changes, so you have to set elements in $$$[r'+1, r-1]$$$ to $$$0$$$;
• • the only other element that changes is the nearest 1 to the left of position $$$l$$$, which does not represent a suffix max anymore.
• find the maximum: it's equal to the number of suffix maximums, which depends on $$$r$$$ and on the number of components.

This solution allows us to replace a $$$O(\log n)$$$ factor with a $$$O(\alpha(n))$$$ factor.

Complexity: $$$O(n \sqrt n \alpha(n))$$$

[Bonus: there exists a data structure faster than DSU to solve the subproblem above, so you can solve the problem in $$$O(n \sqrt n)$$$. See here.]

Suppose you are given a starting city and you want to win. Find several strategies to win (if possible) and try to work with the simplest ones.

The valid starting cities are either zero, or all the cities in $$$I := \cap_{i=1}^n [i - a_i + 1, i + a_i - 1] = [l, r]$$$.

Now you have some bounds on the $$$a_i$$$.

Fix the interval $$$I$$$ and try to find a (slow) DP.

Counting paths seems easier than counting arrays. Make sure that, for each array, you make exactly one path (or a number of paths which is easy to handle).

How many distinct states do you calculate in your DP?

Lemma 1

For a fixed starting city, if you can win, this strategy works:

• [Strategy 1] If there is a city on the right whose distance is $$$t$$$ and whose deadline is in $$$t$$$ turns, go to the right. Otherwise, go to the left.

Proof:

• All constraints on the right hold.
• This strategy minimizes the time to reach any city on the left. So, if any strategy works, this strategy works too.

Corollary

For a fixed starting city, if you can win, this strategy works:

• [Strategy 2] If there is a city whose distance is $$$t$$$ and whose deadline is in $$$t$$$ turns, go to that direction. Otherwise, go to any direction.

Lemma 2

The valid starting cities are either zero, or all the cities in $$$I := \cap_{i=1}^n [i - a_i + 1, i + a_i - 1] = [l, r]$$$.

Proof:

• The cities outside $$$I$$$ are losing, because there exists at least one unreachable city.
• Let's start from any city $$$x$$$ in $$$I$$$, and use Strategy 2.
• You want to show that, for any $$$x$$$ in $$$I$$$, Strategy 2 can visit all cities in $$$I$$$ first, then all the other cities. Then, you can conclude that either all the cities in $$$I$$$ are winning, or they are all losing.
• The interval $$$I$$$ gives bounds on the $$$a_i$$$: specifically, $$$a_i \geq \max(i-l+1, r-i+1)$$$. Then, you can verify that visiting the interval $$$I$$$ first does not violate Strategy 2.

Corollary

If you use Strategy 1, the first move on the right determines $$$l$$$.

$$$\LARGE O(n^4)$$$ DP

Let's iterate on the (non-empty) interval $$$I$$$. Let's calculate the bounds $$$a_i \geq \max(i-l+1, r-i+1)$$$. Note that Strategy 1 is deterministic (i.e., it gives exactly one visiting order for each fixed pair (starting city, $$$a$$$)). From now, you will use Strategy 1.

Now you will calculate the number of pairs ($$$a$$$, visiting order) such that the cities in $$$I$$$ are valid starting cities (and there might be other valid starting cities).

Let's define dp[i][j][k] = number of pairs ($$$a$$$, visiting order), restricted to the interval $$$[i, j]$$$, where $$$k =$$$ "are you forced to go to the right in the next move?". Here are the main ideas to find the transitions:

• If you go from $$$[i+1, j]$$$ to $$$[i, j]$$$, you must ensure that $$$a_i \geq \max(i-l+1, r-i+1, j-i+1)$$$ (because you visit it at time $$$j-i+1$$$). Also, $$$k$$$ must be $$$0$$$.
• If you go from $$$[i, j-1]$$$ to $$$[i, j]$$$, and you want to make $$$k = 0$$$, you must make $$$a_j = j-i+1$$$. It means that $$$j$$$ was the city that was enforcing you to go to the right.

In my code, the result is stored in int_ans[i][j].

Now you want to calculate the number of pairs ($$$a$$$, visiting order) such that the cities in $$$I$$$ are the only valid starting cities. This is similar to 2D prefix sums, and it's enough to make int_ans[i][j] -= int_ans[i - 1][j] + int_ans[i][j + 1] - int_ans[i - 1][j + 1].

Since, for a fixed $$$a$$$, the visiting order only depends on the starting city, the number of $$$a$$$ for the interval $$$[i, j]$$$ is now int_ans[i][j] / (j - i + 1).

You have solved $$$k \geq 1$$$. The answer for $$$k = 0$$$ is just $$$n^n$$$ minus all the other answers.

$$$\LARGE O(n^3)$$$ DP

In the previous section, you are running the same DP for $$$O(n^2)$$$ different "bound arrays" on the $$$a_i$$$ (in particular, $$$O(n)$$$ arrays for each $$$k$$$). Now you want to solve a single $$$k$$$ with a single DP.

For a fixed $$$k$$$, you can notice that, if you run the DP on an array of length $$$2n$$$ instead of $$$n$$$, the bound array obtained from $$$I = [n-k+1, n]$$$ contains all the bound arrays you wanted as subarrays of length $$$n$$$. So you can run the DP and get all the results as dp[i][i + n - 1][0].

$$$\LARGE O(n^2)$$$ DP

You still have $$$O(n^3)$$$ distinct states in total. How to make "bound arrays" simpler?

It turns out that you can handle $$$l$$$ and $$$r$$$ differently! You can create bound arrays only based on $$$r$$$ (and get $$$O(n^2)$$$ distinct states), and find $$$l$$$ using the Corollary of Lemma 2. The transitions before finding $$$l$$$ are very simple (you always go to the left). So a possible way to get $$$O(n^2)$$$ complexity is processing Strategy 1 and the DP in reverse order (from time $$$n$$$ to time $$$1$$$).

Complexity: $$$O(n^2)$$$

Div. 1:

1. jiangly
2. PEIMUDA
3. hos.lyric
4. turmax
5. squareOf105

Div. 2:

1. youngherd
2. Cylrx
3. dieselhuang
4. Regener4tion
5. JiangYang

Div. 1 first solves:

• A: squareOf105
• B: jiangly
• C: FantasyNumber
• D: ksun48
• E1: dorijanlendvaj
• E2: jiangly
• F1: rainboy
• F2: rainboy
• F3: rainboy

Div. 2 first solves:

• A: SSafarov
• B: rixiepixie
• C: justin_zed
• D: eimil
• E: zzzYteng
• F: Cylrx

If costs were distinct, it would work. The proof would be something like "suppose you find an optimal configuration with intersections; remove an intersection by swapping two endpoints and get a strictly better configuration, contradiction".

But here costs can be equal, so you don't necessarily get a strictly better configuration. It might happen that all the optimal configurations have intersections, and if you swap endpoints you never reach the bracket matching (i.e., you loop over the optimal configurations with intersections infinitely). So the last part of the proof is showing that this is not possible (i.e., "the process ends in a finite number of steps").

Anyway, I'm surprised that no one asked how to prove "the process ends in a finite number of steps". I think it's the hardest part of the proof (I can only prove it with tedious casework, and I think it's not that interesting, so I omitted it).

Winners:

1. zh0ukangyang
2. maroonrk
3. jiangly
4. FastFreeTask
5. ksun48
6. ugly2333
7. Um_nik
8. cnnfls_csy
9. maspy
10. RanaKaname

First solves:

• A: Barys
• B: tourist
• C: Petr
• D: maspy
• E: QueenOfDiamonds
• F1: ksun48
• F2: menjihuang
• G: zh0ukangyang
• H: maroonrk
• I: zh0ukangyang

(problems D', H', etc. were not used)

• Feb 19, 2022: I proposed problem D' to Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round), but it was not used.
• Mar 13, 2023: I invented problem A.
• May 16: I invented problem H'.
• May 19: I realized problem G can be solved in $$$O(n)$$$ time and we used it in the Italian team selection test for IOI.
• Jul 04: I opened a Div. 1 proposal containing A, D', G, H' and other problems which are not going to be used.
• Aug 09: I invented problem I, with intended solution in $$$O(n^3)$$$.
• Sep 27: I invented problem C.
• Oct 14: errorgorn replied to my contest proposal.
• Nov 02: I invented problem D''. errorgorn solved problem I in $$$O(n^2 \log n)$$$.
• Nov 08: I invented problems E and F. I didn't propose problem F because I thought it was too easy.
• Nov 10: I invented problem H with $$$O(n \log n)$$$ operations. We had a preliminary problemset, with problems A, D', C, D'', E, H1, G, H', I. I started preparing the problems.
• Nov 14: I finished preparing the problems, and the round was ready for testing. dario2994 tested and didn't solve problem D''. I realized the official solution of problem D'' was wrong (and now I don't have any solution).
• Nov 15: I removed problem D'' from the contest and replaced it with problem F.
• Nov 17: I invented problem E'.
• Nov 19: I invented problem F', which was rejected because it was proposed independently to errorgorn by the authors of another round.
• Nov 22: gamegame tested and said problem H' is well-known in China. I removed it.
• Nov 26: we realized problem D' was too hard for position B.
• Nov 28: I invented problem D with $$$k = 1$$$ and $$$a_i \geq 2$$$, and I proposed it as B.
• Nov 29: I invented problem B. Endagorion solved problem H in $$$2n$$$ operations.
• Dec 07: the problemset was A, B, C, D', F1, F2, E, G, H1, H2, I, but there was a huge gap between D' and the next problems. We ended up using A, B, C, D, E', E, F2, G, H2, I (i.e., 10 problems). D still had $$$k = 1$$$ and $$$a_i \geq 2$$$.
• Dec 13: we removed the constraints $$$k = 1$$$ and $$$a_i \geq 2$$$ from problem D.
• Dec 18: problem E' appeared in Educational Codeforces Round 160 (Rated for Div. 2). We removed it and we decided to use subtasks on problem F.

Suppose you can only use $$$\texttt{U}$$$, $$$\texttt{R}$$$, $$$\texttt{D}$$$. Which cells can you reach?

If you only use buttons $$$\texttt{U}$$$, $$$\texttt{R}$$$, $$$\texttt{D}$$$, you can never reach the points with $$$x \lt 0$$$. However, if all the special points have $$$x \geq 0$$$, you can reach all of them with the following steps:

• visit all the special points with $$$x = 0$$$, using the buttons $$$\texttt{U}$$$, $$$\texttt{D}$$$;
• press the button $$$\texttt{R}$$$ to reach $$$x = 1$$$;
• visit all the special points with $$$x = 1$$$, using the buttons $$$\texttt{U}$$$, $$$\texttt{D}$$$;
• $$$\dots$$$
• visit all the special points with $$$x = 100$$$, using the buttons $$$\texttt{U}$$$, $$$\texttt{D}$$$.

Similarly, if you use at most $$$3$$$ buttons in total, you can reach all the special points if at least one of the following conditions is true:

• all $$$x_i \geq 0$$$;
• all $$$x_i \leq 0$$$;
• all $$$y_i \geq 0$$$;
• all $$$y_i \leq 0$$$.

Complexity: $$$O(n)$$$

Find a value of $$$k$$$ that works in many cases.

$$$k = 2$$$ works in many cases. What if it does not work?

If $$$k = 2$$$ does not work, either all the numbers are even or all the numbers are odd. Which $$$k$$$ can you try now?

Let $$$f(k)$$$ be the number of distinct values after the operation, using $$$k$$$.

Let's try $$$k = 2$$$. It works in all cases, except when either all the numbers are even or all the numbers are odd.

Let's generalize. If $$$a_i \text{ mod } k = x$$$, one of the following holds:

• $$$a_i \text{ mod } 2k = x$$$;
• $$$a_i \text{ mod } 2k = x+k$$$;

It means that, if $$$f(k) = 1$$$ (i.e., all the values after the operations are $$$x$$$), either $$$f(2k) = 1$$$ (if either all the values become $$$x$$$, or they all become $$$x+k$$$), or $$$f(2k) = 2$$$.

Therefore, it is sufficient to try $$$k = 2^1, \dots, 2^{57}$$$. In fact, $$$f(1) = 1$$$ and $$$f(2^{57}) = n$$$, so there must exist $$$m \lt 57$$$ such that $$$f(2^m) = 1$$$ and $$$f(2^{m+1}) \neq 1 \implies f(2^{m+1}) = 2$$$.

Alternative (more intuitive?) interpretation:

• $$$a_i \text{ mod } 2^j$$$ corresponds to the last $$$j$$$ digits in the binary representation of $$$a_i$$$. There must exist $$$j$$$ such that the last $$$j$$$ digits make exactly $$$2$$$ distinct blocks.

In the following picture, $$$a = [1005, 2005, 7005, 11005, 16005]$$$ and $$$k = 16$$$:

Complexity: $$$O(n \log(\max a_i))$$$

Assign bigger costs to shorter intervals.

Solve the problem with $$$n = 2$$$.

Solve the following case: $$$l = [1, 2]$$$, $$$r = [3, 4]$$$, $$$c = [1, 2]$$$. Can you generalize it?

You have to match each $$$l_i$$$ with some $$$r_j \gt l_i$$$.

Construct $$$v = {l_1, l_2, \dots, l_n, r_1, r_2, \dots, r_n}$$$ and sort it. If you replace every $$$l_i$$$ with the symbol $$$\texttt{(}$$$ and every $$$r_i$$$ with the symbol $$$\texttt{)}$$$, you get a regular bracket sequence (sketch of proof: $$$l_i \lt r_i$$$ for each $$$i$$$, so each prefix of symbols contains at least as many $$$\texttt{(}$$$ as $$$\texttt{)}$$$, so the bracket sequence is regular).

Now match each $$$\texttt{(}$$$ with the corresponding $$$\texttt{)}$$$. You can show that this is the optimal way to rearrange the $$$l_i$$$ and the $$$r_i$$$. (From now, let the $$$l_i$$$, $$$r_i$$$ and $$$c_i$$$ be the values after your rearrangement.)

Proof:

• If you match the brackets in any other way, you get two intervals such that their intersection is non-empty but it is different from both intervals (i.e., you get $$$l_i \lt l_j \lt r_i \lt r_j$$$).
• You have also assigned some cost $$$c_i$$$ to $$$[l_i, r_i]$$$ and $$$c_j$$$ to $$$[l_j, r_j]$$$. Without loss of generality, $$$c_i \leq c_j$$$ (the other case is symmetrical).
• If you swap $$$r_i$$$ and $$$r_j$$$, the cost does not increase.
• Keep swapping endpoints until you get the "regular" bracket matching. You can show that the process ends in a finite number of steps. For example, you can show that $$$\sum ((r_i - l_i)^2)$$$ strictly increases after each step, and it is an integer $$$\leq \sum (r_i^2)$$$.

Now, you can get the minimum cost by sorting the intervals by increasing length and sorting the $$$c_i$$$ in decreasing order.

Alternative (more intuitive?) interpretation:

• If you solve the problem with $$$n = 2$$$ and try to generalize, you can notice that it seems optimal to match every $$$r_i$$$ with the largest unused $$$l_i$$$ (if you iterate over $$$r_i$$$ in increasing order).

You can implement the solution by using either a stack (to simulate the bracket matching) or a set (to find the largest unused $$$l_i$$$).

Complexity: $$$O(n \log n)$$$

Solve the problem with $$$k = 0$$$.

Solve the problem with generic $$$k$$$. When is the answer $$$-1$$$?

Do you notice any similarities between the cases with $$$k = 0$$$ and with generic $$$k$$$?

Consider the "shifted" problem, where each $$$x$$$ on the blackboard (at any moment) is replaced with $$$x' = x-k$$$.

Now, the operation becomes "replace $$$x$$$ with $$$y+z$$$ such that $$$y+z = x+k \implies (y'+k)+(z'+k) = (x'+k)+k \implies y'+z' = x'$$$". Therefore, in the shifted problem, $$$k' = 0$$$.

Now you can replace every $$$a'_i := a_i - k$$$ with any number of values with sum $$$a'_i$$$, and the answer is the amount of numbers on the blackboard at the end, minus $$$n$$$.

If we want to make all the values equal to $$$m'$$$, it must be a divisor of every $$$a'_i$$$.

• If all the $$$a'_i$$$ are positive, it is optimal to choose $$$m' = \gcd a'_i$$$.
• If all the $$$a'_i$$$ are zero, the answer is $$$0$$$.
• If all the $$$a'_i$$$ are negative, it is optimal to choose $$$m' = -\gcd -a'_i$$$.
• Otherwise, the answer is $$$-1$$$.

Alternative way to get this result:

• You have to split each $$$a_i$$$ into $$$p_i$$$ pieces equal to $$$m$$$, and their sum must be equal to $$$a_i + k(p_i - 1) = (a_i - k) + kp_i = mp_i$$$. Then, $$$(a_i - k) = (m - k)p_i$$$, so $$$m' = m-k$$$ must be a divisor of every $$$a'_i = a_i - k$$$.

In both the positive and the negative case, you will only write positive elements (in the original setup), as wanted.

• If all the $$$a'_i$$$ are positive, the numbers you will write on the shifted blackboard are positive, so they will be positive also in the original blackboard.
• If all the $$$a'_i$$$ are negative, the numbers you will write on the shifted blackboard are greater than the numbers you will erase, so they will be greater than the numbers in input (and positive) in the original blackboard.

Complexity: $$$O(n + \log(\max a_i))$$$

Find a strategy that turns "few" lamps on in most cases.

Pressing all the buttons turns $$$\lfloor \sqrt n \rfloor$$$ lamps on.

If the strategy in Hint 2 does not work, at most $$$3$$$ lamps must be on at the end.

Iterate over all subsets of at most $$$3$$$ lamps that must be on at the end.

If you press all the buttons, lamp $$$i$$$ is toggled by all the divisors of $$$i$$$, so it will be on if $$$i$$$ has an odd number of divisors, i.e., if $$$i$$$ is a perfect square.

Then, the strategy of pressing all the buttons works if $$$\lfloor \sqrt n \rfloor \leq \lfloor n/5 \rfloor$$$, which is true for $$$n \geq 20$$$.

If $$$n \leq 19$$$, at most $$$\lfloor 19/5 \rfloor = 3$$$ lamps must be turned on at the end.

If you know which lamps must be turned on at the end, you can iterate over the buttons from $$$1$$$ to $$$n$$$ and press button $$$i$$$ if and only if lamp $$$i$$$ is in the wrong state. So you can iterate over all subsets of at most $$$3$$$ lamps, and check if the corresponding choice of buttons is valid (i.e., the $$$m$$$ constraints hold). You can remove a $$$\log n$$$ factor by precalculating the choice of buttons for all small subsets before running the testcases.

Complexity for each test: $$$O(\sum n + (\sum m \cdot k^{2k-4}))$$$ (if $$$\lfloor n/k \rfloor$$$ lamps must be on; in this case, $$$k = 5$$$).

Find a clean way to visualize the problem.

Draw a $$$n \times n$$$ grid, with tokens in $$$(i, p_i)$$$. Which constraints on the tokens do you have?

You have some "L" shapes, and each of them must contain a fixed number of tokens (in 1909F1 - Small Permutation Problem (Easy Version) the shapes are $$$1$$$ cell wide and must contain at most $$$2$$$ tokens). Iterate over the shapes in increasing order of $$$i$$$.

Split each shape into $$$2$$$ rectangles and iterate over the number of tokens in the first rectangle.

Draw a $$$n \times n$$$ grid, with tokens in $$$(i, p_i)$$$.

Consider any $$$a_i \neq -1$$$ and the nearest $$$a_j \neq -1$$$ on the left (if it does not exist, let's set $$$j = a_j = 0$$$). Then, there must be $$$a_i$$$ tokens in the subgrid $$$[1, i] \times [1, i]$$$. We can suppose we have already inserted the $$$a_j$$$ tokens in $$$[1, j] \times [1, j]$$$, and we have to insert $$$a_i - a_j$$$ tokens in the remaining cells of $$$[1, i] \times [1, i]$$$ (they make an "L" shape).

WLOG, the $$$a_j$$$ tokens in $$$[1, j] \times [1, j]$$$ are in the cells $$$(1, 1), \dots, (a_j, a_j)$$$. Then, we can put tokens in the blue cells in the picture.

The blue shape can be further split into these two rectangles:

Iterate over $$$k$$$, the number of tokens in the first rectangle ($$$0 \leq k \leq a_i - a_j$$$). Then, you have to insert $$$k$$$ tokens into a $$$h_1 \times w_1$$$ rectangle, and the remaining $$$a_i - a_j - k$$$ tokens into a $$$h_2 \times (w_2 - k)$$$ rectangle.

The number of ways to insert $$$k$$$ tokens into a $$$h \times w$$$ rectangle is equal to the product of the number of ways to choose $$$k$$$ rows, the number of ways to choose $$$k$$$ columns, and the number of ways to fill the resulting $$$k \times k$$$ subgrid: the result is $$$\binom{h}{k} \binom{w}{k} k!$$$.

$$$a_n = n$$$ automatically (if $$$a_n \neq n$$$ and $$$a_n \neq -1$$$, the answer is $$$0$$$). If the non-negative $$$a_i$$$ are non-decreasing, the sum of the $$$a_i - a_j + 1$$$ (i.e., the $$$k$$$ over which you have to iterate) is $$$O(n)$$$, so the algorithm is efficient enough. Otherwise, the answer is $$$0$$$.

Complexity: $$$O(n)$$$

If you remove the condition $$$s = x+y+z$$$, the problem becomes harder.

Solve for a fixed $$$|y|$$$ (length of $$$y$$$).

Suppose you have found a valid $$$y$$$. Shift it one position to the right. When is it still valid?

The valid $$$y$$$ with $$$|y| = l$$$ start in consecutive positions.

Using the same idea of the proof of Hint 4, you can find all the valid $$$y$$$.

Let's use $$$s[l, r]$$$ to indicate the substring $$$[l, r]$$$ of $$$s$$$. Let's use $$$(a, b)$$$ to indicate the triple of strings $$$(s[1, a], s[a+1, b], s[b+1, n])$$$.

Suppose $$$(a, b)$$$ is valid. Then, $$$(a+1, b+1)$$$ is valid if and only if $$$s_{b+1} = t_{b+1}$$$.

If $$$(a, b)$$$ is valid, $$$s[1, b] = t[1, b]$$$; so if $$$s_b \neq t_b$$$, $$$(a+k, b+k)$$$ is invalid for $$$k \geq 0$$$. Therefore, if $$$(a, b)$$$ is the first valid pair with $$$b-a=l$$$ (i.e., with $$$|y| = l$$$), and $$$k$$$ is the smallest positive integer such that $$$(a+k, b+k)$$$ is invalid, then $$$s_{b+k} \neq t_{b+k}$$$, so the only valid pairs with $$$|y| = l$$$ are the $$$(a+j, b+j)$$$ with $$$0 \leq j \lt k$$$ (i.e., the valid $$$y$$$ with $$$|y| = l$$$ start in consecutive positions).

Now let's find all the valid $$$y$$$ with $$$|y| = l$$$. Suppose $$$(a, b)$$$ is valid, and $$$c$$$ is the minimum index such that $$$s_c \neq t_c$$$. Then, $$$b \lt c$$$, and $$$(a+k, b+k)$$$ is valid for all $$$b \leq b+k \lt c$$$. Similarly, if $$$d$$$ is the minimum integer such that $$$s_{n-d} \neq t_{m-d}$$$, $$$(a+k, b+k)$$$ is valid for all $$$n-d \lt a+k \leq a \implies n-d+l \lt b+k \leq b$$$.

Therefore, it's enough to check only one pair for each length, with $$$b$$$ in $$$[n-d+l+1, c-1]$$$ (because either all these pairs are valid or they are all invalid). This is possible by precomputing the rolling hash of the two strings. Alternatively, you can use z-function.

Complexity: $$$O(n)$$$

Find a strategy which is as simple and "easy to handle" as possible.

Only perform operations such that all swapped pairs have $$$a_i \gt a_{i+1}$$$. Let's call such subarrays "swappable".

First, for each $$$i$$$ from left to right, do the operation on $$$[j, i]$$$, where $$$j$$$ is the minimum index such that $$$[j, i]$$$ is swappable.

Repeat the same algorithm from right to left.

After Hints 3 and 4, the array is sorted. Prove it (it will be useful).

Assign $$$\texttt{B}$$$ to the indices $$$i$$$ such that $$$a_i \lt a_{i-1}$$$ and $$$\texttt{A}$$$ to the other indices. During the process in Hint 3, after the operation on index $$$i$$$, which properties do $$$\texttt{A}$$$, $$$\texttt{B}$$$ have in the prefix $$$[1, i]$$$?

Answer to Hint 6:

• the values of type $$$\texttt{A}$$$ are increasing;
• there are no two consecutive elements of type $$$\texttt{B}$$$.

The rest of the proof (i.e., what happens during the process in Hint 4) is relatively easy.

Now let's find an efficient implementation. We have to use the properties in Hint 7.

You have to find the longest $$$\texttt{AB} \dots \texttt{AB}$$$ ending in position $$$i$$$, and perform the operation on it. What happens during the operation?

$$$\texttt{A}$$$ will always remain $$$\texttt{A}$$$. For each $$$\texttt{B}$$$, you have to detect when it becomes $$$\texttt{A}$$$.

For each $$$\texttt{B}$$$, you can precompute the number of moves needed to make it $$$\texttt{A}$$$.

For example, you can use a segment tree with the following information: the type of each element, the positions of the elements of type $$$\texttt{B}$$$, and the number of moves required for each $$$\texttt{B}$$$ to become $$$\texttt{A}$$$.

Let's only perform operations such that all swapped pairs have $$$a_i \gt a_{i+1}$$$. Let's call such subarrays "swappable".

• First, for each $$$i$$$ from left to right, do the operation on $$$[j, i]$$$, where $$$j$$$ is the minimum index such that $$$[j, i]$$$ is swappable (let's call it "operation $$$1.i$$$").
• Then, for each $$$i$$$ from right to left, do the operation on $$$[j, i]$$$, where $$$j$$$ is the minimum index such that $$$[j, i]$$$ is swappable (let's call it "operation $$$2.i$$$").

After these operations, the array is sorted. Let's prove it.

Assign $$$\texttt{B}$$$ to the indices $$$i$$$ such that $$$a_i \lt a_{i-1}$$$ and $$$\texttt{A}$$$ to the other indices. After operation $$$1.i$$$, only assign letters in the prefix $$$[1, i]$$$ and ignore the other elements. During the operations $$$2.i$$$, assign letters to all the elements.

Most of the following proofs are by induction. After the operation $$$1.i$$$ (supposing the properties were true after the operation $$$1.(i-1)$$$):

• An element of type $$$\texttt{A}$$$ will always remain of type $$$\texttt{A}$$$. Proof: the only elements of type $$$\texttt{A}$$$ whose previous element changes are the ones in the subarray $$$[j, i]$$$, which are swapped with a smaller element of type $$$\texttt{B}$$$.
• There are no two consecutive elements of type $$$\texttt{B}$$$. Proof: if you swap $$$[j, i]$$$, $$$p_{j-1}$$$ (if it exists) must be of type $$$\texttt{A}$$$ (otherwise $$$[j-2, i]$$$ is swappable).
• The elements of type $$$\texttt{A}$$$ are increasing. Proof: it's true if no $$$\texttt{B}s$$$ become $$$\texttt{A}s$$$, and it's also true if some $$$\texttt{B}s$$$ become $$$\texttt{A}s$$$ because any of them is adjacent to two $$$\texttt{A}s$$$.

After the operation $$$2.i$$$:

• The three properties above are still true.
• The suffix $$$[i, n]$$$ contains the values in $$$[i, n]$$$ in order. Proof: $$$a_i$$$ is an $$$\texttt{A}$$$, so it must be the largest $$$p_i$$$ in $$$[1, i]$$$, which is $$$i$$$.

Now let's understand how we can implement the algorithm. Example implementation:

• We maintain a segment tree. The $$$i$$$-th position of the segment tree contains information about the element which was initially $$$p_i$$$. Note that the relative position of $$$\texttt{B}s$$$ never changes: for example, if you want information about the last $$$k$$$ $$$\texttt{B}s$$$ in the current permutation, and you search them in the segment tree, you will find exactly the last $$$k$$$ $$$\texttt{B}s$$$, even though their indices will not correspond to the current indices.
• We have to find the longest swappable subarray ending at $$$i$$$. It means we need the current positions of the $$$\texttt{B}s$$$. For each $$$\texttt{B}$$$ maintain the current position, and assume the position of all the $$$\texttt{A}s$$$ is $$$0$$$. Also maintain, for each element, if it is a $$$\texttt{B}$$$ or not. Note that the $$$\texttt{B}s$$$ that are affected by each operation can be found in a suffix of the segment tree.
• In this way, finding the longest swappable subarray can be done with a binary search on the segment tree: since $$$\texttt{B}s$$$ cannot be consecutive, you have to find the longest suffix such that the sum of the positions of the $$$\texttt{B}s$$$ is the maximum possible (i.e., if there are $$$k$$$ $$$\texttt{B}s$$$ and the last of them is in position $$$i$$$, the sum of their positions must be $$$k(i-k+1)$$$).
• After finding the longest subarray in the segment tree, you have to perform the operation on it, i.e., subtract $$$1$$$ from all the nonzero positions.
• Some $$$\texttt{B}s$$$ may become $$$\texttt{A}s$$$. How to detect them? Since $$$\texttt{A}s$$$ never become $$$\texttt{B}s$$$, a $$$\texttt{B}$$$ becomes $$$\texttt{A}$$$ after it is swapped with all the elements greater than it on its left. So you can precompute the number of swaps that every $$$\texttt{B}$$$ needs to become $$$\texttt{A}$$$, and put it in the segment tree as well. Again, the operation is "subtract $$$1$$$ from a range".
• Detecting $$$\texttt{A}s$$$ means detecting elements which need $$$0$$$ swaps to become $$$\texttt{A}s$$$. You can find them after each operation by traversing the segment tree (which must support "range min" on the number of swaps needed), and set their position to $$$0$$$ and the number of swaps needed to $$$\infty$$$.

Complexity: $$$2n-3$$$ moves, $$$O(n \log n)$$$ time.

Insert the elements into the permutation in some comfortable order.

Suppose $$$m$$$ is even. You can insert elements in the order $$$[m/2, m/2 - 1, m/2 + 1, m/2 - 2, \dots]$$$.

You can solve for a single $$$m$$$ with DP. Can you calculate the DP for multiple $$$m$$$ simultaneously?

The first part of the DP (where you insert both "small" and "big" elements) is the same for each $$$m$$$ (but with a different length), and for the second part (where you only insert "small" elements) you don't need DP.

The second part of the DP can be replaced with combinatorics formulas.

Binomials are compatible with NTT.

Let's solve for a single $$$m$$$. Suppose $$$m$$$ is even. Start from an empty array, and insert the elements in the order $$$[m/2, m/2 - 1, m/2 + 1, m/2 - 2, \dots]$$$. At any moment, all the elements are concatenated, and you can insert new elements either at the beginning, at the end or between two existing elements.

• When you insert an element $$$\geq m/2$$$, the sum with any of the previous inserted elements is $$$\geq m$$$.
• Otherwise, the sum is $$$ \lt m$$$.

So you can calculate $$$dp_{i,j} =$$$ number of ways to insert the first $$$i$$$ elements (of $$$[m/2, m/2 - 1, m/2 + 1, m/2 - 2, \dots]$$$) and make $$$j$$$ "good" pairs (with sum $$$\geq m$$$).

You can split the ordering $$$[m/2, m/2 - 1, m/2 + 1, m/2 - 2, \dots]$$$ into two parts:

• small and big elements alternate;
• there are only small elements.

For the second part, you don't need DP. Suppose you have already inserted $$$i$$$ elements, and there are $$$j$$$ good pairs, but when you will have inserted all elements you want $$$k$$$ good pairs. The number of ways to insert the remaining elements can be computed with combinatorics in $$$O(1)$$$ after precomputing factorials and inverses (you have to choose which pairs to break and use stars and bars; we skip exact formulas because they are relatively easy to find).

If you rearrange the factorials correctly, you can get that all the answers for a fixed $$$m$$$ can be computed by multiplying two polynomials, one of which contains the $$$dp_{i,j}$$$, where $$$i$$$ is equal to the length of the "alternating" prefix. NTT is fast enough.

Complexity: $$$O(n^2 \log n)$$$

Done :D

After inventing 1485A - Add and Divide and 1485B - Replace and Keep Sorted, I tried to invent "Add and Keep Sorted".

Some months later, 1667A - Make it Increasing appeared in a contest. It's basically the same problem with an extra step, and it looks much cooler than preoii_vm - Aggiornamento della macchina virtuale.

I came up with this problem while trying to find a div2A for Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round).

Yet another rejected problem A of Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round).

Basically, it's terry 2023/4 - Viaggio intrigante with $$$3$$$ distinct buttons instead of $$$2$$$. The solution turns out to be quite different.

First, I randomly came up with "given $$$a$$$, you can make $$$a := 2a$$$ or $$$a := \lfloor a/2 \rfloor$$$ any number of times, can you make $$$a = b$$$?" It was rejected because it's well-known. Then, I tried to generate a problem with the same solution.

At some point, I wanted to make an IntervalForces div2 round, but I ended up using the problems on CodeChef because the queue for div2 was too long.

Yet another rejected problem A of Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round).

The idea was "generate a problem where you have to find a pair of elements that maximizes something, and the key idea is that it's optimal to choose the maximum element". So, I was searching for some formula such that, if $$$c$$$ (one of the elements) is fixed, $$$x$$$ (the other element) should be the maximum, i.e., $$$f_c(x)$$$ is non-decreasing.

$$$f_c(x) = c+x+(c-x)\%m$$$ worked.

It was problem A of Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round) for a long time during testing, but eventually we decided to change it because it looked too hard.

I proposed it in a Turing machine competition (since the implementation is doable), but it turned out I could use it in Codeforces Round 889 (Div. 2), so I withdrew the proposal.

First, I proposed it on Codeforces, and it was accepted but we ended up using another problem. Then, I proposed it on CodeChef and it was rejected :D

I ended up using it for regional OI. The setup is very similar to 1329A - Dreamoon Likes Coloring, but the solution is different.

This problem was inspired by real life. I saw someone erasing a name from a sorted list and putting his name instead, but the list became unsorted. Then, I wondered in how many ways you can keep the list sorted under certain constraints.

Invented the same day as 1909B - Make Almost Equal With Mod, while looking for a div2B. We didn't use it in Pinely Round 3 (Div. 1 + Div. 2), but it filled a difficulty gap in Codeforces Round 924 (Div. 2).

Yet another IntervalForces problem.

"Count subarrays with some property" is an easy way to get decent problems.

The intended solution is subquadratic (using sets, or binary search). Unfortunately, I forgot that the competition was output only with a TL of $$$10$$$ minutes (and no one seemed to notice it during testing), so $$$O(n^2)$$$ and even $$$O(n^2 \log n)$$$ passed :(

I'm sorry for making this year's regional OI ridiculously easy.

After proposing a lot of div2B problems which turned out to be too hard, I proposed this, suspecting it was also too hard. It turned out it wasn't.

I was thinking about how swapping the endpoints of two intervals to make them non-intersecting always makes one interval shorter (and possibly the other longer). Then I realized I could use rearrangement inequality on this setup.

Yet another proposal for problem A of Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round) (rejected because too hard). In fact, its rating on CodeChef is 2566 :D

Standard but educational problem.

Challenge: solve arc155_d - Coprime Game. If you are stuck, solve cc THROWTAKE - Throw and Take and 1731E - Graph Cost first.

Why didn't this problem exist before?

Inspired by arc122_c - Calculator. The statement is nearly the same as 1746B - Rebellion, but the solution is quite different.

I proposed this problem to UOI, but it wasn't used. So, I proposed it on Codeforces. The initial version had only one subtask with $$$35$$$ operations. Then we decided to make two subtasks with $$$50$$$ and $$$31$$$ operations to make the contest more balanced.

First, I proposed $$$k = 0$$$ as an easy problem for a local competition. Then, I realized $$$k = 1$$$ (and $$$a_i \geq 2$$$) makes sense and I proposed it as div2B. Then we used the version with generic $$$k$$$.

During testing we underestimated the difficulty of this problem, but it ended up to be quite tricky for many people.

I came up with this problem by playing Tanto Cuore and misunderstanding the rules. Only some time later I realized the solution can be optimized using a bitset. I was not sure about making the constraints bigger (and let only the bitset solution pass), but we decided to use this version mainly because a smaller $$$n$$$ could have spoiled that the intended solution is DP.

Yet another standard problem, but it was used in a practice OI contest, so it doesn't matter.

Inspired by arc122_c - Calculator. First, I found a solution with $$$1000$$$ operations, but someone told me the problem can be solved in $$$300$$$ operations :D

My first problem! The solution is slightly annoying to write, and maybe the problem would have been better if we used a matrix (with vertical edges) instead of a generic tree, but the other setters and the coordinator preferred the tree version.

It's one of my favorite problems, mainly because it's a "programming" problem (not a math problem) with an extremely short solution code. Inspired by 1144G - Two Merged Sequences: I gradually made changes to the statement until finding 1485F - Copy or Prefix Sum.

I proposed the problem with $$$t = 1$$$. While preparing the problem, I accidentally realized $$$t \leq 10^4$$$ makes the problem much harder.

Inspired by 1329B - Dreamoon Likes Sequences: I gradually made changes to the statement until finding cc NDANDANDOR - Non-decreasing AND and OR.

I was trying to calculate some expected values in an $$$n \times n$$$ grid with blocks. Suddenly I came up with 1854C - Expected Destruction and I realized you don't need to actually define the grid in the statement.

Yet another "count subarrays" problem. First, I came up with an $$$O(n \log n)$$$ solution. Then, a contestant found a different $$$O(n \log n)$$$ solution, and I realized it could become $$$O(n)$$$ by adding a few lines.

It's the only problem I know that uses this funny idea.

The statement was generated almost randomly, the solution is $$$O((n \log n)^{4/3})$$$.

Easy problem about Connected Components DP. Some contestants were able to invent Connected Components DP from scratch :D

Initially, I thought this problem was trivial and I tried to find harder variations. Later, tourist and Petr proved me wrong :D

The story of this problem is quite weird.

First, I overkilled 1787D - Game on Axis, using the random solution from JOI 2019 — Virus Experiment. Then I tried to invent a problem with the same trick.

My initial idea was

• There are a red tree and a blue tree. So, if an ancestor of a node is red (blue), the node itself is red (blue). Let's say nodes $$$1$$$ and $$$2$$$ are the roots of the red and the blue tree, respectively.
• You want to find red nodes.
• Intended solution: random shuffle the nodes, and for each node ask its ancestors in order, until you find one whose color is already known. So, you ask $$$O(n \log n)$$$ ancestors on average.

Then, I realized that asking the same problem on functional graphs instead of trees looked much better (and had a completely different solution). The coordinator found another solution that worked on any functional graph, not necessarily with $$$2$$$ components, so it turned out that removing the first line of the statement made the problem even better.

Anyway, I still wanted to make a problem where the intended solution uses the random shuffle, basically because it required $$$\approx n (\ln n + 1)$$$ queries (on average), while the other solutions required $$$\approx n (\log_2 n - 1)$$$ queries (always). I tried a lot of modifications, including giving additional points for increasing subsequences of queries, and giving points according to the best case instead of the worst case. Unfortunately, all these variants turned out to be nonsense and / or have unintended easy solutions.

I proposed this problem for Italian team selection test with $$$n \leq 2 \cdot 10^5$$$. While preparing the problem, I realized a linear solution that seemed wrong was in fact correct, so I could raise $$$n$$$ to $$$10^7$$$.

Inspired by 1842H - Tenzing and Random Real Numbers (which is the hardest problem I solved during a Codeforces contest). The coordinator lowered the solution complexity from $$$O(n^3)$$$ to $$$O(n^2 \log n)$$$.

I invented this problem (with $$$O(n \log n)$$$ operations) at 6 AM, a few hours before my algebra exam. During testing we realized you can solve the problem in $$$O(n)$$$ operations!

Initially, the tastiness was defined as $$$\min( \{ |a_i - a_{i+1}| \} )$$$ and the goal was to minimize the tastiness. The coordinator suggested the current version, which is more natural and has exactly the same solution.

Fun fact: according to CLIST, 1654A - Maximum Cake Tastiness is the 9th easiest problem on Codeforces.

I proposed the problem on a general graph (but I didn't have an efficient solution). Then, my teammates realized that the problem makes sense on a tree.

Our initial solution was very overkill, but later we realized there exists a simple solution using the diameter. Fun fact: this problem and 1294F - Three Paths on a Tree have a different statement, but their solution is exactly the same.

Initially, Codeforces Round 701 (Div. 2) didn't have this problem C. Fortunately, we decided to add it to make the contest more balanced (it turned out the old problem C has a rating of $$$2200$$$). Actually, I had proposed a slightly different statement, but the coordinator swapped some variables and made the current statement, which is better.

I invented this problem and donated it to a Codeforces round I tested, but in the meanwhile the same exact problem was proposed independently by other people on AtCoder, where it appeared first. Some people who tested the Codeforces round and took part in the AtCoder contest got AC just by copying my solution :D

It's basically "implement parallel binary search". The coordinator proposed the last subtask: "implement parallel square root decomposition".

I wanted to write a simple application of range DP. The actual solution is $$$O(n^3)$$$, but it can be made faster by using some heuristics and optimizations. Maybe this problem shouldn't exist.

My contribution to this problem is the last subtask. It was hard to convince organizers to use the last subtask (because "adding queries cannot make a problem better"), but contestants seemed to like it.

The original version didn't include weights (you had to find the sum of $$$d(1, n)$$$ over all unweighted trees), but it could be found on OEIS. The authors tried to change the solution formula by giving different weights to even and odd subtrees, and I found out a natural way to achieve it (i.e., the current statement).

I thought this would have made the problem just slightly more difficult (I estimated rating $$$1900$$$), but it turned out to be much harder.

This is one of my favorite problems.

I initially proposed the problem with $$$M \leq \frac{N}{2}$$$ and $$$O(1)$$$ queries, and you were also given the indices of the maximum / minimum subarray. Then, my teammates made the statement more natural and the problem became much more difficult and funny.

I had proposed "make the elements nonnegative in $$$5$$$ moves" with different types of moves. Then, the UOI organizers made the problem impossible (now, it requires a D&C of convex hulls).

First, I proposed the problem with $$$n \leq 2000$$$ and $$$m = 0$$$, and the intended solution was Connected Components DP. Then, the coordinator made the problem impossible (now, it requires generating functions and a differential equation).

Div. 1:

1. Radewoosh
2. cnnfls_csy
3. tourist
4. DearMargaret
5. Geothermal

Div. 2:

1. triple__a
2. challenger_2023
3. shadoush
4. 5af
5. VisenP

Div. 1 first solves:

• A1: feecIe6418
• A2: 998batrr
• B: tourist
• C: 244mhq
• D: cnnfls_csy
• E: VivaciousAubergine
• F: Benq (after the contest)

Div. 2 first solves:

• A: Azaml
• B: CristianoPenaldo
• C1: fsanitize-undefined
• C2: timreizin
• D: _Okkotsu
• E: jun40ju
• F: triple__a

What's the most efficient way to make the sad students happy?

In most cases, you can make $$$2$$$ sad students happy in $$$1$$$ move.

Let $$$s$$$ be the number of sad students at the beginning. The answer is $$$\lceil \frac{s}{2} \rceil$$$.

In one move, you can make at most $$$2$$$ sad students happy (because you can change the position of at most two students), so you need at least $$$\lceil \frac{s}{2} \rceil$$$ moves.

In fact, you can make everyone happy in exactly $$$\lceil \frac{s}{2} \rceil$$$ moves:

• while there are at least $$$2$$$ sad students, you can swap them and both of them will be happy;
• if there is exactly $$$1$$$ sad student left, you can swap it with any other student.

Complexity: $$$O(n)$$$

What's the answer if $$$n$$$ is odd?

Try to generalize Hint 1.

What's the answer if $$$n$$$ is not a multiple of $$$3$$$?

If the answer is not a multiple of $$$x$$$, the answer is $$$ \lt x$$$. If the answer is a multiple of $$$1, \dots, x$$$, the answer is $$$\geq x$$$.

Suppose you find a valid interval $$$[l, r]$$$. Note that the interval $$$[l, r]$$$ contains at least one multiple of $$$x$$$ for each $$$1 \leq x \leq r-l+1$$$ (you can find it out by looking at the values in $$$[l, r]$$$ modulo $$$x$$$). Then, the interval $$$[1, r-l+1]$$$ is also valid and has the same length.

So, it's enough to check intervals with $$$l = 1$$$, i.e., find the smallest $$$x$$$ that does not divide $$$n$$$. The answer is $$$x-1$$$.

Complexity: $$$O(\log(\max n))$$$

There are several solutions to the easy version. In any case, how to get $$$a_i \leq a_{i+1}$$$?

For example, you can try making $$$a_{i+1}$$$ bigger using a positive element.

What to do if all the elements are negative?

If all the elements are negative, you can win in $$$n-1$$$ moves.

If there is a positive element, you can try to make $$$a_1 \leq a_2$$$, then $$$a_2 \leq a_3$$$, etc.

Make a big positive element using moves $$$(i, i)$$$, then make $$$a_2$$$ bigger.

If all the elements are negative, you can make suffix sums (they are nondecreasing) with moves $$$(n-1, n), (n-2, n-1), \dots$$$

If there is at least one positive element $$$a_x$$$,

• make $$$a_x \gt 20$$$ using $$$5$$$ moves $$$(x, x)$$$;
• make $$$a_2$$$ the biggest element using $$$2$$$ moves $$$(2, x)$$$;
• make $$$a_3$$$ the biggest element using $$$2$$$ moves $$$(3, 2)$$$;
• ...

This strategy requires $$$5 + 2(n-1) \leq 43$$$ moves.

Complexity: $$$O(n)$$$

You can win in $$$n-1$$$ moves if all the elements are negative, but also if all the elements are positive.

Again, make a big positive / negative element, then use it to make everything positive / negative.

In how many moves can you either make everything positive or make everything negative?

Assume the positive elements are at least as many as the negative elements. Can you win in $$$34$$$ moves?

The bottleneck is making the big positive element. Is it always necessary? Can you find a better bound on the "best" number of moves?

If you either make everything positive or make everything negative, you can win in $$$n-1 \leq 19$$$ moves by making prefix sums or suffix sums, respectively. So, you have to reach one of these configurations in $$$12$$$ moves.

How to make everything positive? First, you create a big element with the maximum absolute value (this requires $$$x_1$$$ moves), then you add it to every negative element (this requires $$$x_2$$$ moves). $$$y_1$$$ and $$$y_2$$$ are defined similarly in the negative case.

So,

• one of $$$x_1$$$ and $$$y_1$$$ is $$$0$$$ (because the element with the maximum absolute value at the beginning is either positive or negative), and the other one is $$$\leq 5$$$ (because you can make $$$|a_i| \geq 32$$$ in $$$5$$$ moves);
• $$$x_2$$$ is the number of negative elements, $$$y_2$$$ is the number of positive elements. So, $$$x_2 + y_2 \leq n \leq 20$$$.

Therefore, you need additional $$$\min(x_1 + x_2, y_1 + y_2)$$$ moves. Since $$$x_1 + x_2 + y_1 + y_2 \leq 25$$$, $$$\min(x_1 + x_2, y_1 + y_2) \leq \lfloor \frac{25}{2} \rfloor = 12$$$, as we wanted. Now you can simulate the process in both cases (positive and negative), and choose one that requires $$$\leq 31$$$ moves in total.

Complexity: $$$O(n)$$$

The order of used cards doesn't matter. So, you can assume you always use the card on the top.

Suppose that you unlock $$$x$$$ cards in total. How many points can you get?

If you unlock $$$x$$$ cards, it means you end up making moves with the first $$$x$$$ cards. So, you know the total number of (cards + points) that you get.

If you unlock $$$x$$$ cards, the number of points is uniquely determined. It's convenient to assume that $$$x \leq 2n$$$ and the cards $$$n+1, \dots, 2n$$$ have value $$$0$$$.

Now you have to determine the unlockable prefixes of cards (i.e., the values of $$$x$$$ you can reach). It looks similar to knapsack.

You can optimize the solution using a bitset. Be careful not to use locked cards.

First, note that the order of used cards doesn't matter. If you use at least once a card that is not on the top on the deck, you can prove that using the cards in order (from the top) would give the same number of victory points.

Let's add $$$n$$$ cards with value $$$0$$$ at the end of the deck. Then, it's optimal to unlock $$$x \leq 2n$$$ cards, and use cards $$$1, \dots, x$$$, getting $$$a_1 + \dots + a_x - x + 1$$$ points.

Let's find the reachable $$$x$$$. Let $$$dp_i$$$ be a bitset that stores the reachable $$$x$$$ after using the first $$$i$$$ cards.

• Base case: $$$dp_{0,1} = 1$$$.

• Transitions: first, $$$dp_{i}$$$ |= $$$dp_{i-1}$$$ << $$$a_i$$$. If $$$dp_{i,i} = 1$$$, you can update the answer with $$$a_1 + \dots + a_i - i + 1$$$, but you can't unlock any other card, so you have to set $$$dp_{i,i} = 0$$$ before transitioning to $$$i+1$$$.

Complexity: $$$O(n^2/w)$$$

Consider $$$n$$$ blocks in positions $$$S_1, S_2, \dots, S_n$$$. After how much time does block $$$x$$$ disappear? It may be convenient to put a fake "static" block in position $$$m+1$$$.

Block $$$x$$$ disappears when it reaches block $$$x+1$$$. But what if block $$$x+1$$$ disappears before block $$$x$$$?

From the perspective of block $$$x$$$, it's convenient to assume that block $$$x+1$$$ never disappears: when it touches another block $$$y$$$, it's $$$y$$$ that disappears.

When you consider the pair of blocks $$$x, x+1$$$, the other blocks don't really matter, and you can use linearity of expectation to calculate the contribution of each pair independently.

A reasonable interpretation is given by considering an $$$(n+1) \times (m+1)$$$ grid, where the $$$i$$$-th row initially contains a block in column $$$S_i$$$. Then, you are calculating the expected time required for the blocks $$$1, \dots, m$$$ to have another block immediately below them (in the same column).

Blocks $$$x, x+1$$$ both move with probability $$$1/2$$$, unless block $$$x+1$$$ has reached position $$$m+1$$$.

$$$dp_{i,j} =$$$ expected number of moves of block $$$x$$$ before it disappears, if the block $$$x$$$ is in position $$$i$$$ and the block $$$x+1$$$ is in position $$$j$$$.

Consider an $$$(n+1) \times (m+1)$$$ grid, where the $$$i$$$-th row initially contains a block in column $$$S_i$$$, and row $$$n+1$$$ contains a block in column $$$m+1$$$.

• The set is empty if all the blocks are in column $$$m+1$$$; i.e., if every block has reached the block in the following row.
• Every "connected component" of blocks (except the last one) represents an element in the set. These components move equiprobably.

Let's calculate the expected time required for the block in row $$$x$$$ to "reach" the block in row $$$x+1$$$. If you consider a single pair of blocks, every block moves with probability $$$1/2$$$, unless block $$$x+1$$$ is in column $$$m+1$$$.

So, you can calculate $$$dp_{i,j} =$$$ expected number of moves of the block $$$x$$$ before it reaches the block $$$x+1$$$, if the block $$$x$$$ is in position $$$i$$$ and the block $$$x+1$$$ is in position $$$j$$$.

The base cases are $$$dp_{i,m+1} = (m+1)-i$$$ (because only the block $$$x$$$ can move) and $$$dp_{i,i} = 0$$$ (because block $$$x$$$ has already reached block $$$x+1$$$). In the other cases, $$$dp_{i,j} = ((dp_{i+1,j} + 1) + dp_{i,j+1})/2$$$.

By linearity of expectation, the answer is the sum of $$$dp_{S_i, S_{i+1}}$$$.

Complexity: $$$O(m^2)$$$

You can find any $$$a_i$$$ in $$$9$$$ queries.

Find the nodes in the cycle in the component with node $$$1$$$. What happens if you know the whole cycle?

Suppose you already know some nodes in the cycle. Can you find other nodes faster?

Can you "double" the number of nodes in the cycle?

The component with node $$$1$$$ contains a cycle. If you know the whole cycle (of length $$$x$$$), you can win in $$$n-x$$$ queries by asking for each node if it ends up in the cycle after $$$n$$$ moves.

You can get a node in the cycle in $$$9$$$ queries, doing a binary search on the $$$n$$$-th successor of node $$$1$$$.

How to find the rest of the cycle?

• First, find $$$k$$$ nodes in the cycle, doing a binary search on the successor of the last node found. These nodes make a set $$$C$$$.
• Then, check for each node if it's "sufficiently close" to $$$C$$$, by asking $$$(i, k, C)$$$. Now, you know either $$$2k$$$ nodes in the cycle, or the whole cycle.
• Repeat until you get the whole cycle.

If you choose $$$k = 63$$$, you spend at most $$$9 \cdot 63 + (500 - 63) + (500 - 126) + (500 - 252) + (500 - 252) = 1874$$$ queries.

Go for a randomized approach.

Many ones are useful.

Either you go for a greedy or for a backpack.

We describe a randomized solution that solves the problem for $$$m$$$ up to $$$10^{11}$$$ (and, with some additional care, may be able to solve also $$$m$$$ up to $$$10^{12}$$$). We decided to give the problem with the smaller constraint $$$m\le 10^{10}$$$ to make the problem more accessible and because there may be some rare cases below $$$10^{11}$$$ for which our solution is too slow (even though we could not find any). We don't know any provably correct solution, if you have one we would be curious to see it. We expect to see many different solutions for this problem.

Main idea: Choose suitably the values $$$a_1, a_2, \dots, a_h$$$ that belong to $$$[1,29]$$$ and then find $$$a_{h+1}, a_{h+2},\dots,a_k$$$ in $$$[31,60]$$$ by solving a backpack-like problem.

Let us describe more precisely the main idea. Assume that $$$a_1, a_2, \dots, a_h\le 30$$$ are fixed and they satisfy $$$a_1+a_2+\cdots+a_h \lt 60$$$. For any $$$s=0,1,2,\dots,29$$$, let $$$f(s)$$$ be the number of subsets $$$I\subseteq{1,2,\dots,h}$$$ so that $$$\sum_{i\in I}a_i=s$$$. If we can find some values $$$0\le s_1,s_2,\dots,s_{k-h}\le 29$$$ so that $$$f(s_1)+f(s_2)+\cdots+f(s_{k-h})=s$$$, then by setting $$$a_{h+i} = 60-s_i$$$ for $$$i=1,2,\dots, k-h$$$ we have found a valid solution to the problem.

There are two main difficulties:

• How can we find $$$s_1, s_2,\dots, s_{k-h}$$$?
• How should we choose $$$a_1, a_2,\dots, a_h$$$?

Since it is important to get a good intuitive understanding of the computational complexity of the algorithm, let us say now that we will choose $$$h\le 44$$$ and (accordingly) $$$k-h=16$$$. These values are flexible (the solution would still work with $$$h\le 45$$$ and $$$k-h=45$$$ for example). We will say something more about the choice of these values when we will describe how $$$a_1,a_2,\dots, a_h$$$ shall be chosen.

The backpack problem to find $$$s_1, s_2,\dots, s_{k-h}$$$.

The naive way to find $$$s_1,\dots, s_{k-h}$$$ would be to try all of them. There are $$$\binom{k-h + 29}{29}$$$ possible ways (up to order, which does not matter). Since $$$k-h=16$$$ this number is $$$\approx 2\cdot 10^{11}$$$ which is too much to fit in the time limit.

To speed up the process, we will do as follows. Partition randomly $$$A\cup B={0,1,\dots, 29}$$$ into two sets of size $$$15$$$. We iterate over all possible $$$s_1, s_2, \dots, s_{(k-h)/2}\in A$$$ and over all possible $$$s_{(k-h)/2+1},\dots, s_{k-h}\in B$$$ and check whether the sum of one choice from the first group and one choice from the second group yields the result. This is a standard optimization for the subset sum problem. What is its complexity? It can be implemented in linear time in the size of the two groups we have to iterate over, which have size $$$\binom{(k-h)/2+15}{15}\approx 5\cdot 10^5$$$. Notice that in this faster way we will not visit all the $$$\binom{k-h+29}{29}$$$ possible choices $$$s_1,s_2,\dots, s_{k-h}$$$ because we are assuming that exactly half of them belong to $$$A$$$ and exactly half of them belong to $$$B$$$. This is not a big deal because with sufficiently high probability we will find a solution in any case.

The choice of $$$a_1, a_2,\dots, a_{h}$$$.

It remains to decide how we should select $$$a_1, a_2, \dots, a_{h}$$$. The following choice works:

• Approximately the first $$$\log_2(m)$$$ values are set equal to $$$1$$$.
• Five additional values are chosen randomly from $$$[1, 6]$$$ so that the total sum stays below $$$60$$$.

One should repeat the whole process until a solution is found.

Some intuition on the construction. The choice of $$$a_1, \dots, a_{h}$$$ may seem arbitrary; let us try to justify it. The goal is to generate a set of values $$$f(0), f(1),\dots, f(29)$$$ that are simultaneously ``random enough'' and with size smaller but comparable to $$$m$$$. These two conditions are necessary to expect that the backpacking problem finds a solution with high enough probability.

If $$$a_1=a_2=\cdots=a_{h}=1$$$, then $$$f(s) = \binom{k-h}{s}$$$ and these numbers have size comparable to $$$m$$$ if $$$2^{h}$$$ is comparable to $$$m$$$. This observation explains why we start with approximately $$$\log_2(m)$$$ ones. The issue is that we need some flexibility in the process as we may need to repeat it many times, this flexibility is provided by the addition of some additional random elements which don't change the magnitude of the values $$$f(0), f(1), \dots, f(29)$$$ but that modify them as much as possible (if we added a large number it would not affect many $$$f(s)$$$ and thus it would not be very useful).

Solve the 2d version first.

The 4d version is not too different from the 2d one.

Find all the points such that the expected number of necessary moves is wrong.

The $$$2$$$-dimensional case.

Let us begin by cpnsidering the $$$2$$$-dimensional version of the problem. The solution to this simpler version provides the idea of the approach for the $$$4$$$-dimensional version.

We want to reach $$$(a, b)$$$. Can we do it with exactly $$$k$$$ moves? Two simple necessary conditions are:

• $$$|a|+|b|\le 1 + 2 + \cdots + k$$$,
• $$$a+b$$$ and $$$1 + 2 + \cdots + k$$$ shall have the same parity.

It turns out that this two conditions are also sufficient! One can prove it by induction on $$$k$$$ as follows. If $$$k=0$$$ or $$$k=1$$$ or $$$k=2$$$ the statement is simple, thus we may assume $$$k\ge 3$$$.

Without loss of generality we may assume $$$0\le a\le b$$$. If $$$|a|+|b-k| \le 1 + 2 + \cdots + k-1$$$, then the statement follows by inductive hypothesis. Assume by contradiction that such inequality is false. If $$$b\ge k$$$ then we have a contradiction because $$$|a|+|b-k| = |a|+|b|-k \le (1 + 2 + \cdots + k) - k$$$. Otherwise $$$b \lt k$$$ and the contradiction is $$$|a|+|b-k| = a + k-b \le k \le 1 + 2 + \cdots + k-1$$$.

Hence, we have shown:

Lemma 1: The point $$$(a, b)$$$ is reachable with exactly $$$k$$$ moves if and only if $$$|a|+|b| \le 1 + 2 + \cdots + k$$$ and $$$a+b$$$ has the same parity of $$$1+2+\cdots + k$$$.

The $$$4$$$-dimensional case.

One may expect statement analogous to the one of Lemma 1 to hold also when there are $$$4$$$ coordinates. It does not, but it almost does and this is the crucial idea of the solution. More precisely, the number of counter examples to such statement is rather small and we can find all of them. This is the intuition behind the following definition.

Definition: For $$$k\ge 0$$$, let $$$A_k$$$ be the set of points $$$(a, b, c, d)$$$ such that $$$|a|+|b|+|c|+|d|\le 1 + 2 + \cdots + k$$$ and $$$a+b+c+d$$$ has the same parity of $$$1 + 2 + \cdots + k$$$ but $$$(a, b, c, d)$$$ is not reachable with exactly $$$k$$$ moves.

As an immediate consequence of the definition, we have

Observation: The point $$$(a, b, c, d)$$$ is reachable with exactly $$$k$$$ moves if and only if $$$|a|+|b|+|c|+|d| \le 1 + 2 + \dots + k$$$ and $$$a+b+c+d$$$ has the same parity of $$$1+2+\cdots + k$$$ and $$$(a, b, c, d)\not\in A_k$$$.

Thanks to this observation, if one is able to efficiently find $$$A_k$$$ for all interesting values of $$$k$$$, then solving the problem is (comparatively) easy. The following lemma is our main tool for this purpose.

Lemma 2: Assume that $$$(a, b, c, d) \in A_k$$$ with $$$0\le a\le b\le c\le d$$$. Then, either $$$k\le 6$$$ or $$$(a, b, c, d - k) \in A_{k-1}$$$.

Proof: The strategy is the same adopted to show Lemma 1. In some sense, we are saying that the inductive step works also in dimension $$$4$$$, but the base cases don't.

If $$$|a|+|b|+|c|+|d-k|\le 1 + 2 + \cdots + k-1$$$, then it must be $$$(a, b, c, d-k)\in A_{k-1}$$$ because if $$$(a, b, c, d-k$$$ were reachable with $$$k-1$$$ moves then $$$(a, b, c, d)$$$ were reachable with $$$k$$$ and we know that this is not true.

Assume by contradiction that $$$|a|+|b|+|c|+|d-k| \gt 1 + 2 + \cdots + k-1$$$. If $$$d\ge k$$$ then we reach the contradiction $$$|a|+|b|+|c|+|d-k| = a+b+c+d-k \le (1 + 2 + \dots + k) - k$$$. Otherwise, $$$d \lt k$$$ and thus we reach the contradiction $$$|a|+|b|+|c|+|d-k| = a+b+c+k-d\le a+b+k\le 3k-2\le 1 + 2 + \dots + k-1$$$ (for $$$k\ge 7$$$).

We can now describe the solution. Assume that we know $$$A_{k-1}$$$. First of all, notice that it is then possible to determine in $$$O(1)$$$ whether a point belongs to $$$A_k$$$ or not. To generate a list of candidate elements for $$$A_k$$$ we proceed as follows:

• If $$$k\le 6$$$, we simply iterate over all points with $$$|a|+|b|+|c|+|d|\le 1 + 2 + \cdots + k$$$.
• Otherwise, we iterate over the points in $$$A_{k-1}$$$ and we consider as candidate elements for $$$A_k$$$ the points that can be obtained by changing the value of one coordinate by $$$k$$$.

Thanks to Lemma 2, we know that this process finds all the elements in $$$A_k$$$. Once $$$A_0, A_1, A_2, A_3,\dots$$$ are known, the problem boils down to a (relatively) simple counting argument that we skip.

One can verify that to handle correctly all points with coordinates up to $$$1000$$$ it is necessary to compute $$$A_k$$$ for $$$0\le k \le 62$$$.

One additional cheap trick is required to make $$$A_k$$$ sufficiently small and get a sufficiently fast solution. Given $$$(a, b, c, d)$$$, the instance of the problem is equivalent if we change the signs of the coordinates or we change the order of the coordinates. Hence we shall always ``normalize'' the point so that $$$0\le a \le b\le c\le d$$$. If we do this consistently everywhere in the process, the solution becomes an order of magnitude faster. In particular, this trick guarantees $$$|A_k|\le 5000$$$ for all $$$0\le k\le 62$$$.

Bonus question: Find an explicit closed form for the elements in $$$A_k$$$ for any $$$k$$$. (in this way one can solve the problem also with larger constraints on $$$A, B, C, D$$$; but it is tedious)