Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### masaow's blog

By masaow, history, 4 weeks ago, ,

The problem [https://codeforces.com/contest/579/problem/D] can be solved using a simple greedy approach by precalculating prefix ors and suffix ors but I wanted to solve it using DP in which we multiply an array element at most K times ranging from 0 to k. But it fails on test 23. Thanks in advance... my solution : 69268483

• -9

 » 4 weeks ago, # |   0 Auto comment: topic has been updated by masaow (previous revision, new revision, compare).
 » 3 weeks ago, # |   +1 Shouldn't you call $solve(n-1,k)$? Your array is stored from $0$ to $n-1$, but you pass $n$ as $idx$ which means, you are accessing $a[n]$ in first recursion.
•  » » 3 weeks ago, # ^ |   0 Yeah! You are write that's a silly mistake. But with solve(n-1,k) its failing on test 23 i.e ; 3 1 2 17 18 4 expected output is 54 and i'm getting 53 .
•  » » » 3 weeks ago, # ^ |   +1 Okay, so I did some testing, and then I noticed that you're not storing already computed answer. If you don't use answer till now, then you're basically doing greedy, and not dp. Your function $solve(idx,used)$ just calculates maximum OR possible using at most $"used"$ multiplications and indices upto $"idx"$, but if your answer from indices $"idx+1", ... n$ has some bits already, then instead of maximizing $OR$ from left side ( $0,...idx$ ) you instead want maximum and trying to exclude those set bits already. Basically, you need $prev$ ( already calculated answer ) as a state too. Changed your code only a little bit ( used map to memoize, since we need to store long long ) here, but it gives TLE because now there are too many states. I guess you could solve it iteratively instead of using recursion.
•  » » » » 3 weeks ago, # ^ |   +1 Follow up: So I quickly wrote an iterative dp for this, but that fails the same case, because again, it is "greedily" choosing best prefix instead of looking at the whole answer. Code here.
•  » » » » 3 weeks ago, # ^ |   0 Oh superb bro !!!! Amazing I got your point. A simple greedy solution is to precalculate prefix and suffix ors and for each iteration multiply a[idx] by x k times and or it with precalculated prefix and suffix ors and max of this is the answer. THANKS a lot gupta_samarth :)