Editorial for Shopping Mania

Since, to win, any player needs more or equal scores than the other player, considering the other player will always play optimally, at every stage of the game we should find out the maximum difference current player can have over the other player. If the difference is non-negative, that player will surely win no matter what. Otherwise, if the other player plays optimally, the other player will win.

Suppose, at some turn some player sees that item ii is up for sale and there are at most jj skips left. She can either skip this turn or purchase the item. Let dp(i,j)dp(i, j) be the maximum difference of her score over other player’s score. We want to follow the move which maximizes dp(i,j)dp(i, j).

  • Purchase: If we purchase we get pidp(i+1,k)p_i - dp(i + 1, k).

  • Skip: If j>0j > 0, we get dp(i,j1)-dp(i, j-1).

For convenience, we can assume dp(n+1,k)=0dp(n + 1,k) = 0.

Of course, if j=0j = 0, the player have to purchase the current item. Otherwise, if pidp(i+1,k)<dp(i,j1)p_i - dp(i + 1, k) < -dp(i, j - 1), she may skip this turn.

Shapla should go first if dp(1,k)>=0dp(1, k) >= 0, second otherwise.


    40% Solution Ratio

    Um_nikEarliest, 3M ago

    Deshi_TouristFastest, 0.0s

    Um_nikLightest, 262 kB

    NirjhorShortest, 1445B

    Toph uses cookies. By continuing you agree to our Cookie Policy.