Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

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!

Keanu Reeves

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)$$$.

code

Number circle

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))$$$.

code

$$$\textbf{Challenge}$$$

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

Candies!!!

Solution 1 (magic)

Solution 2 (dp)

Add on a tree

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

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$$$ &mdash; 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

Count pairs

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))$$$.

code

$$$\textbf{Challenge}$$$

Solve the task, if numbers are not necessarily different.

Array beauty

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$$$?

code

Make equal

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$$$.

Not so long proof

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

code

$$$\textbf{Challenge}$$$

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

Problem from Red Panda.

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$$$.

Not so long proof

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$$$.

Long proof

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)$$$.

code

$$$\textbf{Challenge}$$$

Find all typos in proofs.

Full text and comments »

244mhq's blog

Keanu Reeves

Number circle

Candies!!!

Add on a tree

Count pairs

Array beauty

Make equal

Problem from Red Panda.