How much does the number decrease when we remove two consecutive $$$3$$$ s?

2048A - Kevin and Combination Lock

When we transform $$$\overline{x33y}$$$ into $$$\overline{xy}$$$ (where $$$x$$$ and $$$y$$$ are decimal numbers), the actual value changes from $$$10^{p+2} \cdot x + 33 \cdot 10^p + y$$$ to $$$10^p \cdot x + y$$$. The decrease is $$$99 \cdot 10^p \cdot x + 33 \cdot 10^p$$$. It is easy to see that $$$33 \mid (99 \cdot 10^p \cdot x + 33 \cdot 10^p)$$$. Therefore, we can replace the operation of removing two consecutive $$$3$$$ s with a series of $$$-33$$$ operations.

Hence, we only need to determine whether $$$x$$$ can be reduced to $$$0$$$ using a series of $$$-33$$$ operations, which is equivalent to checking whether $$$x \bmod 33$$$ equals zero.

If the permutation is sufficiently long, what is the maximum number of length $$$k$$$ subintervals where the minimum value is $$$1$$$?

2048B - Kevin and Permutation

In the entire permutation, at most $$$k$$$ subintervals can contain $$$1$$$. Similarly, at most $$$k$$$ subintervals can contain $$$2, 3, \ldots$$$. To maximize the number of subintervals where the minimum value is as small as possible, we use the following construction:

For the remaining positions, we can fill them arbitrarily with all values from $$$\lfloor \frac{n}{k} \rfloor + 1$$$ to $$$n$$$. It is easy to prove that this construction minimizes the answer.

Is there a substring that must always be selected for all strings?

The substring $$$[1,n]$$$ must be selected. Can we determine the length of the other substring?

Pay special attention to the case where the entire string consists of only $$$1$$$ s.

2048C - Kevin and Binary Strings

To maximize the XOR sum of the two substrings, we aim to maximize the number of binary digits in the XOR result. To achieve this, the substring $$$[1,n]$$$ must always be selected. Suppose the first character of the other substring is $$$1$$$. If it is not $$$1$$$, we can remove all leading zeros.

Next, find the position of the first $$$0$$$ in the string from left to right. We want this position to be flipped to $$$1$$$, while ensuring that the $$$1$$$s earlier in the string are not changed to $$$0$$$s. Therefore, let the position of the first $$$0$$$ be $$$p$$$. The length of the other substring must be $$$n-p+1$$$. By enumerating the starting position of the other substring and calculating the XOR sum of the two substrings linearly, we can take the maximum value. The time complexity of this approach is $$$O(n^2)$$$.

If the entire string consists only of $$$1$$$s, selecting $$$[1,n]$$$ and $$$[1,1]$$$ can be proven to yield the maximum XOR sum among all possible choices.

Interesting fact: This problem can actually be solved in $$$O(n)$$$ time complexity. Specifically, observe that the other substring needs to satisfy the following conditions: its length is $$$n-p+1$$$, and its first character is $$$1$$$. Thus, its starting position must be less than $$$p$$$. This implies that the length of the prefix of $$$1$$$s in the other substring can be chosen from the range $$$[1, p-1]$$$. We aim to flip the first segment of $$$0$$$ s in the original string to $$$1$$$ s, while ensuring that the $$$1$$$ immediately after this segment of $$$0$$$ s remains unchanged. Let the length of the first segment of $$$0$$$ s be $$$q$$$. Then, the length of the prefix of $$$1$$$ s in the other substring must be $$$\min(p-1, q)$$$, and the starting position can be determined efficiently.

When preparing the contest and selecting problems, we determined that the $$$O(n)$$$ solution would be too difficult for a Problem C. Therefore, the problem was designed with an $$$O(n^2)$$$ data range to make it more accessible.

You can ignore all contestants with a rating lower than yours; this does not affect the answer.

You are the contestant with the lowest rating, so any problem you can solve can also be solved by everyone else. Thus, your ranking in a competition only depends on the easiest problem you cannot solve.

Use greedy algorithm.

2048D - Kevin and Competition Memories

Read all the hints.

First, remove all contestants with a rating lower than yours, making you the contestant with the lowest rating. Since any problem you can solve can also be solved by everyone else, this does not affect your ranking. These problems can effectively be treated as having infinite difficulty.

At this point, you cannot solve any problem, so your ranking in a competition is given by $$$(1 + $$$ the number of contestants who solve at least one problem in that competition $$$)$$$. Therefore, we only need to focus on the easiest problem in each competition.

Precompute, for each problem, the number of contestants who can solve it, denoted as $$$c_i$$$. This can be done by sorting the contestants by rating and the problems by difficulty, then using a two-pointer or binary search approach to compute $$$c_i$$$.

The remaining task is: given $$$c_i$$$, divide all $$$c_i$$$ into $$$\lfloor \frac{n}{k} \rfloor$$$ groups, each containing $$$k$$$ elements, and minimize the sum of the maximum values in each group. This can be solved using a greedy algorithm: sort $$$c_i$$$ in ascending order, and for a given $$$k$$$, the answer is $$$(c_k+1) + (c_{2k}+1) + \dots$$$. The brute force calculation is bounded by the harmonic series, and combined with sorting, the time complexity is $$$O(n \log n + m \log m)$$$.

It can be observed that the larger $$$m$$$ is, the harder it is to satisfy the conditions. Try to find an upper bound for $$$m$$$.

2048E - Kevin and Bipartite Graph

The graph has a total of $$$2nm$$$ edges, and each color forms a forest. Therefore, for any given color, there are at most $$$2n + m - 1$$$ edges. Thus, the total number of edges cannot exceed $$$(2n + m - 1)n$$$. This gives the condition: $$$(2n+m-1)n\ge 2nm$$$. Simplifying, we find $$$m \leq 2n - 1$$$.

Next, we only need to construct a valid case for $$$m = 2n - 1$$$ to solve the problem.

In fact, this is easy to construct. Since each right-side vertex has a degree of $$$2n$$$, and there are $$$n$$$ total colors, let each color have exactly $$$2$$$ edges. For any given color, this is equivalent to choosing two left-side vertices to connect (ignoring the existence of the right-side vertices). After $$$2n - 1$$$ connections, the left-side vertices need to form a tree. It turns out that connecting the left-side vertices into a chain suffices. During construction, we can cycle the colors of the first right-side vertex. For example, for $$$n = 4$$$ and $$$m = 7$$$, the result looks like this:

1 4 4 3 3 2 2
1 1 4 4 3 3 2
2 1 1 4 4 3 3
2 2 1 1 4 4 3
3 2 2 1 1 4 4
3 3 2 2 1 1 4
4 3 3 2 2 1 1
4 4 3 3 2 2 1

Thus, a simple construction method is as follows: for left-side vertex $$$i$$$ and right-side vertex $$$j$$$, the color of the edge connecting them is given by:

Can you find a strategy such that only $$$n$$$ intervals might be operated on?

By operating on the entire sequence in each step, the answer can be made $$$\leq 63$$$.

2048F - Kevin and Math Class

Construct a min Cartesian tree for the sequence $$$b$$$. It is easy to observe that we will only operate on the intervals defined by this Cartesian tree.

• Proof: For any $$$b_x$$$, find the last $$$b_p \leq b_x$$$ on its left and the first $$$b_q < b_x$$$ on its right. If we want to divide the interval by $$$b_x$$$, the operation interval cannot include both $$$p$$$ and $$$q$$$. At the same time, choosing the largest possible interval is always optimal. Hence, the operation interval must be $$$[p+1, q-1]$$$. All such intervals are exactly the intervals corresponding to the Cartesian tree.

To solve the problem, we can use DP on the Cartesian tree. Let $$$f_{u,i}$$$ represent the minimum possible maximum value of $$$a_x$$$ within the subtree rooted at $$$u$$$ after performing $$$i$$$ operations on all positions within that subtree.

When merging, suppose the two child subtrees of $$$u$$$ are $$$ls$$$ and $$$rs$$$. The transition can be written as:

Then consider division at the position corresponding to $$$b_u$$$, which updates the DP state:

Since operating on the entire sequence repeatedly can ensure that $$$\log_2(\max(a_i)) \leq 63$$$ operations suffice, the second dimension of the DP state only needs to be defined for $$$0 \sim 63$$$. Thus, the time complexity for this approach is $$$O(n \log^2 a)$$$.

The bottleneck of this approach lies in merging the DP states of the two subtrees. Observing that $$$f_{u,i}$$$ is monotonically non-increasing, the $$$\min-\max$$$ convolution for $$$f_{ls,i}$$$ and $$$f_{rs,i}$$$ is equivalent to merging two sequences using a merge sort-like approach. This reduces the merging complexity to $$$O(\log a)$$$.

Consequently, the overall complexity becomes $$$O(n \log a)$$$, which is an optimal solution.

Can the left-hand side be less than the right-hand side?

Consider the positions where the extremes are reached in the expression. What properties do they have?

Use the principle of inclusion-exclusion.

Apply the Binomial Theorem.

2048G - Kevin and Matrices

Let us assume the left-hand side attains its maximum at position $$$L$$$, and the right-hand side attains its maximum at position $$$R$$$.

For any $$$L, R$$$, let $$$P$$$ be the position in the same row as $$$L$$$ and the same column as $$$R$$$. Then we have $$$a_L \geq a_P \geq a_R$$$, which implies $$$a_L \geq a_R$$$. Hence, we only need to consider cases where $$$a_L = a_R$$$.

Now, consider positions where both sides attain their maximum value, denoted as $$$S$$$. Positions in $$$S$$$ are the maximum in their respective column and the minimum in their respective row. For any two positions $$$P, Q$$$ in $$$S$$$ that are not in the same row or column, we can observe that the positions in the same row as $$$P$$$ and the same column as $$$Q$$$, and vice versa, can also attain the maximum value. By induction, we can conclude that $$$S$$$ forms a subrectangle.

Next, enumerate the maximum value $$$k$$$ and the size of $$$S$$$, denoted by $$$i \times j$$$. The constraints are as follows: all remaining elements in the rows of $$$S$$$ must be $$$\leq k$$$, and all remaining elements in the columns of $$$S$$$ must be $$$\geq k$$$. Using the principle of inclusion-exclusion, we derive:

The naive approach is $$$O(nmv)$$$, which is computationally expensive. Let us simplify:

This resembles the Binomial Theorem. To simplify further, add and subtract the term for $$$j=0$$$:

Thus, the problem can be solved in $$$O(nv\log m)$$$ time.

Consider how to determine if the $$$01$$$ string $$$t$$$ can be generated.

Try designing a DP that only records the useful variables.

Optimize using data structures or improve the complexity of the transitions.

2048H - Kevin and Strange Operation

Assume that after performing several operations on the $$$01$$$ string $$$s$$$, we get the $$$01$$$ string $$$t$$$. It’s not hard to notice that each element in $$$t$$$ corresponds to the $$$\max$$$ of a subset of elements from $$$s$$$. Further observation shows that this subset must form a continuous segment, so we can express $$$t_i$$$ as $$$\max\limits_{k=l_i}^{r_i} s_k$$$.

Initially, $$$t = s$$$, so all $$$l_i = r_i = i$$$. Suppose the current length of string $$$t$$$ is $$$m$$$, corresponding to two sequences $$$l$$$ and $$$r$$$. If an operation is performed at position $$$p$$$ where $$$1 \le p \le m$$$, the new sequence $$$t'$$$ will correspond to two sequences $$$l'$$$ and $$$r'$$$. Then, since for $$$1 \le i < p$$$, we have $$$t'_i=\max(t_i,t_{i+1})$$$, and for $$$p \le i < m$$$, $$$t'_i=t_{i+1}$$$, it can be observed that for $$$1 \le i < p$$$, we have $$$l'_i=l_i,r'_i=r_{i+1}$$$, and for $$$p \le i < m$$$, $$$l'_i=l_{i+1},r'_i=r_{i+1}$$$. If we only focus on the change of sequences $$$l$$$ and $$$r$$$ to $$$l'$$$ and $$$r'$$$, it is equivalent to deleting the values $$$l_p$$$ and $$$r_1$$$.

Thus, performing $$$k$$$ operations starting from the sequence $$$s$$$, the resulting sequence $$$t$$$ will correspond to the sequences $$$l$$$ and $$$r$$$, where $$$l$$$ is obtained by deleting any $$$k$$$ values from $$$1$$$ to $$$n$$$, and $$$r$$$ is the sequence from $$$k+1$$$ to $$$n$$$.

Now, let's consider how to determine if the $$$01$$$ string $$$t$$$ can be generated. By reversing $$$t$$$ to get $$$t'$$$, the task becomes finding $$$n \ge p_1 > p_2 > \dots > p_k \ge 1$$$ such that for all $$$1 \le i \le k$$$, we have $$$t'_i=\max\limits_{k=p_i}^{n-i+1}s_k$$$. A clearly correct greedy strategy is to choose $$$p_i$$$ in the order $$$i=1 \sim k$$$, always selecting the largest possible value.

Now consider performing DP. Let $$$dp_{i,j}$$$ represent how many length-$$$i$$$ $$$01$$$ strings $$$t$$$ can be generated such that after running the above greedy algorithm, $$$p_i$$$ exactly equals $$$j$$$. We assume that $$$p_0 = n+1$$$ and the boundary condition is $$$dp_{0,n+1} = 1$$$. We now consider the transition from $$$dp_{i-1,j}$$$ to $$$dp_{i,*}$$$:

• If $$$s[j-1, n-i+1]$$$ already contains $$$1$$$, then the $$$i$$$-th position in the reversed $$$t$$$ must be $$$1$$$, and it must be the case that $$$p_i = j-1$$$, so we add $$$dp_{i,j-1}$$$ to $$$dp_{i-1,j}$$$.
• If $$$s[j-1, n-i+1]$$$ does not contain $$$1$$$, the $$$i$$$-th position in the reversed $$$t$$$ can be $$$0$$$. If it is $$$0$$$, then it must be the case that $$$p_i = j-1$$$, and we add $$$dp_{i,j-1}$$$ to $$$dp_{i-1,j}$$$; if we want the $$$i$$$-th position in the reversed $$$t$$$ to be $$$1$$$, we need to find the largest $$$pos \le n-i+1$$$ such that $$$s_{pos} = 1$$$, and then set $$$p_i = pos$$$, adding $$$dp_{i,pos}$$$ to $$$dp_{i-1,j}$$$.

Both types of transitions can be considered as adding $$$dp_{i,j-1}$$$ to $$$dp_{i-1,j}$$$, then finding the largest $$$pos \le n-i+1$$$ where $$$s_{pos} = 1$$$, and for all $$$j-1 > pos$$$ (i.e., $$$j \ge pos+2$$$), adding $$$dp_{i,pos}$$$ to $$$dp_{i,j}$$$.

The first type of transition can be viewed as a global shift of the DP array, while the second type requires calculating a segment suffix sum of the DP array and then performing a point update. This can be done efficiently using a segment tree in $$$O(n \log n)$$$ time for all transitions.

The final answer is the sum of all $$$1 \le i \le n, 1 \le j \le n$$$ of $$$dp_{i,j}$$$. Using a segment tree for maintenance, we can also query the sum of each entry of $$$dp_i$$$ in $$$O(1)$$$ time (by setting to zero those entries where $$$dp_{i-1,1}$$$ is out of range after the shift).

Since the transitions have better properties, it's actually possible to solve the problem cleverly using prefix sums in $$$O(n)$$$ time without needing complex data structures, but that is not strictly necessary.

Consider the leftmost and rightmost characters, and recursively construct the sequence.

2048I1 - Kevin and Puzzle (Easy Version)

Lemma: Suppose the largest value filled is $$$mx$$$, and the number of distinct values is $$$c$$$. Let $$$d = c - mx$$$. Then, $$$d = 0$$$ or $$$d = 1$$$.

Proof: Clearly, $$$c \le mx + 1$$$. If $$$c < mx$$$, observe where $$$mx$$$ is placed, and a contradiction arises.

Now, consider the leftmost and rightmost characters in sequence $$$s$$$:

• If they are L and R, we can see that both positions must be filled with $$$0$$$, and no other position can be filled with $$$0$$$. For internal positions, whether L or R, $$$0$$$ counts as a distinct number. Therefore, we can remove these two positions, recursively solve for the remaining part, add $$$1$$$ to all numbers, and then place a $$$0$$$ at both ends.
• If both are L, the leftmost L must be $$$0$$$. Suppose the rightmost L is filled with $$$x$$$. It is easy to prove that $$$x$$$ cannot be placed in internal positions. For internal positions, whether L or R, either $$$0$$$ or $$$x$$$ is counted as a distinct number. So, as in the previous case, we remove the two positions, recursively solve for the remaining part, add $$$1$$$ to all numbers, and then add $$$0$$$ and $$$x$$$ at both ends. The value of $$$x$$$ must be the number of distinct values inside plus 1. This condition is equivalent to the internal region satisfying $$$d = 1$$$.
• If both are R, the analysis is the same as for the L and L case.
• If the leftmost character is R and the rightmost character is L, a simple construction is to fill everything with $$$1$$$. In this case, no $$$0$$$ will appear, so this case can only correspond to $$$d = 0$$$.

We recursively remove the leftmost and rightmost characters, solve for the inner region, add $$$1$$$ to all of them, and place $$$0$$$ and $$$x$$$ at both ends.

Now, consider how $$$d$$$ changes:

• For the LR case, $$$d$$$ remains unchanged.
• For LL or RR, the internal region must satisfy $$$d = 1$$$.
• For RL, the entire region results in $$$d = 0$$$.

Therefore, consider the outermost RL. If it contains LL or RR inside, there is no solution.

Otherwise, a solution always exists, and it can be easily constructed based on the above process, the time complexity is $$$O(n)$$$.

Only the case where the characters on both sides are RL in the simple version needs to be counted. In fact, the numbers at these two positions, RL, must be the same.

Let the number at the RL positions be $$$m$$$, and enumerate the rightmost R position $$$x$$$ that is filled with $$$m$$$, and the leftmost L position $$$y$$$ that is filled with $$$m$$$.

The case where $$$x > y$$$ is easy to resolve. For the case where $$$x < y$$$, analyze the necessary and sufficient conditions for it to hold.

For the final transformed condition, use bitset or convolution to complete the counting.

2048I2 - Kevin and Puzzle (Hard Version)

According to the easy version, we can see that most cases have very few solutions because for LR, LL, and RR, after filling in the inner part, the outer layer only has one unique way to fill. Therefore, if there is no RL layer, the answer must be $$$1$$$.

Next, consider the case where RL is present. Let’s assume that RL is the outermost pair of characters.

It can be proved that the numbers at the R and L positions in this RL must be the same. The specific proof is omitted here, but readers can prove this for themselves easily.

Let this common value be $$$m$$$. Then, enumerate the rightmost R position $$$x$$$ filled with $$$m$$$ and the leftmost L position $$$y$$$ filled with $$$m$$$. Now, let’s discuss the relationship between $$$x$$$ and $$$y$$$:

• If $$$x > y$$$, it can be observed that all Ls to the right of $$$x$$$ must be filled with $$$m$$$, and all Rs to the right of $$$x$$$ have only one way to be filled. The same applies for $$$y$$$. For this case, we can directly enumerate $$$m$$$, then determine the unique positions for $$$x$$$ and $$$y$$$, and check if $$$x > y$$$.

• If $$$x < y$$$, at this point, all Rs to the left of $$$x$$$ must be filled with $$$m$$$, and the Ls to the left of $$$x$$$ have only one way to be filled. Similarly for the right side of $$$y$$$. Now, consider the section between $$$(x, y)$$$. Clearly, $$$m$$$ must not appear in the middle, so we can delete $$$x$$$ and all Rs to its left, as well as $$$y$$$ and all Ls to its right (i.e., remove all positions where the value is $$$m$$$). The resulting sequence is called the remaining sequence. After removing these characters, we solve for the remaining sequence, then add $$$1$$$ to all the numbers obtained, and finally, add all positions filled with $$$m$$$.
  Below is an example of an initial sequence, where the red characters are $$$x$$$ and $$$y$$$, and the omitted part is the section between $$$(x, y)$$$.
  
  Below is the corresponding remaining sequence, with $$$*$$$ representing the original sequence positions of $$$x$$$ and $$$y$$$.
  
  After filling the remaining sequence, we need to analyze the conditions for adding all positions filled with $$$m$$$: we divide the remaining sequence into three parts: "left", "middle", and "right", with the positions of $$$x$$$ and $$$y$$$ as boundaries, where the left part contains only Ls, and the right part contains only Rs. The condition to be satisfied is that let the total number of colors in the "left-middle" part be $$$c_1$$$, and the total number of colors in the "middle-right" part be $$$c_2$$$, then we need $$$m = c_1 + 1 = c_2 + 1$$$. Additionally, $$$m$$$ must not appear in the remaining sequence. This restriction is equivalent to requiring both the "left-middle" and "middle-right" parts to satisfy $$$d = 1$$$. It can be concluded that the remaining sequence satisfies $$$d = 1$$$. For the condition $$$c_1 = c_2$$$, it is easy to see that it is equivalent to: let $$$z$$$ be the larger of the counts of the left and right parts, then the first $$$z$$$ characters of the remaining sequence must all be L, and the last $$$z$$$ characters must all be R.
  The final necessary and sufficient condition is: let $$$x$$$ have $$$a$$$ Ls to the left, and $$$y$$$ have $$$b$$$ Rs to the right. Without loss of generality, assume $$$a \ge b$$$. Remove the substring between $$$(x, y)$$$ (not including $$$x$$$ and $$$y$$$). This remaining substring needs to satisfy that the last $$$a-b$$$ characters are Rs, and after removing these $$$a-b$$$ Rs, the resulting string must satisfy $$$d = 1$$$, meaning there is no RL situation when taking the first and last characters. Since $$$d = 1$$$, if the remaining sequence satisfies this condition, there will be exactly one way to fill it.

Finally, we only need to count the cases separately. The case where $$$x > y$$$ can be counted in $$$O(n)$$$, for the case where $$$x < y$$$, without loss of generality, assume $$$a \ge b$$$, we can enumerate $$$y$$$, calculate the length of the longest consecutive Rs before $$$y$$$, denoted as $$$cnt$$$, so the restriction on $$$a$$$ becomes $$$b \le a \le b + cnt$$$.

• When $$$cnt = 0$$$, the value of $$$a$$$ is fixed, but the corresponding $$$x$$$ can be chosen from any position in a consecutive block of Rs. We find that because $$$cnt = 0$$$, i.e., the position before $$$y$$$ is filled with L, then the position after $$$x$$$ cannot be filled with R, so $$$x$$$ can only be chosen as the last R in the consecutive R block.
• When $$$cnt > 0$$$, we only need to enumerate the values of $$$x$$$. It is easy to see that each $$$x$$$ will be counted at most $$$2$$$ times.

Through the above observations, we only need to enumerate $$$O(n)$$$ pairs of $$$x$$$ and $$$y$$$ and check whether they increase the answer by $$$1$$$. That is, the answer is at the $$$O(n)$$$ level.

The last problem is: for each given interval $$$[l, r]$$$, we need to check if there is any RL situation when taking the first and last characters of this string.

A simple solution is to use a bitset to maintain, for example, by scanning $$$r$$$ from small to large, and maintaining the existence of RL for each $$$l + r$$$. The time complexity of this approach is $$$O(\frac{n^2}{\omega})$$$, which can be handled by this problem.

If using block convolution, a more optimal complexity can be achieved. In fact, if further exploring the properties, the time complexity can be reduced to $$$O(n \log^2 n)$$$ (requiring convolution), which you can explore on your own if you are interested.