User editorial for Codeforces Round 513 by Barcelona Bootcamp (rated, Div. 1 + Div. 2)

Think about two cases: when there are very few 8s, and when there are a lot of 8s.

Let the number of $8$-s given to us be $m$. We can not make more than $\lfloor n / 11 \rfloor$ phone numbers, because every phone number has $11$ digits, and the number of phone numbers can't be more than $m$. So an upper bound on the number of phone numbers is $\min(m, \lfloor n / 11\rfloor)$.

We claim that this is indeed achievable. Indeed, we make the following two cases:

• $m \le n / 11$: this means $n \ge 11 m \implies n - 10m \ge m$. So we have sufficient cards to assign $10$ cards (without an $8$ on them) to each card with an $8$ on it, and this leads to $m$ phone numbers.

• $m > n / 11$: this means that we can pick $\lfloor n / 11 \rfloor$ cards with $8$ on each of them, and assign $10 \lfloor n / 11 \rfloor$ cards out of the rest to them in order to construct $\lfloor n / 11 \rfloor$ phone numbers. This is possible since the total number of cards used is $\lfloor n / 11 \rfloor + 10 \lfloor n / 11 \rfloor = 11 \lfloor n / 11 \rfloor \le n$, the last of which is true since $n$ is non-negative.

The time complexity is $O(n)$.

What happens to the digit sum of the sum of two numbers (compared to their individual digit sums) when there is no carry-bit when adding two numbers? When there is one carry-bit? Two carry-bits? Can you quantify this result? One might guess that we want to maximize the number of carry-bits, and that is correct.

Firstly let's show a claim to show that the intuition was correct.

Claim 1. Let $a, b$ be two non-negative integers. Let the number of carry-bits encountered while adding them be $c$. Then $S(a) + S(b) = S(a + b) + 9c$.

Proof. We will induct on the number of carry-bits in the addition. For this proof to be made amenable to induction, we will need the following observation, and a slight restructuring of the claim.

Observation 1.1. The carry bit when adding two numbers can be at most 1.

Proof. Induction on the current position in the process of addition. At the rightmost position, the carry bit is $0$. So the next carry bit can at most be $\lfloor (9 + 9) / 10 \rfloor = 1$, and the base case is shown. Let's say we are at some position $i$ from the right. Then the carry bit is at most $1$. So the next carry bit can be at most $\lfloor (1 + 9 + 9) / 10 \rfloor = 1$, and we are done.

Claim 1.2. (Relaxation of claim 1): Let $a, b$ be two non-negative integers, and let $\varepsilon$ be one of $0$ and $1$. Let the number of carry bits encountered while adding $a, b, \varepsilon$ be $c$. Then $S(a) + S(b) + S(\varepsilon) = S(a + b + \varepsilon) + 9c$.

Proof. Let's denote by $\ell(a)$ the number of digits in $a$ for $a > 0$ and let $\ell(0) = 0$. We will induct on $\max(\ell(a), \ell(b))$. The base case is trivial. For the inductive step, note that when there is a carry in the last place, then the carry bit $h$ can be at most $\lfloor (1 + 9 + 9) / 10 \rfloor = 1$. Applying the inductive hypothesis for $(\lfloor a/10 \rfloor, \lfloor b/10 \rfloor, h)$, we know that $S(\lfloor a/10 \rfloor) + S(\lfloor b/10 \rfloor) + S(h) = S(\lfloor a/10 \rfloor + \lfloor b/10 \rfloor + h)$. Let's now see what happened at the last place.

We consider the quantity $a \% 10 + b \% 10 + \varepsilon - (a + b + \varepsilon) \% 10 - h$.

• If there was a carry: this quantity reduces by $9$.
• If there was no carry: this quantity stays the same.

Now note that this combined with the conclusion from the inductive hypothesis proves the claim. $\blacksquare$

As a consequence of claim 1, it is easy to see that we want $a, b$ satisfying $a + b = n$ that maximize the number of carry bits when added. By induction on the length of the suffix of the decimal representation of $n$ that consists only of $9$-s, we can show that it is impossible to get any carry bit. Let's remove the largest suffix consisting entirely of $9$-s from $n$. It suffices to find the answer for this $n$ now.

So either you run out of $9$-s in the suffix (in which case $n = 10^k - 1$ for some positive integer $k$), or there is a digit that is not $9$. In the former case, the answer is just the sum of digits of $n$. In the latter, note that we can't get more than $\ell(n) - 1$ carry bits. This is also achievable: consider $b = 10^{\ell(n) - 1} - 1$. (or $1$ if $\ell(n) = 0$).

The time complexity is $O(\log n)$.

Can we get a closed form for the sum of elements of the subrectangle?

Note that for a subrectangle corresponding to $x_1, y_1, x_2, y_2$ as in the statement, $c_{i, j}$ corresponds to the term we get when we multiply $(\sum_{i = x_1}^{x_2} a_i) \cdot (\sum_{j = y_1}^{y_2} b_j)$. This allows us to decouple the rows and the columns of the matrix.

More specifically, consider the subarray of $a$ with indices from $x_1$ to $x_2$ (let's call it $a[x_1 : x_2]$), and also consider the subarray of $b$ with indices from $y_1$ to $y_2$ (let's call it $b[y_1 : y_2]$). Define the cost of a subarray as the sum of elements in it. Then the sum of the subrectangle equals the cost of $a[x_1 : x_2]$ times the cost of $b[y_1 : y_2]$. So now, we focus on only the one dimensional arrays given to us.

For a given value $C$ of the cost, let's try to find the maximum length of a subarray of $a$ with cost $C$ (let's call this $\ell( C)$). Using this, we can compute the maximum length of a subarray that has a cost at most $C$, by finding the prefix maximums of $\ell$. Let's also do this for the array $b$.

The problem now reduces to finding $\max A_i \cdot B_j$ subject to the constraints $i \cdot j \le x$, for two monotonically non-decreasing arrays $A$ and $B$ (the reduction follows by setting $A$ to be the array found in the previous paragraph for $a$, and $B$ to be the analogue of $A$ for $b$).

Now, this problem can be solved in linear time in the sizes of the arrays using two pointers: let's iterate over $i$ from right to left. Note that the rightmost $j$ such that $i \cdot j \le x$ is in fact $\lfloor x / i \rfloor$, and this is non-decreasing as $i$ decreases. In fact, since $B$ is non-decreasing, two pointers are redundant, and we can simply query $B_{\lfloor x / i \rfloor}$.

Note that there is one potential catch: the sizes of $A$ and $B$ might be large. But the constraints on the arrays $a$ and $b$ show that the maximum size is $4 \cdot 10^6$, and the constraints on $n$ show that we can run an $O(n^2)$ loop to compute the arrays $A$ and $B$ from $a$ and $b$ fast enough.

The time complexity is $O(\max(\sum_{i = 1}^n a_i, \sum_{i = 1}^m b_i) + n^2 + m^2)$.

There are two possible approaches to this problem:

1. Try finding a lower bound on the answer. Can you show that it is actually the answer?
2. Try to rephrase the setup in another way, and observe some structure.

Firstly, let's try finding a lower bound on the answer. To visualize this setup better, let's construct a graph where there is an edge from a person to the person on their right. Then the resulting graph is a union of isolated cycles (and possibly self-loops).

Clearly, for a person, there is exactly one person to their right, and every person has exactly one person on their left. So the function that maps a person to the person on their right is a permutation. Also, note that every permutation has a cycle decomposition, and by arranging people according to the cycles in the decomposition, we can recover a valid seating plan. In other words, there is a bijection between seating plans and permutations.

Any edge from a person $i$ to person $j$ contributes $\max(r_i, l_j)$ to the answer, and every person contributes $1$. So we want to minimize $n + \sum_{i = 1}^n \max(r_i, l_{p_i})$ over all permutations $p$ of size $n$. We claim that this expression is minimized when $r_i$ and $l_{p_i}$ are sorted the same way. The proof will be via construction.

Without loss of generality, let's say $r$ is sorted (reindex people if this is not the case).

Consider a permutation $p$ with at least one inversion. Note that here an inversion is defined as $l_{p_j} > l_{p_i}$ for $i < j$ --- in particular, we are not looking at inversions in $p$, but in the "permutation" $l \circ p$, or more precisely the composition of the permutation that you get when you map elements of $l$ to their ranks (ties broken arbitrarily), and $p$.

Every permutation with at least one inversion has at least one inversion with adjacent indices. Let's say those indices are $(i, i + 1)$. This means $l_{p_{i + 1}} < l_{p_i}$ and $r_i \le r_{i + 1}$. We now construct the permutation $p'$ by applying a swap $(i, i + 1)$ to $p$. We claim that $p'$ is at least as good as $p$. In particular, we just need to show that for positive integers $a \le b$ and $c < d$, the following holds: $\max(a, c) + \max(b, d) \le \max(a, d) + \max(b, c)$, or equivalently, that $\max(a, d) - \max(a, c) \ge \max(b, d) - \max(b, c)$. Consider the function $f(x) = \max(x, d) - \max(x, c)$. For $x \le c$ it evaluates to $d - c$, for $c < x \le d$ it evaluates to $d - x$, and for $d < x$ it evaluates to $0$. So, this is a non-increasing function, and we are done.

This operation (replacing $p$ by $p'$) reduces the number of inversions by exactly one. By doing this process while there is at least one inversion, we come to a permutation such that $l \circ p$ is the identity permutation --- that is, $l$ and $r$ are sorted the same way.

Now that we are done with the proof, we have shown that there exists an optimal seating plan which requires $n + \sum_{i = 1}^n \max(L_i, R_i)$ chairs, where $L, R$ are the arrays you get when you sort $l, r$ respectively.

The time complexity is $O(n \log n)$ for sorting.

Can we map shortest paths in the new graph to shortest paths in the tree?

Consider a shortest path between two vertices $u$ and $v$ in the new graph. It consists of two types of edges: edges that were originally in the tree, and edges that were added to the tree. Let's call them old and new edges respectively.

We construct a walk in the original tree corresponding to this shortest path: for every new edge, replace it by two adjacent old edges due to which this new edge was added.

So if the number of old edges is $n_1$ and the number of new edges is $n_2$, the length of the considered shortest path is $n_1 + n_2$, and the length of the walk in the original tree is $n_1 + 2 n_2$. By reducing this walk to a path, we get a path in the tree of length $\le n_1 + 2 n_2$. Note that this is at most twice the length of the considered shortest path.

Conversely, from a shortest path (in fact, the unique path) of length $l$ in the tree between $u$ and $v$, we can construct a path of length $\lceil l / 2 \rceil$ in the new tree. Since $l \le n_1 + 2 n_2 \le 2 (n_1 + n_2)$, we have $\lceil l / 2 \rceil \le n_1 + n_2$, so this is indeed the shortest path between the two vertices in the new graph.

This shows that for vertices $u, v$, the distance between them in the new graph is $\lceil d(u, v) / 2 \rceil$.

Now we only need to compute the sum of this expression over all $u, v$. $\lceil d(u, v) / 2 \rceil$ equals $d(u, v) / 2$ if the distance between $u, v$ is even, and $(d(u, v) + 1) / 2$ otherwise. In other words, we just need to compute the sum of $d(u, v)$ over all vertices, and the number of pairs of vertices that are at an odd distance to each other. Since we can color a tree in 2 colors, we just need to find the product of the sizes of the two bipartitions.

Computing the sum of $d(u, v)$ is standard: every edge contributes $1$ to each pair $(u, v)$ of vertices such that removing that edge will disconnect these vertices. So we can root the tree, do a DFS, and then compute the number of such pairs for each edge quite easily.

The time complexity is $O(n)$.

Fix the vertex for which we want the answer, and call it the root. Let's try to think about the operations sequentially. We have a total of $2^{n-1} (n-1)!$ choices, corresponding to sequence of (edge, choice) pairs where the choice is to choose which label is assigned to the collapsed vertex. Try to count the sequences of these choices which allow the root to survive. A probabilistic interpretation works too.

Read the previous spoiler if not done already for the basic intuition behind the solution.

Let $\sigma$ and $\pi$ be two permutations. Applying the mapping $x \mapsto x + |\sigma|$ to the array $\pi$ and shuffling the elements of $\sigma$ and $\pi$ together, while keeping their internal order the same will generate another permutation with size $|\sigma| + |\pi|$. We shall call this operation interleaving. Note that when $\sigma$ and $\pi$ vary over all permutations, and the interleavings are taken over all possible $\binom{|\sigma| + |\pi|}{|\pi|}$ interleavings, this generates all possible permutations of size $|\sigma| + |\pi|$. We can generalize this to adding an extra bit of information with every element of $\sigma$ and $\pi$, and an analogous result holds true for this setup too.

We will look at the choices as interleavings of the choices for each of the children's subtrees (with an extra edge added on top for each subtree). The operation corresponding to adding an extra edge corresponds to interleaving the permutation $\{1\}$ with the permutation for the subtree (and there is precisely one choice that must be taken whenever we consider the extra edge). We'll call this edge the hanging edge for that subtree.

Now at any stage of the interleaving, note how the structure of the tree looks like. It might be helpful to consider the shrinking operations in the following way: initially all edges are represented with dotted lines (implying that they're just a template for connecting edges, and don't connect the edges at this stage), and every vertex is its own representative, and every shrinkage converts a dotted line into a solid line, and sets the representative of the sets of vertices connected by this edge to one of the representatives randomly. Basically how DSU works.

In this interpretation, consider the component containing the root. The choices made for the children subtrees that have only one correct choice (for the root to survive) correspond to the choices that end up in the root's component. Let's un-interleave these choices. Then this problem reduces to the same problem but for the child subtrees. Also, note that when interleaving these subtrees and counting the number of choices that allow the root to survive, only the number of choices made (before choosing the hanging edge) for each subtree matter. Also, note that we can do these interleavings associatively (that is, first the first subtree, then the second with the result of the first subtree, then the third with the result of the first and second subtrees and so on), and the computation remains the same.

So the merges will go as follows: for a vertex, we will compute the answers for its children, and for each child, extend the set of choices by the extra choice that needs to be made for adding a hanging edge (by interleaving with the single choice), and then interleave these choices again.

Using these ideas, we can do a DP with the following state: dp[u][k] is the number of choices for the subtree of a vertex $u$ when $k$ decisions are done before we choose the hanging edge. For the transitions, you can refer to the submission.

How can you exploit the fact that when there are $k$ $a_i$-s to the left of a number which is not on a pocket, it gets shifted to the left by $k$? Try finding some properties and some nice locations that can help.

We'll reindex $a$ for its indices to start from $0$.

Let's start out with an easy to prove observation:

We call an interval $[a, b]$ of positive integers good if there are exactly $b - a + 1$ pockets with positions $< b$. Then after a single operation, a good interval moves to positions that form a good interval. The proof goes as follows: let's say there are $c$ pockets under the interval. Then the left endpoint moves by $b - a + 1 - c$ (potentially falling into a pocket), the right endpoint moves by $b - a + 1$, and balls that didn't fall into a pocket remain contiguous (filling holes if formed).

Let's try to take advantage of such good intervals. We will try to construct good intervals with some maximal right endpoints, so as to partition the integer line into some partitions.

Define the sequence $\{r_i\}_{i = 0}^{n - 1}$ by $r_0 = a_0 - 1$ and $r_i = r_{i - 1} + i \cdot \left\lfloor \frac{a_i - 1 - r_{i - 1}}{i} \right\rfloor$ for $i > 0$. This is clearly a non-decreasing sequence.

This roughly corresponds to the set of right endpoints of our intervals (though some $r_i$ will be repeated here, and though we'll ignore them in the current analysis, they'll be helpful for implementation).

Observation 1. By the definition of floor, we have $r_i + 1 \le a_i \le r_i + i$.

Observation 2. Whenever $r_i > r_{i - 1}$, we have $r_i > a_{i-1}$.

Proof. Since $r_i - r_{i - 1}$ is divisible by $i$, the difference is at least $i$. So by the previous observation, we have $r_i \ge r_{i - 1} + i \ge a_{i - 1} + 1 > a_{i - 1}$, as desired.

From this, we get that if $r_i > r_{i - 1}$, the length of the moving interval $[r_i - i + 1, r_i]$ stays intact for $\left\lfloor \frac{a_i - 1 - r_{i - 1}}{i} \right\rfloor - 1$ operations, and after one more operation, it ends up at some suffix of positions $\le r_{i - 1}$. That is, $r_i$ after some operations hits $r_{i - 1}$. This sequence gives a partition of the integer line into smaller chunks that can be reasoned about locally.

Now that the main idea of the solution is complete, all that remains is to back-compute the number that ends up at a given position. For this, it is (theoretically) straightforward to compute the answer if you reason about the number that ends up at certain $r_i$-s close to $x$. For the relevant book-keeping that needs to be done as a part of implementation details, a persistent segment tree can be used. Note that the queries can also be solved offline, but that needs some more work.

What kinds of operations can we implement using addition alone? Try small cases, like $d = 2$.

Using addition, we can implement multiplication by a "compile-time" constant $n$ in $O(\log n)$ steps. Since arithmetic is modular, we can implement this in $O(\log p)$ steps (remember that multiplication by $0$ is an edge case here, so it needs to be handled like multiplication by $p$).

If you try $d = 2$, you can realize that it suffices to be able to find $a^2$ from a variable $a$, because then we have $xy = ((x + y)^2 - x^2 - y^2) \cdot ((p + 1) / 2))$.

Now we only want to be able to go from $x^d$ to $x^2$. For this, note that there is a set of $d + 1$ linear equations in the formal variables $1, x, x^2, \dots, x^d$ relating them to $(x + i)^d$ for $i = 0$ to $d$. The determinant of the matrix is non-zero since it is a non-zero (mod $p$ too, because $d < p$) factor times the Vandermonde determinant (which is non-zero mod $p$ because $d < p$), so it is invertible.

By inverting this matrix, we can get $x^2$ from $(x + i)^d$ for $i = 0$ to $d$. The total number of queries is about $O(d \log p)$ in both space and memory, and it passes very comfortably.