ORDNCHS - EDITORIAL

general
, , , ,
1

PROBLEM LINK:

Practice
Contest

Setter: David Stolp
Tester: Lewin Gan and Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Game Theory, Maker-Breaker Games, Pairing Strategy.

PROBLEM:

Given a 6*6 empty grid, Chef and user play a game, playing roles of ORDER and CHAOS where both players in their turn can place either O or X in an empty cell, with ORDER having the first move. ORDER tries to place five same signs in the same direction (vertically, horizontally or diagonally) while CHAOS wants to stop ORDER from doing so. We can choose to play either as ORDER or CHAOS.

QUICK EXPLANATION

  • We have a winning strategy for CHAOS where we shall pair all the cells in the grid in such a way that when ORDER makes move in one cell of pair, CHAOS makes move in another cell of the same pair.
  • All possible five in a row can be either vertical, horizontal or diagonal. To avoid vertical five in a row, we can pair two non-border positions in a column so that if ORDER places a sign in one of the two cells, we can place the opposite sign in the second cell in pair. Since both cells are non-border, there can’t be a five in a row for that column. Similar reasoning goes for rows.
  • For diagonals of length six, we can pair opposite corners and ensure same sign on opposite corners, which would guarantee either six in a row or four or less in a row. So, we are not having five in a row on main diagonals.
  • There are four diagonals of length five, where for every diagonal, we can choose any two unpaired cells on same diagonal and ensure opposite sign on both to remove the possibility of five in a row.

EXPLANATION

Here, one player wants to achieve something while the other player aims to stop the first player. This category of Positional games is known as Maker-Breaker games, about which can be read here in detail.

The Maker (ORDER) is the one trying to achieve a winning position (exact five in a row) while Breaker (CHAOS) is the one aiming to stop Maker from achieving a winning position.

We shall use the Pairing strategy for Maker-Breaker games which are used to guarantee the victory of either player, depending upon rules of the game. This Wikipedia article on Pairing Strategy is quite useful and is required for understanding.

For this game, We have a winning strategy for Breaker. We can divide all cells into disjoint pairs such that to ensure that every possible five in a row contain both members of at least one pair. This guarantees that if Maker needs to win, he has to get both members of at least one pair, which breaker shall avoid.

So, to ensure victory, breaker needs to make pairs such that if he has one member of each pair, there is no exact five in a row.

Consider all possible five in a row. They can be either in a vertical or horizontal or diagonal direction. We shall block each one separately.

For all rows, we need to have one pair, whose both cells lie in the same row and none of these cells is the leftmost or rightmost cell in a row. Whenever ORDER marks one member of pair with a sign, CHAOS can mark another cell with the opposite cell, which guarantees no five in a row for that particular row. The reason behind leftmost and rightmost cells is that five in a row exist even when one border cell is marked with the opposite sign. (Example row OOOOOX and pair (2,6)).

The similar explanation goes for columns.

For Diagonals, we can consider two cases. Two on main diagonals and Four possible positions adjacent to main diagonals.

For five in a row on diagonals adjacent to main diagonals, we use the same idea, having both cells of a pair lie on same diagonal which if colored opposite, shall guarantee no five in a row for that diagonal.

For the main diagonal, it is a bit different. Here, We change our strategy. Earlier we were trying to stop five in a row. Now, We shall try to rely on exact five-in-a-row to win by making it a six in a row. If we mark the opposite corners with the same sign, we cannot have exact five in a row. If all non-corner cells of diagonal are marked the same as corners, it shall become a six in a row.

After this, the problem is just finding a valid pairing of cells to ensure victory. I ain’t gonna spoil the fun by helping you here, though will share the pairings used by tester and editorialist. Implementation is just a piece of cake then!

Click to view

Tester


1  3  7  7  4  2
5 11 12 15 15  6
8 11 12 16 16 10
8 13 13 17 18 10
4 14 14 17 18  3
2  6  9  9  5  1

Editorialist


1  3  7  7  5  2
4 11 17 18 11  6
9 13 15 15 14 10
9 13 16 16 14 10
5 12 17 18 12  3
2  6  8  8  4  1

Time Complexity

Time complexity is O(T*C) per test case where C is the constant factor.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile: