What is the reason behind this, if m < a or m < b or m < c?

Thanks, fixed.

Я также подумал, но потом понял, что при входных данных до 2e5 это просто не зайдет на плюсах

Instead of three distinct number you can consider two number a and d(b.c) where a is the least factor of n and d(b.c) is another or greatest factor of n. Then try breaking d into b and c such that a, b and c are not equal. For example 24. Smallest factor is a=2 and another factor is d=12. Further break d into it's own factor b=3 and c=4 such that they are not equal.

Although my approach is a bit slower than editorial's, it is very intuitive. Find all distinct factors of N other than 1 and N. This can be done in O(sqrt(N)). Sort these factors. Run two nested loops over the factors. Outer loop picks the value for A. Now we have to find two distinct factors of N / A. Since the factors are sorted, we can use a two pointer approach and find it in one iteration of the inner loop. The idea is something like this: Let L = 0, R = size of factors array — 1. Repeat while L < R: If factors[L] * factors[R] < N / A, increment L. If factors[L] * factors[R] > N / A, decrement R. If factors[L] * factors[R] == N / A, we have found our answer. Make sure to not use the same factor that was picked by the outer loop.

I also want to know how to solve E.

I think this problem is the most difficult one of all the six problems.

First you have to see that for each column minimum operation have to be calculated now for each column you have to see how much circular rotation is needed for each element in the column now u have the count of each type of cyclic rotation some elements need 1 rotations some 2 etc.. now using this data we can say that n — (count of ith rotation) + i is needed to set the column calculate minimum of this now add minimums of all column

Sry i am bad in explanation

Lets just take a look at only one column. We can rotate the column or modify one elememnt per move.

We should admit that these moves are REVERSIBLE, so it's the same problem as: "We need to rotate the disordered column and THEN modify its element to get the standard column". So we create an array Moves[N] (means if we firstly rotate the column i times, and the total moves we need to get the standard column is Moves[i] , Moves[i] is initally assigned n + i since we suppose that every elements need to be modified), but some elements (for example: element "x") don't need modify IF (x is in the standard column). Thus we need to do Moves[the right the rotating times]--; And the answer for this column is min{Moves[i] (0 <= i < n) } The final result is the sum of each column's answer.

Hope i could help you. qwq.

For E you can divide it into subproblems 1. Solve Each column as an independent entity 2. How to solve? 3. Notice columns are in form of m*i+(j+1), here 0<=i<=n-1, jth column number , remove (j+1) all column are in same form. 4. Each column- Now make a dictionary to count number of elements in that rotation(how far that element is from it's actual position) (you can see in this solution 69363795 ) and first check element is valid or not. now run through the dictionary (d[x]=y) ans = min(x+(n-d[x]), ans) (ans = n initially)

Maybe I am too late to answer, the obvious observation is all columns are independent. Now, to solve each column, you need to find a rotation, which sets most of the numbers at their position and rest will be fixed by modifying. How do we get our best move ? We may have best number for rotations from 0 to n-1, where n is the number of elements in that column. We run a loop from 0 to n-1, and calculate the element required at ith position, in column. Now we need to know, where is this element in original column, and hence the required number of rotation. We store these required number of rotations by each element. Now, if there is a rotation value 2, which appears 3 times, that means, by rotating 2 times, we will get three elements at their position. So if a rotation x appears y times, that means x moves will fix y elements at their position, and we will need n-y moves to fix rest of elements. We need the minimum value for this. That query for original positions of values can be done by storing original values and their positions in a multimap.

In case 1: x = 3 then: if ($$$cnt_0 == k$$$) ($$$cnt_0$$$ declared above) you can take the elements in this $$$set = {0,3,6,9,12,...}$$$ by increasing x or decreasing x. if ($$$cnt_1 == k$$$) you can take the elements in this $$$set = {1,4,7,10,13,...}$$$ by increasing x or decreasing x. if ($$$cnt_2 == k$$$) you can take the elements in this $$$set = {2,5,8,11,14,...}$$$ by increasing x or decreasing x. Suppose $$$y = min(cnt_0 = 5,cnt_1 = 3,cnt_2 = 4)$$$ Obveriously $$$cnt_1 = 3$$$ is the least. then $$$set_0 = {0,3,6,9,12}$$$ $$$set_1 = {1,4,7}$$$ $$$set_2 = {2,5,8,11}$$$ $$$mex(set_0 \cup set_1 \cup set_2) = ((x = 3) \times (cnt_1 = 3) + 1) = 10$$$ So the answer is 10. So at the begining you can consider all elements modulo x.Because this operation has no effect on the final answer Sorry for my bad English

In one move you can choose any element $$$a_i$$$ and change it to $$$a_i:=a_i+x$$$ or $$$a_i:=a_i−x$$$ any number of times only with the condition that $$$a_i$$$ never becomes negative. If you have an element of the form $$$kx + c$$$ in which $$$0 \leq c < x$$$, it could change to $$$c, x + c, 2x + c ... (k-1)x + c, kx + c, (k+1)x + c$$$ and so on. For example, if you have $$$0$$$ as an element, then, it can stay at $$$0$$$ or change to $$$x, 2x, 3x$$$ and so on. As a consequence, in this particular case, all the numbers $$$a_i \equiv 0 (mod x)$$$ can take the place of any of them. In general, if $$$a_i \equiv b (mod x)$$$, you can change that $$$a_i$$$ to any number that has the same remainder $$$b$$$ after dividing it by $$$x$$$. So your $$$mex$$$ start with the number $$$0$$$ because the first number you need. Then, on each query you are going to add on an array one more element with the remainder that the number of that query has. Let's suppose you are still in $$$0$$$ and you read a number whose remainder is $$$0$$$, you decrement the frequency in your array with index $$$0$$$ by one and while your $$$mex$$$ can increase, you repeat that before going to the next query because you can have many numbers with remainder $$$1$$$, $$$2$$$, even until $$$x-1$$$ that can increase the $$$mex$$$. The time complexity is $$$O(n)$$$ because there will be at most $$$n$$$ times in which you could substract one to the frequency of a remainder in the array.

check this link

You can check that the optimal answer always goes through the midpoint of diameter

Update: What I am writing is serious! Not for joking

proof by contradiction .Suppose take any three paths not involving the diameter .Then take the diameter and connect one of the vertices of diameter with vertex on three paths and take one of the branch .Since the branch left has length shorter than the diameter hence contradiction .

Hi can you please explain what maximum here means? maximum distance node in each subtree?

Link : This isn't too detailed, but you get the gist.

It would also be interesting to see that we can also do multi-source shortest path using Djikstra's, for which I have a gfg link : Link

just like dp finding diameter of tree

https://mirror.codeforces.com/contest/1294/submission/69449118 You can view my code.

dp[i]->the i-th vertex is the root,and choose the vertex as a/b/c,another two is under the i-th vertex.

dp[i]

=max(

dp[j]+1 there is a path between the i-th vertex and the j-th vertex ,

the biggest two deep[j] + 2 deep[j] is the number of paths between j and i

)

You can change the i-th vertex to its kids,and update the value in O(1)!

Total complete in O(n).

because you have to find maximum no. of unique edges between a-b, b-c, and c-a. so, if your diameter have n-1 edges then you can pick any vertex, but if less than n-1 then you have to find 3rd vertex in order to make unique edges maximum.

Means that particualr aij value does not fit in the jth that column, aij value must be change in that case

It is because all numbers in the j-th column must have j as a reminder when divided by m. It's clear to see why this is true looking at the image in the problem. So, numbers that don't have this property don't belong to the j-th column, therefore there's no cyclic shift that will put them in place because they don't belong to that column.

For dist == n, your code is printing YES two times

Oh, I got it. You just have to root the tree and for each node check if this node is the node with degree = 3 in the answer. (in case that the tree has no node with degree >= 3 we can just print two nodes with degree 1 and another arbitrary node).
For each node u with degree >= 3 we will maximize between the two following cases :
1- sum of the maximum length of a path to a leaf passing through 3 different children of u starting from u (if has at least 3 children)
2- sum of the maximum length of a path to a leaf passing through 2 different children of u starting from u and the maximum length of a path going to a leaf from parent of u starting from u (if u has parent)
Of course we need to maintain the leaves that give us optimal answer.

This is a good question.

What we are doing at the moment is calculating the cost for all $$$n$$$ rotations.

I think we would do the same thing except that we would calculate the cost for all $$$2n$$$ rotations.

We can try an exchange argument.

Suppose we have chosen 2 nodes $$$u, v$$$. If $$$u, v$$$ lie on the diameter, then we can extend $$$u, v$$$ to the diameter ends and get a larger answer.

If $$$u, v$$$ do not lie on the diameter, then we can get a bigger answer by choosing the diameter. (Since the definition of the diameter is the two nodes who are furthest apart.)

Could you explain your approach or intuition behind your solution too?

great solution !!!!, I saw this problem in another way : you can check my solution here : 200922897

my approach: Without loss of generality let's a < b < c; let's see how much a (the min of three) can grow! , it's obvious that the maximum of a will be less than ∛n; now let's see b , b will be a < b < X; let's see what is X; we already fixed a , so with b and c , we need to make n/a

so b must be < √(n/a) and c in the other part ! complexity is less than 1e8 -> it passes

but your solution is much better!

Sorry for necroposting, but same approach! Here's the implementation in case anyone's wondering: My submission

https://mirror.codeforces.com/blog/entry/73274?#comment-575441

I'll tell you a simple solution, which might give you an intuition

$$$a + A = k$$$ (some value)

$$$b + B = k$$$

$$$c + C = k$$$

add all these three equations

$$$a+b+c+(A+B+C)= 3*k$$$

$$$a+b+c+n= 3*k$$$

$$$\frac{(a+b+c+n)}{3}= k$$$

So check if $$$(a+b+c+n)$$$ is divisible by $$$3$$$

now $$$k= \frac{(a+b+c+n)}{3}$$$ and since

$$$a + A = k$$$ this implies $$$k-a=A$$$

$$$b + B = k$$$ this implies $$$k-b=B$$$

$$$c + C = k$$$ this implies $$$k-c=C$$$

Since the above 3 should be +ve, check if $$$k > max(a,b,c)$$$

So effectively check 2 things

1. if $$$(a+b+c+n)$$$ is divisible by $$$3$$$

3. if $$$\frac{(a+b+c+n)}{3} > max(a,b,c)$$$