diegorpc's blog

By diegorpc, history, 3 years 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

»
3 years 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.

  • »
    »
    16 months 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

»
3 years 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)

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

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice

  • »
    »
    2 years 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.

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

      You will traverse the groups in this sort of pattern:
         /\       /
        /   \    /
       /     \  /
      /       \/
      Instead of this one:
         /|   /|   /|
        / |  / |  / |
       /  | /  | /  |
      /   |/   |/   |
      Thus if you count each dash as one iteration, you can easily see you would need approx. twice the number of iterations, which on a tightly time bound problem such as this one would lead to a TLE.

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

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

»
3 years 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 .

»
3 years 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

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

In my opinion, this is possible to resolve with Mo's Algorithm but C++ is not a good choice to implement an abstract solution. In some case, you need to use a big vector or Array to get store the frequency but in this case is possible to use a hash map. Unfortunately, the implementation of the C++ map is very bad. Maybe Java can be faster than C++ in this case.

Anyway, this is my solution, that uses pure Mo'a algorithm https://codeforces.com/contest/86/submission/103715846

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

After using ios_base::sync_with_stdio(false); it worked, lol!