Editorial by me for you (Div3 round 565)

Revision en3, by Mahdi_Hajibeygi, 2019-06-10 18:01:11

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);


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

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

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.

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.


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.



  Rev. Lang. By When Δ Comment
en7 English Mahdi_Hajibeygi 2019-06-10 21:25:44 148
en6 English Mahdi_Hajibeygi 2019-06-10 19:14:11 370
en5 English Mahdi_Hajibeygi 2019-06-10 18:31:12 0 (published)
en4 English Mahdi_Hajibeygi 2019-06-10 18:18:14 101
en3 English Mahdi_Hajibeygi 2019-06-10 18:01:11 59
en2 English Mahdi_Hajibeygi 2019-06-10 17:56:09 17 (saved to drafts)
en1 English Mahdi_Hajibeygi 2019-06-10 17:44:39 2546 Initial revision (published)