1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Bicolored Segments
Contest: Educational Codeforces Round 92 (Rated for Div. 2)
Difficulty rating: 2600
Tags: data structures, dp, graph matchings, sortings

You are given $$$n$$$ segments $$$[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$$$. Each segment has one of two colors: the $$$i$$$-th segment's color is $$$t_i$$$.

Let's call a pair of segments $$$i$$$ and $$$j$$$ bad if the following two conditions are met:

- $$$t_i \ne t_j$$$;
- the segments $$$[l_i, r_i]$$$ and $$$[l_j, r_j]$$$ intersect, embed or touch, i. e. there exists an integer $$$x$$$ such that $$$x \in [l_i, r_i]$$$ and $$$x \in [l_j, r_j]$$$.

Calculate the maximum number of segments that can be selected from the given ones, so that there is no bad pair among the selected ones.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — number of segments.

The next $$$n$$$ lines contains three integers $$$l_i, r_i, t_i$$$ ($$$1 \le l_i \le r_i \le 10^9; t_i \in \{1, 2\}$$$) — description of the $$$i$$$-th segment.

Output format:
Print the maximum number of segments that can be selected, so that there is no bad pair among the selected segments.

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

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

Example output:
2

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

Example output:
4

Editorial:
There are two approaches to this problem. Most of the participants of the round got AC by implementing dynamic programming with data structures such as segment tree, but I will describe another solution which is much easier to code.
Let's consider a graph where each vertex represents a segment, and two vertices are connected by an edge if the corresponding segments compose a bad pair.
Since each bad pair is formed by two segments of different colors, the graph is bipartite. The problem asks us to find the maximum independent set, and in bipartite graphs, the size of the independent set is equal to $$$V - M$$$, where $$$V$$$ is the number of vertices, and $$$M$$$ is the size of the maximum matching.
The only thing that's left is finding the maximum matching. Let's use event processing approach to do it: for each segment, create two events "the segment begins" and "the segment ends". While processing the events, maintain the currently existing segments in two sets (grouped by their colors and sorted by the time they end). When a segment ends, let's try to match it with some segment of the opposite color — and it's quite obvious that we should choose a segment with the minimum $$$r_i$$$ to form a pair.
Overall, this solution runs in $$$O(n \log n)$$$.
Army
Contest: School Personal Contest #1 (Winter Computer School 2010/11) - Codeforces Beta Round 38 (ACM-ICPC Rules)
Difficulty rating: 800
Tags: implementation

The Berland Armed Forces System consists of n ranks that are numbered using natural numbers from 1 to n, where 1 is the lowest rank and n is the highest rank.

One needs exactly di years to rise from rank i to rank i + 1. Reaching a certain rank i having not reached all the previous i - 1 ranks is impossible.

Vasya has just reached a new rank of a, but he dreams of holding the rank of b. Find for how many more years Vasya should serve in the army until he can finally realize his dream.

Input format:
The first input line contains an integer n (2 ≤ n ≤ 100). The second line contains n - 1 integers di (1 ≤ di ≤ 100). The third input line contains two integers a and b (1 ≤ a < b ≤ n). The numbers on the lines are space-separated.

Output format:
Print the single number which is the number of years that Vasya needs to rise from rank a to rank b.

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

Example input:
3
5 6
1 2

Example output:
5

Example input:
3
5 6
1 3

Example output:
11

Editorial:
Chess
Contest: School Personal Contest #1 (Winter Computer School 2010/11) - Codeforces Beta Round 38 (ACM-ICPC Rules)
Difficulty rating: 1200
Tags: brute force, implementation, math

Two chess pieces, a rook and a knight, stand on a standard chessboard 8 × 8 in size. The positions in which they are situated are known. It is guaranteed that none of them beats the other one.

Your task is to find the number of ways to place another knight on the board so that none of the three pieces on the board beat another one. A new piece can only be placed on an empty square.

Input format:
The first input line contains the description of the rook's position on the board. This description is a line which is 2 in length. Its first symbol is a lower-case Latin letter from a to h, and its second symbol is a number from 1 to 8. The second line contains the description of the knight's position in a similar way. It is guaranteed that their positions do not coincide.

Output format:
Print a single number which is the required number of ways.

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

Example input:
a1
b2

Example output:
44

Example input:
a8
d4

Example output:
38

Editorial:
Blinds
Contest: School Personal Contest #1 (Winter Computer School 2010/11) - Codeforces Beta Round 38 (ACM-ICPC Rules)
Difficulty rating: 1400
Tags: brute force

The blinds are known to consist of opaque horizontal stripes that can be rotated thus regulating the amount of light flowing in the room. There are n blind stripes with the width of 1 in the factory warehouse for blind production. The problem is that all of them are spare details from different orders, that is, they may not have the same length (it is even possible for them to have different lengths)

Every stripe can be cut into two or more parts. The cuttings are made perpendicularly to the side along which the length is measured. Thus the cuttings do not change the width of a stripe but each of the resulting pieces has a lesser length (the sum of which is equal to the length of the initial stripe)

After all the cuttings the blinds are constructed through consecutive joining of several parts, similar in length, along sides, along which length is measured. Also, apart from the resulting pieces an initial stripe can be used as a blind if it hasn't been cut. It is forbidden to construct blinds in any other way.

Thus, if the blinds consist of k pieces each d in length, then they are of form of a rectangle of k × d bourlemeters.

Your task is to find for what window possessing the largest possible area the blinds can be made from the given stripes if on technical grounds it is forbidden to use pieces shorter than l bourlemeter. The window is of form of a rectangle with side lengths as positive integers.

Input format:
The first output line contains two space-separated integers n and l (1 ≤ n, l ≤ 100). They are the number of stripes in the warehouse and the minimal acceptable length of a blind stripe in bourlemeters. The second line contains space-separated n integers ai. They are the lengths of initial stripes in bourlemeters (1 ≤ ai ≤ 100).

Output format:
Print the single number — the maximal area of the window in square bourlemeters that can be completely covered. If no window with a positive area that can be covered completely without breaking any of the given rules exist, then print the single number 0.

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

Note:
In the first sample test the required window is 2 × 4 in size and the blinds for it consist of 4 parts, each 2 bourlemeters long. One of the parts is the initial stripe with the length of 2, the other one is a part of a cut stripe with the length of 3 and the two remaining stripes are parts of a stripe with the length of 4 cut in halves.

Example input:
4 2
1 2 3 4

Example output:
8

Example input:
5 3
5 5 7 3 1

Example output:
15

Editorial:
Vasya the Architect
Contest: School Personal Contest #1 (Winter Computer School 2010/11) - Codeforces Beta Round 38 (ACM-ICPC Rules)
Difficulty rating: 1900
Tags: implementation

Once Vasya played bricks. All the bricks in the set had regular cubical shape. Vasya vas a talented architect, however the tower he built kept falling apart.

Let us consider the building process. Vasya takes a brick and puts it on top of the already built tower so that the sides of the brick are parallel to the sides of the bricks he has already used. Let's introduce a Cartesian coordinate system on the horizontal plane, where Vasya puts the first brick. Then the projection of brick number i on the plane is a square with sides parallel to the axes of coordinates with opposite corners in points (xi, 1, yi, 1) and (xi, 2, yi, 2). The bricks are cast from homogeneous plastic and the weight of a brick a × a × a is a3 grams.

It is guaranteed that Vasya puts any brick except the first one on the previous one, that is the area of intersection of the upper side of the previous brick and the lower side of the next brick is always positive.

We (Vasya included) live in a normal world where the laws of physical statics work. And that is why, perhaps, if we put yet another brick, the tower will collapse under its own weight. Vasya puts the cubes consecutively one on top of the other until at least one cube loses the balance and falls down. If it happens, Vasya gets upset and stops the construction. Print the number of bricks in the maximal stable tower, that is the maximal number m satisfying the condition that all the towers consisting of bricks 1, 2, ..., k for every integer k from 1 to m remain stable.

Input format:
The first input file contains an integer n (1 ≤ n ≤ 100) which is the number of bricks. Each of the next n lines contains four numbers xi, 1, yi, 1, xi, 2, yi, 2 (xi, 1 ≠ xi, 2, |xi, 1 - xi, 2| = |yi, 1 - yi, 2|) which are the coordinates of the opposite angles of the base of the brick number i. The coordinates are integers and their absolute value does not exceed 50.

The cubes are given in the order Vasya puts them. It is guaranteed that the area of intersection of the upper side of the brick number i - 1 and the lower side of the brick number i is strictly strictly greater than zero for all i ≥ 2.

Output format:
Print the number of bricks in the maximal stable tower.

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

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

Example output:
2

Example input:
2
0 0 3 3
2 0 5 3

Example output:
1

Editorial:
Let's Go Rolling!
Contest: School Personal Contest #1 (Winter Computer School 2010/11) - Codeforces Beta Round 38 (ACM-ICPC Rules)
Difficulty rating: 1800
Tags: dp, sortings

On a number axis directed from the left rightwards, n marbles with coordinates x1, x2, ..., xn are situated. Let's assume that the sizes of the marbles are infinitely small, that is in this task each of them is assumed to be a material point. You can stick pins in some of them and the cost of sticking in the marble number i is equal to ci, number ci may be negative. After you choose and stick the pins you need, the marbles will start to roll left according to the rule: if a marble has a pin stuck in it, then the marble doesn't move, otherwise the marble rolls all the way up to the next marble which has a pin stuck in it and stops moving there. If there is no pinned marble on the left to the given unpinned one, it is concluded that the marble rolls to the left to infinity and you will pay an infinitely large fine for it. If no marble rolled infinitely to the left, then the fine will consist of two summands:

- the sum of the costs of stuck pins;
- the sum of the lengths of the paths of each of the marbles, that is the sum of absolute values of differences between their initial and final positions.

Your task is to choose and pin some marbles in the way that will make the fine for you to pay as little as possible.

Input format:
The first input line contains an integer n (1 ≤ n ≤ 3000) which is the number of marbles. The next n lines contain the descriptions of the marbles in pairs of integers xi, ci ( - 109 ≤ xi, ci ≤ 109). The numbers are space-separated. Each description is given on a separate line. No two marbles have identical initial positions.

Output format:
Output the single number — the least fine you will have to pay.

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

Example input:
3
2 3
3 4
1 2

Example output:
5

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

Example output:
11

Editorial:
Smart Boy
Contest: School Personal Contest #1 (Winter Computer School 2010/11) - Codeforces Beta Round 38 (ACM-ICPC Rules)
Difficulty rating: 2100
Tags: dp, games, strings

Once Petya and Vasya invented a new game and called it "Smart Boy". They located a certain set of words — the dictionary — for the game. It is admissible for the dictionary to contain similar words.

The rules of the game are as follows: first the first player chooses any letter (a word as long as 1) from any word from the dictionary and writes it down on a piece of paper. The second player adds some other letter to this one's initial or final position, thus making a word as long as 2, then it's the first player's turn again, he adds a letter in the beginning or in the end thus making a word as long as 3 and so on. But the player mustn't break one condition: the newly created word must be a substring of a word from a dictionary. The player who can't add a letter to the current word without breaking the condition loses.

Also if by the end of a turn a certain string s is written on paper, then the player, whose turn it just has been, gets a number of points according to the formula:

$$$$

where

- $$\mathrm{value}(c)$$ is a sequence number of symbol c in Latin alphabet, numbered starting from 1. For example, $$value(\mathbf{a}) = 1$$, and $$value(z) = 26$$.
- $$\text{num}(s)$$ is the number of words from the dictionary where the line s occurs as a substring at least once.

Your task is to learn who will win the game and what the final score will be. Every player plays optimally and most of all tries to win, then — to maximize the number of his points, then — to minimize the number of the points of the opponent.

Input format:
The first input line contains an integer n which is the number of words in the located dictionary (1 ≤ n ≤ 30). The n lines contain the words from the dictionary — one word is written on one line. Those lines are nonempty, consisting of Latin lower-case characters no longer than 30 characters. Equal words can be in the list of words.

Output format:
On the first output line print a line "First" or "Second" which means who will win the game. On the second line output the number of points of the first player and the number of points of the second player after the game ends. Separate the numbers by a single space.

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

Example input:
2
aba
abac

Example output:
Second
29 35

Example input:
3
artem
nik
max

Example output:
First
2403 1882

Editorial:
Queue
Contest: School Personal Contest #1 (Winter Computer School 2010/11) - Codeforces Beta Round 38 (ACM-ICPC Rules)
Difficulty rating: 2300
Tags: data structures

On a cold winter evening our hero Vasya stood in a railway queue to buy a ticket for Codeforces championship final. As it usually happens, the cashier said he was going to be away for 5 minutes and left for an hour. Then Vasya, not to get bored, started to analyze such a mechanism as a queue. The findings astonished Vasya.

Every man is characterized by two numbers: ai, which is the importance of his current task (the greater the number is, the more important the task is) and number ci, which is a picture of his conscience. Numbers ai form the permutation of numbers from 1 to n.

Let the queue consist of n - 1 people at the moment. Let's look at the way the person who came number n behaves. First, he stands at the end of the queue and the does the following: if importance of the task ai of the man in front of him is less than an, they swap their places (it looks like this: the man number n asks the one before him: "Erm... Excuse me please but it's very important for me... could you please let me move up the queue?"), then he again poses the question to the man in front of him and so on. But in case when ai is greater than an, moving up the queue stops. However, the man number n can perform the operation no more than cn times.

In our task let us suppose that by the moment when the man number n joins the queue, the process of swaps between n - 1 will have stopped. If the swap is possible it necessarily takes place.

Your task is to help Vasya model the described process and find the order in which the people will stand in queue when all the swaps stops.

Input format:
The first input line contains an integer n which is the number of people who has joined the queue (1 ≤ n ≤ 105). In the next n lines descriptions of the people are given in order of their coming — space-separated integers ai and ci (1 ≤ ai ≤ n, 0 ≤ ci ≤ n). Every description is located on s single line. All the ai's are different.

Output format:
Output the permutation of numbers from 1 to n, which signifies the queue formed according to the above described rules, starting from the beginning to the end. In this succession the i-th number stands for the number of a person who will stand in line on the place number i after the swaps ends. People are numbered starting with 1 in the order in which they were given in the input. Separate numbers by a space.

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

Example input:
2
1 0
2 1

Example output:
2 1

Example input:
3
1 3
2 3
3 3

Example output:
3 2 1

Editorial:
Constructive Problems
Contest: Codeforces Round 915 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, math

Gridlandia has been hit by flooding and now has to reconstruct all of it's cities. Gridlandia can be described by an $$$n \times m$$$ matrix.

Initially, all of its cities are in economic collapse. The government can choose to rebuild certain cities. Additionally, any collapsed city which has at least one vertically neighboring rebuilt city and at least one horizontally neighboring rebuilt city can ask for aid from them and become rebuilt without help from the government. More formally, collapsed city positioned in $$$(i, j)$$$ can become rebuilt if both of the following conditions are satisfied:

- At least one of cities with positions $$$(i + 1, j)$$$ and $$$(i - 1, j)$$$ is rebuilt;
- At least one of cities with positions $$$(i, j + 1)$$$ and $$$(i, j - 1)$$$ is rebuilt.

If the city is located on the border of the matrix and has only one horizontally or vertically neighbouring city, then we consider only that city.

Illustration of two possible ways cities can be rebuilt by adjacent aid. White cells are collapsed cities, yellow cells are initially rebuilt cities (either by the government or adjacent aid), and orange cells are rebuilt cities after adjacent aid.

The government wants to know the minimum number of cities it has to rebuild such that after some time all the cities can be rebuild.

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

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 100$$$) — the sizes of Gridlandia.

Output format:
For each test case, output a single integer — the minimum number of cities the government needs to rebuild.

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

Note:
In the first test case, it's enough for the government to rebuild cities $$$(1, 2)$$$ and $$$(2, 1)$$$.

In the second test case, it's enough for the government to rebuild cities $$$(1, 4)$$$, $$$(2, 2)$$$, $$$(3, 1)$$$, $$$(3, 6)$$$, $$$(4, 3)$$$, $$$(5, 5)$$$, $$$(5, 7)$$$.

Example input:
3
2 2
5 7
3 2

Example output:
2
7
3

Editorial:
Begginer's Zelda
Contest: Codeforces Round 915 (Div. 2)
Difficulty rating: 1100
Tags: greedy, trees

You are given a tree$$$^{\dagger}$$$. In one zelda-operation you can do follows:

- Choose two vertices of the tree $$$u$$$ and $$$v$$$;
- Compress all the vertices on the path from $$$u$$$ to $$$v$$$ into one vertex. In other words, all the vertices on path from $$$u$$$ to $$$v$$$ will be erased from the tree, a new vertex $$$w$$$ will be created. Then every vertex $$$s$$$ that had an edge to some vertex on the path from $$$u$$$ to $$$v$$$ will have an edge to the vertex $$$w$$$.

Illustration of a zelda-operation performed for vertices $$$1$$$ and $$$5$$$.

Determine the minimum number of zelda-operations required for the tree to have only one vertex.

$$$^{\dagger}$$$A tree is a connected acyclic undirected graph.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of vertices.

$$$i$$$-th of the next $$$n − 1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n, u_i \ne v_i$$$) — the numbers of vertices connected by the $$$i$$$-th edge.

It is guaranteed that the given edges form a tree.

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

Output format:
For each test case, output a single integer — the minimum number of zelda-operations required for the tree to have only one vertex.

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

Note:
In the first test case, it's enough to perform one zelda-operation for vertices $$$2$$$ and $$$4$$$.

In the second test case, we can perform the following zelda-operations:

1. $$$u = 2, v = 1$$$. Let the resulting added vertex be labeled as $$$w = 10$$$;
2. $$$u = 4, v = 9$$$. Let the resulting added vertex be labeled as $$$w = 11$$$;
3. $$$u = 8, v = 10$$$. After this operation, the tree consists of a single vertex.

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

Example output:
1
3
2
2

Editorial: