INS14J - Checkers
Digo has completed all his initial assignments and is now eyeing for a promotion in the CIA office. There is only one seat available for which there are two contenders, Digo and his arch rival Sharry. Both are equally qualified for the promotion and their interviewer finds himself unable to chose between the two of them. Finally he decided to settle it by allowing the two gentlemen to play a game and see who wins it.
In the game, there is an infinite grid, with certain cells filled with checkers. Each checker occupies exactly one cell, and the cells are 0-indexed. The positions of the checkers are given in the form of Cartesian coordinates (x, y).
For example a grid with 5 checkers placed at positions {(1, 0), (1, 2), (2, 5), (4, 2), (4, 4)} would look like:
There are an infinite number of diagonals of the form y = x + k, where k is an integer, drawn on this grid. Each diagonal can be uniquely identified by the value of this 'k', which is known as the index of the diagonal. There is at most one checker on every diagonal. In one turn, a person can chose a checker and move it along the diagonal it lies on, in the south-west direction only (i.e. towards decreasing coordinates). The checkers cannot be moved outside the first quadrant (i.e., their coordinates can never be made negative throughout the game). Whenever a person moves a checker, the checker lying on the next higher occupied diagonal moves an equal distance along the north-east direction. A diagonal with a greater index is said to be higher than a diagonal with a smaller index. Thus if the person moves the checker at position (4, 2) {diagonal index - 2} one cell south-west, the checker at position (1, 0) {diagonal index -1} moves one cell north-east.
The final position of the checkers after this move would be:
Note that if a person moves the checker lying on the highest occupied diagonal (the checker at position (2, 5) in our case), no other checker is disturbed.
The game ends when no move is possible. The last person to make a move wins. Sharry is an over-confident guy and allows Digo to move first. Help Digo determine whether he will win the game or not.
NOTE: Large input files. Use faster I/O.
Input
The first line contains T, the number of test cases.The first line of every test case contains N, the number of checkers on the grid. This is followed by N lines. The ith line contains two integers x[i] and y[i], which are the coordinates of the ith checker.
Output
For every test case output a single line containing "Yes" if it is possible for Digo to win the game, or "No" otherwise. (quotes added for clarity)Constraints
1 <= T <= 201 <= N <= 10000
0 <= x[i], y[i] <= 1000000000
Example
Input: 1 5 1 0 1 2 2 5 4 2 4 4 Output: Yes
hide comments
|
Piyush Kumar:
2016-06-22 15:03:16
Without the images,its still a bit unclear. I am getting WA.
|
|
Mitch Schwartz:
2014-07-01 18:33:21
I think the images aren't necessary to understand the problem.
|
|
wisfaq:
2014-07-01 14:37:48
It seems that the domain where the images were hosted doesn't exist any more.
|
|
NISHANT RAJ:
2014-06-05 06:28:41
I am also unable to see the image..
|
|
Bhavik:
2014-06-04 15:26:26
i am unable to see images!!am i the only one or others are also facing the same problem?? Last edit: 2014-06-04 15:31:07 |
Added by: | Surya Kiran |
Date: | 2014-03-20 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Insomnia 2014 |