1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Zero Tree
Contest: Codeforces Round 168 (Div. 1)
Difficulty rating: 1800
Tags: dfs and similar, dp, greedy, trees

A tree is a graph with n vertices and exactly n - 1 edges; this graph should meet the following condition: there exists exactly one shortest (by number of edges) path between any pair of its vertices.

A subtree of a tree T is a tree with both vertices and edges as subsets of vertices and edges of T.

You're given a tree with n vertices. Consider its vertices numbered with integers from 1 to n. Additionally an integer is written on every vertex of this tree. Initially the integer written on the i-th vertex is equal to vi. In one move you can apply the following operation:

1. Select the subtree of the given tree that includes the vertex with number 1.
2. Increase (or decrease) by one all the integers which are written on the vertices of that subtree.

Calculate the minimum number of moves that is required to make all the integers written on the vertices of the given tree equal to zero.

Input format:
The first line of the input contains n (1 ≤ n ≤ 105). Each of the next n - 1 lines contains two integers ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi) indicating there's an edge between vertices ai and bi. It's guaranteed that the input graph is a tree.

The last line of the input contains a list of n space-separated integers v1, v2, ..., vn (|vi| ≤ 109).

Output format:
Print the minimum number of operations needed to solve the task.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

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

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

Example output:
3

Editorial:
The Last Hole!
Contest: Codeforces Round 168 (Div. 1)
Difficulty rating: 2600
Tags: brute force, geometry

Luyi has n circles on the plane. The i-th circle is centered at (xi, yi). At the time zero circles start to grow simultaneously. In other words, the radius of each circle at time t (t > 0) is equal to t. The circles are drawn as black discs on an infinite white plane. So at each moment the plane consists of several black and white regions. Note that the circles may overlap while growing.

We define a hole as a closed, connected white region. For instance, the figure contains two holes shown by red border. During growing some holes may be created and it is easy to see that each created hole will disappear eventually. Luyi asks you to find moment of time such that the last hole disappears. In other words, you should find the first moment such that no hole can be seen after that.

Input format:
The first line of the input contains integer n (1 ≤ n ≤ 100). Each of the next n lines contains two integers xi and yi ( - 104 ≤ xi, yi ≤ 104), indicating the location of i-th circle.

It's guaranteed that no two circles are centered at the same point.

Output format:
Print the moment where the last hole disappears. If there exists no moment in which we can find holes print -1.

The answer will be considered correct if the absolute or relative error does not exceed 10 - 4.

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

Example input:
3
0 0
1 1
2 2

Example output:
-1

Example input:
4
0 0
0 2
2 2
2 0

Example output:
1.414214

Editorial:
Lovely Matrix
Contest: Codeforces Round 168 (Div. 1)
Difficulty rating: 2200
Tags: dfs and similar, graphs, greedy, sortings

Lenny had an n × m matrix of positive integers. He loved the matrix so much, because each row of the matrix was sorted in non-decreasing order. For the same reason he calls such matrices of integers lovely.

One day when Lenny was at school his little brother was playing with Lenny's matrix in his room. He erased some of the entries of the matrix and changed the order of some of its columns. When Lenny got back home he was very upset. Now Lenny wants to recover his matrix.

Help him to find an order for the columns of the matrix so that it's possible to fill in the erased entries of the matrix to achieve a lovely matrix again. Note, that you can fill the erased entries of the matrix with any integers.

Input format:
The first line of the input contains two positive integers n and m (1 ≤ n·m ≤ 105). Each of the next n lines contains m space-separated integers representing the matrix. An integer -1 shows an erased entry of the matrix. All other integers (each of them is between 0 and 109 inclusive) represent filled entries.

Output format:
If there exists no possible reordering of the columns print -1. Otherwise the output should contain m integers p1, p2, ..., pm showing the sought permutation of columns. So, the first column of the lovely matrix will be p1-th column of the initial matrix, the second column of the lovely matrix will be p2-th column of the initial matrix and so on.

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

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

Example output:
3 1 2

Example input:
2 3
1 2 2
2 5 4

Example output:
1 3 2

Editorial:
Mirror Room
Contest: Codeforces Round 168 (Div. 1)
Difficulty rating: 3000
Tags: data structures, implementation

Imagine an n × m grid with some blocked cells. The top left cell in the grid has coordinates (1, 1) and the bottom right cell has coordinates (n, m). There are k blocked cells in the grid and others are empty. You flash a laser beam from the center of an empty cell (xs, ys) in one of the diagonal directions (i.e. north-east, north-west, south-east or south-west). If the beam hits a blocked cell or the border of the grid it will reflect. The behavior of the beam reflection in different situations is depicted in the figure below.

After a while the beam enters an infinite cycle. Count the number of empty cells that the beam goes through at least once. We consider that the beam goes through cell if it goes through its center.

Input format:
The first line of the input contains three integers n, m and k (1 ≤ n, m ≤ 105, 0 ≤ k ≤ 105). Each of the next k lines contains two integers xi and yi (1 ≤ xi ≤ n, 1 ≤ yi ≤ m) indicating the position of the i-th blocked cell.

The last line contains xs, ys (1 ≤ xs ≤ n, 1 ≤ ys ≤ m) and the flash direction which is equal to "NE", "NW", "SE" or "SW". These strings denote directions ( - 1, 1), ( - 1,  - 1), (1, 1), (1,  - 1).

It's guaranteed that no two blocked cells have the same coordinates.

Output format:
In the only line of the output print the number of empty cells that the beam goes through at least once.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

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

Example input:
3 3 0
1 2 SW

Example output:
6

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

Example output:
14

Editorial:
We Need the Zero
Contest: Codeforces Round 862 (Div. 2)
Difficulty rating: 800
Tags: bitmasks, brute force

There is an array $$$a$$$ consisting of non-negative integers. You can choose an integer $$$x$$$ and denote $$$b_i=a_i \oplus x$$$ for all $$$1 \le i \le n$$$, where $$$\oplus$$$ denotes the bitwise XOR operation. Is it possible to choose such a number $$$x$$$ that the value of the expression $$$b_1 \oplus b_2 \oplus \ldots \oplus b_n$$$ equals $$$0$$$?

It can be shown that if a valid number $$$x$$$ exists, then there also exists $$$x$$$ such that ($$$0 \le x < 2^8$$$).

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

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 10^3$$$) — the length of the array $$$a$$$.

The second line of the test case contains $$$n$$$ integers — array $$$a$$$ ($$$0 \le a_i < 2^8$$$).

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

Output format:
For each set test case, print the integer $$$x$$$ ($$$0 \le x < 2^8$$$) if it exists, or $$$-1$$$ otherwise.

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

Note:
In the first test case, after applying the operation with the number $$$6$$$ the array $$$b$$$ becomes $$$[7, 4, 3]$$$, $$$7 \oplus 4 \oplus 3 = 0$$$.

There are other answers in the third test case, such as the number $$$0$$$.

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

Example output:
6
0
3
-1
1

Editorial:
Note that $$$(a_1 \oplus x) \oplus (a_2 \oplus x) \oplus ...$$$ equals $$$a_1 \oplus a_2 \oplus \ldots \oplus a_n$$$ if $$$n$$$ is even, or $$$a_1 \oplus a_2 \oplus \ldots \oplus a_n \oplus x$$$ if $$$n$$$ is odd. Then, if the length of the array is odd, you must print $$$\oplus$$$ of the whole array. And if the length is even, we can't change the value of the expression with our operation. It turns out that if $$$\oplus$$$ of the whole array is $$$0$$$, we can output any number, but otherwise there is no answer.
The String Has a Target
Contest: Codeforces Round 862 (Div. 2)
Difficulty rating: 800
Tags: greedy, strings

You are given a string $$$s$$$. You can apply this operation to the string exactly once: choose index $$$i$$$ and move character $$$s_i$$$ to the beginning of the string (removing it at the old position). For example, if you apply the operation with index $$$i=4$$$ to the string "abaacd" with numbering from $$$1$$$, you get the string "aabacd". What is the lexicographically minimal$$$^{\dagger}$$$ string you can obtain by this operation?

$$$^{\dagger}$$$A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ of the same length if and only if the following holds:

- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10 ^ 5$$$) — the length of the string.

The second line of each test case contains the string $$$s$$$ of length $$$n$$$, consisting of lowercase English letters.

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

Output format:
For each test case, on a separate line print the lexicographically smallest string that can be obtained after applying the operation to the original string exactly once.

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

Note:
In the first test case, you need to move the last character to the beginning.

In the second case, you need to move the second letter "a".

In the third set you need to apply the operation with $$$i=1$$$, then the string will not change.

Example input:
4
3
cba
4
acac
5
abbcb
4
aaba

Example output:
acb
aacc
abbcb
aaab

Editorial:
At first, note that the operation should be applied only to the position of the minimal element of the string (since the 1st position in the final string should always contain the minimal letter).
Next, let the positions of the minimum letter are $$$a_1, a_2, \ldots, a_k$$$. Then we must apply the operation to the last position ($$$a_k$$$). Indeed, let us apply the operation to another occurrence: then the prefixes will coincide, and after that there will be a character that is equal to the minimal one if we applied the operation to $$$a_k$$$ and will not be equal to it otherwise, which contradicts the minimal string.
A Wide, Wide Graph
Contest: Codeforces Round 862 (Div. 2)
Difficulty rating: 1800
Tags: dfs and similar, dp, graphs, greedy, trees

You are given a tree (a connected graph without cycles) with $$$n$$$ vertices.

Consider a fixed integer $$$k$$$. Then, the graph $$$G_k$$$ is an undirected graph with $$$n$$$ vertices, where an edge between vertices $$$u$$$ and $$$v$$$ exists if and only if the distance between vertices $$$u$$$ and $$$v$$$ in the given tree is at least $$$k$$$.

For each $$$k$$$ from $$$1$$$ to $$$n$$$, print the number of connected components in the graph $$$G_k$$$.

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

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), denoting an edge between vertices $$$u$$$ and $$$v$$$ in the tree. It is guaranteed that these edges form a valid tree.

Output format:
Output $$$n$$$ integers: the number of connected components in the graph $$$G_k$$$ for each $$$k$$$ from $$$1$$$ to $$$n$$$.

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

Note:
In the first example: If $$$k=1$$$, the graph has an edge between each pair of vertices, so it has one component. If $$$k=4$$$, the graph has only edges $$$4 \leftrightarrow 6$$$ and $$$5 \leftrightarrow 6$$$, so the graph has $$$4$$$ components.

In the second example: when $$$k=1$$$ or $$$k=2$$$ the graph has one component. When $$$k=3$$$ the graph $$$G_k$$$ splits into $$$3$$$ components: one component has vertices $$$1$$$, $$$4$$$ and $$$5$$$, and two more components contain one vertex each. When $$$k=4$$$ or $$$k=5$$$ each vertex is a separate component.

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

Example output:
1 1 2 4 6 6

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

Example output:
1 1 3 5 5

Editorial:
Find the diameter (the longest path) in the original tree. Now if the number $$$k$$$ is greater than the length of the diameter, then there will be no edges in the graph. Otherwise, the ends of this diameter are connected to each other, and possibly to other vertices as well. Then we can pre-calculate the answer for each $$$k$$$ in descending order. Let's maintain the set of vertices already reachable. Then for updating the answer for $$$k=x$$$ only vertices at a distance $$$x$$$ from one end of the diameter can be added to the answer.
There Should Be a Lot of Maximums
Contest: Codeforces Round 862 (Div. 2)
Difficulty rating: 2300
Tags: brute force, data structures, dfs and similar, dp, trees, two pointers

You are given a tree (a connected graph without cycles). Each vertex of the tree contains an integer. Let's define the $$$\mathrm{MAD}$$$ (maximum double) parameter of the tree as the maximum integer that occurs in the vertices of the tree at least $$$2$$$ times. If no number occurs in the tree more than once, then we assume $$$\mathrm{MAD}=0$$$.

Note that if you remove an edge from the tree, it splits into two trees. Let's compute the $$$\mathrm{MAD}$$$ parameters of the two trees and take the maximum of the two values. Let the result be the value of the deleted edge.

For each edge, find its value. Note that we don't actually delete any edges from the tree, the values are to be found independently.

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

Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$) — the ends of an edge of the tree. It's guaranteed that the given edges form a valid tree.

The last line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the numbers in the vertices.

Output format:
For each edge in the input order, print one number — the maximum of the $$$\mathrm{MAD}$$$ parameters of the two trees obtained after removing the given edge from the initial tree.

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

Note:
In the first example, after removing edge $$$(1, 2)$$$ no number repeats $$$2$$$ times in any of the resulting subtrees, so the answer is $$$\max(0, 0)=0$$$.

After removing edge $$$(2, 3)$$$, in the bigger subtree, $$$1$$$ is repeated twice, and $$$2$$$ is repeated twice, so the $$$\mathrm{MAD}$$$ of this tree is $$$2$$$.

After removing edge $$$(2, 4)$$$, in the bigger subtree, only the number $$$1$$$ is repeated, and in the second subtree, only one number appears, so the answer is $$$1$$$.

In the second example, if edge $$$1 \leftrightarrow 4$$$ is not removed, then one of the subtrees will have two $$$1$$$, so the answer — $$$1$$$. And if edge $$$1 \leftrightarrow 4$$$ is deleted, both subtrees have no repeating values, so the answer is $$$0$$$.

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

Example output:
0
2
1
2

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

Example output:
1
1
0
1
1

Editorial:
First, find $$$MAD$$$ of the initial tree. If each number in the tree occurs no more than once, then for each query the answer is $$$0$$$. Then, if $$$MAD$$$ occurs at least $$$3$$$ times in the tree, then for each query the answer will be $$$MAD$$$, because by pigeonhole principle there will be at least $$$2$$$ $$$MAD$$$ in one of the two trees.
At last, in the case where $$$MAD$$$ occurs exactly $$$2$$$ times in the tree: if the deleted edge is not on the path between two occurrences of $$$MAD$$$, then the answer — $$$MAD$$$ of the whole tree. And for edges between entries, you need to maintain sets of values in each tree and traverse the edges, changing the sets accordingly.
Survival of the Weakest (easy version)
Contest: Codeforces Round 862 (Div. 2)
Difficulty rating: 2600
Tags: binary search, brute force, implementation, math, sortings

This is the easy version of the problem. It differs from the hard one only in constraints on $$$n$$$. You can make hacks only if you lock both versions.

Let $$$a_1, a_2, \ldots, a_n$$$ be an array of non-negative integers. Let $$$F(a_1, a_2, \ldots, a_n)$$$ be the sorted in the non-decreasing order array of $$$n - 1$$$ smallest numbers of the form $$$a_i + a_j$$$, where $$$1 \le i < j \le n$$$. In other words, $$$F(a_1, a_2, \ldots, a_n)$$$ is the sorted in the non-decreasing order array of $$$n - 1$$$ smallest sums of all possible pairs of elements of the array $$$a_1, a_2, \ldots, a_n$$$. For example, $$$F(1, 2, 5, 7) = [1 + 2, 1 + 5, 2 + 5] = [3, 6, 7]$$$.

You are given an array of non-negative integers $$$a_1, a_2, \ldots, a_n$$$. Determine the single element of the array $$$\underbrace{F(F(F\ldots F}_{n-1}(a_1, a_2, \ldots, a_n)\ldots))$$$. Since the answer can be quite large, output it modulo $$$10^9+7$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 3000$$$) — the initial length of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the array elements.

Output format:
Output a single number — the answer modulo $$$10^9 + 7$$$.

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

Note:
In the first test, the array is transformed as follows: $$$[1, 2, 4, 5, 6] \to [3, 5, 6, 6] \to [8, 9, 9] \to [17, 17] \to [34]$$$. The only element of the final array is $$$34$$$.

In the second test, $$$F(a_1, a_2, \ldots, a_n)$$$ is $$$[2, 2, 2, 8, 8, 8, 8, 8]$$$. This array is made up of $$$3$$$ numbers of the form $$$1 + 1$$$ and $$$5$$$ numbers of the form $$$1 + 7$$$.

In the fourth test, the array is transformed as follows: $$$[10^9, 10^9, 777] \to [10^9+777, 10^9+777] \to [2 \cdot 10^9 + 1554]$$$. $$$2 \cdot 10^9 + 1554$$$ modulo $$$10^9+7$$$ equals $$$1540$$$.

Example input:
5
1 2 4 5 6

Example output:
34

Example input:
9
1 1 1 7 7 7 9 9 9

Example output:
256

Editorial:
Cutting Figure
Contest: Codeforces Round 122 (Div. 1)
Difficulty rating: 1700
Tags: constructive algorithms, graphs, trees

You've gotten an n × m sheet of squared paper. Some of its squares are painted. Let's mark the set of all painted squares as A. Set A is connected. Your task is to find the minimum number of squares that we can delete from set A to make it not connected.

A set of painted squares is called connected, if for every two squares a and b from this set there is a sequence of squares from the set, beginning in a and ending in b, such that in this sequence any square, except for the last one, shares a common side with the square that follows next in the sequence. An empty set and a set consisting of exactly one square are connected by definition.

Input format:
The first input line contains two space-separated integers n and m (1 ≤ n, m ≤ 50) — the sizes of the sheet of paper.

Each of the next n lines contains m characters — the description of the sheet of paper: the j-th character of the i-th line equals either "#", if the corresponding square is painted (belongs to set A), or equals "." if the corresponding square is not painted (does not belong to set A). It is guaranteed that the set of all painted squares A is connected and isn't empty.

Output format:
On the first line print the minimum number of squares that need to be deleted to make set A not connected. If it is impossible, print -1.

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

Note:
In the first sample you can delete any two squares that do not share a side. After that the set of painted squares is not connected anymore.

The note to the second sample is shown on the figure below. To the left there is a picture of the initial set of squares. To the right there is a set with deleted squares. The deleted squares are marked with crosses.

Example input:
5 4
####
#..#
#..#
#..#
####

Example output:
2

Example input:
5 5
#####
#...#
#####
#...#
#####

Example output:
2

Editorial:
Xor
Contest: Codeforces Round 122 (Div. 1)
Difficulty rating: 2000
Tags: brute force

John Doe has four arrays: a, b, k, and p. Each array consists of n integers. Elements of all arrays are indexed starting from 1. Array p is a permutation of integers 1 to n.

John invented a game for his friends and himself. Initially a player is given array a. The player must consecutively execute exactly u operations on a. You are permitted to execute the following operations:

- Operation 1: For each $$i \in \{1, 2, \ldots, n\}$$ change ai into $$a_{i} \oplus b_{i}$$. Expression $$x \oplus y$$ means applying the operation of a bitwise xor to numbers x and y. The given operation exists in all modern programming languages, for example, in language C++ and Java it is marked as "^", in Pascal — as "xor".
- Operation 2: For each $$i \in \{1, 2, \ldots, n\}$$ change ai into api + r. When this operation is executed, all changes are made at the same time.

After all u operations are applied, the number of points the player gets is determined by the formula $$s = \sum_{i=1}^{i\leq n} a_i k_i$$.

John wants to find out what maximum number of points a player can win in his game. Help him.

Input format:
The first line contains space-separated integers n, u and r (1 ≤ n, u ≤ 30, 0 ≤ r ≤ 100) — the number of elements in each array, the number of operations and the number that describes one of the operations.

Each of the next four lines contains n space-separated integers — arrays a, b, k, p. The first line has array a, the second line has array b, the third line has array k and the fourth one has array p.

It is guaranteed that elements of arrays a and b are positive and do not exceed 104 (1 ≤ ai, bi ≤ 104), elements of array k do not exceed 104 in the absolute value (|k| ≤ 104) and p is a permutation of numbers from 1 to n.

Output format:
On a single line print number s — the maximum number of points that a player can win in John's game.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

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

Note:
In the first sample you should first apply the operation of the first type, then the operation of the second type.

Example input:
3 2 1
7 7 7
8 8 8
1 2 3
1 3 2

Example output:
96

Example input:
2 1 0
1 1
1 1
1 -1
1 2

Example output:
0

Editorial: