kishore_p's blog

Change in Mo's algo sort function gives different results
By kishore_p, history, 6 years ago, In English

I used Mo's algo to solve this problem .

First compare function: It gives me wrong answer Submission1

bool comp(query &a,query &b)
{
 int x=a.L/bsize;
 int y=b.L/bsize;
 
 if(x!=y)
 return x<y;
 if(x&1)
 return (a.R > b.R);
 else
 return (a.R < b.R);
}

Second function : Gives me AC Submission2

bool comp(query &a,query &b)
{
 int x=a.L/bsize;
 int y=b.L/bsize;
 
 if(x!=y)
 return x<y;
 else
 return a.R < b.R;
}

First one is an optimisation,but not able to find why it gives wrong answer

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

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

In the first code, as you go backwards(going from (L1, R1) to some (L2, R2) such that L2 < L1 and R2 < L1) you will call dec on an element that has not yet been added. In order to avoid this, you should first increase the size of segment you're on, and then dec, i.e. first call inc(++right) and inc(--left) and then dec(left++) and dec(right--).

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

    Thanks for the reply. It is clear now . Any sort function try to inc the range first and then dec.

    So if I interchange less than and greater than as below. inc,inc,dec,dec will still work

    bool comp(query &a,query &b)
{
 int x=a.L/bsize;
 int y=b.L/bsize;
 
 if(x!=y)
 return x<y;
 if(x&1)
 return (a.R < b.R);
 else
 return (a.R > b.R);
}
    → Reply