gyanendra371's blog

By gyanendra371, history, 4 weeks ago, In English,

question and discussion link https://discuss.codechef.com/questions/135298/andsqr-editorial

somebody explain bit easier what the editor was doing here ; not able to understand

LL fsu[31][N];

    for(i=0;i<31;i++)//Initialize 

        fsu[i][n]=n+1;

    for(i=n-1;i>=1;i--)
    {

        for(j=0;j<31;j++)
        {

            if((1<<j)&a[i+1])//If the bit is set

                fsu[j][i]=fsu[j][i+1];

            else //If the bit changes

                fsu[j][i]=i+1;

        }

    }
 
 
 
 
  • Vote: I like it  
  • -7
  • Vote: I do not like it  

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This is pretty simple. fsu[i][j] = The first index k,k > i, where ak doesn't have the j-th bit set. This is useful to know because the and operation is destructive and will only be able to change at most times. The next change is given by fsu[i][j].

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how do we know and is changing and why if the bit is off we store the last index.