1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Little Elephant and Broken Sorting
Contest: Codeforces Round 157 (Div. 1)
Difficulty rating: 2600
Tags: dp, math, probabilities

The Little Elephant loves permutations of integers from 1 to n very much. But most of all he loves sorting them. To sort a permutation, the Little Elephant repeatedly swaps some elements. As a result, he must receive a permutation 1, 2, 3, ..., n.

This time the Little Elephant has permutation p1, p2, ..., pn. Its sorting program needs to make exactly m moves, during the i-th move it swaps elements that are at that moment located at the ai-th and the bi-th positions. But the Little Elephant's sorting program happened to break down and now on every step it can equiprobably either do nothing or swap the required elements.

Now the Little Elephant doesn't even hope that the program will sort the permutation, but he still wonders: if he runs the program and gets some permutation, how much will the result of sorting resemble the sorted one? For that help the Little Elephant find the mathematical expectation of the number of permutation inversions after all moves of the program are completed.

We'll call a pair of integers i, j (1 ≤ i < j ≤ n) an inversion in permutatuon p1, p2, ..., pn, if the following inequality holds: pi > pj.

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 1000, n > 1) — the permutation size and the number of moves. The second line contains n distinct integers, not exceeding n — the initial permutation. Next m lines each contain two integers: the i-th line contains integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — the positions of elements that were changed during the i-th move.

Output format:
In the only line print a single real number — the answer to the problem. The answer will be considered correct if its relative or absolute error does not exceed 10 - 6.

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

Example input:
2 1
1 2
1 2

Example output:
0.500000000

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

Example output:
3.000000000

Editorial:
Little Elephant and Tree
Contest: Codeforces Round 157 (Div. 1)
Difficulty rating: 2400
Tags: data structures, dfs and similar, trees

The Little Elephant loves trees very much, he especially loves root trees.

He's got a tree consisting of n nodes (the nodes are numbered from 1 to n), with root at node number 1. Each node of the tree contains some list of numbers which initially is empty.

The Little Elephant wants to apply m operations. On the i-th operation (1 ≤ i ≤ m) he first adds number i to lists of all nodes of a subtree with the root in node number ai, and then he adds number i to lists of all nodes of the subtree with root in node bi.

After applying all operations the Little Elephant wants to count for each node i number ci — the number of integers j (1 ≤ j ≤ n; j ≠ i), such that the lists of the i-th and the j-th nodes contain at least one common number.

Help the Little Elephant, count numbers ci for him.

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 105) — the number of the tree nodes and the number of operations.

Each of the following n - 1 lines contains two space-separated integers, ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi), that mean that there is an edge between nodes number ui and vi.

Each of the following m lines contains two space-separated integers, ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi), that stand for the indexes of the nodes in the i-th operation.

It is guaranteed that the given graph is an undirected tree.

Output format:
In a single line print n space-separated integers — c1, c2, ..., cn.

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

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

Example output:
0 3 3 3 3

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

Example output:
0 6 7 6 0 2 0 5 4 5 5

Editorial:
Gift Carpet
Contest: Codeforces Round 894 (Div. 3)
Difficulty rating: 800
Tags: dp, greedy, implementation, strings

Recently, Tema and Vika celebrated Family Day. Their friend Arina gave them a carpet, which can be represented as an $$$n \cdot m$$$ table of lowercase Latin letters.

Vika hasn't seen the gift yet, but Tema knows what kind of carpets she likes. Vika will like the carpet if she can read her name on. She reads column by column from left to right and chooses one or zero letters from current column.

Formally, the girl will like the carpet if it is possible to select four distinct columns in order from left to right such that the first column contains "v", the second one contains "i", the third one contains "k", and the fourth one contains "a".

Help Tema understand in advance whether Vika will like Arina's gift.

Input format:
Each test consists of multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 20$$$) — the sizes of the carpet.

The next $$$n$$$ lines contain $$$m$$$ lowercase Latin letters each, describing the given carpet.

Output format:
For each set of input data, output "YES" if Vika will like the carpet, otherwise output "NO".

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

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

Note:
In the first sample, Vika can read her name from left to right.

In the second sample, Vika cannot read the character "v", so she will not like the carpet.

Example input:
5
1 4
vika
3 3
bad
car
pet
4 4
vvvv
iiii
kkkk
aaaa
4 4
vkak
iiai
avvk
viaa
4 7
vbickda
vbickda
vbickda
vbickda

Example output:
YES
NO
YES
NO
YES

Editorial:
Note that if the answer is «YES», then there exists a reading of the word «vika» in which the leftmost letter «v» is included. Among such readings, we can also consider the one in which the leftmost letter «i» is included, which is located to the right of the first occurrence of «v». Similarly, we can do the same for the remaining letters. Therefore, it is sufficient to greedily search for the characters in order.
Let's store the input data in a 2D array and process it by going through the columns from left to right. First, we will search for the character «v» by iterating through all the characters in each processed column. Once we find the character «v», we will similarly search for the character «i» and so on.
Sushi for Two
Contest: Codeforces Round 545 (Div. 2)
Difficulty rating: 900
Tags: binary search, greedy, implementation

Arkady invited Anna for a dinner to a sushi restaurant. The restaurant is a bit unusual: it offers $$$n$$$ pieces of sushi aligned in a row, and a customer has to choose a continuous subsegment of these sushi to buy.

The pieces of sushi are of two types: either with tuna or with eel. Let's denote the type of the $$$i$$$-th from the left sushi as $$$t_i$$$, where $$$t_i = 1$$$ means it is with tuna, and $$$t_i = 2$$$ means it is with eel.

Arkady does not like tuna, Anna does not like eel. Arkady wants to choose such a continuous subsegment of sushi that it has equal number of sushi of each type and each half of the subsegment has only sushi of one type. For example, subsegment $$$[2, 2, 2, 1, 1, 1]$$$ is valid, but subsegment $$$[1, 2, 1, 2, 1, 2]$$$ is not, because both halves contain both types of sushi.

Find the length of the longest continuous subsegment of sushi Arkady can buy.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 100\,000$$$) — the number of pieces of sushi.

The second line contains $$$n$$$ integers $$$t_1$$$, $$$t_2$$$, ..., $$$t_n$$$ ($$$t_i = 1$$$, denoting a sushi with tuna or $$$t_i = 2$$$, denoting a sushi with eel), representing the types of sushi from left to right.

It is guaranteed that there is at least one piece of sushi of each type. Note that it means that there is at least one valid continuous segment.

Output format:
Print a single integer — the maximum length of a valid continuous segment.

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

Note:
In the first example Arkady can choose the subsegment $$$[2, 2, 1, 1]$$$ or the subsegment $$$[1, 1, 2, 2]$$$ with length $$$4$$$.

In the second example there is no way but to choose one of the subsegments $$$[2, 1]$$$ or $$$[1, 2]$$$ with length $$$2$$$.

In the third example Arkady's best choice is the subsegment $$$[1, 1, 1, 2, 2, 2]$$$.

Example input:
7
2 2 2 1 1 2 2

Example output:
4

Example input:
6
1 2 1 2 1 2

Example output:
2

Editorial:
It is more or less obvious that the answer is the maximum among the minimums of the length of two consecutive segments of equal elements. As for implementation, just go from left to right and keep the last element, the length of the current segment and the length of the next segment. When the current element is not the same as the last element, update the answer.
Collecting Coins
Contest: Codeforces Round 615 (Div. 3)
Difficulty rating: 800
Tags: math

Polycarp has three sisters: Alice, Barbara, and Cerene. They're collecting coins. Currently, Alice has $$$a$$$ coins, Barbara has $$$b$$$ coins and Cerene has $$$c$$$ coins. Recently Polycarp has returned from the trip around the world and brought $$$n$$$ coins.

He wants to distribute all these $$$n$$$ coins between his sisters in such a way that the number of coins Alice has is equal to the number of coins Barbara has and is equal to the number of coins Cerene has. In other words, if Polycarp gives $$$A$$$ coins to Alice, $$$B$$$ coins to Barbara and $$$C$$$ coins to Cerene ($$$A+B+C=n$$$), then $$$a + A = b + B = c + C$$$.

Note that A, B or C (the number of coins Polycarp gives to Alice, Barbara and Cerene correspondingly) can be 0.

Your task is to find out if it is possible to distribute all $$$n$$$ coins between sisters in a way described above.

You have to answer $$$t$$$ independent test cases.

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

The next $$$t$$$ lines describe test cases. Each test case is given on a new line and consists of four space-separated integers $$$a, b, c$$$ and $$$n$$$ ($$$1 \le a, b, c, n \le 10^8$$$) — the number of coins Alice has, the number of coins Barbara has, the number of coins Cerene has and the number of coins Polycarp has.

Output format:
For each test case, print "YES" if Polycarp can distribute all $$$n$$$ coins between his sisters and "NO" otherwise.

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

Example input:
5
5 3 2 8
100 101 102 105
3 2 1 100000000
10 20 15 14
101 101 101 3

Example output:
YES
YES
NO
NO
YES

Editorial:
Suppose $$$a \le b \le c$$$. If it isn't true then let's rearrange our variables. Then we need at least $$$2c - b - a$$$ coins to make $$$a$$$, $$$b$$$ and $$$c$$$ equal. So if $$$n < 2c - b - a$$$ then the answer is "NO". Otherwise, the answer if "YES" if the number $$$n - (2c - b - a)$$$ is divisible by $$$3$$$. This is true because after making $$$a, b$$$ and $$$c$$$ equal we need to distribute all remaining candies between three sisters.
Product of Three Numbers
Contest: Codeforces Round 615 (Div. 3)
Difficulty rating: 1300
Tags: greedy, math, number theory

You are given one integer number $$$n$$$. Find three distinct integers $$$a, b, c$$$ such that $$$2 \le a, b, c$$$ and $$$a \cdot b \cdot c = n$$$ or say that it is impossible to do it.

If there are several answers, you can print any.

You have to answer $$$t$$$ independent test cases.

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

The next $$$n$$$ lines describe test cases. The $$$i$$$-th test case is given on a new line as one integer $$$n$$$ ($$$2 \le n \le 10^9$$$).

Output format:
For each test case, print the answer on it. Print "NO" if it is impossible to represent $$$n$$$ as $$$a \cdot b \cdot c$$$ for some distinct integers $$$a, b, c$$$ such that $$$2 \le a, b, c$$$.

Otherwise, print "YES" and any possible such representation.

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

Example input:
5
64
32
97
2
12345

Example output:
YES
2 4 8 
NO
NO
NO
YES
3 5 823

Editorial:
Suppose $$$a < b < c$$$. Let's try to minimize $$$a$$$ and maximize $$$c$$$. Let $$$a$$$ be the minimum divisor of $$$n$$$ greater than $$$1$$$. Then let $$$b$$$ be the minimum divisor of $$$\frac{n}{a}$$$ that isn't equal $$$a$$$ and $$$1$$$. If $$$\frac{n}{ab}$$$ isn't equal $$$a$$$, $$$b$$$ and $$$1$$$ then the answer is "YES", otherwise the answer is "NO".
Time complexity: $$$O(\sqrt{n})$$$ per query.
Three Paths on a Tree
Contest: Codeforces Round 615 (Div. 3)
Difficulty rating: 2000
Tags: dfs and similar, dp, greedy, trees

You are given an unweighted tree with $$$n$$$ vertices. Recall that a tree is a connected undirected graph without cycles.

Your task is to choose three distinct vertices $$$a, b, c$$$ on this tree such that the number of edges which belong to at least one of the simple paths between $$$a$$$ and $$$b$$$, $$$b$$$ and $$$c$$$, or $$$a$$$ and $$$c$$$ is the maximum possible. See the notes section for a better understanding.

The simple path is the path that visits each vertex at most once.

Input format:
The first line contains one integer number $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

Next $$$n - 1$$$ lines describe the edges of the tree in form $$$a_i, b_i$$$ ($$$1 \le a_i$$$, $$$b_i \le n$$$, $$$a_i \ne b_i$$$). It is guaranteed that given graph is a tree.

Output format:
In the first line print one integer $$$res$$$ — the maximum number of edges which belong to at least one of the simple paths between $$$a$$$ and $$$b$$$, $$$b$$$ and $$$c$$$, or $$$a$$$ and $$$c$$$.

In the second line print three integers $$$a, b, c$$$ such that $$$1 \le a, b, c \le n$$$ and $$$a \ne, b \ne c, a \ne c$$$.

If there are several answers, you can print any.

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

Note:
The picture corresponding to the first example (and another one correct answer):

If you choose vertices $$$1, 5, 6$$$ then the path between $$$1$$$ and $$$5$$$ consists of edges $$$(1, 2), (2, 3), (3, 4), (4, 5)$$$, the path between $$$1$$$ and $$$6$$$ consists of edges $$$(1, 2), (2, 3), (3, 4), (4, 6)$$$ and the path between $$$5$$$ and $$$6$$$ consists of edges $$$(4, 5), (4, 6)$$$. The union of these paths is $$$(1, 2), (2, 3), (3, 4), (4, 5), (4, 6)$$$ so the answer is $$$5$$$. It can be shown that there is no better answer.

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

Example output:
5
1 8 6

Editorial:
There is some obvious dynamic programming solution that someone can describe in the comments, but I will describe another one, that, in my opinion, much easier to implement.
Firstly, let's find some diameter of the tree. Let $$$a$$$ and $$$b$$$ be the endpoints of this diameter (and first two vertices of the answer). You can prove yourself why it is always good to take the diameter and why any diameter can be taken in the answer. Then there are two cases: the length of the diameter is $$$n-1$$$ or the length of the diameter is less than $$$n-1$$$. In the first case, you can take any other vertex as the third vertex of the answer $$$c$$$, it will not affect the answer anyway. Otherwise, we can run multi-source bfs from all vertices of the diameter and take the farthest vertex as the third vertex of the answer. It is always true because we can take any diameter and the farthest vertex will increase the answer as much as possible.
Time complexity: $$$O(n)$$$.
Translation
Contest: Codeforces Beta Round 40 (Div. 2)
Difficulty rating: 800
Tags: implementation, strings

The translation from the Berland language into the Birland language is not an easy task. Those languages are very similar: a Berlandish word differs from a Birlandish word with the same meaning a little: it is spelled (and pronounced) reversely. For example, a Berlandish word code corresponds to a Birlandish word edoc. However, making a mistake during the "translation" is easy. Vasya translated the word s from Berlandish into Birlandish as t. Help him: find out if he translated the word correctly.

Input format:
The first line contains word s, the second line contains word t. The words consist of lowercase Latin letters. The input data do not contain unnecessary spaces. The words are not empty and their lengths do not exceed 100 symbols.

Output format:
If the word t is a word s, written reversely, print YES, otherwise print NO.

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

Example input:
code
edoc

Example output:
YES

Example input:
abb
aba

Example output:
NO

Editorial:
Martian Dollar
Contest: Codeforces Beta Round 40 (Div. 2)
Difficulty rating: 1400
Tags: brute force

One day Vasya got hold of information on the Martian dollar course in bourles for the next n days. The buying prices and the selling prices for one dollar on day i are the same and are equal to ai. Vasya has b bourles. He can buy a certain number of dollars and then sell it no more than once in n days. According to Martian laws, one can buy only an integer number of dollars. Which maximal sum of money in bourles can Vasya get by the end of day n?

Input format:
The first line contains two integers n and b (1 ≤ n, b ≤ 2000) — the number of days and the initial number of money in bourles. The next line contains n integers ai (1 ≤ ai ≤ 2000) — the prices of Martian dollars.

Output format:
Print the single number — which maximal sum of money in bourles can Vasya get by the end of day n.

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

Example input:
2 4
3 7

Example output:
8

Example input:
4 10
4 3 2 1

Example output:
10

Editorial:
Email address
Contest: Codeforces Beta Round 40 (Div. 2)
Difficulty rating: 1300
Tags: expression parsing, implementation

Sometimes one has to spell email addresses over the phone. Then one usually pronounces a dot as dot, an at sign as at. As a result, we get something like vasyaatgmaildotcom. Your task is to transform it into a proper email address ([email protected]).

It is known that a proper email address contains only such symbols as . @ and lower-case Latin letters, doesn't start with and doesn't end with a dot. Also, a proper email address doesn't start with and doesn't end with an at sign. Moreover, an email address contains exactly one such symbol as @, yet may contain any number (possible, zero) of dots.

You have to carry out a series of replacements so that the length of the result was as short as possible and it was a proper email address. If the lengths are equal, you should print the lexicographically minimal result.

Overall, two variants of replacement are possible: dot can be replaced by a dot, at can be replaced by an at.

Input format:
The first line contains the email address description. It is guaranteed that that is a proper email address with all the dots replaced by dot an the at signs replaced by at. The line is not empty and its length does not exceed 100 symbols.

Output format:
Print the shortest email address, from which the given line could be made by the described above replacements. If there are several solutions to that problem, print the lexicographically minimal one (the lexicographical comparison of the lines are implemented with an operator < in modern programming languages).

In the ASCII table the symbols go in this order: . @ ab...z

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

Example input:
vasyaatgmaildotcom

Example output:
[email protected]

Example input:
dotdotdotatdotdotat

Example output:
[email protected]

Editorial:
Pawn
Contest: Codeforces Beta Round 40 (Div. 2)
Difficulty rating: 1900
Tags: dp

On some square in the lowest row of a chessboard a stands a pawn. It has only two variants of moving: upwards and leftwards or upwards and rightwards. The pawn can choose from which square of the lowest row it can start its journey. On each square lay from 0 to 9 peas. The pawn wants to reach the uppermost row having collected as many peas as possible. As there it will have to divide the peas between itself and its k brothers, the number of peas must be divisible by k + 1. Find the maximal number of peas it will be able to collect and which moves it should make to do it.

The pawn cannot throw peas away or leave the board. When a pawn appears in some square of the board (including the first and last square of the way), it necessarily takes all the peas.

Input format:
The first line contains three integers n, m, k (2 ≤ n, m ≤ 100, 0 ≤ k ≤ 10) — the number of rows and columns on the chessboard, the number of the pawn's brothers. Then follow n lines containing each m numbers from 0 to 9 without spaces — the chessboard's description. Each square is described by one number — the number of peas in it. The first line corresponds to the uppermost row and the last line — to the lowest row.

Output format:
If it is impossible to reach the highest row having collected the number of peas divisible by k + 1, print -1.

Otherwise, the first line must contain a single number — the maximal number of peas the pawn can collect given that the number must be divisible by k + 1. The second line must contain a single number — the number of the square's column in the lowest row, from which the pawn must start its journey. The columns are numbered from the left to the right with integral numbers starting from 1. The third line must contain a line consisting of n - 1 symbols — the description of the pawn's moves. If the pawn must move upwards and leftwards, print L, if it must move upwards and rightwards, print R. If there are several solutions to that problem, print any of them.

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

Example input:
3 3 1
123
456
789

Example output:
16
2
RL

Example input:
3 3 0
123
456
789

Example output:
17
3
LR

Editorial:
3-cycles
Contest: Codeforces Beta Round 40 (Div. 2)
Difficulty rating: 1900
Tags: constructive algorithms, graphs, greedy

During a recent research Berland scientists found out that there were n cities in Ancient Berland, joined by two-way paths. Any two cities are joined by no more than one path. No path joins a city with itself. According to a well-known tradition, the road network was built so that it would be impossible to choose three cities from each of which one can get to any other one directly. That is, there was no cycle exactly as long as 3. Unfortunately, the road map has not been preserved till nowadays. Now the scientists are interested how much developed a country Ancient Berland was. Help them - find, what maximal number of roads could be in the country. You also have to restore any of the possible road maps.

Input format:
The first line contains an integer n (1 ≤ n ≤ 100) — the number of cities in Berland.

Output format:
On the first line must be printed number m — the maximal number of roads in Berland. Then print m lines containing two numbers each — the numbers of cities that the given road joins. The cities are numbered with integers from 1 to n. If there are several variants of solving the problem, print any of them.

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

Example input:
3

Example output:
2
1 2
2 3

Example input:
4

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

Editorial: