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!!!

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

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

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

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:

1. $$$j < i$$$

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

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

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.