mbstu_nitai's blog

Mo's algo sort function differences.
By mbstu_nitai, history, 6 years ago, In English

=====================================================================

What are the differences between this three sort functions in Mo's algo?

First approach: 

bool comp(stt q1, stt q2)
{
    int block_a = q1.l / sq, block_b = q2.l / sq;
    if(block_a == block_b)
        return q1.r < q2.r;
    return block_a < block_b;
}

Second approach:

bool comp(stt q1, stt q2)
{
  if (q1.l / sq != q2.l / sq) 
     return q1.l< q2.l;
  return (q1.r < q2.r)^(q1.l/sq%2);
}

Third approach:

bool comp(stt q1, stt q2)
{
    if(q1.l/sq != q2.l/sq)
    {
        return q1.l < q2.l;
    }
    if((q1.l/sq) & 1)
    {
        return q1.r < q2.r;
    }
    return q1.r > q2.r;
}

Problem link

The first approach gives the TLE on test 9 Submission link the second approach gives the TLE on test 67 Submission link but the third approach gives AC Submission link . Thanks in advance. :)

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

Comments Comments (6)
| Write comment?
»
6 years ago, # |
← Rev. 4   Vote: I like it +19 Vote: I do not like it

Please write your code indented like this:

bool comp (stt q1, stt q2) {
  int block_a = q1.l / sq, block_b = q2.l / sq;
  if (block_a == block_b) {
    return q1.r < q2.r;
  }
  return block_a < block_b
}

bool comp (stt q1, stt q2) {
  if (q1.l / sq != q1.l / sq) {
    return q1.l < q2.l;
  }
  return (q1.r < q2.r) ^ (q1.l / (sq % 2));
}

bool comp (stt q1, stt q2) {
  if (q1.l / sq != q2.l / sq) {
    return q1.l < q2.l;
  }

  if ((q1.l / sq) & 1) {
    return q1.r < q2.r;
  }

  return q1.r > q2.r;
}

(in general if you want people to help you you should make it as easy as possible for them to help you)

Anyway, the first comparator is the classical Mo comparator, nothing much to say about that. The third comparator is a common trick to speed up Mo's algorithm by a constant factor. With the first comparator, the right pointer moves to the right times, and then jumps to the left after each time. This takes approximately steps (I'm assuming the number of queries and the length of the array are both N for simplicity). But with the third comparator, the right pointer makes a zig-zag pattern and only takes about steps.

The second comparator appears to be a blotched attempt to write the third style. Indeed, if the return line of the second comparator read return (q1.r < q2.r) ^ ((q1.l / sq) % 2);, it would perform identically to the third. Since you didn't get FPE, I'm assuming sq is always odd, thus (q1.l / (sq % 2)) is simplified to q1.l / 1 or just q1.l. The line then can be simplified to return (q1.r < q2.r) ^ q1.l which flips the queries only if q1.l is one. Probably you just got lucky and got a TLE at a later test because this is not any better than the first one. In fact the second comparator does not technically define a total order.

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

    (PS: i am just adding on a bit. hope this is helpful)

    Just to clarify the zigzag pattern that is mentioned for the 3rd comparator, notice that in the first comparator, when the right pointer goes to the left again, all the moves are wasted. And we again have to go to the right all the way potentially. Instead of doing this, depending on the parity of the block (odd/even) we utilize these leftshifting moves by sorting the alternate blocks in alternate right pointer orderings.. so that when we go left, we keep utilizing the moves as the queries are also sorted in this order. In the next block, since the sorting is again reversed, when we go right we again utilize our moves.

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

    (q1.l / sq % 2) should be ((q1.l / sq) % 2) instead of (q1.l / (sq % 2)), so the second approach is equivalent to

    if (q1.l / sq != q1.l / sq)
    return q1.l < q2.l;
if ((q1.l / sq) & 1) 
    return !(q1.r < q2.r);
else
    return q1.r < q2.r;
    → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thank you for your help and advice. I have not posted a source code in the Codeforces before. For this reason, I have made this mistake. I have edited this post and next time I will try to follow your advice. :)

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

Also randomizing sq by +-50 does help a bit.

→ Reply