NothingFU's blog

CSES — Removal Game
By NothingFU, history, 8 months ago, In English

I was read a solution of problem at here. But i don't know why minus dp[l+1][r] if first people choose a[l] and dp[l][r-1] if first people choose a[r]. Can else help me, thanks :>>

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

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I got an AC score for a problem. I wrote something that can help you.

For example, if the first person chooses a[l], the subsequence a seq [l+1..r] will be chosen by the second person. This is because both individuals are optimizing their scores. So, I will swap the positions of the second person with the second position of the first person and calculate

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you need to understand it properly.

dp[l][r] = $$$score_1-score_2$$$ if the game played only on interval [l, r].

Now note 2 things: $$$score_1$$$ is score of $$$player_1$$$ and $$$score2$$$ is score of $$$player_2$$$ and on each move, $$$player_1$$$ and $$$player_2$$$ are alternating.

Let's say $$$A$$$ is $$$player_1$$$ and $$$B$$$ is $$$player_2$$$ on segment [l,r]. $$$A$$$ chooses x[l]. Now in segment [l+1,r], $$$B$$$ will be the $$$player_1$$$. This is how it becomes a dynamic programming problem. The output of smaller subsegments don't change no matter what and they help build outputs for bigger subsegments. Note that $$$A$$$ and $$$B$$$ will always be $$$player_1$$$ on the same subsegments no matter which numbers are removed first.

In short:

  • IF it's move for $$$A$$$ on [l,r], then dp[l][r] will store scoreA-scoreB.
  • THEN it's move for $$$B$$$ on [l+1,r] then dp[l+1][r] will store scoreB-scoreA,
  • OR it's move for $$$B$$$ on [l,r-1] then dp[l][r-1] will store scoreB-scoreA.

I hope that makes sense why dp[l][r] = max(x[l] - dp[l+1][r] , x[r] - dp[l][r-1])

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hey . could you explain why cant we take a greedy approach on the problem? specifically what i thought was for every turn calculate sum of odd and even indexed terms left in sequence and choose left or right end accordingly. for example, if i see 4 5 1 3 as vector , i take left at 4 and right at 3 inititally now player one calculates sum of even positions -> 4 + 1=5 , and odd positions-> 5+3=8. so he goes with 3 as first choice ,next second player does the same(as both play optimally) and he goes with 4 . the player 1 ends with 5 making his total 5+3. However this strategy fails in many cases and i am unable to figure out why. please help

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What does your solution do when number of positions is odd? In that case, left and right indexes both would be at even position, so how do you know what to choose then?

      → Reply
      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what does optimally means in all these type of questions ?

        → Reply
        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          One way to think about it is to think recursively.

          If it's A's turn, he will check every possibility and make the move that gives him best chances in the worst case scenario. And, B will do the same.

          → Reply