Блог пользователя GLAYS

Getting TLE using MO's.Any chance of improvement? — HackerRank problem
Автор GLAYS, история, 6 лет назад, По-английски

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 !

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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));
}
→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Thanks.

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

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

      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

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

        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.

        → Ответить
        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

          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.

          → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится

        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).

        → Ответить
        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          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;
          → Ответить
        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +6 Проголосовать: не нравится

          Thanks.

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

          → Ответить