Connection Status:
Competition Arena > Rectoggle

Rectoggle

TCO19 SRM 748 · 2019-01-09 · by misof

TCO19 SRM 748 · 2019-01-09 · by misof · Advanced Math, Dynamic Programming
Class Name: Rectoggle
Return Type: int
Method Name: whoWins
Arg Types: (vector<int>, vector<int>, int, int)
Problem Statement

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:

  1. Select any rectangular region with at most maxrows rows, at most maxcols columns, and a lit LED in the bottom right corner.
  2. 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.

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
0)
{}
{}
4
7
Returns: 2

Player 1 has no valid moves, so they lose immediately.

1)
{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.

2)
{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.

3)
{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.

4)
{1,1,2,3,5,8,13,21}
{1,2,3,5,8,13,21,34}
4
7
Returns: 1

An example of a non-trivial game.

5)
{65535}
{32767}
100000
100000
Returns: 1

Internal note: Watch out for int overflow, the grundy number here is 2^31.

Submissions are judged against all 140 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Rectoggle with a public method int whoWins(vector<int> ledrow, vector<int> ledcol, int maxrows, int maxcols) · 140 test cases · 2 s / 256 MB per case

Submitting as anonymous