1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
BerDonalds
Contest: Codeforces Round 163 (Div. 2)
Difficulty rating: 2400
Tags: graphs, math, shortest paths

BerDonalds, a well-known fast food restaurant, is going to open a cafe in Bertown. The important thing is to choose the new restaurant's location so that it would be easy to get there. The Bertown road system is represented by n junctions, connected by m bidirectional roads. For each road we know its length. We also know that we can get from any junction to any other one, moving along the roads.

Your task is to find such location of the restaurant, that the shortest distance along the roads from the cafe to the farthest junction would be minimum. Note that the restaurant can be located not only on the junction, but at any point of any road.

Input format:
The first line contains two integers n and m ($$2 \leq n \leq 200; n - 1 \leq m \leq \frac{n(n-1)}{2}$$) — the number of junctions and the number of roads, correspondingly. Then m lines follow, describing all Bertown roads. Each road is described by three integers ai, bi, wi (1 ≤ ai, bi ≤ n, ai ≠ bi; 1 ≤ wi ≤ 105), where ai and bi are the numbers of the junctions, connected by the i-th road, and wi is the length of the i-th road.

It is guaranteed that each road connects two distinct junctions, there is at most one road between any two junctions, and you can get from any junction to any other one.

Output format:
Print a single real number — the shortest distance from the optimal restaurant location to the farthest junction. The answer will be considered correct, if its absolute or relative error doesn't exceed 10 - 9.

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

Example input:
2 1
1 2 1

Example output:
0.50

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

Example output:
1.00

Editorial:
More Queries to Array...
Contest: Codeforces Round 163 (Div. 2)
Difficulty rating: 2500
Tags: data structures, math

You've got an array, consisting of n integers: a1, a2, ..., an. Your task is to quickly run the queries of two types:

1. Assign value x to all elements from l to r inclusive. After such query the values of the elements of array al, al + 1, ..., ar become equal to x.
2. Calculate and print sum $$\sum_{i=l}^{r} a_i \cdot (i-l+1)^k$$, where k doesn't exceed 5. As the value of the sum can be rather large, you should print it modulo 1000000007 (109 + 7).

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 105), showing, how many numbers are in the array and the number of queries, correspondingly. The second line contains n integers: a1, a2, ..., an (0 ≤ ai ≤ 109) — the initial values of the array elements.

Then m queries follow, one per line:

1. The assign query has the following format: "$$l r x$$", (1 ≤ l ≤ r ≤ n; 0 ≤ x ≤ 109).
2. The query to calculate the sum has the following format: "$$? l r k$$", (1 ≤ l ≤ r ≤ n; 0 ≤ k ≤ 5).

All numbers in the input are integers.

Output format:
For each query to calculate the sum print an integer — the required sum modulo 1000000007 (109 + 7).

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

Example input:
4 5
5 10 2 1
? 1 2 1
= 2 2 0
? 2 4 3
= 1 4 1
? 1 4 5

Example output:
25
43
1300

Example input:
3 1
1000000000 1000000000 1000000000
? 1 3 0

Example output:
999999986

Editorial:
Cubes Sorting
Contest: Codeforces Round 672 (Div. 2)
Difficulty rating: 900
Tags: math, sortings

Wheatley decided to try to make a test chamber. He made a nice test chamber, but there was only one detail absent — cubes.

For completing the chamber Wheatley needs $$$n$$$ cubes. $$$i$$$-th cube has a volume $$$a_i$$$.

Wheatley has to place cubes in such a way that they would be sorted in a non-decreasing order by their volume. Formally, for each $$$i>1$$$, $$$a_{i-1} \le a_i$$$ must hold.

To achieve his goal, Wheatley can exchange two neighbouring cubes. It means that for any $$$i>1$$$ you can exchange cubes on positions $$$i-1$$$ and $$$i$$$.

But there is a problem: Wheatley is very impatient. If Wheatley needs more than $$$\frac{n \cdot (n-1)}{2}-1$$$ exchange operations, he won't do this boring work.

Wheatly wants to know: can cubes be sorted under this conditions?

Input format:
Each test contains multiple test cases.

The first line contains one positive integer $$$t$$$ ($$$1 \le t \le 1000$$$), denoting the number of test cases. Description of the test cases follows.

The first line of each test case contains one positive integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^4$$$) — number of cubes.

The second line contains $$$n$$$ positive integers $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — volumes of cubes.

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

Output format:
For each test case, print a word in a single line: "YES" (without quotation marks) if the cubes can be sorted and "NO" (without quotation marks) otherwise.

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

Note:
In the first test case it is possible to sort all the cubes in $$$7$$$ exchanges.

In the second test case the cubes are already sorted.

In the third test case we can make $$$0$$$ exchanges, but the cubes are not sorted yet, so the answer is "NO".

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

Example output:
YES
YES
NO

Editorial:
It is not difficult to see that the answer «NO» in this task is possible when and only when all $$$a_i$$$ are different and sorted in descending order. In this case we need $$$\frac{n \cdot (n-1)}{2}$$$ operations. Otherwise the answer is always «YES».
Why does this solution work? Let's define number of inversions as the number of pairs $$$1 \le i < j \le n$$$ such as $$$a_i > a_j$$$. Note that if the number of inversions is zero, the $$$a$$$ array is sorted in non-decreasing order. If the array is not sorted, we can always choose two neighboring elements such that $$$a_i > a_{i+1}$$$ and swap them. In this case, the number of inversions is reduced by one. In this case, we cannot reduce the number of inversions by more than one, so it is equal to the minimum number of operations we must perform.
Now, all we have to do is notice that the number of inversions does not exceed $$$\frac{n(n-1)}2$$$, and the maximum is only reached when $$$a_i > a_j$$$ for all pairs $$$1 \le i < j \le n$$$. It follows that in this case the array must be strictly descending.
Thus, we have a solution with a time of $$$O(n)$$$.
Eugeny and Array
Contest: Codeforces Round 182 (Div. 2)
Difficulty rating: 800
Tags: implementation

Eugeny has array a = a1, a2, ..., an, consisting of n integers. Each integer ai equals to -1, or to 1. Also, he has m queries:

- Query number i is given as a pair of integers li, ri (1 ≤ li ≤ ri ≤ n).
- The response to the query will be integer 1, if the elements of array a can be rearranged so as the sum ali + ali + 1 + ... + ari = 0, otherwise the response to the query will be integer 0.

Help Eugeny, answer all his queries.

Input format:
The first line contains integers n and m (1 ≤ n, m ≤ 2·105). The second line contains n integers a1, a2, ..., an (ai = -1, 1). Next m lines contain Eugene's queries. The i-th line contains integers li, ri (1 ≤ li ≤ ri ≤ n).

Output format:
Print m integers — the responses to Eugene's queries in the order they occur in the input.

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

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

Example output:
0
1
0

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

Example output:
0
1
0
1
0

Editorial:
Eugeny and Play List
Contest: Codeforces Round 182 (Div. 2)
Difficulty rating: 1200
Tags: binary search, implementation, two pointers

Eugeny loves listening to music. He has n songs in his play list. We know that song number i has the duration of ti minutes. Eugeny listens to each song, perhaps more than once. He listens to song number i ci times. Eugeny's play list is organized as follows: first song number 1 plays c1 times, then song number 2 plays c2 times, ..., in the end the song number n plays cn times.

Eugeny took a piece of paper and wrote out m moments of time when he liked a song. Now for each such moment he wants to know the number of the song that played at that moment. The moment x means that Eugeny wants to know which song was playing during the x-th minute of his listening to the play list.

Help Eugeny and calculate the required numbers of songs.

Input format:
The first line contains two integers n, m (1 ≤ n, m ≤ 105). The next n lines contain pairs of integers. The i-th line contains integers ci, ti (1 ≤ ci, ti ≤ 109) — the description of the play list. It is guaranteed that the play list's total duration doesn't exceed 109 $$(\sum_{i=1}^{n} c_i \cdot t_i \leq 10^9)$$.

The next line contains m positive integers v1, v2, ..., vm, that describe the moments Eugeny has written out. It is guaranteed that there isn't such moment of time vi, when the music doesn't play any longer. It is guaranteed that vi < vi + 1 (i < m).

The moment of time vi means that Eugeny wants to know which song was playing during the vi-th munite from the start of listening to the playlist.

Output format:
Print m integers — the i-th number must equal the number of the song that was playing during the vi-th minute after Eugeny started listening to the play list.

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

Example input:
1 2
2 8
1 16

Example output:
1
1

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

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

Editorial:
Minimum Difficulty
Contest: Codeforces Round 283 (Div. 2)
Difficulty rating: 900
Tags: brute force, implementation, math

Mike is trying rock climbing but he is awful at it.

There are n holds on the wall, i-th hold is at height ai off the ground. Besides, let the sequence ai increase, that is, ai < ai + 1 for all i from 1 to n - 1; we will call such sequence a track. Mike thinks that the track a1, ..., an has difficulty $$d = \max_{1 \leq i \leq n-1} (a_{i+1} - a_i)$$. In other words, difficulty equals the maximum distance between two holds that are adjacent in height.

Today Mike decided to cover the track with holds hanging on heights a1, ..., an. To make the problem harder, Mike decided to remove one hold, that is, remove one element of the sequence (for example, if we take the sequence (1, 2, 3, 4, 5) and remove the third element from it, we obtain the sequence (1, 2, 4, 5)). However, as Mike is awful at climbing, he wants the final difficulty (i.e. the maximum difference of heights between adjacent holds after removing the hold) to be as small as possible among all possible options of removing a hold. The first and last holds must stay at their positions.

Help Mike determine the minimum difficulty of the track after removing one hold.

Input format:
The first line contains a single integer n (3 ≤ n ≤ 100) — the number of holds.

The next line contains n space-separated integers ai (1 ≤ ai ≤ 1000), where ai is the height where the hold number i hangs. The sequence ai is increasing (i.e. each element except for the first one is strictly larger than the previous one).

Output format:
Print a single number — the minimum difficulty of the track after removing a single hold.

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

Note:
In the first sample you can remove only the second hold, then the sequence looks like (1, 6), the maximum difference of the neighboring elements equals 5.

In the second test after removing every hold the difficulty equals 2.

In the third test you can obtain sequences (1, 3, 7, 8), (1, 2, 7, 8), (1, 2, 3, 8), for which the difficulty is 4, 5 and 5, respectively. Thus, after removing the second element we obtain the optimal answer — 4.

Example input:
3
1 4 6

Example output:
5

Example input:
5
1 2 3 4 5

Example output:
2

Editorial:
Secret Combination
Contest: Codeforces Round 283 (Div. 2)
Difficulty rating: 1500
Tags: brute force, constructive algorithms, implementation

You got a box with a combination lock. The lock has a display showing n digits. There are two buttons on the box, each button changes digits on the display. You have quickly discovered that the first button adds 1 to all the digits (all digits 9 become digits 0), and the second button shifts all the digits on the display one position to the right (the last digit becomes the first one). For example, if the display is currently showing number 579, then if we push the first button, the display will show 680, and if after that we push the second button, the display will show 068.

You know that the lock will open if the display is showing the smallest possible number that can be obtained by pushing the buttons in some order. The leading zeros are ignored while comparing numbers. Now your task is to find the desired number.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of digits on the display.

The second line contains n digits — the initial state of the display.

Output format:
Print a single line containing n digits — the desired state of the display containing the smallest possible number.

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

Example input:
3
579

Example output:
024

Example input:
4
2014

Example output:
0142

Editorial:
Removing Columns
Contest: Codeforces Round 283 (Div. 2)
Difficulty rating: 1500
Tags: brute force, constructive algorithms, implementation

You are given an n × m rectangular table consisting of lower case English letters. In one operation you can completely remove one column from the table. The remaining parts are combined forming a new table. For example, after removing the second column from the table

we obtain the table:

A table is called good if its rows are ordered from top to bottom lexicographically, i.e. each row is lexicographically no larger than the following one. Determine the minimum number of operations of removing a column needed to make a given table good.

Input format:
The first line contains two integers  — n and m (1 ≤ n, m ≤ 100).

Next n lines contain m small English letters each — the characters of the table.

Output format:
Print a single number — the minimum number of columns that you need to remove in order to make the table good.

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

Note:
In the first sample the table is already good.

In the second sample you may remove the first and third column.

In the third sample you have to remove all the columns (note that the table where all rows are empty is considered good by definition).

Let strings s and t have equal length. Then, s is lexicographically larger than t if they are not equal and the character following the largest common prefix of s and t (the prefix may be empty) in s is alphabetically larger than the corresponding character of t.

Example input:
1 10
codeforces

Example output:
0

Example input:
4 4
case
care
test
code

Example output:
2

Editorial:
Tennis Game
Contest: Codeforces Round 283 (Div. 2)
Difficulty rating: 1900
Tags: binary search

Petya and Gena love playing table tennis. A single match is played according to the following rules: a match consists of multiple sets, each set consists of multiple serves. Each serve is won by one of the players, this player scores one point. As soon as one of the players scores t points, he wins the set; then the next set starts and scores of both players are being set to 0. As soon as one of the players wins the total of s sets, he wins the match and the match is over. Here s and t are some positive integer numbers.

To spice it up, Petya and Gena choose new numbers s and t before every match. Besides, for the sake of history they keep a record of each match: that is, for each serve they write down the winner. Serve winners are recorded in the chronological order. In a record the set is over as soon as one of the players scores t points and the match is over as soon as one of the players wins s sets.

Petya and Gena have found a record of an old match. Unfortunately, the sequence of serves in the record isn't divided into sets and numbers s and t for the given match are also lost. The players now wonder what values of s and t might be. Can you determine all the possible options?

Input format:
The first line contains a single integer n — the length of the sequence of games (1 ≤ n ≤ 105).

The second line contains n space-separated integers ai. If ai = 1, then the i-th serve was won by Petya, if ai = 2, then the i-th serve was won by Gena.

It is not guaranteed that at least one option for numbers s and t corresponds to the given record.

Output format:
In the first line print a single number k — the number of options for numbers s and t.

In each of the following k lines print two integers si and ti — the option for numbers s and t. Print the options in the order of increasing si, and for equal si — in the order of increasing ti.

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

Example input:
5
1 2 1 2 1

Example output:
2
1 3
3 1

Example input:
4
1 1 1 1

Example output:
3
1 4
2 2
4 1

Editorial:
Distributing Parts
Contest: Codeforces Round 283 (Div. 2)
Difficulty rating: 2100
Tags: greedy, sortings

You are an assistant director in a new musical play. The play consists of n musical parts, each part must be performed by exactly one actor. After the casting the director chose m actors who can take part in the play. Your task is to assign the parts to actors. However, there are several limitations.

First, each actor has a certain voice range and there are some parts that he cannot sing. Formally, there are two integers for each actor, ci and di (ci ≤ di) — the pitch of the lowest and the highest note that the actor can sing. There also are two integers for each part — aj and bj (aj ≤ bj) — the pitch of the lowest and the highest notes that are present in the part. The i-th actor can perform the j-th part if and only if ci ≤ aj ≤ bj ≤ di, i.e. each note of the part is in the actor's voice range.

According to the contract, the i-th actor can perform at most ki parts. Besides, you are allowed not to give any part to some actors (then they take part in crowd scenes).

The rehearsal starts in two hours and you need to do the assignment quickly!

Input format:
The first line contains a single integer n — the number of parts in the play (1 ≤ n ≤ 105).

Next n lines contain two space-separated integers each, aj and bj — the range of notes for the j-th part (1 ≤ aj ≤ bj ≤ 109).

The next line contains a single integer m — the number of actors (1 ≤ m ≤ 105).

Next m lines contain three space-separated integers each, ci, di and ki — the range of the i-th actor and the number of parts that he can perform (1 ≤ ci ≤ di ≤ 109, 1 ≤ ki ≤ 109).

Output format:
If there is an assignment that meets all the criteria aboce, print a single word "YES" (without the quotes) in the first line.

In the next line print n space-separated integers. The i-th integer should be the number of the actor who should perform the i-th part. If there are multiple correct assignments, print any of them.

If there is no correct assignment, print a single word "NO" (without the quotes).

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

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

Example output:
YES
1 1 2

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

Example output:
NO

Editorial:
Bulbs
Contest: Codeforces Round 338 (Div. 2)
Difficulty rating: 800
Tags: implementation

Vasya wants to turn on Christmas lights consisting of m bulbs. Initially, all bulbs are turned off. There are n buttons, each of them is connected to some set of bulbs. Vasya can press any of these buttons. When the button is pressed, it turns on all the bulbs it's connected to. Can Vasya light up all the bulbs?

If Vasya presses the button such that some bulbs connected to it are already turned on, they do not change their state, i.e. remain turned on.

Input format:
The first line of the input contains integers n and m (1 ≤ n, m ≤ 100) — the number of buttons and the number of bulbs respectively.

Each of the next n lines contains xi (0 ≤ xi ≤ m) — the number of bulbs that are turned on by the i-th button, and then xi numbers yij (1 ≤ yij ≤ m) — the numbers of these bulbs.

Output format:
If it's possible to turn on all m bulbs print "YES", otherwise print "NO".

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

Note:
In the first sample you can press each button once and turn on all the bulbs. In the 2 sample it is impossible to turn on the 3-rd lamp.

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

Example output:
YES

Example input:
3 3
1 1
1 2
1 1

Example output:
NO

Editorial:
Let's make a counter of number of buttons that switch every lamp off. If there is a lamp with zero counter, output NO, otherwise YES.
Longtail Hedgehog
Contest: Codeforces Round 338 (Div. 2)
Difficulty rating: 1600
Tags: dp, graphs

This Christmas Santa gave Masha a magic picture and a pencil. The picture consists of n points connected by m segments (they might cross in any way, that doesn't matter). No two segments connect the same pair of points, and no segment connects the point to itself. Masha wants to color some segments in order paint a hedgehog. In Mashas mind every hedgehog consists of a tail and some spines. She wants to paint the tail that satisfies the following conditions:

1. Only segments already presented on the picture can be painted;
2. The tail should be continuous, i.e. consists of some sequence of points, such that every two neighbouring points are connected by a colored segment;
3. The numbers of points from the beginning of the tail to the end should strictly increase.

Masha defines the length of the tail as the number of points in it. Also, she wants to paint some spines. To do so, Masha will paint all the segments, such that one of their ends is the endpoint of the tail. Masha defines the beauty of a hedgehog as the length of the tail multiplied by the number of spines. Masha wants to color the most beautiful hedgehog. Help her calculate what result she may hope to get.

Note that according to Masha's definition of a hedgehog, one segment may simultaneously serve as a spine and a part of the tail (she is a little girl after all). Take a look at the picture for further clarifications.

Input format:
First line of the input contains two integers n and m(2 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000) — the number of points and the number segments on the picture respectively.

Then follow m lines, each containing two integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — the numbers of points connected by corresponding segment. It's guaranteed that no two segments connect the same pair of points.

Output format:
Print the maximum possible value of the hedgehog's beauty.

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

Note:
The picture below corresponds to the first sample. Segments that form the hedgehog are painted red. The tail consists of a sequence of points with numbers 1, 2 and 5. The following segments are spines: (2, 5), (3, 5) and (4, 5). Therefore, the beauty of the hedgehog is equal to 3·3 = 9.

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

Example output:
9

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

Example output:
12

Editorial:
Посчитаем dp[i] – максимальная длина хвоста, заканчивающегося в i-ой вершине. Обновлять его очень просто – пройдем по всем ребрам из вершины и попытаемся увеличить текущее значение в концах ребер. Для ответа пройдемся по всем вершинам и выберем лучшую.