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

Автор try_n_catch, история, 6 лет назад, По-английски

I was trying to do this question when I read the comments I came to know that the problem is about Convex Hull technique of Dp optimisation.Then I read this article on Dp optimisation convex Hull techniqueHere.Can anybody help me in understanding the code.

Полный текст и комментарии »

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

Автор try_n_catch, история, 6 лет назад, По-английски

Can anyone suggest me from where I can start Dynamic Programming. Some problems from which I can be good at DP.

Полный текст и комментарии »

Теги #dp
  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

Автор try_n_catch, история, 7 лет назад, По-английски

Recently I was trying the question Maximum Xor Query of codechef. I decided to go for the editorial there I found to build a segment tree with each node being a trie. I am not able to understand the following piece of code that how they are finding maximum xor. Can anyone help me out??

int solve(vi &vec, int v) {

/*cout<<"VEC : ";
for(int i = 0; i < vec.size(); i++)
{
    cout<<vec[i]<<' ';
}
cout<<'\n';*/
int l = 0; int r = vec.size() - 1;
int cur = 0;
int ans = 0;
//cout<<l<<" "<<r<<endl;
for(int i = 24 - 1; i >= 0; i--)
{
    if(v&(1<<i))
    {
       int x = lower_bound(vec.begin()+l, vec.begin()+r+1, cur+(1<<i)) - vec.begin();
       cout<<1<<" "<<x<<endl;
       if(l<=x-1)
       {
         r = min(r, x-1);
         ans+=(1<<i);
       }
       else
       {
         cur+=(1<<i);
       }
    }
    else
    {
       int x = lower_bound(vec.begin()+l, vec.begin()+r+1, cur+(1<<i)) - vec.begin();
    // cout<<0<<" "<<x<<" "<<i<<endl;
       if(r>=x)
       {
         l = max(x,l);
         ans+=(1<<i);    
         cur+=(1<<i);
       }
    }
}
return ans;

}

Полный текст и комментарии »

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