Rectoggle | Topcoder Archive

Problem Statement

Rectoggle is a game for two players. The game is played on a huge rectangular LED panel. Both rows and columns of the panel are numbered starting from 0 in the top left corner. The players take alternating turns. Each turn looks as follows:

Select any rectangular region with at most maxrows rows, at most maxcols columns, and a lit LED in the bottom right corner.
Toggle all LEDs within the selected region.

The player who cannot make a valid move (because all LEDs are off) loses the game.

You are given the int[]s ledrow and ledcol: coordinates of the lit LEDs at the beginning of the game. More precisely, for each valid i there is a lit LED in row ledrow[i] column ledcol[i]; and there are no other lit LEDs. You are also given the limits maxrows and maxcols. Return 1 if the first player wins and 2 if the second player wins, assuming both play the game optimally.

Definition

Class:: Rectoggle
Method:: whoWins
Parameters:: int[], int[], int, int
Returns:: int
Method signature:: int whoWins(int[] ledrow, int[] ledcol, int maxrows, int maxcols)
(be sure your method is public)

Constraints

ledrow will have between 0 and 200 elements, inclusive.
ledcol will have the same number of elements as ledrow.
Each element of ledrow and ledcol will be between 0 and 10^5, inclusive.
The coordinates of LEDs described by ledrow and ledcol will be distinct.
maxrows and maxcols will each be between 1 and 10^5, inclusive.

Examples

```
{}
```
```
{}
```
```
4
```
```
7
```
```
Returns: 2
```
Player 1 has no valid moves, so they lose immediately.
```
{0,0,0,0,1,1,1,1,2,2,2,2}
```
```
{0,1,2,3,0,1,2,3,0,1,2,3}
```
```
3
```
```
4
```
```
Returns: 1
```
Player 1 can win the game by toggling the 3x4 rectangle in the top left corner of the board. This turns off all twelve LEDs and leaves the second player with no valid moves.
```
{0,0,0,0,1,1,1,1,2,2,2,2}
```
```
{0,1,2,3,0,1,2,3,0,1,2,3}
```
```
1
```
```
1
```
```
Returns: 2
```
A boring game in which the players turn off LEDs one at a time. As the number of LEDs is even, player 2 eventually wins.
```
{100,101,102}
```
```
{100,101,102}
```
```
4
```
```
7
```
```
Returns: 1
```
One possible winning first move for player 1 is to toggle the rectangle in rows and columns 100-102. This will produce a board that has six lit LEDs. That board happens to be symmetrical according to the main diagonal, and has no lit LEDs on that diagonal. It can now be shown that player 2 must always break this property and that player 1 can always restore this property by mirroring player 2's moves. The game is finite, thus player 1 must eventually win.

{1,1,2,3,5,8,13,21}

{1,2,3,5,8,13,21,34}

Returns: 1

An example of a non-trivial game.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.