# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
He said he is going to translate it as soon as possible so just wait :)
I coded it during contest, but I had a 1-char bug:
Changing
dp[35][2][2][3][3][3]
todp[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 theid_bit+1
th bit of X and Y was bit_a and bit_b respectively, and the actualstatus
between L and A isLA
, between A and B isAB
, between B and R isBR
? »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
andbit_b
from recurrence, thus making even easier to code this approach: see 3198623Thanks a lot :)
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)); ..?
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 is1LL << 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).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.net/contest/276/submission/3185384
I am learning DP , So i was curious to know dp approach .
try hard to learn !!