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

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

$$$\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**

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

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

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

$$$\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**

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.

Oh my god I overcomplicated A...I'm so bad at this :(

haha same

Hahahaha i too that sad :(

Don't feel bad, I've been years overcomplicating problems too hahah, anyway experience will be there for you next time.

I have hilariously over complicated the solution.

Please have a good laugh at my expense.

LOL XD

But, I loved solving the problem :)

Now the question is very sad, coz it didn't deserve this much hard-work..loll

Thanks for the fast editorial!

Hello I had a doubt from problem C I tried to solve the question using basic recursion that is give n l and r i combined the adjacent elements into one and storing the resultant array in another array and counting the number of elements greater than 10 and finally I repeated the process for the resultant array so the time complexity of my solution would be O((n+n/2+n/4...)*q)in the worst case which is a solution with quadratic time complexity so the processor would take 10^5*10^5=10^10 computations to solve it but the time limit is of 2 seconds that means I can do 2*10^18 computations which is much higher than my solution, but I am getting TLE in case 9 can you give any suggestion?THanks In ADVANCE!!!

Amazingly Fast.

My solution for problem E works in time $$$O(k+C)$$$ where $$$C$$$ is maximal element, not the sum of elements.

I need one more lemma: for every possible configuration there exists a sequence of action in which we do not increase the number of balloons with one particular color (and it is easy to see that the number of operations with each color is uniquely determined).

So we can count number of sequence of such actions. Try all possibilities of length of such sequence, it is bounded by $$$C$$$. Then do thing similar to editorial, but now both parameters of binomial coefficients are bounded by $$$k+C$$$.

You can see the submission here: 56582671

Cool one :)

Hello, I had a doubt from problem C I tried to solve the question using basic recursion that is given l and r I combined the adjacent elements into one and storing the resultant array in another array and counting the number of elements greater than 10 and finally I repeated the process for the resultant array so the time complexity of my solution would be O((n+n/2+n/4...)*q)in the worst case which is a solution with quadratic time complexity so the processor would take 10^5*10^5=10^10 computations to solve it but the time limit is of 2 seconds that means I can do 2*10^18 computations which is much higher than my solution, but I am getting TLE in case 9 can you give any suggestion?THanks In ADVANCE!!!

Pretty interesting! Solved C via Segment Tree :)

help!

My submission using segment tree

I also tried using segment tree but had to use 2 segment trees depending on query l, r if l is even or odd Link can you please help me as test case it is failing on is pretty huge.

can u plz.. explain the solution using segment tree.. i am new with segment tree that's why i can't understand ur solution.. thanks.

whole point of segment tree is merging two nodes into one,so this data structure is perfect for this problem. Observe the merge of nodes where 'node' is current node '2*node' is left child '2*node+1' is right child Recursively both child added and their sum is stored in parent.

in the parent, is sum of node is stored or sum of candies is stored.. thanks for the reply....

Thanks now i understand that segment tree is doing the same thing as out dp presum doing

I am afraid that your solution may do the same work as the O(n) magical solution in the tutorial. Your segment tree actually save the sum of intervals since 'sum' is the part which is moduled by 10 and 'candy' the part divided by 10. And this can be done by a PRESUM array in the complexity of O(n). Besides, if the given array has elements bigger or equal than 10, then neither your solution nor the magical solution will do.

Yes us r write presum is easier than segment tree in implementing but how can u say that is digit is greater than 10 then none of the code will work?? can u give some proof.

is dp solution work?? if work can u plz explain me the dp solution.. thanks!!_

First, calcucate the pair(remainder,candy) of intervals with fixed length in advance. say, length of $$$1,2,4...2^k$$$. There are logN types of length to calcuate, and the number of intervals with length $$$t$$$ is $$$n-t+1$$$ . So we refer to the complexity as O(nlogn) .

To give an example, if we have the array [9,6,7,8],we should do as follows:

length1: [(9,0),(6,0),(7,0),(8,0)]---->{1}{2}{3}{4}

length2: [(5,1),(3,1),(5,1)]---->[1,2],[2,3],[3,4]

length4: [(0,2)]---->[1,4]

If you are familiar with dynamic programming, you can easily figure out the dp formula.

Given length and the left end, you can deal with any query in O(1).

DP can deal with problems of this type in a more general way without such strict constraint "digits are less than 10".

"digits greater than 10" is not a proper example. I was trying to demonstrate that if there are different constraint conditions, the solution based on Interval Subtraction Propert（the magic and segment tree） will no longer work.

Say, if the problem is fixed as follows:

After a combination of two neighbouring digits, the new value is no longer $$$(x+y) \mod 10$$$ but $$$((x+y)*2+3)\mod 10$$$ , then dp is the only way(maybe not, as long as it has some property) to solve this problem in O(nlogn).

Thanks.. for great explanation .. amazing..

http://codeforces.com/contest/1189/submission/56576073

I don't want a link. I can find it myself. I need an explanation.

Hello I had a doubt from problem C I tried to solve the question using basic recursion that is give n l and r i combined the adjacent elements into one and storing the resultant array in another array and counting the number of elements greater than 10 and finally I repeated the process for the resultant array so the time complexity of my solution would be O((n+n/2+n/4...)*q)in the worst case which is a solution with quadratic time complexity so the processor would take 10^5*10^5=10^10 computations to solve it but the time limit is of 2 seconds that means I can do 2*10^18 computations which is much higher than my solution, but I am getting TLE in case 9 can you give any suggestion?THanks In ADVANCE!!!

On problem C, Isn't it suppose to take always a pair and then replace it with mod of sum of them? If I use this array: [110 120 130 140], I take 2 pairs (110, 120) and (130, 140), it's obvious that I got 2 candies, but, when I replace them the array now is [0 0], so I only take 2 candies. If I use Editorial's claim I got 50 candies. I think I can't understand the problem, can anyone help me with this doubt?

Numbers are digits, i.e. they can't be larger than 9

Thanks bro, now I get it!

Read the constraint carefully

Yeah lol, even i didn't read the constraints and ended up using sparse tables.

I liked the DP solution for problem C as it can be applied to any function rather than modulo.

I did the challenge for Div 2 B in the contest. It's O(n) if I'm not mistaken. https://codeforces.com/contest/1189/submission/56577088

Your solution's complexity is O(nlog(n)) as you have sorted the whole array.

I wonder how most people prove their solutions to 1189D1 - Add on a Tree instead of knowing how to construct the solution(1189D2 - Add on a Tree: Revolution)

For each pair of leaves (say $$$i$$$ and $$$j$$$) let $$$x_{ij}$$$ denote an operation performed on the pair. It is obvious that we need not choose a pair twice, since we can combine them to a single one.

We can show that if none of the nodes have degree 2, then the value of each edge, expressed as an equation will be different. (Every edge, splits the leaves into two sets, and the value of the edge will be $$$\sum{x_{ij}}$$$ (for every pair of leaves i, j such that the edge belongs on the path from i to j)

We will then have $$$n-1$$$ equations and $$${L}\choose{2}$$$ variables. We can also show that if all non-leaf nodes are of degree $$$\geq$$$ 3, then $$$L$$$ (the number of leaves) is atleast $$$(n+2)/2$$$. Hence the result follows.

However, forgiving my poor english , even if there are infinit variables ,i cant prove that the variables of every equation are different.

It should also be noted for completeness that each edge has a unique summand, otherwise we cannot claim the system of equations has a solution only based on the number of variables and pair wise independence(Actually having a unique summand is sufficient condition for there being a solution).

What if x is odd in the proof of D1 ?

In D1, x is

realnumberplease explain problem c magic solution

For [ 9, 8, 5, 6 ]:

9 + 8 = 17. we have digitsum = 7 and candy = 1

5 + 6 = 11. we have digitsum = 1 and candy = 1

In the next step, we have 1 + 7 = 8 and no extra candy

but in each step, we're adding the candies, 1 + 1 = 2. Notice, we don't mod this by 10 or change it in any other way.

It's basically the same as doing:

we can get sum(l,r) = candy * 10 + sum in this way

and bob's your uncle

Another approach for Problem C is using Segment Trees, it was very interesting.

Yeah I know about that , but still wondering how this magic thing is working

Because The No. are in range b/w 0 to 9.

can you elaborate

What actually we are doing is that we are counting the number of times our sum exceed 10 and we make it sum%10 i.e count it as 1 and then leave the remainder to contribute further to the sum. (It can be also seen as subtracting 10 from the total sum and count it as 1 for the answer) So our problem broke down to the number of times we can subtract 10 from the sum of the range. This can be achieved by taking sum of the whole range and then answer = sum/10. That's the magic solution using prefix array.

Problem C can be solved using Segment Tree.

in the challenge of problem E, if x = y (mod p) => (x + y) * (x ^ 2 + y ^ 2) = 4 * x ^ 3 (mod p) and then what you have to do is first for each number you must check if its cube mod p = k * inv (4) and if the number of equals to it is

c, then the solution is incremented by c * (c — 1) / 2, afther this check, do the same thing when they are different but with the array after eliminating the equalsYour solution should be correct. We need to proceed this way because for $$$a_i=a_j$$$, we cannot multiply both sides by a $$$0$$$ in the given equation.

Else, add x on path vl and −x on path ul. but u and v are not leaves ?

Read the proof of sufficiency! :)

thanks for challenges)

Hi, for problem "Add on a Tree: Revolution", why can't we just output the input? I mean, for example 1, isn't rewriting the input is exactly the way it can be constructed?

the only operations allowed are choosing two leaves and do the operations on them ,while in the input given the edges are not always between leaves

I have done the challenge of div.2 B but I'm in a hurry so that I cannot check if it is right. It looks like the complexity is O(n), maybe somebody could check it for me?

Here is my code

OK, here is the explanation of my thoughts:

First, deal with the three largest numbers as the tuterial mentioned, put them at the rear, then the problem is how to arrange the other numbers.

if we calculate a value $$$k_i$$$ for every $$$a_i$$$ such that $$$2^{k_i}{\leq}a_i{<}2^{k_{i}+1}$$$, we can make sure that for any three $$$a_i$$$ with the same $$$k$$$, one number plus another is always larger than the other one. Therefore, we can find all the $$$k_i$$$ at first and put all the $$$a_i$$$ with the same $$$k$$$ together. As for $$$a_i$$$ with different $$$k$$$, since the number with larger $$$k$$$ is also larger, so we can arrange $$$a_i$$$ with smaller $$$k$$$ first, then the number with larger $$$k$$$. Besides, for every $$$a_i$$$ with the same $$$k$$$, the smallest should always be arranged at first to make sure the number after it is greater or equal to it.

The complexity of finding the three largest numbers is $$$O(n)$$$. All the $$$k_i$$$ can be found using binary search, so the complexity of calculating all the $$$k_i$$$ is $$$O(nloglog(max(a)))$$$. As to finding all the smallest $$$a_i$$$ with the same $$$k$$$, the complexity is $$$O(n)$$$. Therefore, the total complexity is $$$O(nloglog(max(a)))$$$. Since $$$max(a)$$$ is $$$10^9$$$, I think it is very close to $$$O(n)$$$ already.

Here is my code that was updated.

i cant understand the solution to D ,who can help me please.

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 ulhow to add x on path uv or −x on path ul

Can Some explain

Problem D.I am not able to understand what is it saying.for problem D1, for n>=4 you just have to find any node having only 2 members. If there exixt such a node, the answer is NO otherwise YES. You can see here (https://codeforces.com/contest/1189/submission/56606643)

I am not asking about solution i am asking about Problem. What's problem is saying can you explain what it's saying

you have to find whether it is possible to have different numbers on different edges or not.

can someone please help me out I am doing coding since last one year but I am the same condition which I was one year. In each contest, I am able to solve at most one problem. Please, someone, help me out and how to improve myself.

Solve problems of topics you're not comfortable with or you can start solving a2oj ladders to get used to solving problems of varying topics.

Can anybody explain div 2 B, I cant understand the tutorial given, why to just check a[n] >= a[n-1] + a[n-2]

a[n] neighbours are a[n-1] and a[0] right? So just how we can come to this conclusion to just check the above condition in case of sorted list/array. And how solution becomes an−2,an,an−1,an−4,an−5,…,a1 (if sorted)

because after sorting (an) now is the largest number if we could find 2 numbers their sum is strictly greater than an then there is answer and of course the numbers that could do this will be (an-1) and (an-2) then all numbers except (an) will have a neighbouring number which is greater than or equal to it so the sum of its neighbours will of course be strictly greater than the number and since (an) is fine then we are done

can anyone explain me the solution of C using dp.. I didn't understand from editorial!! thanks..

On Add on a tree: Revolution, can we just add a value x on an edge and keep it as we move downwards? For example, if we have the nodes u (parent) and v and also v has a child c, can we add the required value x to the uv and then on the vc subtract the $$$x - x_{vc}$$$? In such a way, we obtain the desired value (ie. $$$x_{vc}$$$).

Thanks!

sir , IN COUNT PAIRS why did we assume ((a^4)-(k*a))%p is equal to k%p ??? also k is function of ai and aj ,it will vary everytime . please clarify

k is a constant given in the problem, it will not vary. and he did not assume this he said that :(ai+aj)*(ai^2+aj^2) ≡ k mod p so we want (ai+aj)*(ai^2+aj^2)=k when both taken modulo p and after multiplying both sides by (ai-aj) and simplifying both sides we reached to (ai^4-aj^4)=ai*k-aj*k which is equivalent to aj^4 — aj*k=ai^4-ai*k

thanks ,but it looks complicated ,can you tell me ,which math concept is being used here ... i will try to study that

you are welcome.he only used the congruence in modular arithmetic and simple math to simplify both sides of the equation

In editorial of div2 F it was assumed that the array is sorted and problem was solved. How does it apply to unsorted array? Am I missing something ?

The answer doesn't depend on the order of elements in the array

Oh my bad! Thanks a lot for reply!

can anyone explain me the solution of div 2 E given in the editorial.

we want (ai+aj)*(ai^2+aj^2) ≡ k mod p so we want (ai+aj)*(ai^2+aj^2)=k when both taken modulo p now multiply both sides by (ai-aj) and since all elements are different we are not multiplying by zero(ai-aj!=0) now we have : (ai-aj)*(ai+aj)*(ai^2+aj^2)=(ai-aj)*k ,which is equivalent to (ai^4-aj^4)=ai*k-aj*k then for each ai we want this equation to hold aj^4 — aj*k=ai^4-ai*k so we search for the number of aj s that satisfy this equation

but how he deduce that we have to find the number of pairs of equal numbers in the array bi=(a4i−kai) mod p .

for each number we find b=(ai^2-k*ai)%p and count how many numbers in the array have (aj^2-k*aj)%p equal to b also and he deduced that as i wrote in the previous comment

thanks i got it .

you are welcome :D

Can someone explain why submission(56622740) got TLE, while sparse table got accepted 56626183 for div2C

Is the script for add on tree's proof part is broken or is it not loading just for me?

Yup, seems broken!

Please Somebody help me with problem B. Couldn't understand how they came up with this sequence.

Check this https://codeforces.com/blog/entry/68079?#comment-525325

I think in the proof for Add on Tree, "Proof of necessity" and "Proof of sufficiency" are swapped

244mhq

By any chance, is there a solution to Div1. A2 (Tree: Revolution) using gaussian elimination or is the challenge solvable using it. As we can have variables $$$x_{ij}$$$ for operation using

`leaf i`

and`leaf j`

and then we can formulate $$$n-1$$$ equations corresponding to each edge.Please confirm if I am correct. And if it is indeed solvable using Gauss method, the complexity will be $$$O(n^3)$$$, isn't it ?

I suspect the problem you'll have with Gaussian elimination is that it won't necessarily give you an

integersolution. Also you have $$$O(n^2)$$$ variables (one for every pair of leaves) so I think it will be more like $$$O(n^4)$$$.If there are $$$O(n^2)$$$ variables, why is complexity $$$O(n^4)$$$ and not $$$O((n^2)^3)$$$ or $$$O(n^6)$$$?

Because there are only $$$O(n)$$$ equations (one per edge), so you'll only need to pivot $$$O(n)$$$ times, and each pivot will take $$$O(n^3)$$$.

Yea so it seems a fit for solving the challenge part as the editorialist mentioned "the numbers on each edge need not be integers".

However, the $$$O(n^4)$$$ is not feasible for such constraints in case we want to apply Gaussian elimination.

How exactly and efficiently would you solve the challenge part, then?

SpoilerFor the challenge, first try to make all the numbers even (working backwards towards all being 0). The sum of weights adjacent to an internal node cannot change parity, so if it's odd for any internal node then the answer is NO. Otherwise, root the tree at some internal node, and work top-to-bottom to make the edges below each node even. If a node has two odd child edges, add +1 to a path that runs through them.

Now you have all edges even, for which we already have a solution.

I think the complexity is $$$O(n)$$$, but I haven't thought about all the details.

Hi, can someone explain in more detail how to compute dp[last][cnt] in div2F (Array beauties)? I still don't understand how this is computed and optimized despite thinking about the editorial code for awhile. Also, is this a standard dp problem and can anyone suggest any related problems? I noticed that a lot of red coders solved this question very fast. Thanks.

Thenks for the typos!

in B problem's editorial, challenge is what will happen if there would same numbers in array. i can't find what will be changed. i think ans should be same as 2 numbers can be same but theirs indexes would be different. so... i am confused. please someone help me.

.

My solution to the challenge presented in Div1 B's editorial:

Solution (click to view)If we were to run the algorithm despite the fact that not all $$$a_i$$$ are neccessairly different, the only issue is that we will count pairs that satisfy $$$a_i = a_j \text{ & } (a_i + a_j)(a_i^2 + a_j^2) \not\equiv k \pmod p$$$

We shall maintain an additional std::map that will count how many times each value appeared, then after we finished running the original algorithm for all entries in the additional count std::map that we filled with the values' count $$$(x, cnt)$$$ if $$$(x + x)(x^2 + x^2) \not\equiv k \pmod p$$$, then all pairs of $$$(x, x)$$$ are not valid & we counted them, so we should subtract from the answer the number of such pairs, which is exactly $$$cnt \choose 2$$$.

Complexity is still $$$O(nlog(n))$$$.

3

2 to 3 val= -1.5

2 to 4 val= 2.5

4 to 3 val= 2.5