masaow's blog

"Or"game(579D) problem
By masaow, history, 5 years ago, In English

The problem [https://codeforces.net/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

»
5 years 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).

→ Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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 .

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
      • »
        »
        »
        »
        5 years 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 :)

        → Reply