Codeforces question

#1

https://codeforces.com/contest/279/problem/E

what is solution and explaination of this question

#2

Let a single move = addition of 2^k or 2^-k s = the binary string, s[0] being the first digit = the last character in the string

Let dp[POS][i] = minimum number of moves needed to get a string l such that l[0…i] exactly match s[0…i] and l[i+1 …] = 0 Let dp[NEG][i] = (same as above) l such that l[0…i] exactly match s[0…i] and l[i+1 …] = 1

If s[i] == 0, then dp[POS][i] = dp[POS][i-1], since you don’t have to make any additional move. For dp[NEG][i], we can either make our move from a [POS][i-1] state, where we have to turn all bits from l[i+1…] to 1, but leave l[i] =0, so this takes 1+dp[POS][i-1] (just a single move, note that a negative power of 2 turns all bits to the left to 1, but leave the right bits unchanged -> -2^k = 11111… 000…). Or, we can make our move from a [NEG][i-1], which means we have to turn the ith bit to 0. This we can do by adding a single positive power of 2, which means only 1 extra move. Thus. dp[NEG][i-1] = 1+ Min(dp[POS][i-1], dp[NEG][i-1])

And for s[i]==1 case, similar reasoning. Base case -> dp[POS][0] = 0 if first bit is 0, 1 if first bit is 1, dp[NEG][0] = 1, because you still have to make the bits to your left =11111…

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.