Блог пользователя masaow

"Or"game(579D) problem
Автор masaow, история, 5 лет назад, По-английски

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

  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +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.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 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 .

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +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.

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +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.

        → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 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 :)

        → Ответить