WHAT_I_NEED_IS's blog

By WHAT_I_NEED_IS, history, 5 weeks ago, In English,

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

 
 
 
 
  • Vote: I like it
  • +82
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

»
5 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

hab noh ebbiu

nigga you gay

»
5 weeks ago, # |
Rev. 3   Vote: I like it +17 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Wow!

    if you want write your solution if it's faster than mine and i'll edit blog so others can use it

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

What I Need Is WEED

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can u explain C?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    did you under stand part I find a subsequence and make a group?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how to find first 4 than first 8 ans so on?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Have indexes of 0s 1s ... in sets and use upper bound

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          you mean i store indexes of all those 6 numbers in a set?? and then check the sequence?

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            A set for each type of numbers

            read my code you will get what i mean code is neat you will understand it

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      No matter. If you got that part do it and you will get ACC.

      If no i ment get first 0 after that first 1 after that 0 after that first 2 after that 1 and so on.

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Thanks!