### diegorpc's blog

By diegorpc, history, 3 years ago,

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

• 0

 » 3 years ago, # |   0 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, # ^ |   0 Can you explain?Bcz block size is for Queries.So how it is related to freq
 » 3 years ago, # | ← Rev. 3 →   +8 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 →   0 Thank you, ista2000. I got acc using this trick. I will write this trick in my notebbok :P!
•  » » 3 years ago, # ^ |   0 Nice
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 @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, # ^ |   0 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, # ^ |   0 never seen a person naming a variable "_" !!!
 » 3 years ago, # |   0 You can also try with ceil (sqrt (n)) . It worked for me . @gaurav172 taught me this .
 » 3 years ago, # |   0 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, # |   0 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
 » 7 weeks ago, # |   0 After using ios_base::sync_with_stdio(false); it worked, lol!