We hope you liked problems!

We are sorry for some passing wrong solutions for problems G & H.

You can also check ivan100sic comment for other variant of this solution

# | User | Rating |
---|---|---|

1 | tourist | 3735 |

2 | MiFaFaOvO | 3681 |

3 | Um_nik | 3553 |

4 | Benq | 3376 |

5 | ecnerwala | 3295 |

6 | maroonrk | 3229 |

7 | TLE | 3223 |

8 | Radewoosh | 3216 |

9 | scott_wu | 3209 |

10 | Petr | 3205 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 204 |

2 | antontrygubO_o | 191 |

3 | pikmike | 187 |

4 | Monogon | 185 |

5 | vovuh | 184 |

6 | Ashishgup | 182 |

7 | Um_nik | 180 |

8 | SecondThread | 173 |

9 | Radewoosh | 172 |

10 | McDic | 162 |

We hope you liked problems!

We are sorry for some passing wrong solutions for problems G & H.

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

You can also check ivan100sic comment for other variant of this solution

Tutorial of Good Bye 2019

Codes have been added!

We've added challenges(mostly not hard) to some tasks. Feel free to share solutions and ask any questions in comments!

If the string is good, then answer it's itself. Otherwise, there are at least two strings in answer, and we can print substring without its last symbol and its last symbol separately. Complexity $$$O(n)$$$.

Let's suppose that array is sorted. First of all, if $$$a_n \ge a_{n - 1} + a_{n - 2}$$$, than the answer is — NO (because otherwise $$$a_{n}$$$ is not smaller than sum of the neighbors). We claim, that in all other cases answer is — YES. One of the possible constructions (if the array is already sorted) is:

$$$a_{n - 2}, a_{n}, a_{n - 1}, a_{n - 4}, a_{n - 5}, \ldots ,a_1$$$

It's easy to see, that all numbers except $$$a_n$$$ will have at least one neighbor which is not smaller than itself. Complexity $$$O(nlog(n))$$$.

$$$\textbf{Challenge}$$$

Solve the task in $$$O(n)$$$ (if we suppose that all numbers don't exceed $$$10^9$$$).

Claim: $$$f([a_1, a_2, \ldots, a_{2^k}]) = \lfloor \frac{a_1 + a_2 + \ldots + a_{2^k}}{10} \rfloor$$$. Clearly, using it we can answer queries in $$$O(1)$$$ if we create array $$$prefsum$$$, in which $$$prefsum[i] = a_1 + \ldots + a_i$$$.

Imagine, that candy is equal to number $$$10$$$. Then sum of all numbers doesn't change: when we replace $$$(a, b) \to ((a + b) \bmod 10)$$$ we take $$$10$$$ iff $$$a + b$$$ exceeds $$$(a + b) \bmod 10$$$. Also note, that sum of numbers-candies is divisible by $$$10$$$ (because we take only tens). Then, in the end, the remaining digit is equal to the remainder of the division of the initial sum by $$$10$$$, so the number of candies is equal to the quotient.

Asymptotics is $$$O(n + q)$$$.

It's possible to solve the problem using dynamic programming.

For each segment $$$[s_l, s_{l+1}, \ldots, s_r]$$$, length of which is a power of two, we will save pair — digit, which will remain and the number of candies, which we get for this segment. For segment of length $$$1$$$ this pair is $$$(s_l, 0)$$$.

Note that there are at most $$$\log{n}$$$ different lengths of segments, and the number of segments with fixed length is at most $$$n$$$. It follows that there are at most $$$n\log{n}$$$ segments.

Now solution is similar to building sparse table. We will calculate needed pairs for segments in the order of increasing of their length: firstly for segments of length $$$2$$$, then for length $$$4$$$, etc. It turns out that the answer for segment of length $$$2^k$$$ can be calculated from smaller segments in constant time! Indeed, to get pair (last digit, number of candies) for $$$[s_l, s_{l+1}, \ldots, s_{l + 2^k - 1}]$$$, it's sufficient to know, how many candies we got in segments $$$[s_l, s_{l+1}, \ldots, s_{l + 2^{k-1} - 1}]$$$, $$$[s_{l+2^{k-1}}, s_{l+2^{k-1} + 1}, \ldots, s_{l + 2^k - 1}]$$$, and also what digits $$$dig_1, dig_2$$$ were left last in this segments, then last digit on our segment is equal $$$(dig_1 + dig_2)\bmod 10$$$, also if $$$dig_1 + dig_2 \ge 10$$$, we get one more candy.

So, transition for one segment is made in $$$O(1)$$$, which gives asymptotics $$$O(n\log{n})$$$.

We claim, that the answer is YES iff there is no vertex with degree 2. After this, it's easy to get a solution for first subtask in $$$O(n)$$$.

Proof of necessity

If there is a vertex of degree 2, then after any number of operations numbers which are written on two outcoming edges will be equal. Indeed, any path between two leaves, which passes through one edge, passes through other. Hence, we can't get configuration, where numbers on these two edges are different.

Proof of sufficiency

We will show, that there exists a sequence of operation which adds $$$x$$$ on the path between some vertex $$$v$$$ and leaf $$$u$$$(and doesn't change numbers on other edges). If this vertex is leaf, than it's obvious. Otherwise, its degree is at least 3. Than, let's look at two leaves $$$l_1$$$, $$$l_2$$$, such that $$$l_1$$$, $$$l_2$$$, $$$u$$$ lie in different subtrees of $$$v$$$. Then we will make the following operations:

Add $$$\frac{x}{2}$$$ on the path $$$u, l_1$$$.

Add $$$\frac{x}{2}$$$ on the path $$$u, l_2$$$.

Add $$$-\frac{x}{2}$$$ on t he path $$$l_1, l_2$$$.

So, we get, that we've added $$$x$$$ on the path $$$u, v$$$.

Next step is to show how to get any configuration. Let $$$a_e$$$ be the number, which is needed to be written on the edge $$$e$$$ after all operations. Let's root the tree from any vertex and recursively solve the task for subtrees in the following way:

solve($$$v$$$):

if $$$v$$$ doesn't have sons, then return.

otherwise, for each son $$$u$$$ we wiil find a leaf in subtree of $$$u$$$ — let's name it $$$w$$$. Than, add $$$a_{uv}$$$ on the path $$$vw$$$ and recalculate needed numbers on the edge in this path(it means for each edge $$$e$$$ on the path make this - $$$a_e -= a_{uv}$$$), after it, call solve($$$u$$$).

So, there is an algorithm, which for any configuration gets it from all-zero configuration. Sufficiency is proved.

Because all numbers are different, in the second subtask if we have a vertex with degree $$$2$$$ then answer is NO. If there is no such then construction also follows from proof. Indeed, if we can add on any path to leaf, then we can add on one edge. So, consider any edge $$$uv$$$ and suppose we want to add $$$x$$$ on this edge. Let's find any leaf in a subtree of vertex $$$u$$$, which doesn't contain $$$v$$$, let's name it $$$l$$$. If $$$l = u$$$, just add $$$x$$$ on path $$$uv$$$. Else, add $$$x$$$ on path $$$vl$$$ and $$$−x$$$ on path $$$ul$$$. It's clear, that after this two operations we've added $$$x$$$ on edge $$$uv$$$ and didn't add anything on other edges. Then, just add on each edge needed number.

In the end, let's talk about implementation. To add on the path to leaf it's sufficient to find a leaf in the subtree. We can do it naively in $$$O(n)$$$, then complexity is $$$O(n^2)$$$. Also, we can precalculate leaves in each subtree and, for example, root tree at some leaf. Then, it's possible to do all operations in $$$O(1)$$$, and complexity is $$$O(n)$$$, but it wasn't needed.

$$$\textbf{Challenge}$$$

Solve task if numbers are not necessary even and different, but all operations should be also with integer $$$x$$$(now it turns out that sometimes it's possible to solve it in rationals, but not in integers).

code for 1 subtask code for 2 subtask

Let's transform condtition a ittle bit. $$$a_i - a_j \not\equiv 0$$$ $$$mod$$$ $$$p$$$, so condtition is equivalent:

$$$(a_i - a_j)(a_i + a_j)(a^2_{i} + a^2_{j}) \equiv (a_i - a_j)k \Leftrightarrow a^4_{i} - a^4_{j} \equiv ka_i - ka_j \Leftrightarrow a^4_{i} - ka_i \equiv a^4_{j} - ka_j$$$.

That's why we just need to count number of pairs of equal numbers in the array $$$b_i = (a^4_{i} - ka_i)$$$ $$$mod$$$ $$$p$$$. It's easy to do it, for example, using map. Complexity $$$O(n)$$$ or $$$O(nlog(n))$$$.

$$$\textbf{Challenge}$$$

Solve the task, if numbers are not necessarily different.

First of all, let's learn how to solve the following subtask:

For given $$$x$$$ how many subsequences of length $$$k$$$ have beauty at least $$$x$$$? If we know that the answer for $$$x$$$ is $$$p_x$$$, than the answer for original task is $$$p_1 + p_2 + \ldots + p_{max(a)}$$$, where $$$max(a)$$$ is maximum in array $$$a$$$. Let's solve subtask.

Suppose, that array is sorted. We should count subsequence $$$p_1 < p_2, \ldots < p_k$$$, iff:

$$$a_{p_2} \ge a_{p_1} + x, \ldots, a_{p_k} \ge a_{p_{k - 1}} + x$$$.

We will solve this task using dp. The slow solution is:

$$$dp[last][cnt]$$$ — number of subsequences of length $$$cnt$$$, which end in $$$a_{last}$$$. There are transitions from state with $$$last' < last, cnt' = cnt - 1$$$, such that $$$a_{last} \ge a_{last'} + x$$$. To optimize it we need to note, that suitable $$$last'$$$ form some prefix of the array. If we know needed prefixes and prefix sums from the previous layer of dp, then we can make transitions in constant time. We can find needed prefixes using two pointers(because it's obvious, that length of prefixes doesn't decrease). So, we can solve subtask in $$$O(nk)$$$ time.

And, using solution to subtask, we can solve inital task in $$$O(max(a)nk)$$$. And here comes magic:

If $$$x > \frac{max(a)}{k - 1}$$$, than $$$p_x = 0$$$. Indeed, если $$$a_{p_2} \ge a_{p_1} + x, \ldots, a_{p_k} \ge a_{p_{k - 1}} + x$$$, than:

$$$a_n \ge a_{p_k} \ge a_{p_{k-1}} + x \ge a_{p_{k-2}} + 2x \ldots \ge a_{p_1} + (k - 1)x \ge (k - 1)x$$$. It follows: $$$(k - 1)x \le a_n \Leftrightarrow x \le \frac{a_n}{k - 1}$$$.

So we can run our dp only for $$$x \le \frac{max(a)}{k - 1}$$$. In total our solution works in $$$O(\frac{max(a)}{k - 1}nk) = O(max(a)n)$$$ time, because $$$\frac{k}{k - 1} \le 2$$$.

$$$\textbf{Challenge}$$$

How fast you can solve the task if you need to print answer for all $$$2 \le k \le n$$$?

We will suppose, that array is sorted. Let $$$x$$$ be the final number. Than $$$x \ge a_n$$$. Also, if we define $$$bits[c]$$$ — as number of ones in binary notation of $$$c$$$, than, to get $$$x$$$ from $$$a_i$$$ we will spend at least $$$bits[x - a_i]$$$ moves(it follows from the fact, that minumum number of powers of two, which in sum are equal to the number, corresponds to it binary notation). Let $$$t = x - a_n$$$, than $$$x - a_i = t + a_n - a_i$$$. So we need the following task:

Minimize sum $$$bits[t + a_n - a_1] + bits[t + a_n - a_2] + \ldots + bits[t + a_n - a_n]$$$, where $$$t$$$ is some nonnegative integer. Also, let's define $$$b_i$$$ as $$$a_n - a_i$$$.

We will solve this task using dp — value, which we want to minimize is sum $$$bits[t + b_i]$$$, taken over bits up to $$$(k - 1)$$$. Then, suppose we want to decide something about $$$k$$$-th bit. Let's understand, which information from the previous bits is needed for us. Imagine, that we sum $$$t$$$ и $$$b_i$$$ in vertical format. Clearly, to find $$$k$$$-th bit in number $$$t + b_i$$$ it's sufficient to know $$$k$$$-th bit in number $$$t$$$ and do we have carry from previous digit. Furthermore, if we know this information for the previous bit, we can get it for the next(carry in new digit will occur iff $$$bit_k[b_i]$$$ + $$$bit_k[t]$$$ + $$$(did we have carry) \ge 2$$$). But we should save information about carry for all numbers $$$t + b_i$$$, so, at first sight, for one bit we have at least $$$2^n$$$ different states of dp. To reduce the number of states we need to note key fact:

Let $$$t' = t$$$ $$$mod$$$ $$$2^k$$$, $$$c' = c$$$ $$$mod$$$ $$$2^k$$$. Than, carry in $$$k$$$-th bit will occur $$$t + c$$$ iff $$$t' + c' \ge 2^k$$$. Indeed, carry corresponds to the fact that the sum of "cutoff" numbers is at least $$$2^k$$$.

Using this fact we understand that, if we sort numbers $$$b_i' = b_i$$$ $$$mod$$$ $$$2^k$$$, than carry in $$$k$$$-th bit will happen only for some suffix of $$$b_i'$$$. That's why, we get $$$n + 1$$$ different states for one bit, which is good. So we only need to learn how to make transitions fast. It's useful to note, that we don't need to know numbers $$$b_i$$$, it's sufficient to know do we have a carry and value of $$$k$$$-th bit of $$$b_i$$$. Then, transition reduces to count the number of $$$1$$$ and $$$0$$$ in $$$k$$$-th bit on some segment of the array sorted by $$$b_i'$$$. This can be easily done in constant time if we precalculated prefix sums(for better understanding you can read attached code). So, we can solve the task in $$$nlog(n)F$$$ time, where $$$F$$$ is bit up to which we'll write dp. So, it' left to show (or to believe :)), that there is no sense to consider big $$$F$$$.

Let $$$t$$$ be minimum optimal solution and let's suppose that $$$t > b_1$$$. Because $$$a_1$$$ is minimum in $$$a$$$, than $$$b_1$$$ is maximum in $$$b$$$. Let $$$s$$$ be the most significant bit of number $$$t + b_1$$$. Than, $$$2^{s+1} > t + b_1 \ge 2^s$$$. Than, $$$2t > 2^{s}$$$, from what $$$t > 2^{s - 1}$$$. It follows, that the most significant bit of numbers $$$t + b_i$$$ is $$$s$$$, or $$$s - 1$$$. That's why, if we consider $$$t' = t - 2^{s - 1}$$$ we will get:

$$$bits[t' + b_i] = bits[t + b_i] - 1$$$, if at positon $$$s - 1$$$ in binary notation $$$t + b_i$$$ was 1.

$$$bits[t' + b_i] = bits[t + b_i]$$$, if at position $$$s - 1$$$ in binary notation $$$t + b_i$$$ was 0(because in this case the most significant bit of $$$t + b_i$$$ is $$$s$$$).

So, $$$t'$$$ gives the answer which is not bigger than $$$t$$$. So, we can suppose that the optimal solution is not bigger than $$$b_1 \le a_n$$$.

Now we can honestly say that complexity of solution is $$$O(nlog(n)log(max(a))$$$.

$$$\textbf{Challenge}$$$

Can you solve task in $$$O(nlog(max(a))$$$?

We'll suppose(as in 3 tasks before), that the array is sorted. Our operation is equivalent to choosing some $$$1 \le i \le k$$$ and increasing $$$a_i$$$ by $$$k - 1$$$, аnd decreasing remaining $$$a_i$$$ by one. To solve the task, we need to make some claims:

$$$\textbf{Claim 1}$$$

Difference $$$a_i - a_j$$$ $$$mod$$$ $$$k$$$ doesn't change for any $$$i, j$$$. Moreover, in one move $$$a_i$$$ shifts by $$$1$$$ $$$mod$$$ $$$k$$$.

$$$\textbf{Claim 2}$$$

If we've made two sequences of moves of length $$$i$$$ and $$$j$$$, where $$$i < k$$$, $$$j < k$$$, then obtained configurations coincide iff $$$i = j$$$ and chosen colors coincide as multisets(orders can be different, but number of times we've chosen each color needs to be equal).

Proof

Because in one side claim is obvious, we will suppose, that obtained configurations are equal and we'll show that multisets of colors are also equal. Let's define number of baloons, which we've got using first sequence, as $$$b_t$$$ and $$$c_t$$$ for the second. Because $$$b_t \equiv b_t - i$$$ $$$mod$$$ $$$k$$$, $$$c_t \equiv a_t - j$$$ $$$mod$$$ $$$k$$$, то $$$i = j$$$. Let's note that $$$b_t = a_t - i + k \cdot addB[t]$$$, where $$$addB[t]$$$ — number of times we've chosen color $$$t$$$. So, we get that $$$addB[t] = addC[t]$$$ for each $$$1 \le t \le k$$$.

$$$\textbf{Claim 3}$$$

If there is $$$i$$$, such that $$$a_{i + 1} < i$$$, then we'll not make more than $$$i - 1$$$ moves.

Proof

On each move we choose exactly one color, so after $$$i$$$ moves there will be at least one color among first $$$i + 1$$$ that we didn't choose. But then, the number of balloons of this color will be less than $$$i - i = 0$$$, which is not allowed.

Let's call minimum index $$$i$$$ from Claim 3(if it exists) critical.

$$$\textbf{Claim 4}$$$

Suppose critical index is equal to $$$i$$$. Assume, that we decided to make $$$j < k$$$ moves and we've fixed number of choices of each color — $$$add[t]$$$. It's clear, that $$$add[t] \ge 0, add[1] + add[2] + \ldots add[k] = j$$$. Then, there exist correct sequence of moves with this number of choices iff:

$$$j < i$$$

If $$$a_t < j$$$, then $$$add[t] > 0$$$.

Proof of necessity

From Claim 3 $$$j < i$$$. If $$$a_t < j$$$, then we should choose color $$$t$$$ at least one time, so condition 2 is also necessary.

Proof of sufficiency

Let's build this sequence greedily: on each move we will choose such color $$$t$$$ that $$$add[t] > 0$$$ and $$$a_t$$$ is minumum(if we choose color $$$t$$$, then we change $$$a_i$$$ and decrease $$$add[t]$$$ by 1). We will show that this sequence is correct. It's clear that it can be incorrect only if we get that $$$a_p < 0$$$ in some moment. Define $$$x$$$ — number of first move after which we have such situation(we'll suppose that $$$p$$$ is index in the inital sorted $$$a$$$). Note, that because $$$j < i < k$$$, if we've chosen color at least one time, than number of balloons in it will not become negative(because after any move it will be at least $$$k - j$$$). That's why(because $$$x$$$ was defined as first "bad" move) $$$a_p = x - 1$$$. It follows $$$a_p < j$$$, so $$$add[p] > 0$$$. So, we get that we didn't manage to choose color $$$p$$$, and that's why in the initial array we had at least $$$x$$$ colors $$$v$$$, such that $$$a_v \le a_p$$$, so $$$p \ge x + 1$$$. So, $$$a_{x+1} \le a_p = x - 1 < x$$$ — contradiction, because $$$i$$$ is critical index(and $$$j$$$ < $$$i$$$). So we've proved that greedy works and sufficiency is proved.

Using these claims, we can solve the problem if the critical index exists and is equal to $$$i$$$:

Let's iterate through all possible number of moves between $$$0$$$ and $$$i - 1$$$, suppose it's equal to $$$x$$$. Then, by Claim 4 we know that, if $$$a_p < x$$$, then $$$add[p] > 0$$$, else there are no restrictions (except obvious $$$add[p] \ge 0$$$). So, we have arrived to the following problem:

Count the number of nonnegative solutions $$$add[1] + \ldots + add[k] = x$$$, where fixed $$$num$$$ numbers should be positive. By Claims 2 and 4 the solutions of this equation correspond to some final configuration, and this is exactly what we need to count.

This is well known task(stars and bars), answer is given by $$$C^{x - num + k - 1}_{k - 1}$$$

So, the answer is given by the sum of these values over all $$$x$$$.

Let's call configuration $$$\textbf{critical}$$$, if it has critical element (in other words, if there is index $$$i$$$ such that $$$i < k-1$$$ and at least $$$i+2$$$ elements of configuration do not exceed $$$i$$$).

To solve the problem when there is no critical index we need:

$$$\textbf{Claim 5}$$$

If configuration is not critical, then configuration $$$b_i$$$ is reachable iff $$$a_i - b_i \equiv a_j - b_j$$$ $$$mod$$$ $$$k$$$ and $$$b_i \ge 0$$$, $$$a_1 + \ldots a_k = b_1 + \ldots b_k$$$.

Proof

It easily follows by Claim 1 that these conditions are indeed necessary. Let's show, that if configuration $$$b_i$$$ satisfies all conditions, then we can get it.

First of all, let's go from another end. "Backward operation" in our case is to take one of the $$$b_i \ge k-1$$$, substract $$$k-1$$$ from it and increase remaining by one. If we can get this configuration, then by making one more operation we'll get configuration $$$b$$$.

Now let's try to make backward operations, so that $$$b_i$$$ will lie in segment $$$[S, S + k - 1]$$$ for some $$$S$$$. So, suppose that now maximum number — $$$b_{max}$$$ and minimum — $$$b_{min}$$$. If $$$b_{max} \ge b_{min} + k$$$, then let's do backward for $$$b_{max}$$$ all numbers will become at least $$$b_{min} + 1$$$. Doing this we increase minimum by one, so after finite number of operations we'll stop and all numbers will lie in $$$[S, S + k - 1]$$$ for some $$$S$$$.

Because $$$a$$$ is not critical, it follows that $$$a_i \ge i-1$$$ for all $$$i$$$. Then, let's choose color $$$1$$$ and show that after this operation the configuration is critical. Suppose it's not true: so there is $$$i<k-1$$$, such that in new configuration at least $$$i+2$$$ numbers do exceed $$$i$$$. It's not true for $$$i = k-2$$$ because $$$a_1 /ge k-1$$$(in new configuration). For $$$i<k-2$$$ it also can't be true, because if at least $$$i+2$$$ numbers do not exceed $$$i+1$$$, then $$$a_1$$$ will be one of them. After doing operation only these numbers can be not greater than $$$i$$$, but $$$a_1$$$ will become bigger than $$$i$$$. So, there are no more than $$$i + 1$$$ numbers which are at most $$$i$$$, so configuration is indeed not critical.

Note that all numbers decreased by one modulo $$$k$$$. Because we've shown that applying our operation to the "minimum" color leaves configuration noncritical, we can make some shifts before we get that $$$a_1 \equiv b_1 \bmod k$$$. From this will follow that $$$a_i \equiv b_i$$$ $$$mod$$$ $$$k$$$ for all $$$i$$$.

Now, let's try to do the following: if the configuration is critical and $$$a_{max} > a_{min}+k$$$, add $$$k$$$ to $$$a_{min}$$$ and substract $$$a_{max}$$$ by k. We still suppose that the array is sorted, so $$$a_i \ge i-1$$$ and $$$a_k > a_1 + k$$$. Then let's make such sequence of operations: choose $$$i = 1, \ldots, k-1$$$ in this order(it's easy to see that we can do it because $$$a_i \ge i - 1$$$). Now we have such configuration: $$$a_1 + 1, a_2 + 1, \ldots, a_{k-1}+1, a_k - (k-1)$$$. Now, choose $$$1$$$ one more time, so we get $$$a_1+k, a_2, a_3, \ldots, a_{k-1}, a_k-k$$$. It's easy to see, that it's not critical. Indeed, for each $$$i<k-1$$$ no more than $$$i+1$$$ numbers in old configuration were not bigger than $$$i$$$. Note, that $$$a_k$$$ wasn't in this list. $$$k-2$$$ numbers in array didn't change, $$$a_1+k$$$ is surely not in this list and $$$a_k-k>a_1$$$, so number of integers not bigger than $$$i$$$ will not become bigger.

So, that's why we can substract $$$k$$$ from maximum and add it to the minimum, if the difference between them is at least $$$k+1$$$, and configuration will remain critical.

Let's do it as many times as possible. This process will stop, because sum of squares decreases: $$$a_1^2 + a_k^2 > (a_1+k)^2 + (a_k-k)^2 \iff 2k(a_k-a_1) > 2k^2 \iff a_k - a_1 > k$$$, which is true by assumption. So, at some moment we will get configuration whic lies at segment $$$[T, T+k]$$$ for some $$$T$$$.

Note, that for new $$$a_i$$$ and $$$b_i$$$ it's still true $$$a_i \equiv b_i \bmod k$$$, $$$S\le b_i\le S + k-1$$$, $$$T\le a_i \le T + k$$$, $$$a_1 + a_2 + \ldots a_k = b_1 + b_2 + \ldots b_k$$$. Let's show, that from this conditions $$$a_i = b_i$$$ for all $$$i$$$. Indeed, in case $$$S\le T$$$ we get $$$b_i \le S+k-1 \le T+k-1 \le a_i+k-1$$$, but $$$a_i \equiv b_i$$$ $$$mod$$$ $$$k$$$, so $$$b_i \le a_i$$$ for all $$$i$$$. Because sum of $$$a$$$ and $$$b$$$ is equal, it follows $$$a_i = b_i$$$ for all $$$i$$$. Also in other case, if $$$S > T$$$, $$$a_i \le T+k \le S+k-1 \le b_i + k-1$$$, from what we still get $$$a_i = b_i$$$ for all $$$i$$$.

So, doing operations with $$$a$$$ and backward operations with $$$b$$$ we get equal configurations. It follows that $$$b$$$ is reachable from $$$a$$$, the claim is proved.

Now, it only remains to show how to count the number of such $$$b$$$ from Claim 5.

$$$b_1, b_2, \ldots, b_k$$$ should give remainders $$$(a_1+t) \bmod k, (a_2+t) \bmod k, \ldots, (a_k+t) \bmod k$$$ for some $$$t$$$. We сan calculate configurations with such remainders by the following way: remaining $$$a_1 + a_2 + \ldots + a_k - (a_1+t) \bmod k - (a_2+t) \bmod k - \ldots - (a_k+t) \bmod k$$$ are splitted in groups by $$$k$$$ and are distributed in $$$k$$$ elements in any way. So, that's why, for given $$$t$$$ number of configurations(by stars and bars) is given by $$$C^{\frac{a_1 + a_2 + \ldots + a_k - (a_1+t) \bmod k - (a_2+t) \bmod k - \ldots - (a_k+t) \bmod k}{k} + k-1}_{k-1}$$$. Sum $$$a_1 + a_2 + \ldots + a_k - (a_1+t)\bmod k - (a_2+t)\bmod k - \ldots - (a_k+t) \bmod k$$$ can be calculated for $$$t = 0, 1, \ldots , k-1$$$ in $$$O(1)$$$, if we precalculate number of each remainder among $$$a_1, a_2, \ldots, a_k$$$.

That's why final complexity for each of the cases is $$$O(n + k)$$$.

$$$\textbf{Challenge}$$$

Find all typos in proofs.

Tutorial of Codeforces Round #572 (Div. 1)

Tutorial of Codeforces Round #572 (Div. 2)

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/10/2020 21:59:00 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|