Point Elimination
실버 II의견: 0
You have \(N\) (\(2 \leq N \leq 10^5, N\) is even\()\) points \((x_i,y_i)\)
(\(1 \leq x_i, y_i \leq 10^6\)) on an infinite 2D-coordinate plane.
You can perform the following two types of operations any number of times:
- Choose two points that are directly adjacent to each other (manhattan distance of \(1\)), and remove both points.
- Choose any two points and swap their y-coordinates. Formally, points \((a,b)\) and \((c,d)\) become \((a,d)\) and \((c,b)\) respectively.
Determine if it is possible to eliminate all points on the board. Note that it
may be the case that two points may map to the same coordinate; they should
still be treated as different points. You also may not directly delete points on
the same coordinate, as they are technically not directly adjacent.
Problem credits: Alex Pylypenko, Chongtian Ma
SCORING
- Input 2: \(T\le 1000\), \(N \le 6\)
- Inputs 3-5: \(N\le 100\)
- Inputs 6-11: No additional constraints.
Problem credits: Alex Pylypenko, Chongtian Ma
The first line contains \(T\) (\(1 \leq T \leq 5000\)), the number of test cases.
The first line of each test case contains an integer \(N\).
The following \(N\) lines contain two integers \(x_i\) and \(y_i\).
It is guaranteed that the sum of \(N\) over all test cases does not exceed
\(5\cdot 10^5\).
For each test case, output "YES" or "NO" on a new line.
4
2
1 1
1 1
4
6 10
7 11
8 1
8 1
6
1 2
1 3
1 4
1 5
10 10
11 10
6
1 1
1 1
1 1
1 1
10 10
11 11NO
YES
YES
NOFor the first test, the only two points are equal, so no swaps will do anything.
Thus, our answer is NO.
In the second test, we can swap the y-coordinates of 6 and 7 with 8 and 8. Then,
we can remove the first two points (horizontal adjacency) and the last two (vertical).
For the third test, no swaps are needed. We can remove the first pair, second, and
third.
In the last test, it can be shown that no matter how we swap the y-coordinates, we
will never be able to remove all the points in adjacent pairs.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Third Contest > Silver
평가 및 의견
Point Elimination
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Point Elimination