Hi

We have a problem on a tree.

Imagine order of our algorithm is:

Sigma x(i) ^ 2

That if we define sz[v] as number of vertices in subtree of v, x(i) is number of different sz[u] between v's children.

It's easy to see it's O(n * sqrt(n)).

But after this submission for problem 1179D I saw it was realy fast and now I think it might be better than O(n * sqrt(n)).

Any idea?

Thanks from 300iq we got that it's O(n.lg(n)) and after that by dragonslayerintraining smart proof we got it's even O(n.lg(lg(n)).

But even after these proofs I wasn't done so after running the code on problem 1179D in gym and lots of random tests the largest

Sigma x(i) ^ 2 I could find was 1032859 for n <= 500,000 (about 2 * n or n.lg(lg(n)) / 2) so now I think O(n.lg(lg(n))) might be best

order we can proof for this algorithm, how ever some one might proof it's some thing better like O(n.log*), O(n) or...

Hi friends it's not a professional Editorial I just wrote it myself and i hope it can help you.

A: you see the only way we can decrease number of prime factors 2 is to divide n by 2, and the same for 3 and 5;

so for decreasing prime a factor 5 we have to use operation 3 and after that two times operation 1.

for decreasing prime a factor 3 we have to use operation 2 and after that operation 1.

so if we define f(x) to be number of prime factors x in n answer will be f(2) + 2 * f(3) + 3 * f(5);

my_solution

B:

for each query let cnt[x] (0 <= x && x < 3) be number of elements like y that y mod 3 = x. then easily we can prove that we chould not do anything with numbers divisible by 3. and for cnt[1] and cnt[2] we can merge min(cnt[1], cnt[2]) this operation "merge a number x(x mod 3 = 1) with a number y(y mod 3 = 2)" that these make numbers divisible by 3 again and for remaining numbers that all are equal mod 3 if they are x elements we can make [x / 3] numbers divisible by 3 with them

my_solution

C: imagine numbers arr [0, 1, 2, 3, 4, 5] now each round find first 0 1 2 3 4 5 as a subsequence greedy this way "find first 0 after that first 1 and so on" then put them in a group and don't use them in next rounds.

whenever you couldn't find any new subsequence you must delete all remaining elements

my_solution

D: first of all let's call prime numbers in a type_1, others in a type_2, and primes in b type_3, and others in b type_4

now let's solve problem recursive see biggest number(x).

if it is prime it's type_3 cause for each i (i >= 2) Pi > i so if it's type_1 we should have a bigger prime in our numbers that it is not true. so now delete x and y(that P(y) = x) and solve remaining elements recursive.

else it's type_2 cause if it's type_4 imagine it's type_2 so we have inserted x / y that (y > 1) in b that it's false cause x is biggest number. so now delete x and y(maximum divisor of x that is smaller than x) and solve remaining elements recursive.

my_solution

E: let's make a dfs and solve problem with dfs tree.

these tree is bipartite and as we have n >= 2 for each vertex v, d(v) > 1 so if we choose any of these parts we will have condition that we need.

now let's choose smaller one.

my_solution

F:

I suggest you read my_solution for problem F(Destroy it!). I have dp[N][10] that dp[i][j] is maximum sum if we have get x cards from first i round and x mod 10 = j. and it's easy to see that in each round we may use only 3 strongest card that cost 1, strongest card cost 2 and strongest card cost 3 so by a mask on these(at most 5)cards you can update dp easily.

I HOPE IT WAS USEFUL FOR YOU :)