1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Browser
Contest: Educational Codeforces Round 36 (Rated for Div. 2)
Difficulty rating: 1300
Tags: implementation

Luba is surfing the Internet. She currently has n opened tabs in her browser, indexed from 1 to n from left to right. The mouse cursor is currently located at the pos-th tab. Luba needs to use the tabs with indices from l to r (inclusive) for her studies, and she wants to close all the tabs that don't belong to this segment as fast as possible.

Each second Luba can either try moving the cursor to the left or to the right (if the cursor is currently at the tab i, then she can move it to the tab max(i - 1, a) or to the tab min(i + 1, b)) or try closing all the tabs to the left or to the right of the cursor (if the cursor is currently at the tab i, she can close all the tabs with indices from segment [a, i - 1] or from segment [i + 1, b]). In the aforementioned expressions a and b denote the minimum and maximum index of an unclosed tab, respectively. For example, if there were 7 tabs initially and tabs 1, 2 and 7 are closed, then a = 3, b = 6.

What is the minimum number of seconds Luba has to spend in order to leave only the tabs with initial indices from l to r inclusive opened?

Input format:
The only line of input contains four integer numbers n, pos, l, r (1 ≤ n ≤ 100, 1 ≤ pos ≤ n, 1 ≤ l ≤ r ≤ n) — the number of the tabs, the cursor position and the segment which Luba needs to leave opened.

Output format:
Print one integer equal to the minimum number of seconds required to close all the tabs outside the segment [l, r].

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

Note:
In the first test Luba can do the following operations: shift the mouse cursor to the tab 2, close all the tabs to the left of it, shift the mouse cursor to the tab 3, then to the tab 4, and then close all the tabs to the right of it.

In the second test she only needs to close all the tabs to the right of the current position of the cursor.

In the third test Luba doesn't need to do anything.

Example input:
6 3 2 4

Example output:
5

Example input:
6 3 1 3

Example output:
1

Editorial:
If l = 1 and r = n then the answer is 0. If l = 1 and r ≠ n or l ≠ 1 and r = n then answer is |pos - l| + 1 or |pos - r| + 1 respectively. And in the other case (when l ≠ 1 and r ≠ n) the answer is r - l + min(|pos - l|, |pos - r|) + 2.
Permute Digits
Contest: Educational Codeforces Round 36 (Rated for Div. 2)
Difficulty rating: 1700
Tags: dp, greedy

You are given two positive integer numbers a and b. Permute (change order) of the digits of a to construct maximal number not exceeding b. No number in input and/or output can start with the digit 0.

It is allowed to leave a as it is.

Input format:
The first line contains integer a (1 ≤ a ≤ 1018). The second line contains integer b (1 ≤ b ≤ 1018). Numbers don't have leading zeroes. It is guaranteed that answer exists.

Output format:
Print the maximum possible number that is a permutation of digits of a and is not greater than b. The answer can't have any leading zeroes. It is guaranteed that the answer exists.

The number in the output should have exactly the same length as number a. It should be a permutation of digits of a.

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

Example input:
123
222

Example output:
213

Example input:
3921
10000

Example output:
9321

Editorial:
Let's construct the answer digit by digit starting from the leftmost. Obviously, we are asked to build lexicographically maximal answer so in this order we should choose the greatest digit on each step.
Precalc cnti — number of digits i in number a. Iterate over all possible digits starting from the greatest. For each digit check if it's possible to put it in this position. For this you construct minimal suffix (greedily put the lowest digit) and compare the resulting number with number b. If it became less or equal then proceed to the next digit.
Overall complexity: O(|a|2·|AL|), where AL is digits from 0 to 9.
Almost Acyclic Graph
Contest: Educational Codeforces Round 36 (Rated for Div. 2)
Difficulty rating: 2200
Tags: dfs and similar, graphs

You are given a directed graph consisting of n vertices and m edges (each edge is directed, so it can be traversed in only one direction). You are allowed to remove at most one edge from it.

Can you make this graph acyclic by removing at most one edge from it? A directed graph is called acyclic iff it doesn't contain any cycle (a non-empty path that starts and ends in the same vertex).

Input format:
The first line contains two integers n and m (2 ≤ n ≤ 500, 1 ≤ m ≤ min(n(n - 1), 100000)) — the number of vertices and the number of edges, respectively.

Then m lines follow. Each line contains two integers u and v denoting a directed edge going from vertex u to vertex v (1 ≤ u, v ≤ n, u ≠ v). Each ordered pair (u, v) is listed at most once (there is at most one directed edge from u to v).

Output format:
If it is possible to make this graph acyclic by removing at most one edge, print YES. Otherwise, print NO.

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

Note:
In the first example you can remove edge $$2\rightarrow3$$, and the graph becomes acyclic.

In the second example you have to remove at least two edges (for example, $$2 \rightarrow 1$$ and $$2\rightarrow3$$) in order to make the graph acyclic.

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

Example output:
YES

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

Example output:
NO

Editorial:
The constraits are set in such a way that naive O(m·(n + m)) solution won't pass (unmark every edge one by one and check if graph of marked edges doesn't contain cycles with dfs/bfs).
Thus we should somehow limit the number of edges to check. Let's take arbitrary cycle in graph. Do dfs, store the vertex you used to travel to any other vertex and restore edges with this data if cycle is met. With this algo length of cycle will not exceed n. Then do the naive algo but check only edges from this cycle.
Overall complexity: O(n·(n + m)).
Physical Education Lessons
Contest: Educational Codeforces Round 36 (Rated for Div. 2)
Difficulty rating: 2300
Tags: data structures, implementation, sortings

This year Alex has finished school, and now he is a first-year student of Berland State University. For him it was a total surprise that even though he studies programming, he still has to attend physical education lessons. The end of the term is very soon, but, unfortunately, Alex still hasn't attended a single lesson!

Since Alex doesn't want to get expelled, he wants to know the number of working days left until the end of the term, so he can attend physical education lessons during these days. But in BSU calculating the number of working days is a complicated matter:

There are n days left before the end of the term (numbered from 1 to n), and initially all of them are working days. Then the university staff sequentially publishes q orders, one after another. Each order is characterised by three numbers l, r and k:

- If k = 1, then all days from l to r (inclusive) become non-working days. If some of these days are made working days by some previous order, then these days still become non-working days;
- If k = 2, then all days from l to r (inclusive) become working days. If some of these days are made non-working days by some previous order, then these days still become working days.

Help Alex to determine the number of working days left after each order!

Input format:
The first line contains one integer n, and the second line — one integer q (1 ≤ n ≤ 109, 1 ≤ q ≤ 3·105) — the number of days left before the end of the term, and the number of orders, respectively.

Then q lines follow, i-th line containing three integers li, ri and ki representing i-th order (1 ≤ li ≤ ri ≤ n, 1 ≤ ki ≤ 2).

Output format:
Print q integers. i-th of them must be equal to the number of working days left until the end of the term after the first i orders are published.

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

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

Example output:
2
0
2
3
1
4

Editorial:
Let's store current intervals with non-working days in set sorted by the right border. When new query comes you search for the first interval to have its right border greater or equal than the currect left border and update all intervals to intersect the query (either fully delete or insert back its part which doesn't intersect query). Finally, if k = 1 then insert the query into current set. Updates on the number of working days can be done while deleting segments on the fly.
Overall complexity: $${\mathcal O}(q\log q)$$.
Imbalance Value of a Tree
Contest: Educational Codeforces Round 36 (Rated for Div. 2)
Difficulty rating: 2400
Tags: data structures, dsu, graphs, trees

You are given a tree T consisting of n vertices. A number is written on each vertex; the number written on vertex i is ai. Let's denote the function I(x, y) as the difference between maximum and minimum value of ai on a simple path connecting vertices x and y.

Your task is to calculate $$\sum_{i=1}^{n}\sum_{j=i}^{n}I(i,j)$$.

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

The second line contains n integer numbers a1, a2, ..., an (1 ≤ ai ≤ 106) — the numbers written on the vertices.

Then n - 1 lines follow. Each line contains two integers x and y denoting an edge connecting vertex x and vertex y (1 ≤ x, y ≤ n, x ≠ y). It is guaranteed that these edges denote a tree.

Output format:
Print one number equal to $$\sum_{i=1}^{n}\sum_{j=i}^{n}I(i,j)$$.

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

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

Example output:
6

Editorial:
Let's calculate the answer as the difference between sum of maxima and sum of minima over all paths. These sums can be found by the following approach:
Consider the sum of maxima. Let's sort all vertices in ascending order of values of ai (if two vertices have equal values, their order doesn't matter). This order has an important property that we can use: for every path, the maximum on this path is written on the vertex that has the greatest position in sorted order. This allows us to do the following:
Let's denote as t(i) a tree, rooted at vertex i, that is formed by the set of such vertices j that are directly connected to i or some other vertex from the set, and have aj < ai. Consider the vertices that are connected to i in this tree. Let's denote them as v1, v2, ..., vk (the order doesn't matter), and denote by sj the size of the subtree of vj in the tree t(i). Let's try to calculate the number of paths going through i in this tree:
1. $$\sum_{j=1}^{k}s_{j}+1$$ paths that have i as its endpoint;
2. $$\sum_{j=2}^{k}\sum_{x=1}^{j-1}s_j \cdot s_x$$ paths (connecting a vertex from subtree of vx to a vertex from subtree of vj).
So vertex i adds the sum of these values, multiplied by ai, to the sum of maxima. To calculate these sums, we will use the following algorithm:
Initialize a DSU (disjoint set union), making a set for each vertex. Process the vertices in sorted order. When we process some vertex i, find all its already processed neighbours (they will be v1, v2, ..., vk in t(i)). For every neighbour vj, denote the size of its set in DSU as sj. Then calculate the number of paths going through i using aforementioned formulas (to do it in linear time, use partial sums). Add this number, multiplied by ai, to the sum of maxima, and merge i with v1, v2, ..., vk in DSU.
To calculate the sum of minima, you can do the same while processing vertices in reversed order.
Time complexity of this solution is $$O(n \log n)$$.
Music
Contest: Codeforces Round 315 (Div. 2)
Difficulty rating: 1500
Tags: implementation, math

Little Lesha loves listening to music via his smartphone. But the smartphone doesn't have much memory, so Lesha listens to his favorite songs in a well-known social network InTalk.

Unfortunately, internet is not that fast in the city of Ekaterinozavodsk and the song takes a lot of time to download. But Lesha is quite impatient. The song's duration is T seconds. Lesha downloads the first S seconds of the song and plays it. When the playback reaches the point that has not yet been downloaded, Lesha immediately plays the song from the start (the loaded part of the song stays in his phone, and the download is continued from the same place), and it happens until the song is downloaded completely and Lesha listens to it to the end. For q seconds of real time the Internet allows you to download q - 1 seconds of the track.

Tell Lesha, for how many times he will start the song, including the very first start.

Input format:
The single line contains three integers T, S, q (2 ≤ q ≤ 104, 1 ≤ S < T ≤ 105).

Output format:
Print a single integer — the number of times the song will be restarted.

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

Note:
In the first test, the song is played twice faster than it is downloaded, which means that during four first seconds Lesha reaches the moment that has not been downloaded, and starts the song again. After another two seconds, the song is downloaded completely, and thus, Lesha starts the song twice.

In the second test, the song is almost downloaded, and Lesha will start it only once.

In the third sample test the download finishes and Lesha finishes listening at the same moment. Note that song isn't restarted in this case.

Example input:
5 2 2

Example output:
2

Example input:
5 4 7

Example output:
1

Editorial:
Пусть перед очередным запуском прогружено S секунд песни, найдем, сколько будет прогружено перед следующим запуском. $$\frac{x}{q} = \frac{x-S}{q-1}$$. Отсюда x = qS.
Тогда решение: будем умножать S на q пока S < T. Количество таких умножений — это ответ.
Сложность — $${\mathcal O}\left(\log T\right)$$
Inventory
Contest: Codeforces Round 315 (Div. 2)
Difficulty rating: 1200
Tags: greedy, math

Companies always have a lot of equipment, furniture and other things. All of them should be tracked. To do this, there is an inventory number assigned with each item. It is much easier to create a database by using those numbers and keep the track of everything.

During an audit, you were surprised to find out that the items are not numbered sequentially, and some items even share the same inventory number! There is an urgent need to fix it. You have chosen to make the numbers of the items sequential, starting with 1. Changing a number is quite a time-consuming process, and you would like to make maximum use of the current numbering.

You have been given information on current inventory numbers for n items in the company. Renumber items so that their inventory numbers form a permutation of numbers from 1 to n by changing the number of as few items as possible. Let us remind you that a set of n numbers forms a permutation if all the numbers are in the range from 1 to n, and no two numbers are equal.

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

The second line contains n numbers a1, a2, ..., an (1 ≤ ai ≤ 105) — the initial inventory numbers of the items.

Output format:
Print n numbers — the final inventory numbers of the items in the order they occur in the input. If there are multiple possible answers, you may print any of them.

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

Note:
In the first test the numeration is already a permutation, so there is no need to change anything.

In the second test there are two pairs of equal numbers, in each pair you need to replace one number.

In the third test you need to replace 2 by 1, as the numbering should start from one.

Example input:
3
1 3 2

Example output:
1 3 2

Example input:
4
2 2 3 3

Example output:
2 1 3 4

Editorial:
Подойдём к задаче с другой стороны: а сколько максимально можно оставить номеров, чтобы получилась перестановка? Очевидно, что эти номера должны быть от 1 до n, причем среди них не должно быть повторяющихся. И понятно, что это условие необходимое и достаточное.
Такую задачу можно решать жадным алгоритмом. Если мы встретили число, которого ещё не было, при этом оно от 1 до n, то мы его оставим. Для реализации можно завести массив used, в котором отмечать уже использованные числа.
Затем нужно ещё раз пройти по массиву и распределить неиспользованные числа.
Сложность — O(n).
The Fair Nut and the Best Path
Contest: Codeforces Round 526 (Div. 1)
Difficulty rating: 1800
Tags: data structures, dp, trees

The Fair Nut is going to travel to the Tree Country, in which there are $$$n$$$ cities. Most of the land of this country is covered by forest. Furthermore, the local road system forms a tree (connected graph without cycles). Nut wants to rent a car in the city $$$u$$$ and go by a simple path to city $$$v$$$. He hasn't determined the path, so it's time to do it. Note that chosen path can consist of only one vertex.

A filling station is located in every city. Because of strange law, Nut can buy only $$$w_i$$$ liters of gasoline in the $$$i$$$-th city. We can assume, that he has infinite money. Each road has a length, and as soon as Nut drives through this road, the amount of gasoline decreases by length. Of course, Nut can't choose a path, which consists of roads, where he runs out of gasoline. He can buy gasoline in every visited city, even in the first and the last.

He also wants to find the maximum amount of gasoline that he can have at the end of the path. Help him: count it.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — the number of cities.

The second line contains $$$n$$$ integers $$$w_1, w_2, \ldots, w_n$$$ ($$$0 \leq w_{i} \leq 10^9$$$) — the maximum amounts of liters of gasoline that Nut can buy in cities.

Each of the next $$$n - 1$$$ lines describes road and contains three integers $$$u$$$, $$$v$$$, $$$c$$$ ($$$1 \leq u, v \leq n$$$, $$$1 \leq c \leq 10^9$$$, $$$u \ne v$$$), where $$$u$$$ and $$$v$$$ — cities that are connected by this road and $$$c$$$ — its length.

It is guaranteed that graph of road connectivity is a tree.

Output format:
Print one number — the maximum amount of gasoline that he can have at the end of the path.

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

Note:
The optimal way in the first example is $$$2 \to 1 \to 3$$$.

The optimal way in the second example is $$$2 \to 4$$$.

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

Example output:
3

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

Example output:
7

Editorial:
Let's write on edge with length $$$l$$$ number $$$-l$$$. Let sum on the path be sum of amounts of gasoline, which can be bought in cities on this path plus sum of the numbers, which were written on its edges.
If we don't run out of gasoline on some path, sum on it will be equal to amount of gasoline at the end of way. If we run out of gasoline on a path, we can start from the next city after the road, where it happened, and sum on the path won't decrease. So, there is a path with maximal sum, where we don't run out of gasoline. This sum is answer to the problem.
How to find it? Let $$$dp_{i}$$$ is maximal sum on vertical way, which starts in vertex $$$i$$$. It is not difficult to calculate $$$dp_{i}$$$, using $$$dp$$$ values for children of vertex $$$i$$$. Every way can be divided to two vertical ways, so we can calculate answer by turning over $$$i$$$, which is the highest vertex of a path, and taking the two biggest vertical ways, which starts from vertex $$$i$$$.
The Fair Nut and Rectangles
Contest: Codeforces Round 526 (Div. 1)
Difficulty rating: 2400
Tags: data structures, dp, geometry

The Fair Nut got stacked in planar world. He should solve this task to get out.

You are given $$$n$$$ rectangles with vertexes in $$$(0, 0)$$$, $$$(x_i, 0)$$$, $$$(x_i, y_i)$$$, $$$(0, y_i)$$$. For each rectangle, you are also given a number $$$a_i$$$. Choose some of them that the area of union minus sum of $$$a_i$$$ of the chosen ones is maximum.

It is guaranteed that there are no nested rectangles.

Nut has no idea how to find the answer, so he asked for your help.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — the number of rectangles.

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

It is guaranteed that there are no nested rectangles.

Output format:
In a single line print the answer to the problem — the maximum value which you can achieve.

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

Note:
In the first example, the right answer can be achieved by choosing the first and the second rectangles.

In the second example, the right answer can also be achieved by choosing the first and the second rectangles.

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

Example output:
9

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

Example output:
10

Editorial:
Let's order rectangles by $$$x_i$$$, so $$$x_1, ..., x_n$$$ will be increasing. If the $$$x_1, ..., x_n$$$ is increasing, $$$y_1, ..., y_n$$$ is decreasing, because there are no nested rectangles. Then lets define $$$dp_i$$$ as the maximum value, which can be acheived by choosing some subset of first $$$i$$$ rectangles which contains the $$$i$$$-th rectangle. It can be calculated by $$$dp_i = \max\limits_{1 \leq j < i} dp_j + x_i \cdot y_i - x_j \cdot y_i$$$, where $$$j$$$ is the previous chosen rectangle (we subtract $$$x_j \cdot y_i$$$ because it is common square of the subset for $$$dp_j$$$ and $$$i$$$-th rectangle). This formula can be optimized using convex hull trick and calculated in $$$O(n log n)$$$ or in $$$O(n)$$$ if rectangles are already sorted.