1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Path Queries
Contest: Codeforces Round 582 (Div. 3)
Difficulty rating: 1800
Tags: divide and conquer, dsu, graphs, sortings, trees

You are given a weighted tree consisting of $$$n$$$ vertices. Recall that a tree is a connected graph without cycles. Vertices $$$u_i$$$ and $$$v_i$$$ are connected by an edge with weight $$$w_i$$$.

You are given $$$m$$$ queries. The $$$i$$$-th query is given as an integer $$$q_i$$$. In this query you need to calculate the number of pairs of vertices $$$(u, v)$$$ ($$$u < v$$$) such that the maximum weight of an edge on a simple path between $$$u$$$ and $$$v$$$ doesn't exceed $$$q_i$$$.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of vertices in the tree and the number of queries.

Each of the next $$$n - 1$$$ lines describes an edge of the tree. Edge $$$i$$$ is denoted by three integers $$$u_i$$$, $$$v_i$$$ and $$$w_i$$$ — the labels of vertices it connects ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) and the weight of the edge ($$$1 \le w_i \le 2 \cdot 10^5$$$). It is guaranteed that the given edges form a tree.

The last line of the input contains $$$m$$$ integers $$$q_1, q_2, \dots, q_m$$$ ($$$1 \le q_i \le 2 \cdot 10^5$$$), where $$$q_i$$$ is the maximum weight of an edge in the $$$i$$$-th query.

Output format:
Print $$$m$$$ integers — the answers to the queries. The $$$i$$$-th value should be equal to the number of pairs of vertices $$$(u, v)$$$ ($$$u < v$$$) such that the maximum weight of an edge on a simple path between $$$u$$$ and $$$v$$$ doesn't exceed $$$q_i$$$.

Queries are numbered from $$$1$$$ to $$$m$$$ in the order of the input.

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

Note:
The picture shows the tree from the first example:

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

Example output:
21 7 15 21 3

Example input:
1 2
1 2

Example output:
0 0

Editorial:
Let's carry the value $$$res$$$ that means the answer for the current set of edges. Initially it is $$$0$$$. Let's sort all edges by their weight and all queries by their weight also (both in non-decreasing order).
Let's merge components of the tree using DSU (disjoint set union). We need to carry sizes of components also (it is easy if we use DSU). Then let's iterate over all queries in order of non-decreasing their weights. If the current query has weight $$$cw$$$ then let's merge all components connected by edges with weight $$$w_i \le cw$$$. When we merge two components with sizes $$$s_1$$$ and $$$s_2$$$, the answer changes like that: $$$res := res - \binom{s_1}{2} - \binom{s_2}{2} + \binom{s_1 + s_2}{2}$$$. The value $$$\binom{x}{2}$$$ equals to $$$\frac{x(x-1)}{2}$$$. It is so because we subtract all old paths corresponding to these components and add all new paths in the obtained component. So the answer for the current query will be $$$res$$$ after all required merges.
Time complexity: $$$O(n \log n + m \log m)$$$.
Boredom
Contest: Codeforces Round 260 (Div. 1)
Difficulty rating: 1500
Tags: dp

Alex doesn't like boredom. That's why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it.

Given a sequence a consisting of n integers. The player can make several steps. In a single step he can choose an element of the sequence (let's denote it ak) and delete it, at that all elements equal to ak + 1 and ak - 1 also must be deleted from the sequence. That step brings ak points to the player.

Alex is a perfectionist, so he decided to get as many points as possible. Help him.

Input format:
The first line contains integer n (1 ≤ n ≤ 105) that shows how many numbers are in Alex's sequence.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 105).

Output format:
Print a single integer — the maximum number of points that Alex can earn.

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

Note:
Consider the third test example. At first step we need to choose any element equal to 2. After that step our sequence looks like this [2, 2, 2, 2]. Then we do 4 steps, on each step we choose any element equals to 2. In total we earn 10 points.

Example input:
2
1 2

Example output:
2

Example input:
3
1 2 3

Example output:
4

Editorial:
A Lot of Games
Contest: Codeforces Round 260 (Div. 1)
Difficulty rating: 1900
Tags: dfs and similar, dp, games, implementation, strings, trees

Andrew, Fedor and Alex are inventive guys. Now they invent the game with strings for two players.

Given a group of n non-empty strings. During the game two players build the word together, initially the word is empty. The players move in turns. On his step player must add a single letter in the end of the word, the resulting word must be prefix of at least one string from the group. A player loses if he cannot move.

Andrew and Alex decided to play this game k times. The player who is the loser of the i-th game makes the first move in the (i + 1)-th game. Guys decided that the winner of all games is the player who wins the last (k-th) game. Andrew and Alex already started the game. Fedor wants to know who wins the game if both players will play optimally. Help him.

Input format:
The first line contains two integers, n and k (1 ≤ n ≤ 105; 1 ≤ k ≤ 109).

Each of the next n lines contains a single non-empty string from the given group. The total length of all strings from the group doesn't exceed 105. Each string of the group consists only of lowercase English letters.

Output format:
If the player who moves first wins, print "First", otherwise print "Second" (without the quotes).

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

Example input:
2 3
a
b

Example output:
First

Example input:
3 1
a
b
c

Example output:
First

Editorial:
Civilization
Contest: Codeforces Round 260 (Div. 1)
Difficulty rating: 2100
Tags: dfs and similar, dp, dsu, ternary search, trees

Andrew plays a game called "Civilization". Dima helps him.

The game has n cities and m bidirectional roads. The cities are numbered from 1 to n. Between any pair of cities there either is a single (unique) path, or there is no path at all. A path is such a sequence of distinct cities v1, v2, ..., vk, that there is a road between any contiguous cities vi and vi + 1 (1 ≤ i < k). The length of the described path equals to (k - 1). We assume that two cities lie in the same region if and only if, there is a path connecting these two cities.

During the game events of two types take place:

1. Andrew asks Dima about the length of the longest path in the region where city x lies.
2. Andrew asks Dima to merge the region where city x lies with the region where city y lies. If the cities lie in the same region, then no merging is needed. Otherwise, you need to merge the regions as follows: choose a city from the first region, a city from the second region and connect them by a road so as to minimize the length of the longest path in the resulting region. If there are multiple ways to do so, you are allowed to choose any of them.

Dima finds it hard to execute Andrew's queries, so he asks you to help him. Help Dima.

Input format:
The first line contains three integers n, m, q (1 ≤ n ≤ 3·105; 0 ≤ m < n; 1 ≤ q ≤ 3·105) — the number of cities, the number of the roads we already have and the number of queries, correspondingly.

Each of the following m lines contains two integers, ai and bi (ai ≠ bi; 1 ≤ ai, bi ≤ n). These numbers represent the road between cities ai and bi. There can be at most one road between two cities.

Each of the following q lines contains one of the two events in the following format:

- 1 xi. It is the request Andrew gives to Dima to find the length of the maximum path in the region that contains city xi (1 ≤ xi ≤ n).
- 2 xi yi. It is the request Andrew gives to Dima to merge the region that contains city xi and the region that contains city yi (1 ≤ xi, yi ≤ n). Note, that xi can be equal to yi.

Output format:
For each event of the first type print the answer on a separate line.

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

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

Example output:
4

Editorial:
Serega and Fun
Contest: Codeforces Round 260 (Div. 1)
Difficulty rating: 2700
Tags: data structures

Serega loves fun. However, everyone has fun in the unique manner. Serega has fun by solving query problems. One day Fedor came up with such a problem.

You are given an array a consisting of n positive integers and queries to it. The queries can be of two types:

1. Make a unit cyclic shift to the right on the segment from l to r (both borders inclusive). That is rearrange elements of the array in the following manner:a[l], a[l + 1], ..., a[r - 1], a[r] → a[r], a[l], a[l + 1], ..., a[r - 1].
2. Count how many numbers equal to k are on the segment from l to r (both borders inclusive).

Fedor hurried to see Serega enjoy the problem and Serega solved it really quickly. Let's see, can you solve it?

Input format:
The first line contains integer n (1 ≤ n ≤ 105) — the number of elements of the array. The second line contains n integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n).

The third line contains a single integer q (1 ≤ q ≤ 105) — the number of queries. The next q lines contain the queries.

As you need to respond to the queries online, the queries will be encoded. A query of the first type will be given in format: 1 l'i r'i. A query of the second type will be given in format: 2 l'i r'i k'i. All the number in input are integer. They satisfy the constraints: 1 ≤ l'i, r'i, k'i ≤ n.

To decode the queries from the data given in input, you need to perform the following transformations:

li = ((l'i + lastans - 1) mod n) + 1; ri = ((r'i + lastans - 1) mod n) + 1; ki = ((k'i + lastans - 1) mod n) + 1.

Where lastans is the last reply to the query of the 2-nd type (initially, lastans = 0). If after transformation li is greater than ri, you must swap these values.

Output format:
For each query of the 2-nd type print the answer on a single line.

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

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

Example output:
2
1
0
0

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

Example output:
2
0

Editorial:
Function
Contest: Codeforces Round 260 (Div. 1)
Difficulty rating: 2900
Tags: data structures

Serega and Fedor play with functions. One day they came across a very interesting function. It looks like that:

- f(1, j) = a[j], 1 ≤ j ≤ n.
- f(i, j) = min(f(i - 1, j), f(i - 1, j - 1)) + a[j], 2 ≤ i ≤ n, i ≤ j ≤ n.

Here a is an integer array of length n.

Serega and Fedya want to know what values this function takes at some points. But they don't want to calculate the values manually. So they ask you to help them.

Input format:
The first line contains integer n (1 ≤ n ≤ 105) — the length of array a. The next line contains n integers: a[1], a[2], ..., a[n] (0 ≤ a[i] ≤ 104).

The next line contains integer m (1 ≤ m ≤ 105) — the number of queries. Each of the next m lines contains two integers: xi, yi (1 ≤ xi ≤ yi ≤ n). Each line means that Fedor and Serega want to know the value of f(xi, yi).

Output format:
Print m lines — the answers to the guys' queries.

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

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

Example output:
12
9
9
5

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

Example output:
11
4
3
0

Editorial:
Shortest Path with Obstacle
Contest: Codeforces Round 731 (Div. 3)
Difficulty rating: 800
Tags: implementation, math

There are three cells on an infinite 2-dimensional grid, labeled $$$A$$$, $$$B$$$, and $$$F$$$. Find the length of the shortest path from $$$A$$$ to $$$B$$$ if:

- in one move you can go to any of the four adjacent cells sharing a side;
- visiting the cell $$$F$$$ is forbidden (it is an obstacle).

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input. Then $$$t$$$ test cases follow. Before each test case, there is an empty line.

Each test case contains three lines. The first one contains two integers $$$x_A, y_A$$$ ($$$1 \le x_A, y_A \le 1000$$$) — coordinates of the start cell $$$A$$$. The second one contains two integers $$$x_B, y_B$$$ ($$$1 \le x_B, y_B \le 1000$$$) — coordinates of the finish cell $$$B$$$. The third one contains two integers $$$x_F, y_F$$$ ($$$1 \le x_F, y_F \le 1000$$$) — coordinates of the forbidden cell $$$F$$$. All cells are distinct.

Coordinate $$$x$$$ corresponds to the column number and coordinate $$$y$$$ corresponds to the row number (see the pictures below).

Output format:
Output $$$t$$$ lines. The $$$i$$$-th line should contain the answer for the $$$i$$$-th test case: the length of the shortest path from the cell $$$A$$$ to the cell $$$B$$$ if the cell $$$F$$$ is not allowed to be visited.

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

Note:
An example of a possible shortest path for the first test case.

An example of a possible shortest path for the second test case.

Example input:
7

1 1
3 3
2 2

2 5
2 1
2 3

1000 42
1000 1
1000 1000

1 10
3 10
2 10

3 8
7 8
3 7

2 1
4 1
1 1

1 344
1 10
1 1

Example output:
4
6
41
4
4
2
334

Editorial:
Let's suppose that the forbidden cell does not affect the shortest path. In that case, the answer would be $$$|x_A - x_B| + |y_A - y_B|$$$.
The forbidden cell blocks the shortest path if and only if it belongs to every shortest path. In other words, if there is only one shortest path and the forbidden cell belongs to it. So, the answer differs from $$$|x_A - x_B| + |y_A - y_B|$$$ if and only if $$$A$$$ and $$$B$$$ are in one row or column and $$$F$$$ is between them. In that case, the answer is $$$|x_A - x_B| + |y_A - y_B| + 2$$$ (i.e. greater by $$$2$$$).
In order to check that point $$$R$$$ lays between $$$P$$$ and $$$Q$$$ on a straight line, just check $$$\min(P, Q) < R < \max(P, Q)$$$.
So, the correct solution looks like this:
Alphabetical Strings
Contest: Codeforces Round 731 (Div. 3)
Difficulty rating: 800
Tags: greedy, implementation, strings

A string $$$s$$$ of length $$$n$$$ ($$$1 \le n \le 26$$$) is called alphabetical if it can be obtained using the following algorithm:

- first, write an empty string to $$$s$$$ (i.e. perform the assignment $$$s$$$ := "");
- then perform the next step $$$n$$$ times;
- at the $$$i$$$-th step take $$$i$$$-th lowercase letter of the Latin alphabet and write it either to the left of the string $$$s$$$ or to the right of the string $$$s$$$ (i.e. perform the assignment $$$s$$$ := $$$c+s$$$ or $$$s$$$ := $$$s+c$$$, where $$$c$$$ is the $$$i$$$-th letter of the Latin alphabet).

In other words, iterate over the $$$n$$$ first letters of the Latin alphabet starting from 'a' and etc. Each time we prepend a letter to the left of the string $$$s$$$ or append a letter to the right of the string $$$s$$$. Strings that can be obtained in that way are alphabetical.

For example, the following strings are alphabetical: "a", "ba", "ab", "bac" and "ihfcbadeg". The following strings are not alphabetical: "z", "aa", "ca", "acb", "xyz" and "ddcba".

From the given string, determine if it is alphabetical.

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

Each test case is written on a separate line that contains one string $$$s$$$. String $$$s$$$ consists of lowercase letters of the Latin alphabet and has a length between $$$1$$$ and $$$26$$$, inclusive.

Output format:
Output $$$t$$$ lines, each of them must contain the answer to the corresponding test case. Output YES if the given string $$$s$$$ is alphabetical and NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive answer).

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

Note:
The example contains test cases from the main part of the condition.

Example input:
11
a
ba
ab
bac
ihfcbadeg
z
aa
ca
acb
xyz
ddcba

Example output:
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO

Editorial:
For a start, let's find the position of the letter 'a' in string $$$s$$$. If this position does not exist, then the answer would be 'NO'. Suppose that this position exists and equals $$$\text{pos}_a$$$. Let's create two pointers $$$L$$$ and $$$R$$$. Initially $$$L := \text{pos}_a,~R := L$$$. We will try to build string $$$s$$$ using the algorithm from the statement. Suppose that we have built substring $$$s[L..R]$$$ in $$$i$$$ iterations. Consider the next letter of the Latin alphabet $$$c_i$$$. Let's look at cases:
1. find position $$$pos$$$ of the letter $$$c_i$$$ in $$$s$$$ (if it does not exist then 'NO');
2. if $$$pos = L - 1$$$ then make an assignment $$$L := L - 1$$$ and process the next letter $$$c_i$$$;
3. if $$$pos = R + 1$$$ then make an assignment $$$R := R + 1$$$ and process the next letter $$$c_i$$$;
4. otherwise string $$$s$$$ is not alphabetical and the answer is 'NO'.
Colorful Stones (Simplified Edition)
Contest: Codeforces Round 162 (Div. 2)
Difficulty rating: 800
Tags: implementation

There is a sequence of colorful stones. The color of each stone is one of red, green, or blue. You are given a string s. The i-th (1-based) character of s represents the color of the i-th stone. If the character is "R", "G", or "B", the color of the corresponding stone is red, green, or blue, respectively.

Initially Squirrel Liss is standing on the first stone. You perform instructions one or more times.

Each instruction is one of the three types: "RED", "GREEN", or "BLUE". After an instruction c, if Liss is standing on a stone whose colors is c, Liss will move one stone forward, else she will not move.

You are given a string t. The number of instructions is equal to the length of t, and the i-th character of t represents the i-th instruction.

Calculate the final position of Liss (the number of the stone she is going to stand on in the end) after performing all the instructions, and print its 1-based position. It is guaranteed that Liss don't move out of the sequence.

Input format:
The input contains two lines. The first line contains the string s (1 ≤ |s| ≤ 50). The second line contains the string t (1 ≤ |t| ≤ 50). The characters of each string will be one of "R", "G", or "B". It is guaranteed that Liss don't move out of the sequence.

Output format:
Print the final 1-based position of Liss in a single line.

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

Example input:
RGB
RRR

Example output:
2

Example input:
RRRBGBRBBB
BBBRR

Example output:
3

Editorial:
Roadside Trees (Simplified Edition)
Contest: Codeforces Round 162 (Div. 2)
Difficulty rating: 1000
Tags: greedy, implementation

Squirrel Liss loves nuts. There are n trees (numbered 1 to n from west to east) along a street and there is a delicious nut on the top of each tree. The height of the tree i is hi. Liss wants to eat all nuts.

Now Liss is on the root of the tree with the number 1. In one second Liss can perform one of the following actions:

- Walk up or down one unit on a tree.
- Eat a nut on the top of the current tree.
- Jump to the next tree. In this action the height of Liss doesn't change. More formally, when Liss is at height h of the tree i (1 ≤ i ≤ n - 1), she jumps to height h of the tree i + 1. This action can't be performed if h > hi + 1.

Compute the minimal time (in seconds) required to eat all nuts.

Input format:
The first line contains an integer n (1  ≤  n ≤ 105) — the number of trees.

Next n lines contains the height of trees: i-th line contains an integer hi (1 ≤ hi ≤ 104) — the height of the tree with the number i.

Output format:
Print a single integer — the minimal time required to eat all nuts in seconds.

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

Example input:
2
1
2

Example output:
5

Example input:
5
2
1
2
1
1

Example output:
14

Editorial:
Yaroslav and Sequence
Contest: Codeforces Round 182 (Div. 1)
Difficulty rating: 1800
Tags: constructive algorithms

Yaroslav has an array, consisting of (2·n - 1) integers. In a single operation Yaroslav can change the sign of exactly n elements in the array. In other words, in one operation Yaroslav can select exactly n array elements, and multiply each of them by -1.

Yaroslav is now wondering: what maximum sum of array elements can be obtained if it is allowed to perform any number of described operations?

Help Yaroslav.

Input format:
The first line contains an integer n (2 ≤ n ≤ 100). The second line contains (2·n - 1) integers — the array elements. The array elements do not exceed 1000 in their absolute value.

Output format:
In a single line print the answer to the problem — the maximum sum that Yaroslav can get.

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

Note:
In the first sample you do not need to change anything. The sum of elements equals 150.

In the second sample you need to change the sign of the first two elements. Then we get the sum of the elements equal to 100.

Example input:
2
50 50 50

Example output:
150

Example input:
2
-1 -100 -1

Example output:
100

Editorial:
Yaroslav and Time
Contest: Codeforces Round 182 (Div. 1)
Difficulty rating: 2100
Tags: binary search, graphs, shortest paths

Yaroslav is playing a game called "Time". The game has a timer showing the lifespan he's got left. As soon as the timer shows 0, Yaroslav's character dies and the game ends. Also, the game has n clock stations, station number i is at point (xi, yi) of the plane. As the player visits station number i, he increases the current time on his timer by ai. The stations are for one-time use only, so if the player visits some station another time, the time on his timer won't grow.

A player spends d·dist time units to move between stations, where dist is the distance the player has covered and d is some constant. The distance between stations i and j is determined as |xi - xj| + |yi - yj|.

Initially, the player is at station number 1, and the player has strictly more than zero and strictly less than one units of time. At station number 1 one unit of money can increase the time on the timer by one time unit (you can buy only integer number of time units).

Now Yaroslav is wondering, how much money he needs to get to station n. Help Yaroslav. Consider the time to buy and to increase the timer value negligibly small.

Input format:
The first line contains integers n and d (3 ≤ n ≤ 100, 103 ≤ d ≤ 105) — the number of stations and the constant from the statement.

The second line contains n - 2 integers: a2, a3, ..., an - 1 (1 ≤ ai ≤ 103). The next n lines contain the coordinates of the stations. The i-th of them contains two integers xi, yi (-100 ≤ xi, yi ≤ 100).

It is guaranteed that no two stations are located at the same point.

Output format:
In a single line print an integer — the answer to the problem.

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

Example input:
3 1000
1000
0 0
0 1
0 3

Example output:
2000

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

Example output:
1000

Editorial: