### rituranjna's blog

By rituranjna, 9 years ago,

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 ?

• +2

 » 9 years ago, # |   +2 He said he is going to translate it as soon as possible so just wait :)
 » 9 years ago, # | ← Rev. 6 →   0 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 > YNOTE: It is possible to drop away bit_a and bit_b from recurrence, thus making even easier to code this approach: see 3198623
•  » » 9 years ago, # ^ |   +1 Thanks a lot :)
•  » » 9 years ago, # ^ |   0 Can you explain what are you doing in below line of 3198623ll temp = f(bit-1, decidi(LA, (L >> bit) & 1, a), decidi(AB, a, b), decidi(BR, b, (R >> bit) & 1)); ..?
•  » » » 9 years ago, # ^ | ← Rev. 4 →   0 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::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).
 » 9 years ago, # | ← Rev. 3 →   0 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 — 1Think 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.com/contest/276/submission/3185384
•  » » 9 years ago, # ^ |   +1 I am learning DP , So i was curious to know dp approach .
•  » » » 9 years ago, # ^ |   0 try hard to learn !!