ekzhang's blog

Help! Attempting to optimize Mo's Algorithm leads to TLE on case 5?!
By ekzhang, history, 8 years ago, In English

Hi, I am currently trying an O(n(sqrt n)(lg n)) to problem 375D using Mo's Algorithm and a Fenwick Tree. My initial solution got a time limit exceeded on test case 53, so I tried to optimize it.

To optimize, I made a couple of changes to my check() function, that is called every time the Mo's Algorithm window is slid 1 tree node. I was thinking that this would make the algorithm run faster since check is the part that is run the most (n^1.5 lg n times).

My second submission didn't end up working. In fact, somehow, my new submission got TLE on test case 5, which the previous code could solve in 150ms!

Can someone help me figure out what could've happened that would make this attempted optimization run 10x slower?

Original Submission: http://codeforces.me/contest/375/submission/18813131

Second Submission: http://codeforces.me/contest/375/submission/18813311

Diff: https://www.diffchecker.com/nhyeayxp

Thank you very much!

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

»
8 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

When moving the query window, you can try to remove a color before adding it, which leads to infinite loop in the Fenwick update.

Changing the order of the check() calls seems to fix it: 18814449

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

    Thank you so much! I definitely would not have seen that.

    → Reply