GreenLantern__1's blog

By GreenLantern__1, history, 9 days ago, In English,

In Mo's Algorithm, we sort the left pointer by using sqrt(N).

However if we consider two left pointers a and b such that a<b then (a/c)<(b/c) where c=sqrt(N). Thus it won't matter if we sort it by a<b or (a/c)<(b/c).

I know I am missing something, but I can't figure it out.

 
 
 
 
  • Vote: I like it  
  • -3
  • Vote: I do not like it  

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by GreenLantern__1 (previous revision, new revision, compare).

»
9 days ago, # |
Rev. 8   Vote: I like it 0 Vote: I do not like it

The thing is, we need to ensure that 2 intervals (a1, b1), (a2, b2) are sorted such that, in this case, implies that the intervals will be in the same block. So we, need to compare with . first. If they are equal, then we need to ensure that either b1 ≤ b2 or b1 ≥ b2 holds for every interval in that block (i.e. the right pointer must be non-decreasing or non-increasing within a block).

Now, if you simply sort by the condition a1 < a2, how do you sort by b1 and b2 in the same block?

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank you for replying.

    Let's say there are two indexes b and c to the right of another index a. Then if after sorting on the basis of sqrt(N) b lies in the same block as a and c is in different block, then b will be nearer to a than c in the sorted container. Something like a,b,c.

    Then even without sorting using sqrt(N) b will be nearer to a than c in the sorted container.Won't it?

    And for indexes same, we can use the right pointer as a parametric right?

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

      Well. You can sort purely by left pointer and still fulfill the condition that I mentioned for the left pointers. BUT, you will need to do some additional work. Because, the right pointer in each block is not necessarily non-increasing/non-decreasing anymore. So you will need to loop through each block and sort your elements by right pointer.

      Why do more work then necessary? You can simply make one comparator which implements the comparison logic that I mentioned and everything will be good in one sort.

»
9 days ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

In Mo's, if we have (a / c) =  = (b / c) then we sort queries on the basis of the right pointer, in which it is possible that some query [l1, r1] will come after [l2, r2] even when l1 < l2.

While sorting it just on the basis of the left pointer will not ensure us O(sqrt(N)) time complexity.

»
9 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I have no idea what you are talking about. In Mo's algorithm we categorize based on left pointers (put in sqrt bucket) then sort by right pointers. Converesly, it is possible to categorize on right pointers and sort by left pointer but that's weird so I don't see an obvious reason to do so.

We never categorize by left/right pointer AND sort by the same pointer (there would be no point in doing so).

»
9 days ago, # |
  Vote: I like it +36 Vote: I do not like it

If you have an apple, then you have a fruit. But if you have a fruit, you don't necessarily have an apple.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What you are missing is that (a/c) is actually floor(a/c), so a<b does not imply (a/c)<(b/c). Try a = 5, b = 6, c = 4

To understand Mo's algorithm, see LanceTheDragonTrainer's reply.

»
8 days ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

Sorting by (a/c)<(b/c) is splitting the array to blocks of size c and sorting by which block the left pointer is in. Let's analyze running time according to c, n, q (n/c blocks of size c):

  • The left pointer moves, in every query, either inside a block or to some next block. While moving inside a block, the worst case is between its ends, which is O(c) moves. In the worst case it will also move over all blocks in all queries, so that's O(n). We get its work to be O(cq + n).
  • The right pointer moves always to the right, unless our left pointer moves a block, which allows the right pointer to move all the way left (and then it can return right again). On worstcase, for each block it does O(n), which gives .

We want to minimize according to c. Choosing we get while choosing we get . Even though the first one is always faster (according to math, but while ignoring the small change in constant), they probably have no difference in practice, especially when n = q (but the more they differ, the better the first one is in comparison to the second one).

Notice that by the formula, sorting by a < b is having c = 1, which has a complexity O(n2) worstcase.