1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Squares
Contest: Codeforces Beta Round 92 (Div. 1 Only)
Difficulty rating: 1800
Tags: math

You are given an infinite checkered field. You should get from a square (x1; y1) to a square (x2; y2). Using the shortest path is not necessary. You can move on the field squares in four directions. That is, when you are positioned in any square, you can move to any other side-neighboring one.

A square (x; y) is considered bad, if at least one of the two conditions is fulfilled:

- |x + y| ≡ 0 (mod 2a),
- |x - y| ≡ 0 (mod 2b).

Your task is to find the minimum number of bad cells one will have to visit on the way from (x1; y1) to (x2; y2).

Input format:
The only line contains integers a, b, x1, y1, x2 and y2 — the parameters of the bad squares, the coordinates of the initial and the final squares correspondingly (2 ≤ a, b ≤ 109 and |x1|,|y1|,|x2|,|y2| ≤ 109). It is guaranteed that the initial and the final square aren't bad.

Output format:
Print a single number — the minimum number of bad cells that one will have to visit in order to travel from square (x1; y1) to square (x2; y2).

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

Note:
In the third sample one of the possible paths in (3;-1)->(3;0)->(3;1)->(3;2)->(4;2)->(4;3)->(4;4)->(4;5)->(4;6)->(4;7)->(3;7). Squares (3;1) and (4;4) are bad.

Example input:
2 2 1 0 0 1

Example output:
1

Example input:
2 2 10 11 0 1

Example output:
5

Editorial:
Brackets
Contest: Codeforces Beta Round 92 (Div. 1 Only)
Difficulty rating: 2300
Tags: combinatorics, dp, greedy

A two dimensional array is called a bracket array if each grid contains one of the two possible brackets — "(" or ")". A path through the two dimensional array cells is called monotonous if any two consecutive cells in the path are side-adjacent and each cell of the path is located below or to the right from the previous one.

A two dimensional array whose size equals n × m is called a correct bracket array, if any string formed by writing out the brackets on some monotonous way from cell (1, 1) to cell (n, m) forms a correct bracket sequence.

Let's define the operation of comparing two correct bracket arrays of equal size (a and b) like that. Let's consider a given two dimensional array of priorities (c) — a two dimensional array of same size, containing different integers from 1 to nm. Let's find such position (i, j) in the two dimensional array, that ai, j ≠ bi, j. If there are several such positions, let's choose the one where number ci, j is minimum. If ai, j = "(", then a < b, otherwise a > b. If the position (i, j) is not found, then the arrays are considered equal.

Your task is to find a k-th two dimensional correct bracket array. It is guaranteed that for the given sizes of n and m there will be no less than k two dimensional correct bracket arrays.

Input format:
The first line contains integers n, m and k — the sizes of the array and the number of the sought correct bracket array (1 ≤ n, m ≤ 100, 1 ≤ k ≤ 1018). Then an array of priorities is given, n lines each containing m numbers, number pi, j shows the priority of character j in line i (1 ≤ pi, j ≤ nm, all pi, j are different).

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

Output format:
Print the k-th two dimensional correct bracket array.

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

Note:
In the first sample exists only one correct two-dimensional bracket array.

In the second and in the third samples two arrays exist.

A bracket sequence is called regular if it is possible to obtain correct arithmetic expression by inserting characters «+» and «1» into this sequence. For example, sequences «(())()», «()» and «(()(()))» are regular, while «)(», «(()» and «(()))(» are not.

Example input:
1 2 1
1 2

Example output:
()

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

Example output:
(()
())

Editorial:
String
Contest: Codeforces Beta Round 92 (Div. 1 Only)
Difficulty rating: 2300
Tags: string suffix structures

You are given a string s. Each pair of numbers l and r that fulfill the condition 1 ≤ l ≤ r ≤ |s|, correspond to a substring of the string s, starting in the position l and ending in the position r (inclusive).

Let's define the function of two strings F(x, y) like this. We'll find a list of such pairs of numbers for which the corresponding substrings of string x are equal to string y. Let's sort this list of pairs according to the pair's first number's increasing. The value of function F(x, y) equals the number of non-empty continuous sequences in the list.

For example: F(babbabbababbab, babb) = 6. The list of pairs is as follows:

(1, 4), (4, 7), (9, 12)

Its continuous sequences are:

- (1, 4)
- (4, 7)
- (9, 12)
- (1, 4), (4, 7)
- (4, 7), (9, 12)
- (1, 4), (4, 7), (9, 12)

Your task is to calculate for the given string s the sum F(s, x) for all x, that x belongs to the set of all substrings of a string s.

Input format:
The only line contains the given string s, consisting only of small Latin letters (1 ≤ |s| ≤ 105).

Output format:
Print the single number — the sought sum.

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

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

Note:
In the first sample the function values at x equal to "a", "aa", "aaa" and "aaaa" equal 10, 6, 3 and 1 correspondingly.

In the second sample for any satisfying x the function value is 1.

Example input:
aaaa

Example output:
20

Example input:
abcdef

Example output:
21

Editorial:
Maze
Contest: Codeforces Beta Round 92 (Div. 1 Only)
Difficulty rating: 2500
Tags: dfs and similar, dp, probabilities, trees

A maze is represented by a tree (an undirected graph, where exactly one way exists between each pair of vertices). In the maze the entrance vertex and the exit vertex are chosen with some probability. The exit from the maze is sought by Deep First Search. If there are several possible ways to move, the move is chosen equiprobably. Consider the following pseudo-code:

V(x) is the list vertices adjacent to x. The flag array is initially filled as FALSE. DFS initially starts with a parameter of an entrance vertex. When the search is finished, variable count will contain the number of moves.

Your task is to count the mathematical expectation of the number of moves one has to do to exit the maze.

Input format:
The first line determines the number of vertices in the graph n (1 ≤ n ≤ 105). The next n - 1 lines contain pairs of integers ai and bi, which show the existence of an edge between ai and bi vertices (1 ≤ ai, bi ≤ n). It is guaranteed that the given graph is a tree.

Next n lines contain pairs of non-negative numbers xi and yi, which represent the probability of choosing the i-th vertex as an entrance and exit correspondingly. The probabilities to choose vertex i as an entrance and an exit equal $$x_i / \sum_{j=1}^{n} x_j$$ and $$y_i / \sum_{j=1}^{n} y_j$$ correspondingly. The sum of all xi and the sum of all yi are positive and do not exceed 106.

Output format:
Print the expectation of the number of moves. The absolute or relative error should not exceed 10 - 9.

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

Note:
In the first sample the entrance vertex is always 1 and the exit vertex is always 2.

In the second sample the entrance vertex is always 1 and the exit vertex with the probability of 2/5 will be 2 of with the probability if 3/5 will be 3. The mathematical expectations for the exit vertices 2 and 3 will be equal (symmetrical cases). During the first move one can go to the exit vertex with the probability of 0.5 or to go to a vertex that's not the exit vertex with the probability of 0.5. In the first case the number of moves equals 1, in the second one it equals 3. The total mathematical expectation is counted as 2 / 5 × (1 × 0.5 + 3 × 0.5) + 3 / 5 × (1 × 0.5 + 3 × 0.5)

Example input:
2
1 2
0 1
1 0

Example output:
1.00000000000000000000

Example input:
3
1 2
1 3
1 0
0 2
0 3

Example output:
2.00000000000000000000

Editorial:
Minimum LCM
Contest: 2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 1000
Tags: math, number theory

You are given an integer $$$n$$$.

Your task is to find two positive (greater than $$$0$$$) integers $$$a$$$ and $$$b$$$ such that $$$a+b=n$$$ and the least common multiple (LCM) of $$$a$$$ and $$$b$$$ is the minimum among all possible values of $$$a$$$ and $$$b$$$. If there are multiple answers, you can print any of them.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^9$$$).

Output format:
For each test case, print two positive integers $$$a$$$ and $$$b$$$ — the answer to the problem. If there are multiple answers, you can print any of them.

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

Note:
In the second example, there are $$$8$$$ possible pairs of $$$a$$$ and $$$b$$$:

- $$$a = 1$$$, $$$b = 8$$$, $$$LCM(1, 8) = 8$$$;
- $$$a = 2$$$, $$$b = 7$$$, $$$LCM(2, 7) = 14$$$;
- $$$a = 3$$$, $$$b = 6$$$, $$$LCM(3, 6) = 6$$$;
- $$$a = 4$$$, $$$b = 5$$$, $$$LCM(4, 5) = 20$$$;
- $$$a = 5$$$, $$$b = 4$$$, $$$LCM(5, 4) = 20$$$;
- $$$a = 6$$$, $$$b = 3$$$, $$$LCM(6, 3) = 6$$$;
- $$$a = 7$$$, $$$b = 2$$$, $$$LCM(7, 2) = 14$$$;
- $$$a = 8$$$, $$$b = 1$$$, $$$LCM(8, 1) = 8$$$.

In the third example, there are $$$5$$$ possible pairs of $$$a$$$ and $$$b$$$:

- $$$a = 1$$$, $$$b = 4$$$, $$$LCM(1, 4) = 4$$$;
- $$$a = 2$$$, $$$b = 3$$$, $$$LCM(2, 3) = 6$$$;
- $$$a = 3$$$, $$$b = 2$$$, $$$LCM(3, 2) = 6$$$;
- $$$a = 4$$$, $$$b = 1$$$, $$$LCM(4, 1) = 4$$$.

Example input:
4
2
9
5
10

Example output:
1 1
3 6
1 4
5 5

Editorial:
Suppose $$$a \le b$$$. Let's show that if $$$b \bmod a \ne 0$$$, the answer is suboptimal. If $$$b \bmod a = 0$$$, then $$$LCM(a, b) = b$$$, so the answer is less than $$$n$$$. But if $$$b \bmod a \ne 0$$$, then $$$LCM(a, b)$$$ is at least $$$2b$$$, and $$$b$$$ is at least $$$\frac{n}{2}$$$, so in this case, the answer is at least $$$n$$$.
Okay, now we know that in the optimal answer, $$$b \bmod a = 0$$$. This also means that $$$n \bmod a = 0$$$, since $$$n = a + b$$$. So we need to search for $$$a$$$ only among the divisors of $$$n$$$, and it is possible to iterate through all of them in $$$O(n^{0.5})$$$.
Wizards and Demonstration
Contest: Codeforces Round 114 (Div. 2)
Difficulty rating: 900
Tags: implementation, math

Some country is populated by wizards. They want to organize a demonstration.

There are n people living in the city, x of them are the wizards who will surely go to the demonstration. Other city people (n - x people) do not support the wizards and aren't going to go to the demonstration. We know that the city administration will react only to the demonstration involving at least y percent of the city people. Having considered the matter, the wizards decided to create clone puppets which can substitute the city people on the demonstration.

So all in all, the demonstration will involve only the wizards and their puppets. The city administration cannot tell the difference between a puppet and a person, so, as they calculate the percentage, the administration will consider the city to be consisting of only n people and not containing any clone puppets.

Help the wizards and find the minimum number of clones to create to that the demonstration had no less than y percent of the city people.

Input format:
The first line contains three space-separated integers, n, x, y (1 ≤ n, x, y ≤ 104, x ≤ n) — the number of citizens in the city, the number of wizards and the percentage the administration needs, correspondingly.

Please note that y can exceed 100 percent, that is, the administration wants to see on a demonstration more people that actually live in the city ( > n).

Output format:
Print a single integer — the answer to the problem, the minimum number of clones to create, so that the demonstration involved no less than y percent of n (the real total city population).

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

Note:
In the first sample it is necessary that at least 14% of 10 people came to the demonstration. As the number of people should be integer, then at least two people should come. There is only one wizard living in the city and he is going to come. That isn't enough, so he needs to create one clone.

In the second sample 10 people should come to the demonstration. The city has 10 wizards. They will all come to the demonstration, so nobody has to create any clones.

Example input:
10 1 14

Example output:
1

Example input:
20 10 50

Example output:
0

Editorial:
Prison Break
Contest: Технокубок 2021 - Финал
Difficulty rating: 800
Tags: math

Michael is accused of violating the social distancing rules and creating a risk of spreading coronavirus. He is now sent to prison. Luckily, Michael knows exactly what the prison looks like from the inside, especially since it's very simple.

The prison can be represented as a rectangle $$$a\times b$$$ which is divided into $$$ab$$$ cells, each representing a prison cell, common sides being the walls between cells, and sides on the perimeter being the walls leading to freedom. Before sentencing, Michael can ask his friends among the prison employees to make (very well hidden) holes in some of the walls (including walls between cells and the outermost walls). Michael wants to be able to get out of the prison after this, no matter which cell he is placed in. However, he also wants to break as few walls as possible.

Your task is to find out the smallest number of walls to be broken so that there is a path to the outside from every cell after this.

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

Each of the following $$$t$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$1\leq a, b\leq 100$$$), representing a corresponding test case.

Output format:
For each test case print the single integer on a separate line — the answer to the problem.

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

Note:
Some possible escape plans for the example test cases are shown below. Broken walls are shown in gray, not broken walls are shown in black.

Example input:
2
2 2
1 3

Example output:
4
3

Editorial:
Each broken wall increases the number of connected regions of the plane at most by one. Since in the end every single cell must be in the same region as the outside of the prison, there has to be only one connected region, hence the answer is at least $$$nm$$$ (because there were $$$nm + 1$$$ connected regions at the beginning).
To achieve the answer, one can, for example, break the upper wall in every cell.
Basic Diplomacy
Contest: Технокубок 2021 - Финал
Difficulty rating: 1600
Tags: brute force, constructive algorithms, greedy, implementation

Aleksey has $$$n$$$ friends. He is also on a vacation right now, so he has $$$m$$$ days to play this new viral cooperative game! But since it's cooperative, Aleksey will need one teammate in each of these $$$m$$$ days.

On each of these days some friends will be available for playing, and all others will not. On each day Aleksey must choose one of his available friends to offer him playing the game (and they, of course, always agree). However, if any of them happens to be chosen strictly more than $$$\left\lceil\dfrac{m}{2}\right\rceil$$$ times, then all other friends are offended. Of course, Aleksey doesn't want to offend anyone.

Help him to choose teammates so that nobody is chosen strictly more than $$$\left\lceil\dfrac{m}{2}\right\rceil$$$ times.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\leq n, m\leq 100\,000$$$) standing for the number of friends and the number of days to play, respectively.

The $$$i$$$-th of the following $$$m$$$ lines contains an integer $$$k_i$$$ ($$$1\leq k_i\leq n$$$), followed by $$$k_i$$$ distinct integers $$$f_{i1}$$$, ..., $$$f_{ik_i}$$$ ($$$1\leq f_{ij}\leq n$$$), separated by spaces — indices of available friends on the day $$$i$$$.

It is guaranteed that the sums of $$$n$$$ and $$$m$$$ over all test cases do not exceed $$$100\,000$$$. It's guaranteed that the sum of all $$$k_i$$$ over all days of all test cases doesn't exceed $$$200\,000$$$.

Output format:
Print an answer for each test case. If there is no way to achieve the goal, print "NO".

Otherwise, in the first line print "YES", and in the second line print $$$m$$$ space separated integers $$$c_1$$$, ..., $$$c_m$$$. Each $$$c_i$$$ must denote the chosen friend on day $$$i$$$ (and therefore must be one of $$$f_{ij}$$$).

No value must occur more than $$$\left\lceil\dfrac{m}{2}\right\rceil$$$ times. If there is more than one possible answer, print any of them.

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

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

Example output:
YES
1 2 1 1 2 3 
NO

Editorial:
First, for each day we select an arbitrary friend from the list. With this choice, at most one friend will play more than $$$\left\lceil\dfrac{m}{2}\right\rceil$$$ times. Let's call him $$$f$$$. We want to fix schedule such that $$$f$$$ will play exactly $$$\left\lceil\dfrac{m}{2}\right\rceil$$$ times. To do this, we go through all the days and, if $$$f$$$ is assigned on a certain day and someone else can play this day, then we assign anyone except $$$f$$$ for that day. We will make such replacements while $$$f$$$ plays more than $$$\left\lceil\dfrac{m}{2}\right\rceil$$$ times. There is only one case when this is not possible: if $$$f$$$ is the only friend who can play in more than $$$\left\lceil\dfrac{m}{2}\right\rceil$$$ days.
Useful Edges
Contest: Технокубок 2021 - Финал
Difficulty rating: 2400
Tags: graphs, shortest paths

You are given a weighted undirected graph on $$$n$$$ vertices along with $$$q$$$ triples $$$(u, v, l)$$$, where in each triple $$$u$$$ and $$$v$$$ are vertices and $$$l$$$ is a positive integer. An edge $$$e$$$ is called useful if there is at least one triple $$$(u, v, l)$$$ and a path (not necessarily simple) with the following properties:

- $$$u$$$ and $$$v$$$ are the endpoints of this path,
- $$$e$$$ is one of the edges of this path,
- the sum of weights of all edges on this path doesn't exceed $$$l$$$.

Please print the number of useful edges in this graph.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2\leq n\leq 600$$$, $$$0\leq m\leq \frac{n(n-1)}2$$$).

Each of the following $$$m$$$ lines contains three integers $$$u$$$, $$$v$$$ and $$$w$$$ ($$$1\leq u, v\leq n$$$, $$$u\neq v$$$, $$$1\leq w\leq 10^9$$$), denoting an edge connecting vertices $$$u$$$ and $$$v$$$ and having a weight $$$w$$$.

The following line contains the only integer $$$q$$$ ($$$1\leq q\leq \frac{n(n-1)}2$$$) denoting the number of triples.

Each of the following $$$q$$$ lines contains three integers $$$u$$$, $$$v$$$ and $$$l$$$ ($$$1\leq u, v\leq n$$$, $$$u\neq v$$$, $$$1\leq l\leq 10^9$$$) denoting a triple $$$(u, v, l)$$$.

It's guaranteed that:

- the graph doesn't contain loops or multiple edges;
- all pairs $$$(u, v)$$$ in the triples are also different.

Output format:
Print a single integer denoting the number of useful edges in the graph.

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

Note:
In the first example each edge is useful, except the one of weight $$$5$$$.

In the second example only edge between $$$1$$$ and $$$2$$$ is useful, because it belongs to the path $$$1-2$$$, and $$$10 \leq 11$$$. The edge between $$$3$$$ and $$$4$$$, on the other hand, is not useful.

In the third example both edges are useful, for there is a path $$$1-2-3-2$$$ of length exactly $$$5$$$. Please note that the path may pass through a vertex more than once.

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

Example output:
5

Example input:
4 2
1 2 10
3 4 10
6
1 2 11
1 3 11
1 4 11
2 3 11
2 4 11
3 4 9

Example output:
1

Editorial:
Find all distances between vertices via Floyd's algorithm for $$$O(n^3)$$$. Consider all triples with fixed endpoint, say, $$$v$$$. Let's find all useful edges corresponding to such triples.
An edge $$$(a, b, w)$$$ is useful, if there is a triple $$$(v, u_i, l_i)$$$ with
$$$$$$dist(v, a) + w + dist(b, u_i)\leq l_i\Leftrightarrow -l_i + dist(u_i, b)\leq -w - dist(v, a).$$$$$$
Note that the right hand side depends only on the fixed vertex $$$v$$$ and the edge itself, so we are going to minimize the left hand side over all possible triples. It can be done using Dijkstra in $$$O(n^2)$$$ if we initialize the distance to all $$$u_i$$$ with $$$-l_i$$$. After we are done for all vertices $$$v$$$, there only remains to check for each edge whether it has been marked useful for any vertex $$$v$$$.
Exam
Contest: Технокубок 2021 - Финал
Difficulty rating: 3400
Tags: data structures, string suffix structures, trees

This year a Chunin Selection Exam is held again in Konoha, and taking part in it are $$$n$$$ ninjas named $$$s_1$$$, $$$s_2$$$, ..., $$$s_n$$$. All names are distinct. One of the exam stages consists of fights between the participants. This year the rules determining the ninjas for each fight are the following: ninjas $$$i$$$ and $$$j$$$ fight against each other if the following conditions are held:

- $$$i \neq j$$$;
- $$$s_{j}$$$ is a substring of $$$s_{i}$$$;
- there is no $$$k$$$ except $$$i$$$ and $$$j$$$ that $$$s_{j}$$$ is a substring of $$$s_{k}$$$, and $$$s_{k}$$$ is a substring of $$$s_{i}$$$.

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Your task is to find out how many fights are going to take place this year.

Input format:
The first line consists of the only integer $$$n$$$ ($$$1 \leq n \leq 10^{6}$$$) standing for the number of examinees.

The following $$$n$$$ lines contain their names. No two names coincide, all names are non-empty and consist of lowercase English letters. The total length of all names doesn't exceed $$$10^6$$$.

Output format:
Print the only integer standing for the number of fights.

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

Note:
In the first example hidan fights against dan, and hanabi fights against nabi, who also fights bi. Ninjas named hanabi and bi don't fight each other since there is the ninja called nabi who breaks the third condition for them.

In the second example the fights are held between abacaba and acaba, abacaba and abaca, acaba and aca, abaca and aca.

Example input:
5
hidan
dan
hanabi
bi
nabi

Example output:
3

Example input:
4
abacaba
abaca
acaba
aca

Example output:
4

Editorial:
Fix a particular string $$$s$$$ and find all edges outgoing from it. For each position $$$i$$$ of the string let's find the value of $$$left_i$$$ being the starting position of the longest substring which ends at the position $$$i$$$ and is one of the strings $$$s_j$$$. It's easy to see that such strings are the only ones where the outgoing edges from $$$s$$$ can lead to. What remains is to find out which of them need to be excluded.
A string needs to be excluded if there is an occurrence of it into $$$s$$$ which is entirely covered by an occurrence of another substring. So let $$$ind_i = \min\{left_j\,\mid\,j > i\}$$$. Then the strings to be excluded are precisely the strings among $$$s_j$$$'s which are suffixes of the substring $$$[ind_i, i]$$$ for some $$$i$$$. This can be found via the Aho-Corasick structure. Since its suffix links represent a tree, one can find the vertices corresponding to the substrings $$$[ind_i, i]$$$ and mark the way to the root in the suffix links tree. After this one can just check if the vertices of $$$[left_i, i]$$$ are marked. To mark paths efficiently one can use segment trees or std::set. The overall complexity is $$$O(n\log{n})$$$.