1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Tree Recovery
Contest: Codeforces Global Round 21
Difficulty rating: 2600
Tags: brute force, constructive algorithms, dfs and similar, dsu, graphs, trees

Fishingprince loves trees. A tree is a connected undirected graph without cycles.

Fishingprince has a tree of $$$n$$$ vertices. The vertices are numbered $$$1$$$ through $$$n$$$. Let $$$d(x,y)$$$ denote the shortest distance on the tree from vertex $$$x$$$ to vertex $$$y$$$, assuming that the length of each edge is $$$1$$$.

However, the tree was lost in an accident. Fortunately, Fishingprince still remembers some information about the tree. More specifically, for every triple of integers $$$x,y,z$$$ ($$$1\le x<y\le n$$$, $$$1\le z\le n$$$) he remembers whether $$$d(x,z)=d(y,z)$$$ or not.

Help him recover the structure of the tree, or report that no tree satisfying the constraints exists.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 200$$$). Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2\le n\le 100$$$) — the number of vertices in the tree.

Then $$$n-1$$$ lines follow. The $$$i$$$-th line of these $$$n-1$$$ lines contains $$$n-i$$$ strings of length $$$n$$$ consisting of 0 and 1. If the $$$k$$$-th character in the $$$j$$$-th string of the $$$i$$$-th line is 0, it means that $$$d(i,k)\ne d(i+j,k)$$$; if the $$$k$$$-th character in the $$$j$$$-th string of the $$$i$$$-th line is 1, it means that $$$d(i,k)=d(i+j,k)$$$.

It is guaranteed that in one input file,

- there are at most $$$2$$$ test cases that have $$$n>50$$$;
- there are at most $$$5$$$ test cases that have $$$n>20$$$.

Output format:
For each test case:

- if no answer exists, output No;
- otherwise, on the first line output Yes. Then output $$$n-1$$$ lines. Each line should contain two integers $$$x,y$$$ ($$$1\le x,y\le n$$$), denoting an edge between vertices $$$x$$$ and $$$y$$$ of the tree. If there are multiple solutions, print any.

When printing Yes and No, you can print each letter in any case (upper or lower).

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

Example input:
5
2
00
2
10
3
001 000
000
3
001 010
000
5
00000 01001 00000 01100
00000 10000 00000
00000 11010
00000

Example output:
Yes
1 2
No
Yes
1 3
2 3
No
Yes
1 2
1 4
2 3
2 5

Editorial:
Construct a graph with $$$\binom n2$$$ vertices $$$(1,2),(1,3),\dots,(n-1,n)$$$.
If $$$dis(a,b)=dis(b,c)$$$, link an undirected edge between $$$(a,b)$$$ and $$$(b,c)$$$.
Observe that all edges in the tree form a connected component of size exactly $$$n-1$$$ in the graph!
Find all components of size $$$n-1$$$ and try if all vertices in it form a tree that satisfy the input. There are at most $$$\dfrac n2$$$ such components, so complexity is $$$O(n^4)$$$. Proper pre-computation and the usage of bitsets can reduce the complexity to $$$O(n^4/w)$$$.
Puzzles
Contest: Codeforces Round 196 (Div. 2)
Difficulty rating: 900
Tags: greedy

The end of the school year is near and Ms. Manana, the teacher, will soon have to say goodbye to a yet another class. She decided to prepare a goodbye present for her n students and give each of them a jigsaw puzzle (which, as wikipedia states, is a tiling puzzle that requires the assembly of numerous small, often oddly shaped, interlocking and tessellating pieces).

The shop assistant told the teacher that there are m puzzles in the shop, but they might differ in difficulty and size. Specifically, the first jigsaw puzzle consists of f1 pieces, the second one consists of f2 pieces and so on.

Ms. Manana doesn't want to upset the children, so she decided that the difference between the numbers of pieces in her presents must be as small as possible. Let A be the number of pieces in the largest puzzle that the teacher buys and B be the number of pieces in the smallest such puzzle. She wants to choose such n puzzles that A - B is minimum possible. Help the teacher and find the least possible value of A - B.

Input format:
The first line contains space-separated integers n and m (2 ≤ n ≤ m ≤ 50). The second line contains m space-separated integers f1, f2, ..., fm (4 ≤ fi ≤ 1000) — the quantities of pieces in the puzzles sold in the shop.

Output format:
Print a single integer — the least possible difference the teacher can obtain.

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

Note:
Sample 1. The class has 4 students. The shop sells 6 puzzles. If Ms. Manana buys the first four puzzles consisting of 10, 12, 10 and 7 pieces correspondingly, then the difference between the sizes of the largest and the smallest puzzle will be equal to 5. It is impossible to obtain a smaller difference. Note that the teacher can also buy puzzles 1, 3, 4 and 5 to obtain the difference 5.

Example input:
4 6
10 12 10 7 5 22

Example output:
5

Editorial:
Routine Problem
Contest: Codeforces Round 196 (Div. 2)
Difficulty rating: 1400
Tags: greedy, math, number theory

Manao has a monitor. The screen of the monitor has horizontal to vertical length ratio a:b. Now he is going to watch a movie. The movie's frame has horizontal to vertical length ratio c:d. Manao adjusts the view in such a way that the movie preserves the original frame ratio, but also occupies as much space on the screen as possible and fits within it completely. Thus, he may have to zoom the movie in or out, but Manao will always change the frame proportionally in both dimensions.

Calculate the ratio of empty screen (the part of the screen not occupied by the movie) to the total screen size. Print the answer as an irreducible fraction p / q.

Input format:
A single line contains four space-separated integers a, b, c, d (1 ≤ a, b, c, d ≤ 1000).

Output format:
Print the answer to the problem as "p/q", where p is a non-negative integer, q is a positive integer and numbers p and q don't have a common divisor larger than 1.

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

Note:
Sample 1. Manao's monitor has a square screen. The movie has 3:2 horizontal to vertical length ratio. Obviously, the movie occupies most of the screen if the width of the picture coincides with the width of the screen. In this case, only 2/3 of the monitor will project the movie in the horizontal dimension:

Sample 2. This time the monitor's width is 4/3 times larger than its height and the movie's frame is square. In this case, the picture must take up the whole monitor in the vertical dimension and only 3/4 in the horizontal dimension:

Example input:
1 1 3 2

Example output:
1/3

Example input:
4 3 2 2

Example output:
1/4

Editorial:
Quiz
Contest: Codeforces Round 196 (Div. 2)
Difficulty rating: 1600
Tags: binary search, greedy, math, matrices, number theory

Manao is taking part in a quiz. The quiz consists of n consecutive questions. A correct answer gives one point to the player. The game also has a counter of consecutive correct answers. When the player answers a question correctly, the number on this counter increases by 1. If the player answers a question incorrectly, the counter is reset, that is, the number on it reduces to 0. If after an answer the counter reaches the number k, then it is reset, and the player's score is doubled. Note that in this case, first 1 point is added to the player's score, and then the total score is doubled. At the beginning of the game, both the player's score and the counter of consecutive correct answers are set to zero.

Manao remembers that he has answered exactly m questions correctly. But he does not remember the order in which the questions came. He's trying to figure out what his minimum score may be. Help him and compute the remainder of the corresponding number after division by 1000000009 (109 + 9).

Input format:
The single line contains three space-separated integers n, m and k (2 ≤ k ≤ n ≤ 109; 0 ≤ m ≤ n).

Output format:
Print a single integer — the remainder from division of Manao's minimum possible score in the quiz by 1000000009 (109 + 9).

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

Note:
Sample 1. Manao answered 3 questions out of 5, and his score would double for each two consecutive correct answers. If Manao had answered the first, third and fifth questions, he would have scored as much as 3 points.

Sample 2. Now Manao answered 4 questions. The minimum possible score is obtained when the only wrong answer is to the question 4.

Also note that you are asked to minimize the score and not the remainder of the score modulo 1000000009. For example, if Manao could obtain either 2000000000 or 2000000020 points, the answer is 2000000000 mod 1000000009, even though 2000000020 mod 1000000009 is a smaller number.

Example input:
5 3 2

Example output:
3

Example input:
5 4 2

Example output:
6

Editorial:
Book of Evil
Contest: Codeforces Round 196 (Div. 2)
Difficulty rating: 2000
Tags: dfs and similar, divide and conquer, dp, trees

Paladin Manao caught the trail of the ancient Book of Evil in a swampy area. This area contains n settlements numbered from 1 to n. Moving through the swamp is very difficult, so people tramped exactly n - 1 paths. Each of these paths connects some pair of settlements and is bidirectional. Moreover, it is possible to reach any settlement from any other one by traversing one or several paths.

The distance between two settlements is the minimum number of paths that have to be crossed to get from one settlement to the other one. Manao knows that the Book of Evil has got a damage range d. This means that if the Book of Evil is located in some settlement, its damage (for example, emergence of ghosts and werewolves) affects other settlements at distance d or less from the settlement where the Book resides.

Manao has heard of m settlements affected by the Book of Evil. Their numbers are p1, p2, ..., pm. Note that the Book may be affecting other settlements as well, but this has not been detected yet. Manao wants to determine which settlements may contain the Book. Help him with this difficult task.

Input format:
The first line contains three space-separated integers n, m and d (1 ≤ m ≤ n ≤ 100000; 0 ≤ d ≤ n - 1). The second line contains m distinct space-separated integers p1, p2, ..., pm (1 ≤ pi ≤ n). Then n - 1 lines follow, each line describes a path made in the area. A path is described by a pair of space-separated integers ai and bi representing the ends of this path.

Output format:
Print a single number — the number of settlements that may contain the Book of Evil. It is possible that Manao received some controversial information and there is no settlement that may contain the Book. In such case, print 0.

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

Note:
Sample 1. The damage range of the Book of Evil equals 3 and its effects have been noticed in settlements 1 and 2. Thus, it can be in settlements 3, 4 or 5.

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

Example output:
3

Editorial:
Divisor Tree
Contest: Codeforces Round 196 (Div. 2)
Difficulty rating: 2200
Tags: brute force, number theory, trees

A divisor tree is a rooted tree that meets the following conditions:

- Each vertex of the tree contains a positive integer number.
- The numbers written in the leaves of the tree are prime numbers.
- For any inner vertex, the number within it is equal to the product of the numbers written in its children.

Manao has n distinct integers a1, a2, ..., an. He tries to build a divisor tree which contains each of these numbers. That is, for each ai, there should be at least one vertex in the tree which contains ai. Manao loves compact style, but his trees are too large. Help Manao determine the minimum possible number of vertices in the divisor tree sought.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 8). The second line contains n distinct space-separated integers ai (2 ≤ ai ≤ 1012).

Output format:
Print a single integer — the minimum number of vertices in the divisor tree that contains each of the numbers ai.

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

Note:
Sample 1. The smallest divisor tree looks this way:

Sample 2. In this case you can build the following divisor tree:

Sample 3. Note that the tree can consist of a single vertex.

Example input:
2
6 10

Example output:
7

Example input:
4
6 72 8 4

Example output:
12

Editorial:
Prison Break
Contest: Technocup 2021 - Elimination Round 2
Difficulty rating: 800
Tags: brute force, math

There is a prison that can be represented as a rectangular matrix with $$$n$$$ rows and $$$m$$$ columns. Therefore, there are $$$n \cdot m$$$ prison cells. There are also $$$n \cdot m$$$ prisoners, one in each prison cell. Let's denote the cell in the $$$i$$$-th row and the $$$j$$$-th column as $$$(i, j)$$$.

There's a secret tunnel in the cell $$$(r, c)$$$, that the prisoners will use to escape! However, to avoid the risk of getting caught, they will escape at night.

Before the night, every prisoner is in his own cell. When night comes, they can start moving to adjacent cells. Formally, in one second, a prisoner located in cell $$$(i, j)$$$ can move to cells $$$( i - 1 , j )$$$ , $$$( i + 1 , j )$$$ , $$$( i , j - 1 )$$$ , or $$$( i , j + 1 )$$$, as long as the target cell is inside the prison. They can also choose to stay in cell $$$(i, j)$$$.

The prisoners want to know the minimum number of seconds needed so that every prisoner can arrive to cell $$$( r , c )$$$ if they move optimally. Note that there can be any number of prisoners in the same cell at the same time.

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

Each of the next $$$t$$$ lines contains four space-separated integers $$$n$$$, $$$m$$$, $$$r$$$, $$$c$$$ ($$$1 \le r \le n \le 10^9$$$, $$$1 \le c \le m \le 10^9$$$).

Output format:
Print $$$t$$$ lines, the answers for each test case.

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

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

Example output:
18
4
6

Editorial:
The problem is equivalent to finding the farthest cell from $$$( x , y )$$$. It is easy to see that, if they move optimally, $$$( i , j )$$$ can reach $$$( x , y )$$$ just by moving in an L shape, and this is equivalent to the Manhattan distance between the two points. The longest distance a prisoner will move on rows is $$$max( x - 1 , n - x )$$$, and for the columns it is $$$( y - 1 , m - y )$$$. So answer is just $$$max( x - 1 , n - x ) + max( y - 1 , m - y )$$$
Sequence of Comparisons
Contest: Kotlin Heroes: Episode 8
Difficulty rating: 800
Tags: *special

Once upon a time, Petya had an array of integers $$$a$$$ of length $$$n$$$. But over time, the array itself was lost, and only $$$n-1$$$ results of comparisons of neighboring array elements remained. In other words, for every $$$i$$$ from $$$1$$$ to $$$n-1$$$, Petya knows exactly one of these three facts:

- $$$a_i < a_{i+1}$$$;
- $$$a_i = a_{i+1}$$$;
- $$$a_i > a_{i+1}$$$.

Petya wonders if it is possible to uniquely determine the result of comparing $$$a_1$$$ and $$$a_n$$$.

You have to help Petya determine the result of comparing $$$a_1$$$ and $$$a_n$$$ or report that the result cannot be determined unambiguously.

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

The only line of the test case contains the string $$$s$$$ ($$$1 \le |s| \le 100$$$), where $$$s_i$$$ is:

- <, if $$$a_i < a_{i + 1}$$$;
- >, if $$$a_i > a_{i + 1}$$$;
- =, if $$$a_i = a_{i + 1}$$$.

Output format:
For each test case, print a single string equal to:

- <, if $$$a_1 < a_n$$$;
- >, if $$$a_1 > a_n$$$;
- =, if $$$a_1 = a_n$$$;
- ?, if it is impossible to uniquely determine the result of the comparison.

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

Note:
Consider the test cases of the example:

- in the first test case, it's easy to see that $$$a_1 > a_4$$$ since $$$a_1 > a_2 > a_3 > a_4$$$;
- in the second test case, both sequences $$$[1, 2, 0, 10, 10, 15]$$$ and $$$[10, 11, 1, 2, 2, 5]$$$ meet the constraints; in the first one, $$$a_1 < a_6$$$, and in the second one, $$$a_1 > a_6$$$, so it's impossible to compare $$$a_1$$$ and $$$a_6$$$;
- in the third test case, we already know that $$$a_1 = a_2$$$;
- in the fourth test case, it's easy to see that $$$a_3 = a_4 = a_5$$$, and $$$a_1 < a_2 < a_3$$$, so $$$a_1 < a_5$$$.

Example input:
4
>>>
<><=<
=
<<==

Example output:
>
?
=
<

Editorial:
If $$$s$$$ consists only of characters =, then $$$a_1 = a_n$$$.
If $$$s$$$ consists only of characters < and =, then $$$a_1 < a_n$$$.
If $$$s$$$ consists only of characters > and =, then $$$a_1 > a_n$$$.
Otherwise, it is impossible to uniquely determine the relationship between $$$a_1$$$ and $$$a_n$$$. For example, this can be checked on the strings <> and ><.
Boys and Girls
Contest: Codeforces Round 154 (Div. 2)
Difficulty rating: 1100
Tags: greedy

There are n boys and m girls studying in the class. They should stand in a line so that boys and girls alternated there as much as possible. Let's assume that positions in the line are indexed from left to right by numbers from 1 to n + m. Then the number of integers i (1 ≤ i < n + m) such that positions with indexes i and i + 1 contain children of different genders (position i has a girl and position i + 1 has a boy or vice versa) must be as large as possible.

Help the children and tell them how to form the line.

Input format:
The single line of the input contains two integers n and m (1 ≤ n, m ≤ 100), separated by a space.

Output format:
Print a line of n + m characters. Print on the i-th position of the line character "B", if the i-th position of your arrangement should have a boy and "G", if it should have a girl.

Of course, the number of characters "B" should equal n and the number of characters "G" should equal m. If there are multiple optimal solutions, print any of them.

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

Note:
In the first sample another possible answer is BGBGBG.

In the second sample answer BBGBGB is also optimal.

Example input:
3 3

Example output:
GBGBGB

Example input:
4 2

Example output:
BGBGBB

Editorial:
Physics Practical
Contest: Codeforces Round 154 (Div. 2)
Difficulty rating: 1400
Tags: binary search, dp, sortings, two pointers

One day Vasya was on a physics practical, performing the task on measuring the capacitance. He followed the teacher's advice and did as much as n measurements, and recorded the results in the notebook. After that he was about to show the results to the teacher, but he remembered that at the last lesson, the teacher had made his friend Petya redo the experiment because the largest and the smallest results differed by more than two times. Vasya is lazy, and he does not want to redo the experiment. He wants to do the task and go home play computer games. So he decided to cheat: before Vasya shows the measurements to the teacher, he will erase some of them, so as to make the largest and the smallest results of the remaining measurements differ in no more than two times. In other words, if the remaining measurements have the smallest result x, and the largest result y, then the inequality y ≤ 2·x must fulfill. Of course, to avoid the teacher's suspicion, Vasya wants to remove as few measurement results as possible from his notes.

Help Vasya, find what minimum number of measurement results he will have to erase from his notes so that the largest and the smallest of the remaining results of the measurements differed in no more than two times.

Input format:
The first line contains integer n (2 ≤ n ≤ 105) — the number of measurements Vasya made. The second line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 5000) — the results of the measurements. The numbers on the second line are separated by single spaces.

Output format:
Print a single integer — the minimum number of results Vasya will have to remove.

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

Note:
In the first sample you can remove the fourth and the sixth measurement results (values 8 and 7). Then the maximum of the remaining values will be 5, and the minimum one will be 3. Or else, you can remove the third and fifth results (both equal 3). After that the largest remaining result will be 8, and the smallest one will be 4.

Example input:
6
4 5 3 8 3 7

Example output:
2

Example input:
4
4 3 2 4

Example output:
0

Editorial:
Table with Letters - 2
Contest: Codeforces Round 154 (Div. 2)
Difficulty rating: 2000
Tags: brute force, two pointers

Vasya has recently started to learn English. Now he needs to remember how to write English letters. He isn't sure about some of them, so he decided to train a little.

He found a sheet of squared paper and began writing arbitrary English letters there. In the end Vasya wrote n lines containing m characters each. Thus, he got a rectangular n × m table, each cell of the table contained some English letter. Let's number the table rows from top to bottom with integers from 1 to n, and columns — from left to right with integers from 1 to m.

After that Vasya looked at the resulting rectangular table and wondered, how many subtables are there, that matches both following conditions:

- the subtable contains at most k cells with "a" letter;
- all letters, located in all four corner cells of the subtable, are equal.

Formally, a subtable's definition is as follows. It is defined by four integers x1, y1, x2, y2 such that 1 ≤ x1 < x2 ≤ n, 1 ≤ y1 < y2 ≤ m. Then the subtable contains all such cells (x, y) (x is the row number, y is the column number), for which the following inequality holds x1 ≤ x ≤ x2, y1 ≤ y ≤ y2. The corner cells of the table are cells (x1, y1), (x1, y2), (x2, y1), (x2, y2).

Vasya is already too tired after he's been writing letters to a piece of paper. That's why he asks you to count the value he is interested in.

Input format:
The first line contains three integers n, m, k (2 ≤ n, m ≤ 400; 0 ≤ k ≤ n·m).

Next n lines contain m characters each — the given table. Each character of the table is a lowercase English letter.

Output format:
Print a single integer — the number of required subtables.

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

Note:
There are two suitable subtables in the first sample: the first one's upper left corner is cell (2, 2) and lower right corner is cell (3, 3), the second one's upper left corner is cell (2, 1) and lower right corner is cell (3, 4).

Example input:
3 4 4
aabb
baab
baab

Example output:
2

Example input:
4 5 1
ababa
ccaca
ccacb
cbabc

Example output:
1

Editorial: