1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
The Two Routes
Contest: Codeforces Round 333 (Div. 1)
Difficulty rating: 1600
Tags: graphs, shortest paths

In Absurdistan, there are n towns (numbered 1 through n) and m bidirectional railways. There is also an absurdly simple road network — for each pair of different towns x and y, there is a bidirectional road between towns x and y if and only if there is no railway between them. Travelling to a different town using one railway or one road always takes exactly one hour.

A train and a bus leave town 1 at the same time. They both have the same destination, town n, and don't make any stops on the way (but they can wait in town n). The train can move only along railways and the bus can move only along roads.

You've been asked to plan out routes for the vehicles; each route can use any road/railway multiple times. One of the most important aspects to consider is safety — in order to avoid accidents at railway crossings, the train and the bus must not arrive at the same town (except town n) simultaneously.

Under these constraints, what is the minimum number of hours needed for both vehicles to reach town n (the maximum of arrival times of the bus and the train)? Note, that bus and train are not required to arrive to the town n at the same moment of time, but are allowed to do so.

Input format:
The first line of the input contains two integers n and m (2 ≤ n ≤ 400, 0 ≤ m ≤ n(n - 1) / 2) — the number of towns and the number of railways respectively.

Each of the next m lines contains two integers u and v, denoting a railway between towns u and v (1 ≤ u, v ≤ n, u ≠ v).

You may assume that there is at most one railway connecting any two towns.

Output format:
Output one integer — the smallest possible time of the later vehicle's arrival in town n. If it's impossible for at least one of the vehicles to reach town n, output  - 1.

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

Note:
In the first sample, the train can take the route $$1 \rightarrow 3 \rightarrow 4$$ and the bus can take the route $$1 \rightarrow 2 \rightarrow 4$$. Note that they can arrive at town 4 at the same time.

In the second sample, Absurdistan is ruled by railwaymen. There are no roads, so there's no way for the bus to reach town 4.

Example input:
4 2
1 3
3 4

Example output:
2

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

Example output:
-1

Editorial:
Lipshitz Sequence
Contest: Codeforces Round 333 (Div. 1)
Difficulty rating: 2100
Tags: data structures, math

A function $$f : \mathbb{R} \to \mathbb{R}$$ is called Lipschitz continuous if there is a real constant K such that the inequality |f(x) - f(y)| ≤ K·|x - y| holds for all $$x,y \in \mathbb{R}$$. We'll deal with a more... discrete version of this term.

For an array $$h[1..n]$$, we define it's Lipschitz constant $${\cal L}({\bf h})$$ as follows:

- if n < 2, $$L(\mathbf{h}) = 0$$
- if n ≥ 2, $${\displaystyle L(h)=\max \left\{{\frac {|h[j]-h[i]|}{j-i}}\right\}}$$ over all 1 ≤ i < j ≤ n

In other words, $$L = L(h)$$ is the smallest non-negative integer such that |h[i] - h[j]| ≤ L·|i - j| holds for all 1 ≤ i, j ≤ n.

You are given an array $$\alpha$$ of size n and q queries of the form [l, r]. For each query, consider the subarray $$s = a[l..r]$$; determine the sum of Lipschitz constants of all subarrays of ?.

Input format:
The first line of the input contains two space-separated integers n and q (2 ≤ n ≤ 100 000 and 1 ≤ q ≤ 100) — the number of elements in array $$\alpha$$ and the number of queries respectively.

The second line contains n space-separated integers $${\mathbf{a}}^{[1..n]}$$ ($$0 \leq a[i] \leq 10^8$$).

The following q lines describe queries. The i-th of those lines contains two space-separated integers li and ri (1 ≤ li < ri ≤ n).

Output format:
Print the answers to all queries in the order in which they are given in the input. For the i-th query, print one line containing a single integer — the sum of Lipschitz constants of all subarrays of $$a[l_i..r_i]$$.

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

Note:
In the first query of the first sample, the Lipschitz constants of subarrays of $$[5,2,9]$$ with length at least 2 are:

- $${\cal L}([5,2])=3$$
- $$L([2,9])=7$$
- $$L([5,2,9])=7$$

The answer to the query is their sum.

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

Example output:
17
82
23
210

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

Example output:
2
0
22
59
16
8

Editorial:
Kleofáš and the n-thlon
Contest: Codeforces Round 333 (Div. 1)
Difficulty rating: 2300
Tags: dp, math, probabilities

Kleofáš is participating in an n-thlon - a tournament consisting of n different competitions in n different disciplines (numbered 1 through n). There are m participants in the n-thlon and each of them participates in all competitions.

In each of these n competitions, the participants are given ranks from 1 to m in such a way that no two participants are given the same rank - in other words, the ranks in each competition form a permutation of numbers from 1 to m. The score of a participant in a competition is equal to his/her rank in it.

The overall score of each participant is computed as the sum of that participant's scores in all competitions.

The overall rank of each participant is equal to 1 + k, where k is the number of participants with strictly smaller overall score.

The n-thlon is over now, but the results haven't been published yet. Kleofáš still remembers his ranks in each particular competition; however, he doesn't remember anything about how well the other participants did. Therefore, Kleofáš would like to know his expected overall rank.

All competitors are equally good at each discipline, so all rankings (permutations of ranks of everyone except Kleofáš) in each competition are equiprobable.

Input format:
The first line of the input contains two space-separated integers n (1 ≤ n ≤ 100) and m (1 ≤ m ≤ 1000) — the number of competitions and the number of participants respectively.

Then, n lines follow. The i-th of them contains one integer xi (1 ≤ xi ≤ m) — the rank of Kleofáš in the i-th competition.

Output format:
Output a single real number – the expected overall rank of Kleofáš. Your answer will be considered correct if its relative or absolute error doesn't exceed 10 - 9.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $${ \frac { | a - b | } { \operatorname* { m a x } ( 1, b ) } } \leq 1 0 ^ { - 9 }$$.

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

Note:
In the first sample, Kleofáš has overall score 6. Nobody else can have overall score less than 6 (but it's possible for one other person to have overall score 6 as well), so his overall rank must be 1.

Example input:
4 10
2
1
2
1

Example output:
1.0000000000000000

Example input:
5 5
1
2
3
4
5

Example output:
2.7500000000000000

Editorial:
Acyclic Organic Compounds
Contest: Codeforces Round 333 (Div. 1)
Difficulty rating: 2400
Tags: data structures, dfs and similar, dsu, hashing, strings, trees

You are given a tree T with n vertices (numbered 1 through n) and a letter in each vertex. The tree is rooted at vertex 1.

Let's look at the subtree Tv of some vertex v. It is possible to read a string along each simple path starting at v and ending at some vertex in Tv (possibly v itself). Let's denote the number of distinct strings which can be read this way as $$\operatorname{dif}(v)$$.

Also, there's a number cv assigned to each vertex v. We are interested in vertices with the maximum value of $$\mathrm{dif}(v) + c_v$$.

You should compute two statistics: the maximum value of $$\mathrm{dif}(v) + c_v$$ and the number of vertices v with the maximum $$\mathrm{dif}(v) + c_v$$.

Input format:
The first line of the input contains one integer n (1 ≤ n ≤ 300 000) — the number of vertices of the tree.

The second line contains n space-separated integers ci (0 ≤ ci ≤ 109).

The third line contains a string s consisting of n lowercase English letters — the i-th character of this string is the letter in vertex i.

The following n - 1 lines describe the tree T. Each of them contains two space-separated integers u and v (1 ≤ u, v ≤ n) indicating an edge between vertices u and v.

It's guaranteed that the input will describe a tree.

Output format:
Print two lines.

On the first line, print $$m = \max(\operatorname{dif}(i) + c_i)$$ over all 1 ≤ i ≤ n.

On the second line, print the number of vertices v for which $$m = \operatorname{dif}(v) + c_v$$.

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

Note:
In the first sample, the tree looks like this:

The sets of strings that can be read from individual vertices are:

Finally, the values of $$\mathrm{dif}(v) + c_v$$ are:

In the second sample, the values of $$\operatorname{dif}(1..n)$$ are (5, 4, 2, 1, 1, 1). The distinct strings read in T2 are $$a, aa, aaa, ab$$; note that $$\alpha \alpha$$ can be read down to vertices 3 or 4.

Example input:
10
1 2 7 20 20 30 40 50 50 50
cacabbcddd
1 2
6 8
7 2
6 2
5 4
5 9
3 10
2 5
2 3

Example output:
51
3

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

Example output:
6
2

Editorial:
Neverending competitions
Contest: Codeforces Round 397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined)
Difficulty rating: 900
Tags: implementation, math

There are literally dozens of snooker competitions held each year, and team Jinotega tries to attend them all (for some reason they prefer name "snookah")! When a competition takes place somewhere far from their hometown, Ivan, Artsem and Konstantin take a flight to the contest and back.

Jinotega's best friends, team Base have found a list of their itinerary receipts with information about departure and arrival airports. Now they wonder, where is Jinotega now: at home or at some competition far away? They know that:

- this list contains all Jinotega's flights in this year (in arbitrary order),
- Jinotega has only flown from his hometown to a snooker contest and back,
- after each competition Jinotega flies back home (though they may attend a competition in one place several times),
- and finally, at the beginning of the year Jinotega was at home.

Please help them to determine Jinotega's location!

Input format:
In the first line of input there is a single integer n: the number of Jinotega's flights (1 ≤ n ≤ 100). In the second line there is a string of 3 capital Latin letters: the name of Jinotega's home airport. In the next n lines there is flight information, one flight per line, in form "XXX->YYY", where "XXX" is the name of departure airport "YYY" is the name of arrival airport. Exactly one of these airports is Jinotega's home airport.

It is guaranteed that flights information is consistent with the knowledge of Jinotega's friends, which is described in the main part of the statement.

Output format:
If Jinotega is now at home, print "home" (without quotes), otherwise print "contest".

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

Note:
In the first sample Jinotega might first fly from SVO to CDG and back, and then from SVO to LHR and back, so now they should be at home. In the second sample Jinotega must now be at RAP because a flight from RAP back to SVO is not on the list.

Example input:
4
SVO
SVO->CDG
LHR->SVO
SVO->LHR
CDG->SVO

Example output:
home

Example input:
3
SVO
SVO->HKT
HKT->SVO
SVO->RAP

Example output:
contest

Editorial:
Each competition adds two flights to the list — there and back. The only exception is the last competition: if Jinotega is now there, it adds only one flight. So if n is odd, the answer is contest, otherwise home.
Code obfuscation
Contest: Codeforces Round 397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined)
Difficulty rating: 1100
Tags: greedy, implementation, strings

Kostya likes Codeforces contests very much. However, he is very disappointed that his solutions are frequently hacked. That's why he decided to obfuscate (intentionally make less readable) his code before upcoming contest.

To obfuscate the code, Kostya first looks at the first variable name used in his program and replaces all its occurrences with a single symbol a, then he looks at the second variable name that has not been replaced yet, and replaces all its occurrences with b, and so on. Kostya is well-mannered, so he doesn't use any one-letter names before obfuscation. Moreover, there are at most 26 unique identifiers in his programs.

You are given a list of identifiers of some program with removed spaces and line breaks. Check if this program can be a result of Kostya's obfuscation.

Input format:
In the only line of input there is a string S of lowercase English letters (1 ≤ |S| ≤ 500) — the identifiers of a program with removed whitespace characters.

Output format:
If this program can be a result of Kostya's obfuscation, print "YES" (without quotes), otherwise print "NO".

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

Note:
In the first sample case, one possible list of identifiers would be "number string number character number string number". Here how Kostya would obfuscate the program:

- replace all occurences of number with a, the result would be "a string a character a string a",
- replace all occurences of string with b, the result would be "a b a character a b a",
- replace all occurences of character with c, the result would be "a b a c a b a",
- all identifiers have been replaced, thus the obfuscation is finished.

Example input:
abacaba

Example output:
YES

Example input:
jinotega

Example output:
NO

Editorial:
In this problem you needed to check that the first occurrences of letters a, b, ... appear in order (that is, first "a" is before first "b", which, in order, is before first "c", so on). One possible solution: for each letter x check that there is at least one letter x - 1 before it.
Table Tennis Game 2
Contest: Codeforces Round 397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined)
Difficulty rating: 1200
Tags: math

Misha and Vanya have played several table tennis sets. Each set consists of several serves, each serve is won by one of the players, he receives one point and the loser receives nothing. Once one of the players scores exactly k points, the score is reset and a new set begins.

Across all the sets Misha scored a points in total, and Vanya scored b points. Given this information, determine the maximum number of sets they could have played, or that the situation is impossible.

Note that the game consisted of several complete sets.

Input format:
The first line contains three space-separated integers k, a and b (1 ≤ k ≤ 109, 0 ≤ a, b ≤ 109, a + b > 0).

Output format:
If the situation is impossible, print a single number -1. Otherwise, print the maximum possible number of sets.

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

Note:
Note that the rules of the game in this problem differ from the real table tennis game, for example, the rule of "balance" (the winning player has to be at least two points ahead to win a set) has no power within the present problem.

Example input:
11 11 5

Example output:
1

Example input:
11 2 3

Example output:
-1

Editorial:
There are several possible cases how the game could go:
• The first player won all the sets. In this case, each set gave him exactly k points, hence a must be divisible by k. Moreover, b ≤ (a / k)·(k - 1) since the second player could get at most k - 1 points per set. If we have k|a and 0 ≤ b ≤ (a / k)·(k - 1), then the answer is at least a / k.
• The second player won all the sets. The analysis in symmetrical.
• Each player has won at least one set. In this case we must have a ≥ k and b ≥ k. If this condition holds, the game is possible with the maximal number of sets ⌊ a / k⌋ + ⌊ b / k⌋. Indeed, consider the following sequence of sets: $$( k, b \bmod k )$$, $$(a \bmod k, k)$$, (⌊ a / k⌋ - 1) copies of (k, 0), (⌊ b / k⌋ - 1) copies of (0, k).
In short: if (a ≥ k and b ≥ k) or (a divisible by k) or (b divisible by k) the answer ⌊ a / k⌋ + ⌊ b / k⌋, otherwise  - 1. One can check that this is equivalent to the reasoning above.
Artsem and Saunders
Contest: Codeforces Round 397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined)
Difficulty rating: 1700
Tags: constructive algorithms, dsu, math

Artsem has a friend Saunders from University of Chicago. Saunders presented him with the following problem.

Let [n] denote the set {1, ..., n}. We will also write f: [x] → [y] when a function f is defined in integer points 1, ..., x, and all its values are integers from 1 to y.

Now then, you are given a function f: [n] → [n]. Your task is to find a positive integer m, and two functions g: [n] → [m], h: [m] → [n], such that g(h(x)) = x for all $$x \in [m]$$, and h(g(x)) = f(x) for all $$x \in [n]$$, or determine that finding these is impossible.

Input format:
The first line contains an integer n (1 ≤ n ≤ 105).

The second line contains n space-separated integers — values f(1), ..., f(n) (1 ≤ f(i) ≤ n).

Output format:
If there is no answer, print one integer -1.

Otherwise, on the first line print the number m (1 ≤ m ≤ 106). On the second line print n numbers g(1), ..., g(n). On the third line print m numbers h(1), ..., h(m).

If there are several correct answers, you may output any of them. It is guaranteed that if a valid answer exists, then there is an answer satisfying the above restrictions.

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

Example input:
3
1 2 3

Example output:
3
1 2 3
1 2 3

Example input:
3
2 2 2

Example output:
1
1 1 1
2

Editorial:
Suppose that h(g) ≡ f (that is, the functions match on all inputs), and $$g(h) \equiv 1$$ (the identity function). Hence, we must have $$f(f(x))=h(g(h(g(x))))=h(1(g(x)))=h(g(x))=f(x)$$. It means that if f(x) = y, then f(y) = f(f(x)) = f(x) = y, that is, all distinct values of f must be its stable points. If this is violated, we can have no answer.
We will put m equal to the number of stable points. Let's enumerate all distinct values of f as p1, ..., pm, and define a function q that maps a point pi to the index i. We will determine functions g(x) = q(f(x)), and h(x) = px. We can see that:
• if $$x \in [n]$$, then h(g(x)) = pq(f(x)) = f(x).
• if $$x \in [m]$$, then g(h(x)) = q(px) = x.
All enumeration can be done in linear time.
Souvenirs
Contest: Codeforces Round 397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined)
Difficulty rating: 3100
Tags: data structures

Artsem is on vacation and wants to buy souvenirs for his two teammates. There are n souvenir shops along the street. In i-th shop Artsem can buy one souvenir for ai dollars, and he cannot buy more than one souvenir in one shop. He doesn't want to introduce envy in his team, so he wants to buy two souvenirs with least possible difference in price.

Artsem has visited the shopping street m times. For some strange reason on the i-th day only shops with numbers from li to ri were operating (weird? yes it is, but have you ever tried to come up with a reasonable legend for a range query problem?). For each visit, Artsem wants to know the minimum possible difference in prices of two different souvenirs he can buy in the opened shops.

In other words, for each Artsem's visit you should find the minimum possible value of |as - at| where li ≤ s, t ≤ ri, s ≠ t.

Input format:
The first line contains an integer n (2 ≤ n ≤ 105).

The second line contains n space-separated integers a1, ..., an (0 ≤ ai ≤ 109).

The third line contains the number of queries m (1 ≤ m ≤ 3·105).

Next m lines describe the queries. i-th of these lines contains two space-separated integers li and ri denoting the range of shops working on i-th day (1 ≤ li < ri ≤ n).

Output format:
Print the answer to each query in a separate line.

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

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

Example output:
0
1
1
3

Editorial:
We will answer queries offline, moving right endpoint to the right and storing the answer for each left endpoint in a segment tree. The tree will support two operations: set minimum on a segment and get a value in the point. More, we assume that among two elements ai and aj in our array ai > aj and i < j and solve the problem twice — for the original array and for the reversed one.
Consider one step of moving the right endpoint and adding new element x to the position i. We find the first element to the left of i which is not less than x; denote it with aj = y. Obviously, now the answer for all left endpoints in range [0, j] is y - x. Now we find some aj' = y' such that x ≤ y' < y and j' < j, and the answer for all left endpoints in range [0, j'] is at most y' - x. If we repeat this step while possible, we maintain correct values in our segment tree.
The crucial idea of the problem is the following inequality: y' - x < y - y'. Why? Because each segment with r = i and 0 ≤ l ≤ j' contains elements y and y', and adding x will improve the answer for these endpoints only if this inequality holds. Having this, we need to consider only $$O(\log 10^9)$$ values of y.
The asymptotic of the solution is $${\cal O}(n\log n\log 10^{9}+m\log n)$$.
Little C Loves 3 I
Contest: Codeforces Round 511 (Div. 2)
Difficulty rating: 800
Tags: math

Little C loves number «3» very much. He loves all things about it.

Now he has a positive integer $$$n$$$. He wants to split $$$n$$$ into $$$3$$$ positive integers $$$a,b,c$$$, such that $$$a+b+c=n$$$ and none of the $$$3$$$ integers is a multiple of $$$3$$$. Help him to find a solution.

Input format:
A single line containing one integer $$$n$$$ ($$$3 \leq n \leq 10^9$$$) — the integer Little C has.

Output format:
Print $$$3$$$ positive integers $$$a,b,c$$$ in a single line, such that $$$a+b+c=n$$$ and none of them is a multiple of $$$3$$$.

It can be proved that there is at least one solution. If there are multiple solutions, print any of them.

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

Example input:
3

Example output:
1 1 1

Example input:
233

Example output:
77 77 79

Editorial:
If $$$n-2$$$ is not a multiple of $$$3$$$, $$$a=1,b=1,c=n-2$$$ is OK.
Otherwise, $$$a=1,b=2,c=n-3$$$ is OK.
Cover Points
Contest: Codeforces Round 511 (Div. 2)
Difficulty rating: 900
Tags: geometry, math

There are $$$n$$$ points on the plane, $$$(x_1,y_1), (x_2,y_2), \ldots, (x_n,y_n)$$$.

You need to place an isosceles triangle with two sides on the coordinate axis to cover all points (a point is covered if it lies inside the triangle or on the side of the triangle). Calculate the minimum length of the shorter side of the triangle.

Input format:
First line contains one integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i,y_i \leq 10^9$$$).

Output format:
Print the minimum length of the shorter side of the triangle. It can be proved that it's always an integer.

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

Note:
Illustration for the first example:

Illustration for the second example:

Example input:
3
1 1
1 2
2 1

Example output:
3

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

Example output:
4

Editorial:
To cover a point $$$(x_i,y_i)$$$, the length of the shorter side of the triangle should be at least $$$x_i+y_i$$$.
So the answer is $$$max(x_i+y_i)$$$.