The annual Joint School Olympiad in Informatics (JSOI) Lockout TicTacToe is back! After some exciting rounds between some of the smartest people in Hong Kong, the grand finale of div 3 tournament is finally going to begin with HarryBOB versus cl_lmc.
In a round, the two contestants will have unlimited time to solve problems from the given problem set of $N^2$ problems, arranged in an $N \times N$ grid. Each cell in the grid is initially uncolored. Whoever solves a problem first gets the corresponding square colored with their color. In the case where both contestants solve a problem at the same time, the square will remain uncolored for the rest of the game. Whichever contestant occupies $N$ cells that form a line horizontally, vertically or diagonally wins the round. If both contestants form a line at the same time or no one can form a line, it's a draw and no one wins. (The rule is a bit different from the real JSOI, be careful)
For example, in all three $3 \times 3$ grids below, the blue contestant wins the round:
After an insider from the organizers leaked the problem set to cl_lmc, he estimated that for the problem in the $i$-th row and $j$-th column, it takes $A_{i,j}$ minutes for him to solve and $B_{i,j}$ minutes for HarryBOB to solve. However, he only has the strength to solve at most $N$ tasks while HarryBOB has no such limitation. Since he doesn’t have enough time to solve any of the problems before the round starts, he wants to know if there exists a strategy such that he must win the round regardless of how HarryBOB plays.
Input
The first line contains one integer, $N$.
The next $N$ lines contain $N$ integers each.
For the $i$-th line, the $j$-th integer is $A_{i,j}$.
The next $N$ lines contain $N$ integers each.
For the $i$-th line, the $j$-th integer is $B_{i,j}$.
Output
If such a strategy exists, output Yes; otherwise, output No.
Constraints
For all cases, $1 \le N \le 1000, 1 \le A_{i,j}, B_{i,j} \le 10^9$
Subtask 1 (5%): $N = 1$
Subtask 2 (15%): $N = 2$
Subtask 3 (25%): $1 \le N \le 9$
Subtask 4 (20%): $A_{i,j} = 10^9$ for all $2 \le i \le N, 1 \le j \le N$
Subtask 5 (10%): $N$ is odd
Subtask 6 (25%): No additional constraints
Sample Test Cases
| Input | Output | |
|---|---|---|
| 3 1 2 2 2 2 1 3 2 4 2 3 2 3 6 4 5 4 8 |
Yes | |
| Denote the problem in the $i$-th row and $j$-th column as $P_{i,j}$. A winning strategy is to solve $P_{2,1}, P_{2,3}, P_{2,2}$ in order. It can be shown that this strategy can always win the round. | ||
| 3 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 |
No | |
| Notice that solving $P_{1,1}, P_{1,2}, P_{1,3}$ in order does not guarantee a win, since it is possible for HarryBOB to solve $P_{1,3}$ right after the round begins, making $P_{1,3}$ remain uncolored for the rest of the game. | ||
Scoring: Per Subtask
Authored by wy23493
Appeared in 2025 Wah Yan Interschool Olympiad in Informatics 🤯🥷⚡🧠🏆