GLAYS's blog

Getting TLE using MO's.Any chance of improvement? — HackerRank problem
By GLAYS, history, 6 years ago, In English

Here is the problem.

So basically you have an array of integers a[] of size n.

n <  = 1e5 and a[i] <  = 215 ( = 3, 2 * 104).

And you're given q <  = 5e4 queries of the form (x, l, r) for which the answer is the maximum value of x xor a[i] for l <  = i <  = r.

The editorial's solution is about persistent segment trees which I know nothing about.Before reading that I was trying to solve it using MO's algorithm + trie which has a complexity of O((n + q) * sqrt(n)) without counting the time to answer a query using the trie.Now q * sqrt(n) is fine but n * sqrt(n) is too much.Because n * sqrt(n) is caused by the movement of r to the right(which can reach n) I thought, is it possible to use the fact that all the numbers are <= 215 to improve the complexity?

If r moves to the right more than 215 times then at least one element is repeated right?

Is it possible to use this(or any other optimization) to get MO's algorithm to pass?

Here is my code.It passes 11 test cases out of 14 and the rest are getting TLE(actually it says segmentation fault but I think it's TLE).

Any other solution is welcome.

Thanks !

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

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

you can try to speed up MO's a little by sorting the endings ascending if block id is odd and descending otherwise this will make MO's algorithm take about half the time.

bool cmp(pair<pair<ll,ll>,pair<ll,ll> >a,pair<pair<ll,ll>,pair<ll,ll> >b){
    ll x = a.F.F / block , y = b.F.F / block;
    if(x != y) return x < y;
    return ((x&1) ? (a.F.S < b.F.S):(a.F.S > b.F.S));
}
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks.

    I added this but now the solution only passes 10 test cases, and the four others got TLE.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +4 Vote: I do not like it

      oh! it seems time was not the problem there is a problem with line 137 (deleting some thing before you add it) I resubmitted your code with only rewrite this line after add lines and it gives AC

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        Thanks a lot, this really fixed it! (turns out it was segmentation fault after all)

        The correct ordering should be:

        while(cl > l) --cl , add(a[cl]);
while(cr < r) ++cr , add(a[cr]);
while(cr > r) del(a[cr]) , --cr;
while(cl < l) del(a[cl]) , ++cl;

        I find this strange because I always thought the ordering with MO's is "remove add add remove", I remember I passed some problems with it too..

        Also, isn't my solution's complexity too high to get accepted? I know the time limit isn't visible but I think it's too high!

        Anyways, it's okay now.Problem solved.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it +7 Vote: I do not like it

          It's always better to add before remove because removing first may cause some problems as we see here. the complexity is higher than the intended solution ofcourse but it seems that it's enough for MO's even without the speed up I talked about before.

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

        The / operator is too costly. Try pre-calculating blc[i] = i / block and use that in compare function. Hope it'll pass (but there exists quasi-linear solution).

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

          Might be faster (I don't know if GCC optimizes the above loop):


          for(int quot = 0, j = 0; j < n; j += block, quot++)
	for(int i = 0; i < block && i + j < n; i++) b[i + j] = quot;
          → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          Thanks.

          Actually time was not the problem, as was mentioned here.

          → Reply