0341HardMathDynamic ProgrammingMinimaxGame TheoryNim GameSprague–Grundy TheoremZero-Sum Game

Square Cut Cable Duel

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Two riggers, Ada and Boaz, share one spool holding n whole metres of cable. Ada acts first and then they act alternately.

On a turn the rigger whose turn it is must cut away exactly k * k metres for some positive whole number k. The cut may not exceed what is left on the spool, and skipping a turn is not allowed. A rigger who starts a turn with an empty spool has no legal cut and loses the duel.

Both riggers see the whole spool and never misplay. Return True when Ada can win against every defence, and False when Boaz can.

Examples

Example 1

Input: n = 83
Output: true

Ada opens by cutting 16 metres, and from the length that is left she has an answer to every defence Boaz plays, so Boaz is the rigger who eventually starts a turn with nothing to cut. An opening cut of 81 metres also wins for her.

Example 2

Input: n = 39
Output: false

Ada has only a handful of legal openings from 39 metres, and Boaz forces the win after each of them.

Example 3

Input: n = 30
Output: true

Ada opens by cutting 25 metres, leaving 5 metres on the spool, and wins from there.

Constraints

1 <= n <= 10^5

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def winner_square_game(n: int) -> bool:

Java

public boolean winnerSquareGame(int n)

The intended approach

Time O(n * sqrt(n))Space O(n)

Work upwards from an empty spool. A length is winning for whoever faces it when some square cut leads to a length that is losing for the rigger who receives it, so fill a boolean table from 0 to `n` and stop scanning squares at the first losing reply found.

Pythonentry point: winner_square_game

def winner_square_game(n):
    # win[t] is True when the technician facing t metres of cable can force a win.
    # A position wins as soon as one legal cut hands the opponent a losing position.
    # Time O(n * sqrt(n)).  Space O(n) for the table.
    win = [False] * (n + 1)
    for t in range(1, n + 1):
        k = 1
        while k * k <= t:
            if not win[t - k * k]:
                win[t] = True
                break
            k += 1
    return win[n]

The obvious version

Give every length a Grundy value: the smallest non-negative integer missing from the Grundy values of the lengths reachable by one square cut. A length is winning exactly when its Grundy value is non-zero.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_first_cutter_wins(n):
    # Grundy value of every length: mex over the values reachable in one cut.
    grundy = [0] * (n + 1)
    for t in range(1, n + 1):
        seen = set()
        k = 1
        while k * k <= t:
            seen.add(grundy[t - k * k])
            k += 1
        g = 0
        while g in seen:
            g += 1
        grundy[t] = g
    return grundy[n] != 0

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in