Editorial for COCI '21 Contest 1 #2 Kamenčići

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Notice that the state of the game is completely determined by only three numbers: $l$ ~l~ - the leftmost pebble still in the game, $r$ ~r~ - the rightmost pebble still in the game and $m$ ~m~ - the number of red pebbles collected so far by the player whose turn it is. Using prefix sums on the number of red pebbles in the array, from these numbers, we can easily determine which player will win. Since $n, k \le 350$ ~n, k \le 350~ and from each game state, we can make only two possible moves, a natural idea is to use dynamic programming. The state will be $dp[l][r][m]$ ~dp[l][r][m]~ which will be $1$ ~1~ if the current player can win, and $0$ ~0~ otherwise. The number of red pebbles collected so far by the other player can be determined from the information of the state: $h = (\text{num. of red pebbles}) - m - (\text{num. of red pebbles in interval }l, r)$ , where we used $h$ ~h~ to denote this number. The transition is defined as follows:

$dp[l][r][m] = 0$ ~dp[l][r][m] = 0~, if $m \ge k$ ~m \ge k~
$dp[l][r][m] = 1$ ~dp[l][r][m] = 1~, if $h \ge k$ ~h \ge k~
$dp[l][r][m] = {!dp[l+1][r][h]} \mid {!dp[l][r-1][h]}$ , otherwise

Comments

0

LeonLiur commented on Dec. 8, 2021, 2:52 a.m. ← edit 2 →

Edit: Never mind they're just basic logic operators..