Codeforces Round #670 (Div. 2) Editorial

Let us store the count of each number from to in array .

Now would be the smallest for which .Let this be . would be smallest for which . This is because one count of each number less than would go to therefore the element which was present initially once would now not be available for .

Overall Complexity: .

First, if all numbers are less than , then you should print the product of the five biggest numbers of them.

Otherwise, the maximum product must be non-negative. Sort the numbers by their absolute value from big to small.

If the first five numbers' product is positive then print it. Then we can always change one of the five to one of the other numbers to make this product positive. Enumerate which one to replace, and you can solve this problem in time.

Let vertex be the root of the tree. If there is only one centroid, just cut any edge and link it back.

Otherwise there are two centroids. Let them be and , then there must be an edge connecting and . (If not, choose any other vertex on the path from to and the size of the largest connected component after cutting it will be smaller than and ).

Let be 's father. (If not, swap and ) Then just cut a leaf from 's subtree and link it with . After that, becomes the only centroid.

Proof: It's easy to see that the size of 's subtree must be exactly . After cutting and linking, the maxinum component size of becomes while the maxinum component size of is still .

Since sequence is non-decreasing and sequence is non-increasing, we need to mimimize .

Now observe that if then and .Else if then but . Now we calculate .Let this sum be . Now lets assume is . So then is .And as observed before .

Now we just need to minimize . Now it is easily observable that should be .

For the changes, since we only need to know , so only and will change.

Total time complexity: .

If we know what prime factors x has, we can find just using bruteforce.

To find the prime factors, we can just do for every prime in ascending order, meanwhile calculate the numbers there supposed to be without , if it differs with the number the interactor gives, then contains the prime factor .

This way, we can find every prime factor except for the smallest one.

Let be the number of primes no greater than .

Then we can split the prime numbers into groups.

After finishing asking a group, ask and check if the return value same as it supposed to be without . If it's the first time finding it different, it means the smallest prime number is in the range, then just check every prime numbers in the range by asking .

After finding the prime factors, for each factor, ask , it can be proved this step will be done around times.

The total number of operations if around , the total time complexity is