Блог пользователя Mahdi_Hajibeygi

Автор Mahdi_Hajibeygi, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • +82
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

If there is any problem (except that it's too short) tell me to fix it that others can use better blog.

or if you have better solutions for any problem tell me.

»
6 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

you forgot to mention contest code "565(Div3)" in the title. btw thanks for editorial

»
6 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Auto comment: topic has been updated by Mahdi_Hajibeygi (previous revision, new revision, compare).

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

hab noh ebbiu

nigga you gay

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

my_solution for problem F dp[N][10] :| O(N)

»
6 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

What I Need Is WEED

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can u explain C?

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Thanks!