M.A.H.M.O.O.D's blog

By M.A.H.M.O.O.D, history, 7 years ago, In English

Hello everyone.

I've been trying to solve this problem 455D - Серега и веселье but I keep getting RE on test case #9.

I don't know what's wrong with my code could someone please help me in figuring out what's wrong or atleast give me a test case where my solution breaks ??

Here's my submission : 27468511

Thank you very much for reading.

:)

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

could you please explan you're approach i didnt understand it

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    My idea is to divide the array to sqrt(n) blocks then do the following:

    For the first type of queries traverse the sqrt(n) blocks and shuffle the numbers between them that would result in a total of O(sqrt(n) * sqrt(n) * log(sqrt(n)) = O(n * log(sqrt(n)) complexity the first sqrt(n) is because of traversing the sqrt(n) blocks, second is because we have to insert a new element in the beginning of each block and remove one at the end of it and the log factor comes from updating the occurrences map in each block.

    For the second type of queries I keep a map of occurrences in each block so I just have to traverse each block and see what is cnt[k] in each one which will result in O(sqrt(n) * log(sqrt(n)) complexity the sqrt(n) comes from traversing the blocks and the log(sqrt(n)) comes from looking up cnt[k].

    Of course what I said doesn't apply for the first and last block in each query (I calculate those naively)

    I hope that this was understandable if not please reply so I could elaborate further.

    :)