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, In English,

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

 
 
 
 
  • Vote: I like it
  • -9
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by masaow (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 :)