1510. Stone Game IV

Problem Overview

Alice and Bob remove a positive perfect-square number of stones each turn; the player who cannot move loses.

Intuition

Alice and Bob remove a positive perfect-square number of stones each turn; the player who cannot move loses. Alice starts. A pile size i is winning if there exists a square j*j that leaves a losing size for the opponent. Fill dp[0..n] bottom-up: dp[0] is losing, and dp[i] becomes true as soon as one move hits a false state.

Algorithm

1Allocate bool dp[0..n]; dp[0] = false.
2For i = 1..n: for each j with j*j <= i, if !dp[i - j*j] set dp[i] = true and break.
3Return dp[n].

Example Walkthrough

Input: n = 2

1.dp[1]: remove 1 -> leave 0 (losing for opponent) -> Alice wins with 1 stone.
2.dp[2]: only remove 1 -> leave 1 (winning for opponent) -> Alice loses with 2 stones.

Output: false

Common Pitfalls

•dp[0] must stay false - no square removal is possible from an empty pile.
•Break early once a winning move is found for i to save work.
•Squares start at 1 - removing 0 stones is not a legal move.
•Both players optimal: existence of one move to a losing state is enough for a win.

1510.cs

// Approach: Bottom-up win/lose DP. dp[i] = true iff the player to move with i
// stones can force a win. Try removing every square j*j <= i; if any leave the
 // opponent in a losing state (!dp[i - j*j]), then dp[i] is winning.
// Complexity: O(n * sqrt(n)) time and O(n) space.
public class Solution
{
    public bool WinnerSquareGame(int n)
    {
        // dp[i] := the winning result for n = i
        bool[] dp = new bool[n + 1];

        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j * j <= i; ++j)
            {
                if (!dp[i - j * j])
                { // Removing j^2 stones make the opponent lose.
                    dp[i] = true;       // So, we win.
                    break;
                }
            }
        }
        return dp[n];
    }
}

Was this solution helpful?