We'd like to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated!
2183A — Binary Array Game
If the sequence $$$a$$$ consists entirely of $1$s, what will Alice do?
Consider discussing the values of $$$a_1$$$ and $$$a_n$$$.
First, if the entire sequence consists of $$$1$$$ s, Alice wins immediately by operating on the whole sequence.
Note that the last operation must involve at least one of $$$a_1$$$ or $$$a_n$$$. We discuss based on the values of $$$a_1$$$ and $$$a_n$$$:
If $$$a_1 = 1$$$, then Alice can directly operate on the interval $$$[2,n]$$$ to win, because $$$a_{2 \sim n}$$$ must contain at least one $$$0$$$.
If $$$a_n = 1$$$, then Alice can directly operate on the interval $$$[1,n-1]$$$ to win, because $$$a_{1 \sim n-1}$$$ must contain at least one $$$0$$$.
If $$$a_1 = 0$$$ and $$$a_n = 0$$$, then operating on the entire sequence would certainly cause Alice to lose. This implies that Alice cannot operate on both $$$a_1$$$ and $$$a_n$$$ simultaneously. Therefore, after Alice's operation, there will still be at least one $$$0$$$ in the sequence $$$a$$$. Bob can then operate on the entire sequence to win. Hence, in this case, Bob wins.
Time complexity: $$$O(\sum n)$$$.
2183B — Yet Another MEX Problem
Considering that in the end only $$$k - 1$$$ numbers will remain, which numbers in an interval of length $$$k$$$ are invalid?
Consider the Pigeonhole Principle.
Since only $$$k - 1$$$ numbers will remain in the end, it is relatively easy to notice that for any interval of length $$$k$$$, numbers within this interval that are greater than or equal to $$$k-1$$$ or have duplicate values are invalid. One of these two types of numbers can be removed. Since there are only $$$k - 1$$$ numbers from $$$0$$$ to $$$k-2$$$, in any interval of length $$$k$$$, there must be at least one number that can be deleted. Therefore, the answer is $$$\min(\text{mex}(a), k-1)$$$.
Time complexity: $$$O(\sum n)$$$.
2183C — War Strategy
Consider a greedy algorithm.
What shape must the finally occupied bases take?
If the capital is the first city (i.e., $$$k=1$$$), how to solve it?
The finally occupied bases must form an interval containing $$$k$$$.
If the finally occupied bases do not form an interval containing $$$k$$$, then there must exist some $$$x, y$$$ such that $$$1 \le x \lt y \lt k$$$ or $$$k \lt y \lt x \le n$$$, with $$$x$$$ occupied and $$$y$$$ unoccupied. Consider a soldier at $$$y$$$ starting from $$$k$$$ and moving to $$$x$$$; it must pass through base $$$x$$$ along the way. Consider making this soldier stop exactly at $$$x$$$. Then soldier $$$y$$$ ends up at $$$x$$$. After a finite number of such adjustments, we will reach a state where no further adjustment is possible, which implies the finally occupied bases must be an interval containing $$$k$$$.
Suppose this interval contains $$$a$$$ positions to the left of $$$k$$$ and $$$b$$$ positions to the right of $$$k$$$ (excluding $$$k$$$ itself) ($$$0 \le a \le k-1$$$, $$$0 \le b \le n-k$$$). It is possible to occupy this interval if and only if $$$a + b + \max{a, b} - 1 \le m$$$.
Sufficiency:
We can imagine a simple strategy. Initially, we do nothing until the capital contains $$$a$$$ soldiers. Then we move $$$a$$$ soldiers from $$$k$$$ to $$$k-1$$$, then move $$$a-1$$$ soldiers from $$$k-1$$$ to $$$k-2$$$, and so on. Thus $$$k-1, k-2, \ldots, k-a$$$ are all filled with soldiers. Then we wait (if necessary) until the capital contains $$$b$$$ soldiers and move them in the same way to $$$k+1, \ldots, k+b$$$. It can be observed that this strategy requires exactly $$$a + b + \max{a, b} - 1$$$ days.
Necessity:
We prove that for any strategy, the required number of days $$$m$$$ is at least $$$a + b + \max{a, b} - 1$$$.
First, we need at least $$$a+b$$$ days to obtain the extra $$$a+b$$$ soldiers. Second, we cannot move new soldiers to new bases every moment. In fact, we can prove that there are at least $$$\max{a, b} - 1$$$ idle days. The proof is as follows.
Assume without loss of generality that $$$a \ge b$$$.
Define the potential function $$$h(S)$$$ of a state $$$S$$$ as the number of soldiers minus the number of occupied bases.
Suppose the first move to the left is moving $$$t$$$ soldiers to the leftmost consecutive $$$t$$$ positions $$$k-a, \ldots, k-a+t-1$$$.
(If the move is not to the leftmost positions but to some intermediate positions, we can show through adjustment that such a move is suboptimal. Therefore, an optimal solution will not contain such moves.)
Let $$$S_0$$$ be the state before the move, $$$S_1$$$ be the state when moving $$$t$$$ soldiers to $$$k-a+t$$$, $$$S_2$$$ be the state after completing the move of all $$$t$$$ soldiers, and $$$S_3$$$ be the final state.
We have $$$h(S_2) = h(S_1)$$$, $$$h(S_3) \ge h(S_2)$$$.
$$$h(S_1) - h(S_0) \ge a - t$$$ (during the intermediate $$$a-t$$$ steps, the potential increases each time).
$$$h(S_0) \ge t - 1$$$ (at least $$$t$$$ movable soldiers are needed).
Summing up, we get $$$h(S_3) \ge a - 1$$$. Therefore, the number of days needed is at least $$$2a + b - 1$$$.
In summary, at least $$$a + b + \max{a, b} - 1$$$ days are required.
We consider a greedy approach. First, if $$$k-1 \lt n-k$$$, we replace $$$k$$$ with $$$n+1-k$$$.
We define two variables $$$a$$$ and $$$b$$$, representing how many cells have been extended to the left and right, respectively. Initially, $$$a = 0$$$, $$$b = 0$$$. Then we repeatedly try to increase $$$a$$$ and $$$b$$$ by $$$1$$$ in turns. We first try to increase $$$b$$$ by $$$1$$$ (if $$$b \lt n-k$$$ and $$$a + (b+1) + \max{a, b+1} - 1 \le m$$$), then set $$$b$$$ to $$$b+1$$$. Next, we try to increase $$$a$$$ by $$$1$$$ (if $$$a \lt k-1$$$ and $$$(a+1) + b + \max{a+1, b} - 1 \le m$$$). If we cannot increase $$$a$$$, we break the loop. Finally, $$$a + b + 1$$$ (don't forget the capital) is the answer. The time complexity is $$$O(n)$$$.
Solve the problem in $$$O(1)$$$ time per test case.
2183D1 — Tree Coloring (Easy Version)
Consider which points cannot be colored in the same operation.
Find a lower bound for the number of operations.
Suppose the number of points at depth $$$i$$$ is $$$t_i$$$. First, points at the same depth cannot be colored simultaneously, so the lower bound for the answer is $$$\max t_i$$$.
However, note that if points in layer $$$x$$$ share a common parent, they and their parent also cannot be colored simultaneously. Thus, the answer must also be compared with $$$\max(t_x + 1)$$$.
We claim this is the answer. Proof follows from the constructive proof in D2.
2183D2 — Tree Coloring (Hard Version)
When can the minimum number of operations reach $$$\max t_i$$$? How much more than $$$\max t_i$$$ can it be at most?
We claim the maximum number of operations is $$$\max t_i + 1$$$. Consider the following constructive proof.
Let $$$S_i$$$ denote the set of points for the $i$th operation.
Without loss of generality, let $$$T=\max t_i$$$. Find the largest $$$x$$$ such that $$$t_x=T$$$. Clearly, points with $$$d_i=x$$$ cannot be operated on simultaneously; we can place them into $$$S_1, S_2, \cdots, S_T$$$ respectively.
Then we only need to consider placing points of depth $$$\neq x$$$ into $$$S$$$. First, consider points of depth $$$ \gt x$$$. Suppose we have already placed all points of depth $$$k-1$$$. Now, when placing points of depth $$$k$$$, it is clear that each $$$S_i$$$ can contain at most one point of depth $$$k-1$$$.
Now, $$$t_{k-1}$$$ sets contain points of depth $$$k-1$$$, which impose constraints on the depth $$$k$$$ points to be placed; The remaining $$$T-t_{k-1}$$$ sets contain no points of depth $$$k-1$$$ and can freely add any point of depth $$$k$$$ (see the diagram below, where the upper red dots represent sets containing points of depth $$$k-1$$$, and the blue dots represent sets without such points).
\includegraphics{D.png}
For restricted sets (where children cannot be placed), we can retain only one child and place the others into unrestricted sets. Since the number of points in the lower layer is strictly less than $$$T$$$, at least one unrestricted set will remain. At this point, we can place each retained child into the set to its right.
Next, we construct the point of depth $$$ \lt x$$$. Suppose we have already constructed the point of depth $$$k+1$$$. Now we need to place the point of depth $$$k$$$ into a set. Clearly, there are $$$t_{k+1}$$$ sets with restrictions. Assume the current number of sets is $$$a = T$$$ or $$$T + 1$$$. The number of unrestricted sets is $$$c = a - t_{k+1}$$$. We proceed with some case analysis:
- $$$a=T$$$ and $$$c=0$$$: All points at depth $$$k+1$$$ share a common parent.
This parent cannot be placed into any set. We set $$$a$$$ to $$$T+1$$$, place the parent into this new set, and assign the remaining points arbitrarily.
- Points at depth $$$k$$$ have at least two non-leaf neighbors.
We can rotate these fathers into their children's sets, placing the remaining unrestricted nodes arbitrarily.
- A node at depth $$$k$$$ has exactly one non-leaf child, and at least one set lacks any node at depth $$$k+1$$$.
Place this father into the set lacking a node at depth $$$k+1$$$, then place the remaining nodes arbitrarily.
The above process constructs a solution with either $$$T$$$ or $$$T+1$$$ sets. It yields $$$T+1$$$ sets precisely when there are $$$T$$$ points at the same depth with the same parent, making this process clearly optimal. These sets can be maintained in $$$O(n)$$$ or $$$O(n\log n)$$$ time.
Some bottom-up, directly greedy approaches are also valid, but their complexity is generally $$$O(n\log n)$$$.
2183E — LCM is Legendary Counting Master
Consider the term $$$\frac{1}{\operatorname{lcm}(a_i,a_{i+1})}$$$. What properties can you derive if $$$a_i \lt a_{i+1}$$$?
Recall that $$$\frac{1}{\operatorname{lcm}(a_i,a_{i+1})} = \frac{\gcd(a_i,a_{i+1})}{a_i a_{i+1}}$$$. Notice that when $$$a_i \lt a_{i+1}$$$, the inequality $$$\gcd(a_i,a_{i+1}) \le a_{i+1}-a_i$$$ always holds.
You might have bounded the sum of the first $$$n-1$$$ terms. Try comparing the term $$$\frac{a_n-a_1}{a_1 a_n}$$$ (from the telescoping sum) with the last term $$$\frac{a_1}{a_1 a_n}$$$.
If $$$y \gt x$$$ and $$$\gcd(x,y)=y-x$$$, what does this imply about the relationship between $$$x$$$ and $$$y$$$? How many such pairs $$$(x,y)$$$ exist for $$$1\le x \lt y \le m$$$?
Note that
The equality holds if and only if $$$\gcd(a_i,a_{i+1})=a_{i+1}-a_i$$$ for all $$$1\le i \lt n$$$, and $$$a_1=1$$$. Thus, the problem is transformed into counting the number of sequences that satisfy these conditions.
The condition $$$\gcd(x,y)=y-x$$$ implies that $$$y-x$$$ is a divisor of $$$x$$$. In other words, there exists a divisor $$$d$$$ of $$$x$$$ such that $$$y=x+d$$$. Therefore, the total number of such valid pairs $$$(x,y)$$$ is only $$$\mathcal O(m \ln m)$$$. Consequently, we can easily obtain the answer using dynamic programming with a time complexity of $$$O(nm\ln m)$$$.
2183F — Jumping Man
Calculating the sum of squares of counts is difficult.
Calculating the sum of squares of counts is difficult, so we consider transforming it into the number of ways to choose two identical strings.
Try dynamic programming.
The transfer is continuous over the dfn sequence.
Calculating the sum of squares of counts is difficult, so we consider transforming it into the number of ways to choose two identical strings.
Let $$$f_{i,j}$$$ represent the number of ways to choose two strings located at nodes $$$i$$$ and $$$j$$$, respectively, within their subtrees. Clearly, $$$f_{i,j}$$$ has a non-zero value only if $$$c_i = c_j$$$, where $$$c$$$ denotes the string sequence.
Then, $$$f_{p,q}$$$ contributes to $$$f_{i,j}$$$ if and only if $$$p$$$ is in the subtree of $$$i$$$ and $$$q$$$ is in the subtree of $$$j$$$. By performing a depth-first search (DFS) on the tree and marking timestamps, the $$$(dfn_p, dfn_q)$$$ pairs of contributing $$$f_{p,q}$$$ must form a rectangle. Sorting by $$$dfn$$$ and computing suffix sums suffices.
The time complexity is $$$O(n^2)$$$.
2183G — Snake Instructions
Consider under what circumstances you need to return $$$-1$$$.
When there are three consecutive snakes with speeds $$$0, x, 0$$$, we cannot determine whether $$$x$$$ is $$$1$$$ or $$$2$$$, so we need to return $$$-1$$$ in this case. In all other situations, it's easy to have a scheme that uniquely determines all snakes' speeds.
Consider what information you can get by querying the string L.
The case analysis process for this problem is not complicated.
Consider querying three fixed strings to determine all snakes' speeds.
Consider querying the three strings: L, LR, and R.
It can be observed that the sizes of the sets returned from querying L and LR are the same. The specific proof states that after querying LR, the positions of the surviving snakes are exactly their initial positions. Since the relative order of the snakes remains unchanged, performing operation R after operation L will definitely not cause any two snakes to collide. Therefore, the sizes of the returned sets are the same.
By establishing a one-to-one correspondence with the initial coordinates, we can easily deduce the speeds of all snakes that survive after performing operation L.
At this point, we only lack the speeds of the snakes that died after performing operation L. A simple case analysis reveals the following scenarios (the first number on the right represents the speed of the snake that died after operation L, and _ indicates that there is no snake at that initial position):
01.02.0_2.12.
We can directly solve the problem by classifying these cases, but the implementation might be somewhat cumbersome. Therefore, let's consider a more concise approach to the case analysis.
First, try to determine some snakes with speed $$$2$$$. For the position and speed of such a snake, the following cases allow direct determination:
- The previous snake is at a distance of $$$1$$$ and has been determined to have speed $$$1$$$.
- The previous snake is at a distance of $$$1$$$ and has not been determined. Let's explain why this snake's speed is certain in this case:
- If the previous snake's speed is $$$0$$$, it will definitely not be killed in a collision, so this case is impossible.
- If the previous snake's speed is at least $$$1$$$, then this snake must have a speed of at least $$$2$$$ to catch up and collide with the previous snake. Therefore, this snake's speed is at least $$$2$$$.
- The previous snake is at a distance of $$$2$$$ and has been determined to have speed $0`.
The case analysis above naturally eliminates the 0_2 and 12 scenarios.
Now, only the 01 and 02 cases remain. It can be observed that only the patterns 010 and 020 are indistinguishable. Therefore, we can initially ignore this situation: first find one valid solution, and then check if this solution contains such an indistinguishable pattern.
Otherwise, since the snake immediately after this one must have a speed of at least $$$1$$$ (under the condition of a unique solution), the position this snake would reach if it moved ignoring obstacles is exactly the position of the first snake whose position is $$$\ge$$$ this snake's position after performing the R query. If this snake does not come into contact with any other snake while moving right, its position can also be directly determined. Therefore, we can directly deduce the speeds of all snakes using this method.
Time complexity: $$$O(\sum n)$$$ or $$$O(\sum n \log n)$$$.
