Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Scary Big Chessboard

By himuhasib · Limits 1s, 512 MB

Our friend Alice got stuck in a big chessboard. The chessboard has N rows and N columns. Some cells are black, and some cells are white and the remaining cells do not have any color. She can paint the cells which do not already have any color on it to black or white. But she can't repaint the cells which already have some color. If she can make the chessboard consistent, then she can escape the chessboard. A chessboard is consistent if all of its cells are colored and every pair of adjacent cells have different color.

Now you are given the initial configuration of the chessboard. Let's help Alice find out if she can escape the chessboard.


In the first line of input, there will be a number T (1 ≤ T ≤ 50) denoting the number of test cases. T test cases follow.

The first line of each test case contains two space separated integers N(1 ≤ N ≤ 1018) and Q(0 ≤ Q ≤ 1000). Here the chessboard's size is NxN and Q cells are already colored.
On the next Q lines, there will be three integers x, y, c. The y'th(1 ≤ y ≤ N) cell of the x'th(1 ≤ x ≤ N) row has color c(1 ≤ c ≤ 2). You can be sure that no cell will appear more than once in a test case.

Here color c can take two values:
1 represents the color black.
2 represents the color white.


For each test case print a single line with yes or no.

If Alice can escape the chessboard, print yes for that corresponding test case. Otherwise, print no.


2 2
2 2 1
2 1 1
1 1
1 1 2



45% Solution Ratio

NirjhorEarliest, May '17

MarzukFastest, 0.0s

NirjhorLightest, 131 kB

SIR.24Shortest, 506B


Login to submit


You can check if the chessboard is consistent by checking if all the black cells have same parity an...

Toph uses cookies. By continuing you agree to our Cookie Policy.