Tobby_And_Friends's blog

Getting TLE in MO's Algorithm with updates [SPOJ ADAUNIQ — Ada and Unique Vegetable]
By Tobby_And_Friends, history, 6 years ago, In English

Problem link: http://www.spoj.com/problems/ADAUNIQ/

My solution: https://ideone.com/srH91b

Verdict: TLE

How do I optimize my solution? Any help is really appreciated.

[Update] Got AC :) I missed out the fact that block sizes are of n^(2/3)

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

Comments Comments (8)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You're not supposed to compare right ends by buckets, instead, just compare values. So, replace if(r1 != r2) return r1 < r2; with if(a.r != b.r) return a.r < b.r;

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

    In order to experiment, I did that too. Still got TLE :(

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

      Ah, I see. The problem is with time updates, these might take up to O(nq) (lines 81, 82)

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

If you wish to know how to use Mo's algorithm with updates, check out this blog post, but I doubt that it will be fast enough.

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

    Thank You :)

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

    Thanks a ton :) I understood where I was wrong logically. Got AC now :)

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

      Good job! There is also a online solution.

      Hint
      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Though you got AC, I'd like to mention one more thing.
I see you wrote — 

int l1 = a.l/SZ, l2 = b.l/SZ;
int r1 = a.r/SZ, r2 = b.r/SZ;

This might be the reason of your getting TLE. I got 2-3 times too.
Instead of doing this, precompute block numbers and do — 

int l1 = blc[a.l], l2 = blc[b.l];
......

This will significantly reduce your run time.

→ Reply