Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

rituranjna's blog

DP approach for 169-D-Little Girl and Maximum XOR
By rituranjna, 14 years ago, In English

Here Fcdkbear is talking about DP approach for 169-D-Little Girl and Maximum XOR , But i could not understand its DP state( D[P][FL1][FR1][FL2][FR2] ) . Can anybody explain it , please ?

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

»
14 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

He said he is going to translate it as soon as possible so just wait :)

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

I coded it during contest, but I had a 1-char bug:

Changing dp[35][2][2][3][3][3] to dp[75][2][2][3][3][3] makes it work properly.

3189992 (contest submission); 3190350 (fixed submission)

My explanation of this approach:

dp[id_bit][bit_a][bit_b][LA][AB][BR] is the answer to the following question:

« What is the maximum value I can make from X ^ Y (where X and Y can only use bits from 0 to id_bit), knowing that the id_bit+1th bit of X and Y was bit_a and bit_b respectively, and the actual status between L and A is LA, between A and B is AB, between B and R is BR ? »

By status between X and Y we mean: 0 if X == Y, 1 if X < Y, 2 if X > Y

NOTE: It is possible to drop away bit_a and bit_b from recurrence, thus making even easier to code this approach: see 3198623

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

    Thanks a lot :)

    → Reply
  • »
    »
    14 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Can you explain what are you doing in below line of 3198623

    ll temp = f(bit-1, decidi(LA, (L >> bit) & 1, a), decidi(AB, a, b), decidi(BR, b, (R >> bit) & 1)); ..?

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

      The line you mentioned is the recursive step: it tries to "append" bits a and b (I try to append each of the 4 possibilities for such values: 00, 01, 10, 11) respectively to X and Y. For example: decidi(LA, (L >> bit) & 1, a) is the answer to « What is the new status of LA knowing its actual status (that is, considering only the previous bits), and knowing that the next bits in this position will be (L >> bit) & 1 (this just extracts the value of the bit in this position, of the number L) and a respectively ? ».

      Once I know the new states of LA, AB, BR, I call the function to query what is the best I can do in this situation. This "query" maybe will result in  - ∞ (that is numeric_limits<ll>::min()), meaning: « Using this combination of a and b you will surely produce two numbers X and Y that don't satisfy the requirements of the statement (that is, to not go under L and to not go over R) ». For this reason, the next line checks whether the return value is  - ∞. If it is not, then it is a candidate to be the best possible (if a ≠ b then you should note that a ^ b = 1 so the bit at this position will be 1: this means that you have to add 2bit, that is 1LL << bit, to that return value!): finally, the next line tries to update the best found so far.

      Note that the function returns  - ∞ when you have no more bits left to use and the condition (LA < 2 && AB < 2 && BR < 2) is false (that is, when the order L  ≤  A  ≤  B  ≤  R is not respected).

      → Reply
»
14 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

Why do you want to do a DP?

Simply find the leftmost difference in bit representation of the two numbers. If the difference is at the nth bit the answer is 2^n — 1

Think about it.

What you want is the maximum number of different bits in the two numbers. If the leftmost difference occurring in l and r is at nth bit The remaining bits you can always make different at both positions.

http://codeforces.me/contest/276/submission/3185384

→ Reply