Thank you for participating in our round! We hope you enjoyed the problems. We are really sorry for the inconveniences caused by the English statement of problem B.
Idea: Fakewave
Note that maximizing the sum of numbers in the table is equivalent to maximizing the number of chosen pairs that specify a valid cell.
Without loss of generality, we assume that $$$h \leq l$$$. For any cell of the table $$$(x, y)$$$, $$$1 \leq x \leq h$$$, $$$1 \leq y \leq l$$$. Let $$$cnt_h$$$ be the number of elements in the array not exceeding $$$h$$$, and $$$cnt_l$$$ be the number of elements in the array not exceeding $$$l$$$. Then, firstly, the answer does not exceed $$$cnt_h$$$, since each pair must contain a number not exceeding $$$h$$$. Conversely, the answer does not exceed $$$\displaystyle \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$$$, since both numbers in each pair must not exceed $$$l$$$. It remains to be seen that $$$\displaystyle min(cnt_h, \Big\lfloor \frac{cnt_l}{2} \Big\rfloor)$$$ pairs can be obtained. To do this, let's consider two cases.
if $$$\displaystyle cnt_h \leq \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$$$, then it is sufficient to pair each number $$$x \leq h$$$ with its own number $$$h \lt y \leq l$$$, and there will be $$$cnt_h$$$ pairs. This can be done since there are at least as many suitable numbers $$$y$$$ as there are suitable $$$x$$$.
if $$$\displaystyle cnt_h \gt \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$$$, then we need to pair each number $$$h \lt y \leq l$$$ with its own number $$$x \leq h$$$. After this, split the remaining numbers $$$x \leq h$$$ into pairs (there may be one extra number left over). We'll get exactly $$$\displaystyle \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$$$ pairs.
Note that the problem is equivalent to minimizing the number of rollbacks to reach a point with a number $$$\geq x$$$. (Consider the moment when the frog first reached the point $$$\geq x$$$. Instead of a full jump, the frog could have jumped not the full distance, but exactly to the point $$$x$$$). We then assume that the frog always jumps $$$a_i$$$ units forward using the $$$i$$$-th type of jump.
First, the frog can use the $$$i$$$-th type of jump $$$b_i-1$$$ times without any rollbacks. Let $$$r$$$ be the number of units remaining to the number $$$x$$$ after these jumps (if $$$r \leq 0$$$, then $$$0$$$ rollbacks are required).
Now, any jump will cause a rollback. However, note that after one jump with rollback, if we used the $$$i$$$th type of jump, we can use the same jump $$$b_i-1$$$ more times without rollbacks. After that, we'll find ourselves in the same situation (any jump creates a rollback), but we have moved $$$a_ib_i-c_i$$$ units. Therefore, it's always worth using the jump with the maximum value of $$$a_ib_i-c_i$$$.
Let $$$m = \max(a_ib_i-c_i)$$$ over all $$$i$$$ from $$$1$$$ to $$$n$$$. Then, if $$$m \leq 0$$$, we can't move forward (as we first get a rollback of $$$c_i$$$, and only then move by $$$a_ib_i$$$), and the answer is $$$-1$$$. Otherwise, $$$\displaystyle \Big\lceil \frac{r}{m} \Big\rceil$$$ rollbacks will be required.
2189C1 - XOR Convenience (Easy Version)
Idea: Fakewave
2189C2 - XOR-convenience (Hard Version)
2189D1 - Little String (Easy Version)
Let's consider which permutations $$$p$$$ satisfy the condition of the string $$$w$$$. It is obvious that if $$$w_1 = \texttt{0}$$$ or $$$w_n = \texttt{0}$$$, there are no suitable $$$p$$$ (in any permutation, there is a subsegment with only the number $$$0$$$ and a subsegment with all numbers), so we will assume that $$$w_1 = w_n = \texttt{1}$$$. Let's construct $$$p$$$, starting with $$$p = [0]$$$ and sequentially inserting the numbers $$$1, 2, \ldots, n - 1$$$ into some positions.
Suppose we have placed the numbers $$$0, 1, \ldots, k - 1$$$ and are now going to insert the number $$$k$$$ relative to them. We have $$$k + 1$$$ options for where to insert it.
If we insert $$$k$$$ before all the numbers or after all the numbers, we can always choose all remaining numbers as a segment and get $$$\operatorname{mex} = k$$$ (note that inserting subsequent numbers will not affect the $$$\operatorname{mex}$$$ of this segment, since all subsequent values are $$$ \gt k$$$).
However, if we insert $$$k$$$ between some values, we will have a situation where there is a value $$$ \lt k$$$ both to the left and to the right of $$$k$$$. Then, to achieve $$$\operatorname{mex} = k$$$, we need to collect all numbers $$$ \lt k$$$, but since they exist both to the left and to the right, we will include $$$k$$$, resulting in $$$\operatorname{mex} \gt k$$$.
In total, we have $$$2$$$ options for ensuring $$$w_k=1$$$, and $$$k-1$$$ options for $$$w_k=0$$$. We have derived that
In this version of the problem, $$$w = s$$$, so we only need to check whether $$$f(w)$$$ is divisible by $$$c$$$. To do this, we will iterate through all $$$i$$$ and reduce $$$c$$$ by the greatest common divisor of the current factor and the number $$$c$$$. If we end up with $$$c = 1$$$, then the answer is $$$-1$$$. Otherwise, the answer is $$$f(w)$$$.
2189D2 - Little String (Hard Version)
From D1 we have:
We will calculate the product of the multiplicative terms for all symbols $$$s$$$ that are given (\texttt{0} or \texttt{1}), and we will call this number $$$b$$$; the product of the remaining terms will be called $$$x$$$. The remaining symbols can be chosen, so we need to find the smallest value
that is not divisible by $$$c$$$. We can eliminate $$$b$$$, $$$x$$$ must not be divisible by $$$c' = \frac{c}{\gcd(b, c)}$$$. (In the implementation, to obtain $$$c'$$$, we divide $$$c$$$ by the gcd with each term of the product $$$b$$$ to avoid overflow.) If we can choose $$$s_2$$$, we will choose $$$s_2 = \texttt{1}$$$, which will make one of the terms in the product equal to $$$1$$$~--- this will not cause divisibility and will not increase the number. In the end, we need to choose for several $$$j \ge 2$$$ (for $$$j = i - 1$$$, where $$$s_i = \texttt{?}$$$) to multiply $$$x$$$ either by $$$2$$$ or by $$$j$$$, so that the product is minimal and not divisible by $$$c'$$$, and the answer will be $$$bx$$$.
Let's consider two cases.
- $$$c'$$$ is a power of $$$2$$$. For all even $$$j$$$, we will choose to multiply by $$$2$$$, since multiplying by $$$2$$$ instead of a positive even number will not cause divisibility and will not increase the product. We will greedily choose to multiply by $$$2$$$ for the largest of the remaining $$$j$$$ as long as possible (while $$$c'$$$ still does not divide $$$x$$$) to minimize $$$x$$$.
- $$$c'$$$ is not a power of $$$2$$$. Then, by choosing to multiply by $$$2$$$ each time, $$$x$$$ will not be divisible by $$$c'$$$, and the product will be minimal, since each time we chose the smaller of the possible factors ($$$2 \le j$$$).
Final asymptotic complexity: $$$\mathcal{O}(n \log n)$$$.
Let's start by saying the answer is $$$-1$$$ if the string consists only of $$$0$$$'s.
Suppose we performed $$$k$$$ operations, where the $$$i$$$-th operation cost $$$a_i$$$. Then
$$$(a_1 - 1) + (a_2 - 1) + \dots + (a_k - 1) = n - 1$$$ (the number of characters that need to be removed), so
$$$cost = a_1 + a_2 + \dots + a_k = n - 1 + k$$$.
Thus the problem reduces to finding the minimal number of operations $$$k$$$ needed to achieve the goal. The answer will be $$$n - 1 + k$$$.
We show that $$$k \le 4$$$.
Let $$$s_i = 1$$$. Replace substrings $$$[1, i-1]$$$ and $$$[i+1, n]$$$ with some characters. Now we have the string $$$x 1 y$$$. Replace the substring $$$[1, 2]$$$ with $$$1$$$, giving $$$1 y$$$. Finally replace it with the string $$$1$$$.
Now we determine when the minimal number of operations is $$$k = 0, 1, 2, 3$$$ (otherwise $$$k = 4$$$).
By the difference of a string we mean the difference between the number of $$$1$$$'s and $$$0$$$'s.
It is claimed that $$$k$$$ operations are sufficient if:
$$$k = 0$$$ When $$$s = 1$$$.
$$$k = 1$$$ The string's difference is nonnegative.
$$$k = 2$$$ Either the string has a prefix or suffix with positive difference (then the remaining part can be replaced with any symbol, after which the whole string can be turned into $$$1$$$ in one move),
or the string's difference equals $$$-1$$$ (if the first condition does not hold, then we can replace substring $$$[1, n-1]$$$ with $$$1$$$ — its difference is $$$0$$$ because $$$s_n = 0$$$ — obtaining the string $$$10$$$, which can be changed to $$$1$$$ in one operation).$$$k = 3$$$ Either the string has a prefix or suffix with nonnegative difference (then the remaining part can be replaced by $$$0$$$, that part can be turned into $$$1$$$, resulting in string $$$10$$$ or $$$01$$$, after which one operation suffices),
or there are two consecutive $$$1$$$'s (then replace the prefix before them and the suffix after them with something, obtaining a string with difference $$$\ge 0$$$, which can be turned into $$$1$$$).$$$k = 4$$$ Otherwise.
Now we proceed to the proofs for $$$k \ge 2$$$:
- $$$k = 2$$$ Assume the goal cannot be achieved in $$$k \lt 2$$$ operations, but can in $$$k = 2$$$, under the conditions that the difference is not $$$-1$$$ and there is no prefix/suffix with positive difference.
If the first operation is on a prefix or suffix, then that substring's difference is $$$\ge 0$$$. To finish in one more operation, the remaining part must have difference $$$-1$$$ (if it had difference $$$\ge 0$$$, the whole original string would have nonnegative difference; if $$$ \lt -1$$$, the total after the first operation would be $$$ \lt 0$$$). In this case the whole original string's difference would also be $$$-1$$$.
If the first operation is on some middle substring, then after it the difference $$$\le -1 + 1 + (-1) = -1$$$, so winning becomes impossible.
- $$$k = 3$$$ Assume the goal cannot be achieved in $$$k \lt 3$$$ operations, but can in $$$k = 3$$$, under the conditions that no prefix/suffix has nonnegative difference and there are no two consecutive $$$1$$$'s.
Let the initial difference be $$$z$$$. Suppose the first operation is on substring $$$[l, r]$$$. Let the difference in $$$[1, l-1]$$$ be $$$a \lt 0$$$, in $$$[l, r]$$$ be $$$b$$$, and in $$$[r+1, n]$$$ be $$$c \lt 0$$$.
Case $$$b = 0$$$
Now the difference becomes $$$a + 1 + c$$$.
If $$$a + c + 1 = -1$$$, then $$$a + c = -2$$$ with $$$a, c \le -1$$$, so $$$a = c = -1$$$. But then if substring $$$[l, r]$$$ starts and ends with $$$0$$$ (otherwise prefix $$$[1..l]$$$ or suffix $$$[r..n]$$$ would have nonnegative difference). Then substring $$$[l+1, r-1]$$$ has difference $$$2$$$, so its length is even (if zeros $$$= x$$$, ones $$$= 2 + x$$$, total $$$= 2 + 2x$$$). Group adjacent pairs $$$(l+1, l+2), \dots, (r-2, r-1)$$$. In each pair difference $$$\le 0$$$ (since no two consecutive $$$1$$$'s), so difference of the whole sub-substring cannot be $$$2$$$ — contradiction.
Otherwise, suppose a positive prefix/suffix emerges after the operation (w.l.o.g., a prefix).
Let $$$T$$$ be that positive prefix. It contains the $$$1$$$ produced from $$$b$$$ plus some part $$$M$$$ from suffix $$$[r+1..n]$$$ with difference $$$d \gt 0$$$. Then $$$T$$$'s difference is $$$a + 1 + d \ge 1$$$, so $$$a + d \le 0$$$. We already know $$$d \le 1$$$ (otherwise there would be two consecutive $$$1$$$'s), so $$$a \ge -1$$$, hence $$$a = -1$$$. Then $$$M$$$ starts with $$$0$$$ (otherwise $$$a + b + 1 = 0$$$ giving a prefix with nonnegative difference). Thus the used part $$$M$$$ must have difference $$$2$$$, so it contains two consecutive $$$1$$$'s — contradiction.
Case $$$b \lt 0$$$ If difference becomes $$$-1$$$, then $$$a - 1 + c = -1 \implies a + c = 0$$$, impossible.
Otherwise, suppose a positive prefix emerges (w.l.o.g., a prefix).
- If $$$l = 1$$$, then suffix $$$[r+1..n]$$$ remains. We get $$$0$$$ + a prefix from $$$M$$$, so that prefix must have difference $$$\ge 2 \implies$$$ two consecutive $$$1$$$'s — contradiction.
- Otherwise, the new prefix includes $$$[1..l-1]$$$ + $$$0$$$ (from $$$b$$$) + prefix $$$M$$$ from $$$[r+1..n]$$$. That prefix would need difference $$$\ge 3$$$ (since $$$[1..l-1]$$$ has difference $$$\le -1$$$ and we add a $$$0$$$), so again two consecutive $$$1$$$'s — contradiction.
2189F - Zhora the Vacuum Cleaner
Idea: yanb0
We call a vertex dead if it has $$$0$$$ nuts, and if we root the tree in it, among the subtrees of its children, there is at most one subtree with a positive sum of the numbers of nuts.
We denote the movement operation for a vertex $$$v$$$ as $$$\operatorname{c}(v)$$$.
Let $$$A$$$ be the forest consisting of all living vertices. We prove that $$$A$$$ is always connected, i.e., it is a tree. Suppose for a contradiction, $$$A$$$ has at least two connected components, then the path between them must contain a dead vertex $$$v$$$. However, $$$v$$$ is alive, since both connected components are in different subtrees of $$$v$$$'s children when the tree's rooted in $$$v$$$, a contradiction, q.e.d.
Let $$$\deg(v)$$$ be the degree of $$$v$$$ in $$$A$$$. It's easy to see that when applying $$$\operatorname{c}(v)$$$, $$$a_v := a_v + \deg(v)$$$, and for all other vertices $$$u \in A$$$, $$$a_u := a_u + \deg(u) - 2$$$. If $$$v \not \in A$$$, then $$$a_v := a_v + 1$$$, $$$a_u := a_u + \deg(u) - 2$$$, $$$a_p := a_p + \deg(p) - 1$$$, where $$$p$$$ is the closest vertex from $$$A$$$ to $$$v$$$. $$$[*]$$$
For a sequence of operations, we define the tree $$$L$$$ as $$$A$$$ at the moment after all $$$\operatorname{c}(v)$$$ operations and before the nuts are eaten.
Suppose we have a sequence of operations (including the eating) that results in no nuts remaining. Let us prove that the last operation $$$\operatorname{c}(v)$$$, where $$$v \not \in L$$$, can be replaced by $$$\operatorname{c}(u)$$$, where $$$u \in L$$$. In this case, $$$A$$$ becomes a non-strict subset of itself, and again, there are no nuts left. Consider the moment before applying $$$\operatorname{c}(v)$$$. There are two options:
$$$v$$$ is alive. Then, when replacing $$$\operatorname{c}(v)$$$ with $$$\operatorname{c}(u)$$$, $$$a_v$$$ decreases by $$$2$$$, and $$$a_u$$$ increases by $$$2$$$ according to $$$[*]$$$.
$$$v$$$ is dead. Let $$$p$$$ be the closest vertex in $$$A$$$ to $$$v$$$. Then, when replacing $$$\operatorname{c}(v)$$$ with $$$\operatorname{c}(u)$$$, $$$a_v$$$ and $$$a_u$$$ will decrease by $$$1$$$ (become equal to $$$0$$$), and $$$a_p$$$ will increase by $$$1$$$ according to $$$[*]$$$.
In both cases, all $$$a_x$$$ for $$$x \not \in L$$$ will decrease, and it is easy to see that the sequence of operations after $$$\operatorname{c}(v)$$$ will also bring all nuts into $$$L$$$, after which the same eating operations will remove all nuts, q.e.d. Thus, all operations of type $$$\operatorname{c}(v)$$$, where $$$v \not \in L$$$, can be (sequentially from the end) replaced by $$$\operatorname{c}(u)$$$ for some $$$u \in L$$$.
Now we have to solve the following problem:
We need to choose a subtree $$$L$$$ of the original tree, then repeatedly apply $$$\operatorname{c}(u)$$$, $$$u \in L$$$, to make all vertices not in $$$L$$$ dead, and then apply the eat operation to all $$$v \in L$$$. Note that by $$$[*]$$$, all vertices not in $$$L$$$ will become dead regardless of which vertices in $$$L$$$ we choose; in other words, we can apply all $$$\operatorname{c}(v)$$$ to only one vertex $$$v$$$.
Consider the dynamics along directed edges $$$xy$$$, $$$dp[x][y]$$$: the smallest number of $$$\operatorname{c}(v)$$$ operations, where $$$v$$$ is on the $$$x$$$ side of $$$xy$$$, needed to make all vertices on the $$$y$$$ side (including $$$y$$$) of $$$xy$$$ dead. The value of $$$a_y$$$ can only decrease when $$$\deg(y) = 1$$$, so $$$dp[x][y] = \sum_{i=0}^{k}dp[y][ch[i]]$$$, that is, $$$dp[x][y]$$$ is equal to the sum of $$$a_v$$$ over all $$$v$$$ in the subtree $$$y$$$, if we hang the entire tree on $$$x$$$.
For all vertices $$$v \not \in L$$$, at some point and always after that, $$$a_v = 0$$$. It is also possible that $$$a_v = 0$$$ before all operations; $$$a_v$$$ is never equal to $$$0$$$ again.
We define $$$zero[y]$$$ to be the smallest number of $$$\operatorname{c}(v)$$$ operations required for $$$a_y = 0$$$ after any number of $$$\operatorname{c}(v)$$$ operations at least equal to $$$zero[y]$$$. $$$zero[y] = \min_x({dp[x][y]})$$$ for all $$$x$$$ adjacent to $$$y$$$, and $$$zero[y] = 0$$$ if $$$a_y = 0$$$ and $$$\deg(y) = 2$$$ initially. This is true because if $$$a_y \ne 0$$$ or $$$\deg(y) \ne 2$$$, $$$y$$$ will finally ``zero out'' only when it becomes dead. $$$\min_x({dp[x][v]})$$$ is greater than $$$dp[v][u]$$$ for all, possibly except one, vertices $$$u$$$ adjacent to $$$v$$$, and therefore is greater than $$$\min_t({dp[t][u]})$$$ for $$$t$$$ adjacent to $$$u$$$ adjacent to $$$v$$$. Therefore, applying $$$\operatorname{c}(v)$$$ to $$$v$$$ with the largest $$$zero[v]$$$, each $$$a_u$$$ will become equal to $$$0$$$ after $$$zero[u]$$$ operations.
Thus, either there are no $$$\operatorname{c}(x)$$$ operations, and the eating operation must be applied to all $$$y$$$ with initial $$$a_y = 0$$$, or there are $$$\operatorname{c}(x)$$$ $$$k$$$ operations, and the eating operation must be applied to all vertices $$$y$$$ with $$$zero[y] \ge k$$$. For the first case, we simply calculate the cost of this sequence of operations. For the second case, we sort $$$zero$$$ in $$$O(n \log n)$$$, then iterate over the number of ``zeroed'' vertices, iterating over $$$zero$$$, and calculate the answer as $$$(n - i) \cdot q + zero[i - 1] \cdot p$$$. The answer to the problem will be the minimum of the obtained ones.
Total complexity: $$$O(n \log n)$$$.
