1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Robot Rapping Results Report
Contest: CROC 2016 - Elimination Round
Difficulty rating: 1800
Tags: binary search, dp, graphs

While Farmer John rebuilds his farm in an unfamiliar portion of Bovinia, Bessie is out trying some alternative jobs. In her new gig as a reporter, Bessie needs to know about programming competition results as quickly as possible. When she covers the 2016 Robot Rap Battle Tournament, she notices that all of the robots operate under deterministic algorithms. In particular, robot i will beat robot j if and only if robot i has a higher skill level than robot j. And if robot i beats robot j and robot j beats robot k, then robot i will beat robot k. Since rapping is such a subtle art, two robots can never have the same skill level.

Given the results of the rap battles in the order in which they were played, determine the minimum number of first rap battles that needed to take place before Bessie could order all of the robots by skill level.

Input format:
The first line of the input consists of two integers, the number of robots n (2 ≤ n ≤ 100 000) and the number of rap battles m ($$1 \leq m \leq \min \left( 100\,000, \frac{n(n-1)}{2} \right)$$).

The next m lines describe the results of the rap battles in the order they took place. Each consists of two integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi), indicating that robot ui beat robot vi in the i-th rap battle. No two rap battles involve the same pair of robots.

It is guaranteed that at least one ordering of the robots satisfies all m relations.

Output format:
Print the minimum k such that the ordering of the robots by skill level is uniquely defined by the first k rap battles. If there exists more than one ordering that satisfies all m relations, output -1.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, the robots from strongest to weakest must be (4, 2, 1, 3), which Bessie can deduce after knowing the results of the first four rap battles.

In the second sample, both (1, 3, 2) and (3, 1, 2) are possible orderings of the robots from strongest to weakest after both rap battles.

Example input:
4 5
2 1
1 3
2 3
4 2
4 3

Example output:
4

Example input:
3 2
1 2
3 2

Example output:
-1

Editorial:
The robots will become fully sorted if and only if there exists a path with n vertices in the graph of relations. We can compute the longest path in this directed acyclic graph (DAG) by dynamic programming / topologically sorting. After computing this longest path, it obviously must be unique. If the longest path has less than n vertices, then print  - 1.
Otherwise, there is a path of length n - 1 edges. Therefore, the point at which we know the whole ordering is the latest time that an edge from this path is added.
The time this takes is O(n).
Alternatively, do the same approach as above but instead binary search on the number of relations needed. This might be easier to see, and takes $${\mathcal {O}}(n\log n).$$
Telephone Number
Contest: Educational Codeforces Round 65 (Rated for Div. 2)
Difficulty rating: 800
Tags: brute force, greedy, strings

A telephone number is a sequence of exactly 11 digits, where the first digit is 8. For example, the sequence 80011223388 is a telephone number, but the sequences 70011223388 and 80000011223388 are not.

You are given a string $$$s$$$ of length $$$n$$$, consisting of digits.

In one operation you can delete any character from string $$$s$$$. For example, it is possible to obtain strings 112, 111 or 121 from string 1121.

You need to determine whether there is such a sequence of operations (possibly empty), after which the string $$$s$$$ becomes a telephone number.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of string $$$s$$$.

The second line of each test case contains the string $$$s$$$ ($$$|s| = n$$$) consisting of digits.

Output format:
For each test print one line.

If there is a sequence of operations, after which $$$s$$$ becomes a telephone number, print YES.

Otherwise, print NO.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case you need to delete the first and the third digits. Then the string 7818005553535 becomes 88005553535.

Example input:
2
13
7818005553535
11
31415926535

Example output:
YES
NO

Editorial:
To solve this problem, we just need to find the first occurrence of the digit $$$8$$$, let's denote it as $$$x$$$.
Now if $$$n - x \ge 10$$$ then answer is $$$YES$$$, otherwise $$$NO$$$.
News Distribution
Contest: Educational Codeforces Round 65 (Rated for Div. 2)
Difficulty rating: 1400
Tags: dfs and similar, dsu, graphs

In some social network, there are $$$n$$$ users communicating with each other in $$$m$$$ groups of friends. Let's analyze the process of distributing some news between users.

Initially, some user $$$x$$$ receives the news from some source. Then he or she sends the news to his or her friends (two users are friends if there is at least one group such that both of them belong to this group). Friends continue sending the news to their friends, and so on. The process ends when there is no pair of friends such that one of them knows the news, and another one doesn't know.

For each user $$$x$$$ you have to determine what is the number of users that will know the news if initially only user $$$x$$$ starts distributing it.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 5 \cdot 10^5$$$) — the number of users and the number of groups of friends, respectively.

Then $$$m$$$ lines follow, each describing a group of friends. The $$$i$$$-th line begins with integer $$$k_i$$$ ($$$0 \le k_i \le n$$$) — the number of users in the $$$i$$$-th group. Then $$$k_i$$$ distinct integers follow, denoting the users belonging to the $$$i$$$-th group.

It is guaranteed that $$$\sum \limits_{i = 1}^{m} k_i \le 5 \cdot 10^5$$$.

Output format:
Print $$$n$$$ integers. The $$$i$$$-th integer should be equal to the number of users that will know the news if user $$$i$$$ starts distributing it.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
7 5
3 2 5 4
0
2 1 2
1 1
2 6 7

Example output:
4 4 1 4 4 2 2

Editorial:
The first intention after reading the problem is to reformulate it in graph theory terms. Let people be vertices, edge between two vertices $$$x$$$ and $$$y$$$ exists if $$$x$$$ and $$$y$$$ have some group in common. Basically, if person $$$x$$$ starts distributing the news, everyone in his connectivity component recieves it. Thus, the task is to calculate the number of vertices of each vertex component.
As of now, the graph can have up to $$$O(n^2)$$$ edges (consider the case where everyone is in the same group). Let's reduce the number of edges without changing connectivity components. For each group you know for sure that people in it are in the same component. Let's connect not just every pair of vertices in it, but every pair of neighbouring ones in each group. It's easy to see that they are still in the same component.
This graph will have $$$O(\sum \limits_{i = 1}^{m} k_i)$$$ edges which is a much smaller number. You can use dfs or dsu to find the components and their sizes.
Overall complexity: $$$O(n + \sum \limits_{i = 1}^{m} k_i)$$$.
Range Deleting
Contest: Educational Codeforces Round 65 (Rated for Div. 2)
Difficulty rating: 2100
Tags: binary search, combinatorics, data structures, two pointers

You are given an array consisting of $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ and an integer $$$x$$$. It is guaranteed that for every $$$i$$$, $$$1 \le a_i \le x$$$.

Let's denote a function $$$f(l, r)$$$ which erases all values such that $$$l \le a_i \le r$$$ from the array $$$a$$$ and returns the resulting array. For example, if $$$a = [4, 1, 1, 4, 5, 2, 4, 3]$$$, then $$$f(2, 4) = [1, 1, 5]$$$.

Your task is to calculate the number of pairs $$$(l, r)$$$ such that $$$1 \le l \le r \le x$$$ and $$$f(l, r)$$$ is sorted in non-descending order. Note that the empty array is also considered sorted.

Input format:
The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n, x \le 10^6$$$) — the length of array $$$a$$$ and the upper limit for its elements, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots a_n$$$ ($$$1 \le a_i \le x$$$).

Output format:
Print the number of pairs $$$1 \le l \le r \le x$$$ such that $$$f(l, r)$$$ is sorted in non-descending order.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case correct pairs are $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$ and $$$(2, 3)$$$.

In the second test case correct pairs are $$$(1, 3)$$$, $$$(1, 4)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(3, 3)$$$ and $$$(3, 4)$$$.

Example input:
3 3
2 3 1

Example output:
4

Example input:
7 4
1 3 1 2 2 4 3

Example output:
6

Editorial:
Lets find the maximum number $$$pref$$$ such that all values $$$1, 2, \dots, pref$$$ form the non-descending order array. It can be done the following way. Let values $$$1, 2, \dots, x$$$ form the non-descending order array. Then values $$$1, 2, \dots, x, x+1$$$ will form the non-descending order array if the first occurrence of $$$x+1$$$ in array $$$a$$$ is after the last occurrence of $$$x$$$. In similar manner we can find the minimum number $$$suf$$$ such that all values $$$suf, suf+1, \dots, x$$$ form the non-descending order array.
Now let's find out how to get the minimum number $$$s$$$ such that all values $$$1, 2, \dots, p, s, s + 1, \dots, x$$$ form the non-descending order array if we fixed the value $$$p$$$. We denote this value $$$s$$$ for some fixed value $$$p$$$ as $$$f(p)$$$. Firstly, conditions $$$s > p$$$, $$$suf \le s$$$ and $$$p \le pre$$$ should hold. Secondly, there should be no such a pair $$$(m, r)$$$ that conditions $$$1 \le m < r \le n$$$, $$$1 \le a_r, \le p$$$ and $$$s \le a_m \le x$$$ hold. Since the condition $$$p \le pre$$$ is satisfied, it means that $$$s$$$ must be greater than $$$\max\limits_{1 \le i \le lst} a_i$$$, where $$$lst$$$ is the last occurrence of $$$p$$$ in array $$$a$$$.
In this way the answer is $$$\sum\limits_{i=1}^{pref} (x - f(i) + 1)$$$.
Leaving the Bar
Contest: Codeforces Round 492 (Div. 1) [Thanks, uDebug!]
Difficulty rating: 2300
Tags: brute force, data structures, geometry, greedy, math, sortings

For a vector $$$\vec{v} = (x, y)$$$, define $$$|v| = \sqrt{x^2 + y^2}$$$.

Allen had a bit too much to drink at the bar, which is at the origin. There are $$$n$$$ vectors $$$\vec{v_1}, \vec{v_2}, \cdots, \vec{v_n}$$$. Allen will make $$$n$$$ moves. As Allen's sense of direction is impaired, during the $$$i$$$-th move he will either move in the direction $$$\vec{v_i}$$$ or $$$-\vec{v_i}$$$. In other words, if his position is currently $$$p = (x, y)$$$, he will either move to $$$p + \vec{v_i}$$$ or $$$p - \vec{v_i}$$$.

Allen doesn't want to wander too far from home (which happens to also be the bar). You need to help him figure out a sequence of moves (a sequence of signs for the vectors) such that his final position $$$p$$$ satisfies $$$|p| \le 1.5 \cdot 10^6$$$ so that he can stay safe.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of moves.

Each of the following lines contains two space-separated integers $$$x_i$$$ and $$$y_i$$$, meaning that $$$\vec{v_i} = (x_i, y_i)$$$. We have that $$$|v_i| \le 10^6$$$ for all $$$i$$$.

Output format:
Output a single line containing $$$n$$$ integers $$$c_1, c_2, \cdots, c_n$$$, each of which is either $$$1$$$ or $$$-1$$$. Your solution is correct if the value of $$$p = \sum_{i = 1}^n c_i \vec{v_i}$$$, satisfies $$$|p| \le 1.5 \cdot 10^6$$$.

It can be shown that a solution always exists under the given constraints.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3
999999 0
0 999999
999999 0

Example output:
1 1 -1

Example input:
1
-824590 246031

Example output:
1

Editorial:
We first prove a claim which will help us significantly. The claim is that among any three vectors $$$\vec{v_1}, \vec{v_2}, \vec{v_3}$$$ of lengths at most $$$r$$$, then some sum $$$\vec{v_i} + \vec{v_j}$$$ or difference $$$\vec{v_i} - \vec{v_j}$$$ has at length at most $$$r$$$.
Draw a circle with radius $$$r$$$ centered at the origin. If we plot the vectors $$$\vec{v_1}, \vec{v_2}, \vec{v_3}, -\vec{v_1}, -\vec{v_2},-\vec{v_3}$$$ from the origin, two of these will lie in the same $$$60^{\circ}$$$ sector. Any two points in this sector will have distance at most $$$r$$$.
Therefore, as long as there are at least $$$3$$$ vectors, two of them can be combined and the input constraints will still be satisfied. In the final step, we can combine two vectors of length at most $$$r$$$ into one of length at most $$$\sqrt{2} r$$$.
Implementation can be done in a number of ways: for example, constructing a binary tree with the input vectors as leaves, or maintaining sets of signed vectors and merging small sets to large sets. These approaches can take $$$O(n)$$$ or $$$O(n \log n)$$$.
Number Clicker
Contest: Codeforces Round 492 (Div. 1) [Thanks, uDebug!]
Difficulty rating: 2700
Tags: divide and conquer, graphs, meet-in-the-middle, number theory

Allen is playing Number Clicker on his phone.

He starts with an integer $$$u$$$ on the screen. Every second, he can press one of 3 buttons.

1. Turn $$$u \to u+1 \pmod{p}$$$.
2. Turn $$$u \to u+p-1 \pmod{p}$$$.
3. Turn $$$u \to u^{p-2} \pmod{p}$$$.

Allen wants to press at most 200 buttons and end up with $$$v$$$ on the screen. Help him!

Input format:
The first line of the input contains 3 positive integers: $$$u, v, p$$$ ($$$0 \le u, v \le p-1$$$, $$$3 \le p \le 10^9 + 9$$$). $$$p$$$ is guaranteed to be prime.

Output format:
On the first line, print a single integer $$$\ell$$$, the number of button presses. On the second line, print integers $$$c_1, \dots, c_\ell$$$, the button presses. For $$$1 \le i \le \ell$$$, $$$1 \le c_i \le 3$$$.

We can show that the answer always exists.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
In the first example the integer on the screen changes as $$$1 \to 2 \to 3$$$.

In the second example the integer on the screen changes as $$$3 \to 2$$$.

Example input:
1 3 5

Example output:
2
1 1

Example input:
3 2 5

Example output:
1
3

Editorial:
Our first observation is that the game can be modeled the following way. Construct an undirected graph on $$$\{0, 1, \dots, p-1\}$$$ such that $$$i$$$ is connected to $$$i-1, i+1,$$$ and $$$i^{p-2} \pmod{p}.$$$
We want to find a path of length at most 200 between $$$u$$$ and $$$v$$$ in this graph. Running a BFS will take too long, so we need different techniques. We present two solutions, which both essentially use the fact that the graph is almost "random". This follows from some known number theoretic results on expander graphs (keyword is "Margulis expanders").
Solution 1: Generate $$$\sqrt{p}$$$ random paths of length $$$100$$$ from vertex $$$u$$$. Now, generate random paths from $$$v$$$ of length $$$100$$$ until some pair of endpoints coincide. By the birthday paradox, assuming that the graph is approximately random, the runtime will be $$$O(\sqrt{p} \log p).$$$
Solution 2: We can try running a simultaneous BFS from both directions (starting at $$$u$$$ and $$$v$$$). When they meet, make that path. If you are careful, it should be possible to cover $$$\le 10^7$$$ vertices, which should then run in time.
Additionally, our tester found a different solution. It suffices to find a path from $$$u \to 1$$$ of length $$$100.$$$ The way we do this is: pick a random $$$x \pmod{p}.$$$ Now run the Euclidean algorithm on $$$(ux \pmod{p}, x)$$$, using operation $$$2$$$ for a normal subtraction step, and a $$$3$$$ for the flipping the two entries step. It happens to take a few steps in most cases, but we have no proof.
Cowmpany Cowmpensation
Contest: Codeforces Round 492 (Div. 1) [Thanks, uDebug!]
Difficulty rating: 2700
Tags: combinatorics, dp, math, trees

Allen, having graduated from the MOO Institute of Techcowlogy (MIT), has started a startup! Allen is the president of his startup. He also hires $$$n-1$$$ other employees, each of which is assigned a direct superior. If $$$u$$$ is a superior of $$$v$$$ and $$$v$$$ is a superior of $$$w$$$ then also $$$u$$$ is a superior of $$$w$$$. Additionally, there are no $$$u$$$ and $$$v$$$ such that $$$u$$$ is the superior of $$$v$$$ and $$$v$$$ is the superior of $$$u$$$. Allen himself has no superior. Allen is employee number $$$1$$$, and the others are employee numbers $$$2$$$ through $$$n$$$.

Finally, Allen must assign salaries to each employee in the company including himself. Due to budget constraints, each employee's salary is an integer between $$$1$$$ and $$$D$$$. Additionally, no employee can make strictly more than his superior.

Help Allen find the number of ways to assign salaries. As this number may be large, output it modulo $$$10^9 + 7$$$.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$D$$$ ($$$1 \le n \le 3000$$$, $$$1 \le D \le 10^9$$$).

The remaining $$$n-1$$$ lines each contain a single positive integer, where the $$$i$$$-th line contains the integer $$$p_i$$$ ($$$1 \le p_i \le i$$$). $$$p_i$$$ denotes the direct superior of employee $$$i+1$$$.

Output format:
Output a single integer: the number of ways to assign salaries modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample case, employee 2 and 3 report directly to Allen. The three salaries, in order, can be $$$(1,1,1)$$$, $$$(2,1,1)$$$, $$$(2,1,2)$$$, $$$(2,2,1)$$$ or $$$(2,2,2)$$$.

In the second sample case, employee 2 reports to Allen and employee 3 reports to employee 2. In order, the possible salaries are $$$(1,1,1)$$$, $$$(2,1,1)$$$, $$$(2,2,1)$$$, $$$(2,2,2)$$$, $$$(3,1,1)$$$, $$$(3,2,1)$$$, $$$(3,2,2)$$$, $$$(3,3,1)$$$, $$$(3,3,2)$$$, $$$(3,3,3)$$$.

Example input:
3 2
1
1

Example output:
5

Example input:
3 3
1
2

Example output:
10

Editorial:
A immediate simple observation is that we can compute the answer in $$$O(nD)$$$ with a simple dynamic program. How to speed it up though?
To speed it up, we need the following lemma.
Lemma 1: For a tree with $$$n$$$ vertices, the answer is a polynomial in $$$D$$$ of degree at most $$$n$$$.
We can prove this via induction, and the fact that for any polynomial $$$p(x)$$$ of degree $$$d$$$, the sum $$$p(0) + p(1) + \dots + p(n)$$$ is a polynomial in $$$n$$$ of degree $$$d+1.$$$
Now the solution is easy: compute the answer for $$$0 \le D \le n$$$ and use interpolation to compute the answer for $$$D > n.$$$ The complexity is $$$O(n^2)$$$ for the initial dp and $$$O(n)$$$ for the interpolation step.
Li Hua and Maze
Contest: Codeforces Round 864 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, flows, graphs, greedy, implementation

There is a rectangular maze of size $$$n\times m$$$. Denote $$$(r,c)$$$ as the cell on the $$$r$$$-th row from the top and the $$$c$$$-th column from the left. Two cells are adjacent if they share an edge. A path is a sequence of adjacent empty cells.

Each cell is initially empty. Li Hua can choose some cells (except $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$) and place an obstacle in each of them. He wants to know the minimum number of obstacles needed to be placed so that there isn't a path from $$$(x_1, y_1)$$$ to $$$(x_2, y_2)$$$.

Suppose you were Li Hua, please solve this problem.

Input format:
The first line contains the single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases.

The first line of each test case contains two integers $$$n,m$$$ ($$$4\le n,m\le 10^9$$$) — the size of the maze.

The second line of each test case contains four integers $$$x_1,y_1,x_2,y_2$$$ ($$$1\le x_1,x_2\le n, 1\le y_1,y_2\le m$$$) — the coordinates of the start and the end.

It is guaranteed that $$$|x_1-x_2|+|y_1-y_2|\ge 2$$$.

Output format:
For each test case print the minimum number of obstacles you need to put on the field so that there is no path from $$$(x_1, y_1)$$$ to $$$(x_2, y_2)$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In test case 1, you can put obstacles on $$$(1,3), (2,3), (3,2), (4,2)$$$. Then the path from $$$(2,2)$$$ to $$$(3,3)$$$ will not exist.

Example input:
3
4 4
2 2 3 3
6 7
1 1 2 3
9 9
5 1 3 6

Example output:
4
2
3

Editorial:
We can put obstacles around $$$(x_1,y_1)$$$ or $$$(x_2,y_2)$$$ and the better one is the answer. More formally, let's define a function $$$f$$$:
$$$$$$ f(x,y)= \begin{cases} 2,&(x,y)\textrm{ is on the corner}\\ 3,&(x,y)\textrm{ is on the border}\\ 4,&(x,y)\textrm{ is in the middle}\\ \end{cases} $$$$$$
Then the answer is $$$\min\{f(x_1,y_1),f(x_2,y_2)\}$$$.
Without loss of generality, assume that $$$f(x_1,y_1)\le f(x_2,y_2)$$$. As the method is already given, the answer is at most $$$f(x_1,y_1)$$$. Let's prove that the answer is at least $$$f(x_1,y_1)$$$.
If $$$(x_1,y_1)$$$ is on the corner, we can always find two paths from $$$(x_1,y_1)$$$ to $$$(x_2,y_2)$$$ without passing the same cell (except $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$).
Similarly, we can always find three or four paths respectively if $$$(x_1,y_1)$$$ is on the border or in the middle.
As the paths have no common cell, we need to put an obstacle on each path, so the answer is at least $$$f(x_1,y_1)$$$.
In conclusion, the answer is exactly $$$f(x_1,y_1)$$$. As we assumed that $$$f(x_1,y_1)\le f(x_2,y_2)$$$, the answer to the original problem is $$$\min\{f(x_1,y_1),f(x_2,y_2)\}$$$.
Time complexity: $$$O(1)$$$.
Li Hua and Pattern
Contest: Codeforces Round 864 (Div. 2)
Difficulty rating: 1100
Tags: constructive algorithms, greedy

Li Hua has a pattern of size $$$n\times n$$$, each cell is either blue or red. He can perform exactly $$$k$$$ operations. In each operation, he chooses a cell and changes its color from red to blue or from blue to red. Each cell can be chosen as many times as he wants. Is it possible to make the pattern, that matches its rotation by $$$180^{\circ}$$$?

Suppose you were Li Hua, please solve this problem.

Input format:
The first line contains the single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains two integers $$$n,k$$$ ($$$1\le n\le 10^3,0\le k \le 10^9$$$) — the size of the pattern and the number of operations.

Each of next $$$n$$$ lines contains $$$n$$$ integers $$$a_{i,j}$$$ ($$$a_{i,j}\in\{0,1\}$$$) — the initial color of the cell, $$$0$$$ for blue and $$$1$$$ for red.

It's guaranteed that sum of $$$n$$$ over all test cases does not exceed $$$10^3$$$.

Output format:
For each set of input, print "YES" if it's possible to make the pattern, that matches its rotation by $$$180^{\circ}$$$ after applying exactly $$$k$$$ of operations, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In test case 1, you can't perform any operation. The pattern after rotation is on the right.

In test case 2, you can perform operations on $$$(2,1),(3,2),(3,4)$$$. The pattern after operations is in the middle and the pattern after rotation is on the right.

Example input:
3
4 0
1 1 1 1
0 0 0 1
1 0 1 0
1 1 1 1
4 3
1 0 1 1
1 0 0 0
0 1 0 1
1 1 0 1
5 4
0 0 0 0 0
0 1 1 1 1
0 1 0 0 0
1 1 1 1 1
0 0 0 0 0

Example output:
NO
YES
YES

Editorial:
We can calculate the minimum needed operations $$$k_{\min}$$$ easily by enumerating through the cells and performing an operation if the color of the cell is different from the targeted cell. Obviously, if $$$k < k_{\min}$$$, the problem has no solution.
Otherwise, there are two cases:
• If $$$2\mid n$$$, the solution exists if and only if $$$2\mid(k-k_{\min})$$$, as we must perform two operations each time to meet the requirement.
• If $$$2\nmid n$$$, the solution always exists, as we can perform the remaining operations at the center of the pattern.
Time complexity: $$$O(n^2)$$$.