1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Harder Problem
Contest: Codeforces Round 993 (Div. 4)
Difficulty rating: 1100
Tags: constructive algorithms, greedy, math

Given a sequence of positive integers, a positive integer is called a mode of the sequence if it occurs the maximum number of times that any positive integer occurs. For example, the mode of $$$[2,2,3]$$$ is $$$2$$$. Any of $$$9$$$, $$$8$$$, or $$$7$$$ can be considered to be a mode of the sequence $$$[9,9,8,8,7,7]$$$.

You gave UFO an array $$$a$$$ of length $$$n$$$. To thank you, UFO decides to construct another array $$$b$$$ of length $$$n$$$ such that $$$a_i$$$ is a mode of the sequence $$$[b_1, b_2, \ldots, b_i]$$$ for all $$$1 \leq i \leq n$$$.

However, UFO doesn't know how to construct array $$$b$$$, so you must help her. Note that $$$1 \leq b_i \leq n$$$ must hold for your array for all $$$1 \leq i \leq n$$$.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of $$$a$$$.

The following line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output $$$n$$$ numbers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq n$$$) on a new line. It can be shown that $$$b$$$ can always be constructed. If there are multiple possible arrays, you may print any.

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

Note:
Let's verify the correctness for our sample output in test case $$$2$$$.

- At $$$i = 1$$$, $$$1$$$ is the only possible mode of $$$[1]$$$.
- At $$$i = 2$$$, $$$1$$$ is the only possible mode of $$$[1, 1]$$$.
- At $$$i = 3$$$, $$$1$$$ is the only possible mode of $$$[1, 1, 2]$$$.
- At $$$i = 4$$$, $$$1$$$ or $$$2$$$ are both modes of $$$[1, 1, 2, 2]$$$. Since $$$a_i = 2$$$, this array is valid.

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

Example output:
1 2
1 1 2 2
4 5 5 1 1 2 2 3
1 8 2 2 1 3 3 9 1 1

Editorial:
Insane Problem
Contest: Codeforces Round 993 (Div. 4)
Difficulty rating: 1300
Tags: binary search, greedy, implementation, math, number theory

Wave is given five integers $$$k$$$, $$$l_1$$$, $$$r_1$$$, $$$l_2$$$, and $$$r_2$$$. Wave wants you to help her count the number of ordered pairs $$$(x, y)$$$ such that all of the following are satisfied:

- $$$l_1 \leq x \leq r_1$$$.
- $$$l_2 \leq y \leq r_2$$$.
- There exists a non-negative integer $$$n$$$ such that $$$\frac{y}{x} = k^n$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The only line of each test case contains five integers $$$k$$$, $$$l_1$$$, $$$r_1$$$, $$$l_2$$$, and $$$r_2$$$ ($$$2 \leq k \leq 10^9, 1 \leq l_1 \leq r_1 \leq 10^9, 1 \leq l_2 \leq r_2 \leq 10^9$$$).

Output format:
For each test case, output the number of matching ordered pairs $$$(x, y)$$$ on a new line.

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

Note:
In the third test case, the matching ordered pairs are the following:

- $$$(5,15)$$$
- $$$(5,45)$$$
- $$$(6,18)$$$
- $$$(6,54)$$$
- $$$(7,21)$$$
- $$$(7,63)$$$

In the fourth test case, the only valid ordered pair is $$$(1,1\,000\,000\,000)$$$

Example input:
5
2 2 6 2 12
2 1 1000000000 1 1000000000
3 5 7 15 63
1000000000 1 5 6 1000000000
15 17 78 2596 20914861

Example output:
12
1999999987
6
1
197

Editorial:
Easy Demon Problem
Contest: Codeforces Round 993 (Div. 4)
Difficulty rating: 1900
Tags: binary search, brute force, data structures, math, number theory

For an arbitrary grid, Robot defines its beauty to be the sum of elements in the grid.

Robot gives you an array $$$a$$$ of length $$$n$$$ and an array $$$b$$$ of length $$$m$$$. You construct a $$$n$$$ by $$$m$$$ grid $$$M$$$ such that $$$M_{i,j}=a_i\cdot b_j$$$ for all $$$1 \leq i \leq n$$$ and $$$1 \leq j \leq m$$$.

Then, Robot gives you $$$q$$$ queries, each consisting of a single integer $$$x$$$. For each query, determine whether or not it is possible to perform the following operation exactly once so that $$$M$$$ has a beauty of $$$x$$$:

1. Choose integers $$$r$$$ and $$$c$$$ such that $$$1 \leq r \leq n$$$ and $$$1 \leq c \leq m$$$
2. Set $$$M_{i,j}$$$ to be $$$0$$$ for all ordered pairs $$$(i,j)$$$ such that $$$i=r$$$, $$$j=c$$$, or both.

Note that queries are not persistent, meaning that you do not actually set any elements to $$$0$$$ in the process — you are only required to output if it is possible to find $$$r$$$ and $$$c$$$ such that if the above operation is performed, the beauty of the grid will be $$$x$$$. Also, note that you must perform the operation for each query, even if the beauty of the original grid is already $$$x$$$.

Input format:
The first line contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$1 \leq n,m \leq 2\cdot 10^5, 1 \leq q \leq 5\cdot 10^4$$$) — the length of $$$a$$$, the length of $$$b$$$, and the number of queries respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq |a_i| \leq n$$$).

The third line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \leq |b_i| \leq m$$$).

The following $$$q$$$ lines each contain a single integer $$$x$$$ ($$$1 \leq |x| \leq 2\cdot 10^5$$$), the beauty of the grid you wish to achieve by setting all elements in a row and a column to $$$0$$$.

Output format:
For each testcase, output "YES" (without quotes) if there is a way to perform the aforementioned operation such that the beauty is $$$x$$$, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

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

Note:
In the second example, the grid is

0 -2 5 0 -3

0 4 -10 0 6

0 -6 15 0 -9

0 0 0 0 0

0 0 0 0 0

By performing the operation with $$$r=4$$$ and $$$c=2$$$, we create the following grid:

0 0 5 0 -3

0 0 -10 0 6

0 0 15 0 -9

0 0 0 0 0

0 0 0 0 0

which has beauty $$$4$$$. Thus, we output YES.

In the second query, selecting $$$r=3$$$ and $$$c=5$$$ creates a grid with beauty $$$-3$$$.

In the third query, selecting $$$r=3$$$ and $$$c=3$$$ creates a grid with beauty $$$5$$$.

Example input:
3 3 6
-2 3 -3
-2 2 -1
-1
1
-2
2
-3
3

Example output:
NO
YES
NO
NO
YES
NO

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

Example output:
YES
YES
YES
YES
NO
YES

Editorial:
Medium Demon Problem (easy version)
Contest: Codeforces Round 993 (Div. 4)
Difficulty rating: 1700
Tags: dfs and similar, graph matchings, graphs, implementation, trees

This is the easy version of the problem. The key difference between the two versions is highlighted in bold.

A group of $$$n$$$ spiders has come together to exchange plushies. Initially, each spider has $$$1$$$ plushie. Every year, if spider $$$i$$$ has at least one plushie, he will give exactly one plushie to spider $$$r_i$$$. Otherwise, he will do nothing. Note that all plushie transfers happen at the same time. In this version, if any spider has more than $$$1$$$ plushie at any point in time, they will throw all but $$$1$$$ away.

The process is stable in the current year if each spider has the same number of plushies (before the current year's exchange) as he did the previous year (before the previous year's exchange). Note that year $$$1$$$ can never be stable.

Find the first year in which the process becomes stable.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of spiders.

The following line contains $$$n$$$ integers $$$r_1, r_2, \ldots, r_n$$$ ($$$1 \leq r_i \leq n, r_i \neq i$$$) — the recipient of the plushie of each spider.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output an integer on a new line, the first year in which the process becomes stable.

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

Note:
For the second test case:

- At year $$$1$$$, the following array shows the number of plushies each spider has: $$$[1, 1, 1, 1, 1]$$$. Then, year $$$1$$$'s exchange happens.
- At year $$$2$$$, the following array shows the number of plushies each spider has: $$$[1, 1, 1, 1, 1]$$$. Since this array is the same as the previous year, this year is stable.

For the third test case:

- At year $$$1$$$, the following array shows the number of plushies each spider has: $$$[1, 1, 1, 1, 1]$$$. Then, year $$$1$$$'s exchange happens.
- At year $$$2$$$, the following array shows the number of plushies each spider has: $$$[1, 1, 1, 1, 0]$$$. Then, year $$$2$$$'s exchange happens. Note that even though two spiders gave spider $$$2$$$ plushies, spider $$$2$$$ may only keep one plushie.
- At year $$$3$$$, the following array shows the number of plushies each spider has: $$$[1, 1, 0, 1, 0]$$$. Then, year $$$3$$$'s exchange happens.
- At year $$$4$$$, the following array shows the number of plushies each spider has: $$$[1, 1, 0, 0, 0]$$$. Then, year $$$4$$$'s exchange happens.
- At year $$$5$$$, the following array shows the number of plushies each spider has: $$$[1, 1, 0, 0, 0]$$$. Since this array is the same as the previous year, this year is stable.

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

Example output:
2
2
5
4
5

Editorial:
Medium Demon Problem (hard version)
Contest: Codeforces Round 993 (Div. 4)
Difficulty rating: 1900
Tags: dfs and similar, dp, dsu, graphs, implementation, trees

This is the hard version of the problem. The key difference between the two versions is highlighted in bold.

A group of $$$n$$$ spiders has come together to exchange plushies. Initially, each spider has $$$1$$$ plushie. Every year, if spider $$$i$$$ has at least one plushie, he will give exactly one plushie to spider $$$r_i$$$. Otherwise, he will do nothing. Note that all plushie transfers happen at the same time. In this version, each spider is allowed to have more than 1 plushie at any point in time.

The process is stable in the current year if each spider has the same number of plushies (before the current year's exchange) as he did the previous year (before the previous year's exchange). Note that year $$$1$$$ can never be stable.

Find the first year in which the process becomes stable.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of spiders.

The following line contains $$$n$$$ integers $$$r_1, r_2, \ldots, r_n$$$ ($$$1 \leq r_i \leq n, r_i \neq i$$$) — the recipient of the plushie of each spider.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output an integer on a new line, the first year in which the process becomes stable.

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

Note:
For the second test case:

- At year $$$1$$$, the following array shows the number of plushies each spider has: $$$[1, 1, 1, 1, 1]$$$. Then, year $$$1$$$'s exchange happens.
- At year $$$2$$$, the following array shows the number of plushies each spider has: $$$[1, 1, 1, 1, 1]$$$. Since this array is the same as the previous year, this year is stable.

For the third test case:

- At year $$$1$$$, the following array shows the number of plushies each spider has: $$$[1, 1, 1, 1, 1]$$$. Then, year $$$1$$$'s exchange happens.
- At year $$$2$$$, the following array shows the number of plushies each spider has: $$$[1, 2, 1, 1, 0]$$$. Then, year $$$2$$$'s exchange happens.
- At year $$$3$$$, the following array shows the number of plushies each spider has: $$$[1, 3, 0, 1, 0]$$$. Then, year $$$3$$$'s exchange happens.
- At year $$$4$$$, the following array shows the number of plushies each spider has: $$$[1, 4, 0, 0, 0]$$$. Then, year $$$4$$$'s exchange happens.
- At year $$$5$$$, the following array shows the number of plushies each spider has: $$$[1, 4, 0, 0, 0]$$$. Since this array is the same as the previous year, this year is stable.

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

Example output:
2
2
5
5
5

Editorial:
Hard Demon Problem
Contest: Codeforces Round 993 (Div. 4)
Difficulty rating: 2100
Tags: constructive algorithms, data structures, dp, implementation, math

Swing is opening a pancake factory! A good pancake factory must be good at flattening things, so Swing is going to test his new equipment on 2D matrices.

Swing is given an $$$n \times n$$$ matrix $$$M$$$ containing positive integers. He has $$$q$$$ queries to ask you.

For each query, he gives you four integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ and asks you to flatten the submatrix bounded by $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ into an array $$$A$$$. Formally, $$$A = [M_{(x1,y1)}, M_{(x1,y1+1)}, \ldots, M_{(x1,y2)}, M_{(x1+1,y1)}, M_{(x1+1,y1+1)}, \ldots, M_{(x2,y2)}]$$$.

The following image depicts the flattening of a submatrix bounded by the red dotted lines. The orange arrows denote the direction that the elements of the submatrix are appended to the back of $$$A$$$, and $$$A$$$ is shown at the bottom of the image.

Afterwards, he asks you for the value of $$$\sum_{i=1}^{|A|} A_i \cdot i$$$ (sum of $$$A_i \cdot i$$$ over all $$$i$$$).

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases.

The first line of each test contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n \leq 2000, 1 \leq q \leq 10^6$$$) — the length of $$$M$$$ and the number of queries.

The following $$$n$$$ lines contain $$$n$$$ integers each, the $$$i$$$'th of which contains $$$M_{(i,1)}, M_{(i,2)}, \ldots, M_{(i,n)}$$$ ($$$1 \leq M_{(i, j)} \leq 10^6$$$).

The following $$$q$$$ lines contain four integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, and $$$y_2$$$ ($$$1 \leq x_1 \leq x_2 \leq n, 1 \leq y_1 \leq y_2 \leq n$$$) — the bounds of the query.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$ and the sum of $$$q$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, output the results of the $$$q$$$ queries on a new line.

Constraints:
Time limit: 3.5 s
Memory limit: 512.0 MB

Note:
In the second query of the first test case, $$$A = [9, 5, 5, 2]$$$. Therefore, the sum is $$$1 \cdot 9 + 2 \cdot 5 + 3 \cdot 5 + 4 \cdot 2 = 42$$$.

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

Example output:
500 42 168 
14 42 5

Editorial:
Perpendicular Segments
Contest: Educational Codeforces Round 171 (Rated for Div. 2)
Difficulty rating: 900
Tags: constructive algorithms, geometry, greedy, math

You are given a coordinate plane and three integers $$$X$$$, $$$Y$$$, and $$$K$$$. Find two line segments $$$AB$$$ and $$$CD$$$ such that

1. the coordinates of points $$$A$$$, $$$B$$$, $$$C$$$, and $$$D$$$ are integers;
2. $$$0 \le A_x, B_x, C_x, D_x \le X$$$ and $$$0 \le A_y, B_y, C_y, D_y \le Y$$$;
3. the length of segment $$$AB$$$ is at least $$$K$$$;
4. the length of segment $$$CD$$$ is at least $$$K$$$;
5. segments $$$AB$$$ and $$$CD$$$ are perpendicular: if you draw lines that contain $$$AB$$$ and $$$CD$$$, they will cross at a right angle.

Note that it's not necessary for segments to intersect. Segments are perpendicular as long as the lines they induce are perpendicular.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases. Next, $$$t$$$ cases follow.

The first and only line of each test case contains three integers $$$X$$$, $$$Y$$$, and $$$K$$$ ($$$1 \le X, Y \le 1000$$$; $$$1 \le K \le 1414$$$).

Additional constraint on the input: the values of $$$X$$$, $$$Y$$$, and $$$K$$$ are chosen in such a way that the answer exists.

Output format:
For each test case, print two lines. The first line should contain $$$4$$$ integers $$$A_x$$$, $$$A_y$$$, $$$B_x$$$, and $$$B_y$$$ — the coordinates of the first segment.

The second line should also contain $$$4$$$ integers $$$C_x$$$, $$$C_y$$$, $$$D_x$$$, and $$$D_y$$$ — the coordinates of the second segment.

If there are multiple answers, print any of them.

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

Note:
The answer for the first test case is shown below:

Example input:
4
1 1 1
3 4 1
4 3 3
3 4 4

Example output:
0 0 1 0
0 0 0 1
2 4 2 2
0 1 1 1
0 0 1 3
1 2 4 1
0 1 3 4
0 3 3 0

Editorial:
Let's look at all segments with a fixed angle between them and the X-axis. Let's take the shortest one with integer coordinates and length at least $$$K$$$ as $$$AB$$$. Let's say that a bounding box of $$$AB$$$ has width $$$w$$$ and height $$$h$$$.
It's easy to see that a bounding box of segment $$$CD$$$ will have width at least $$$h$$$ and height at least $$$w$$$, since the shortest segment $$$CD$$$ will be just the segment $$$AB$$$ rotated at ninety degrees.
So, in order to fit both segments $$$AB$$$ and $$$CD$$$, both $$$h$$$ and $$$w$$$ should be at most $$$M = \min(X, Y)$$$. But if both $$$w \le M$$$ and $$$h \le M$$$, then what is the longest segment that can fit in such a bounding box? The answer is to set $$$h = w = M$$$, then the length $$$|AB| \le M \sqrt{2}$$$.
In such a way, we found out that $$$K$$$ must not exceed $$$M \sqrt{2}$$$, but if $$$K \le M \sqrt{2}$$$, then we can always take the following two segments: $$$(0, 0) - (M, M)$$$ and $$$(0, M) - (M, 0)$$$ where $$$M = \min(X, Y)$$$. They are perpendicular, fit in the allowed rectangle, and have length exactly $$$M \sqrt{2}$$$.
Black Cells
Contest: Educational Codeforces Round 171 (Rated for Div. 2)
Difficulty rating: 1300
Tags: binary search, brute force, constructive algorithms, greedy

You are given a strip divided into cells, numbered from left to right from $$$0$$$ to $$$10^{18}$$$. Initially, all cells are white.

You can perform the following operation: choose two white cells $$$i$$$ and $$$j$$$, such that $$$i \ne j$$$ and $$$|i - j| \le k$$$, and paint them black.

A list $$$a$$$ is given. All cells from this list must be painted black. Additionally, at most one cell that is not in this list can also be painted black. Your task is to determine the minimum value of $$$k$$$ for which this is possible.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 < a_i < 10^{18}$$$; $$$a_i < a_{i + 1}$$$).

Additional constraint on the input: the sum of $$$n$$$ across all test cases does not exceed $$$2000$$$.

Output format:
For each test case, print a single integer — the minimum value of $$$k$$$ for which it is possible to paint all the given cells black.

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

Note:
In the first example, with $$$k=1$$$, it is possible to paint the cells $$$(1, 2)$$$.

In the second example, with $$$k=1$$$, it is possible to paint the cells $$$(7, 8)$$$.

In the third example, with $$$k=2$$$, it is possible to paint the cells $$$(2, 4)$$$ and $$$(8, 9)$$$.

In the fourth example, with $$$k=3$$$, it is possible to paint the cells $$$(0, 1)$$$, $$$(5, 8)$$$ and $$$(10, 13)$$$.

Example input:
4
2
1 2
1
7
3
2 4 9
5
1 5 8 10 13

Example output:
1
1
2
3

Editorial:
First, let's consider the case when $$$n$$$ is even. It is not difficult to notice that to minimize the value of $$$k$$$, the cells have to be painted in the following pairs: $$$(a_1, a_2)$$$, $$$(a_3, a_4)$$$, ..., $$$(a_{n-1}, a_n)$$$. Then the answer is equal to the maximum of the distances between the cells in the pairs.
For odd $$$n$$$, it is necessary to add one more cell (so that cells can be divided into pairs). If we add a new cell from the segment $$$(a_i, a_{i+1})$$$, it's paired either with the $$$i$$$-th cell or with the $$$(i+1)$$$-th cell (depending on the parity of $$$i$$$). Therefore, to minimize the value of $$$k$$$, the new cell should be chosen among $$$(a_i+1)$$$ and $$$(a_{i+1}-1)$$$ (in fact, only one of the two options is needed, but we can keep both). Note that one of these options may already be an existing cell, in which case it does not need to be considered. Thus, there are $$$O(n)$$$ options for the new cell, and for each of them, we can calculate the answer in $$$O(n)$$$ or $$$O(n\log{n})$$$, and take the minimum among them.
Thus, we obtained a solution in $$$O(n^2)$$$ (or $$$O(n^2\log{n})$$$ depending on the implementation). There is also a faster solution in $$$O(n)$$$, but it was not required for this problem.