diegorpc's blog

By diegorpc, history, 21 month(s) ago, In English,

Hi guys

I was solving the problem 86D — Powerful Array using Mo's algorithm. But I get TLE.

Someone can help me?

My solution

Cod
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

block = sqrt(n), should be block = sqrt(maxn) in this case, as you are reasoning on the frequency of each element on the array, not the array it self.

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

    Can you explain?Bcz block size is for Queries.So how it is related to freq

»
21 month(s) ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

Also, I learnt this thing from teja349: If L1 and L2 lie in the same block, you check the parity of the block. If the parity is even, then you sort according to increasing R or else you sort according to decreasing R. This reduces runtime to half and is quite enough to get AC on this problem.

My AC submission using this trick: http://codeforces.com/contest/86/submission/28243471 (Sorry for the incredibly ill-named variables)

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank you, MagicPotato. I got acc using this trick. I will write this trick in my notebbok :P!

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice

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

    @MagicPotato can you please explain why "if the parity is even, then you sort according to increasing R or else you sort according to decreasing R" would reduce the runtime to half ? Thanks in advance.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    never seen a person naming a variable "_" !!!

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can also try with ceil (sqrt (n)) . It worked for me . @gaurav172 taught me this .

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

your update function can be optimized to run much more efficiently. I tried this in java and on 9th attempt got it to work.35944895 3 methods. solve, add and remove to make it work. add()/ remove() is where the trick lies