Stick Game Problem: Solution and Code in Python, C, Java

Given a grid of n horizontal and m vertical sticks, the stick game asks which player wins under optimal play. The answer reduces to one comparison: check whether min(n, m) is odd or even.

The full solution is five lines of code. The derivation behind it is the useful part, because the same pattern of reasoning applies to a family of grid-based competitive programming problems.

What the Stick Game Looks Like

The game runs on a rectangular grid formed by n horizontal sticks and m vertical sticks. Where these sticks cross, they create intersection points. An n × m grid produces exactly n × m intersection points.

Two players alternate turns; the first player moves first. On each turn, the current player picks any remaining intersection point and removes all sticks that pass through it. Every intersection lies on exactly one horizontal stick and one vertical stick, so each move removes:

• The entire horizontal stick for that row, which also eliminates every other intersection on that row.
• The entire vertical stick for that column, which also eliminates every other intersection on that column.

In a 3 × 3 grid, picking the top-left intersection removes the top-row stick and the left-column stick. That leaves four remaining intersections arranged in a 2 × 2 pattern.

A player loses when no intersection points remain at the start of their turn.

This falls under the category of problems studied in combinatorial game theory: two players alternate moves on a finite state, and the player who faces an empty state loses.

Why the Total Move Count Is Always min(n, m)

Here is the core derivation. Trace the game state step by step:

• Before move 1: n rows, m columns, n × m intersections.
• After move 1: one row and one column are gone. Now n - 1 rows and m - 1 columns remain, with (n-1) × (m-1) intersections.
• After move 2: n - 2 rows and m - 2 columns remain.
• After move k: n - k rows and m - k columns remain.
• The game ends when either n - k = 0 or m - k = 0, whichever comes first.
• That happens at k = min(n, m).

Every move removes exactly one row and one column. There is no branching, no choice that changes the total. The game always ends in exactly min(n, m) moves.

Parity then determines the winner. Move 1 is Arun Gupta’s, move 2 is Mani Iyer’s, alternating from there:

• If min(n, m) is odd: Arun Gupta makes the last move. Mani Iyer faces an empty grid and loses.
• If min(n, m) is even: Mani Iyer makes the last move. Arun Gupta faces an empty grid and loses.

No game tree. No recursion. One comparison.

This is why “both players play optimally” is a red herring for this problem. Every intersection is equivalent in terms of game outcome. There is no move that improves or worsens either player’s position. The result is determined the moment n and m are known.

Verified Sample Walkthroughs

The derivation above predicts all three provided sample outputs. Verify each:

Sample 1: n = 2, m = 2

• min(2, 2) = 2 (even)
• Predicted winner: Mani Iyer
• Sample output: Mani Iyer ✓

Walkthrough: Arun picks any intersection, say the top-left. That removes the top row and left column, leaving only the bottom-right intersection. Mani takes it, removing the remaining sticks. Arun faces an empty grid and loses.

Sample 2: n = 2, m = 3

• min(2, 3) = 2 (even)
• Predicted winner: Mani Iyer
• Sample output: Mani Iyer ✓

The narrower dimension is 2 horizontal sticks. The game ends in 2 moves regardless of which column each player targets.

Sample 3: n = 3, m = 3

• min(3, 3) = 3 (odd)
• Predicted winner: Arun Gupta
• Sample output: Arun Gupta ✓

Three moves in a symmetric grid. Move 3 belongs to Arun, leaving Mani with no intersections.

All three match. The algorithm is correct and the legacy WP derivation has no arithmetic errors.

Algorithm and Code

The algorithm has three steps:

1. Read n and m.
2. Compute res = min(n, m).
3. Print “Mani Iyer” if res % 2 == 0; otherwise print “Arun Gupta”.

Python

n, m = map(int, input().split())
res = min(n, m)
if res % 2 == 0:
    print("Mani Iyer")
else:
    print("Arun Gupta")

C

#include <stdio.h>
int main() {
    int n, m, res;
    scanf("%d %d", &n, &m);
    res = (n < m) ? n : m;
    if (res % 2 == 0)
        printf("Mani Iyer\n");
    else
        printf("Arun Gupta\n");
    return 0;
}

Java

import java.util.Scanner;
public class StickGame {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int res = Math.min(n, m);
        if (res % 2 == 0)
            System.out.println("Mani Iyer");
        else
            System.out.println("Arun Gupta");
    }
}

All three handle the constraint 1 ≤ n, m ≤ 100 without additional edge-case logic. The min computation covers every valid input.

Time and Space Complexity

Both are O(1). The solution reads two integers, performs one comparison, and outputs a string. Memory usage stays constant regardless of how large n and m are. For a full walkthrough of how to derive and report complexity in coding rounds, see space and time complexity of algorithms.

A naive game-tree search on a 100 × 100 grid would need to explore exponentially many move sequences. The O(1) parity solution sidesteps that entirely by identifying the game’s structure before writing a single line of code.

The stick game belongs to the broader family of two-player problems where the total move count is fixed regardless of strategy. The GeeksforGeeks game theory section covers Nim, Sprague-Grundy, and related patterns that placement tests draw from.

For other programming problems where a single insight replaces an expensive algorithm, see the Wordakshari game problem and the equilibrium index problem. Both reward the same approach: understand the structure first, then write five lines of code.

The min(n, m) parity check is straightforward once you see it, but recognising that structure quickly in a new problem takes practice across varied problem sets. TinkerLLM is a coding playground where you can build and test variations of this type of problem without IDE setup; a month’s access starts at ₹299.