# | User | Rating |
---|---|---|

1 | tourist | 3882 |

2 | maroonrk | 3539 |

3 | Benq | 3513 |

4 | MiracleFaFa | 3466 |

5 | ksun48 | 3462 |

6 | ecnerwala | 3446 |

7 | slime | 3428 |

8 | Um_nik | 3426 |

9 | jiangly | 3401 |

10 | greenheadstrange | 3393 |

# | User | Contrib. |
---|---|---|

1 | awoo | 192 |

2 | -is-this-fft- | 191 |

3 | Monogon | 185 |

4 | Um_nik | 182 |

4 | YouKn0wWho | 182 |

6 | maroonrk | 169 |

7 | antontrygubO_o | 167 |

8 | errorgorn | 166 |

9 | kostka | 165 |

9 | SecondThread | 165 |

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/20/2022 11:38:34 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

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]`

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+1`

th 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 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

aandb(I try to append each of the 4 possibilities for such values: 00, 01, 10, 11) respectively toXandY. For example:`decidi(LA, (L >> bit) & 1, a)`

is the answer to « What is the new status ofLAknowing itsactualstatus (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 numberL) andarespectively ? ».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 ofaandbyou willsurelyproduce two numbersXandYthatdon't satisfythe requirements of the statement (that is, to not go underLand to not go overR) ». 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 (ifa≠bthen you should note thata^b= 1 so the bit at this position will be 1: this means that you have to add 2^{bit}, 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 orderL≤A≤B≤Ris 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.com/contest/276/submission/3185384

I am learning DP , So i was curious to know dp approach .

try hard to learn !!