1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Circle of Monsters
Contest: Educational Codeforces Round 85 (Rated for Div. 2)
Difficulty rating: 1600
Tags: brute force, constructive algorithms, greedy, math

You are playing another computer game, and now you have to slay $$$n$$$ monsters. These monsters are standing in a circle, numbered clockwise from $$$1$$$ to $$$n$$$. Initially, the $$$i$$$-th monster has $$$a_i$$$ health.

You may shoot the monsters to kill them. Each shot requires exactly one bullet and decreases the health of the targeted monster by $$$1$$$ (deals $$$1$$$ damage to it). Furthermore, when the health of some monster $$$i$$$ becomes $$$0$$$ or less than $$$0$$$, it dies and explodes, dealing $$$b_i$$$ damage to the next monster (monster $$$i + 1$$$, if $$$i < n$$$, or monster $$$1$$$, if $$$i = n$$$). If the next monster is already dead, then nothing happens. If the explosion kills the next monster, it explodes too, damaging the monster after it and possibly triggering another explosion, and so on.

You have to calculate the minimum number of bullets you have to fire to kill all $$$n$$$ monsters in the circle.

Input format:
The first line contains one integer $$$T$$$ ($$$1 \le T \le 150000$$$) — the number of test cases.

Then the test cases follow, each test case begins with a line containing one integer $$$n$$$ ($$$2 \le n \le 300000$$$) — the number of monsters. Then $$$n$$$ lines follow, each containing two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^{12}$$$) — the parameters of the $$$i$$$-th monster in the circle.

It is guaranteed that the total number of monsters in all test cases does not exceed $$$300000$$$.

Output format:
For each test case, print one integer — the minimum number of bullets you have to fire to kill all of the monsters.

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

Example input:
1
3
7 15
2 14
5 3

Example output:
6

Editorial:
We cannot utilize the explosion of the last monster we kill. So the naive approach is to iterate on the monster we kill the last, break the circle between this monster and the next one, and then shoot the first monster in the broken circle until it's dead, then the second one, and so on.
Let's calculate the number of bullets we will fire this way. If the circle is broken after the monster $$$i$$$, then the first monster gets $$$a_{i + 1}$$$ bullets, the second one — $$$\max(0, a_{i + 2} - b_{i + 1})$$$, and so on; all monsters except the first one get exactly $$$\max(0, a_i - b_{i - 1})$$$ bullets.
So we should choose an index $$$i$$$ such that $$$a_{i + 1} - \max(0, a_{i + 1} - b_i)$$$ is minimum possible, since this is the number of bullets we have to spend additionally since we cannot utilize the explosion of the $$$i$$$-th monster. After breaking the circle between the monsters $$$i$$$ and $$$i + 1$$$, you may use a formula to calculate the required number of bullets, or just model the shooting.
Minimum Euler Cycle
Contest: Educational Codeforces Round 85 (Rated for Div. 2)
Difficulty rating: 1800
Tags: constructive algorithms, graphs, greedy, implementation

You are given a complete directed graph $$$K_n$$$ with $$$n$$$ vertices: each pair of vertices $$$u \neq v$$$ in $$$K_n$$$ have both directed edges $$$(u, v)$$$ and $$$(v, u)$$$; there are no self-loops.

You should find such a cycle in $$$K_n$$$ that visits every directed edge exactly once (allowing for revisiting vertices).

We can write such cycle as a list of $$$n(n - 1) + 1$$$ vertices $$$v_1, v_2, v_3, \dots, v_{n(n - 1) - 1}, v_{n(n - 1)}, v_{n(n - 1) + 1} = v_1$$$ — a visiting order, where each $$$(v_i, v_{i + 1})$$$ occurs exactly once.

Find the lexicographically smallest such cycle. It's not hard to prove that the cycle always exists.

Since the answer can be too large print its $$$[l, r]$$$ segment, in other words, $$$v_l, v_{l + 1}, \dots, v_r$$$.

Input format:
The first line contains the single integer $$$T$$$ ($$$1 \le T \le 100$$$) — the number of test cases.

Next $$$T$$$ lines contain test cases — one per line. The first and only line of each test case contains three integers $$$n$$$, $$$l$$$ and $$$r$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le l \le r \le n(n - 1) + 1$$$, $$$r - l + 1 \le 10^5$$$) — the number of vertices in $$$K_n$$$, and segment of the cycle to print.

It's guaranteed that the total sum of $$$n$$$ doesn't exceed $$$10^5$$$ and the total sum of $$$r - l + 1$$$ doesn't exceed $$$10^5$$$.

Output format:
For each test case print the segment $$$v_l, v_{l + 1}, \dots, v_r$$$ of the lexicographically smallest cycle that visits every edge exactly once.

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

Note:
In the second test case, the lexicographically minimum cycle looks like: $$$1, 2, 1, 3, 2, 3, 1$$$.

In the third test case, it's quite obvious that the cycle should start and end in vertex $$$1$$$.

Example input:
3
2 1 3
3 3 6
99995 9998900031 9998900031

Example output:
1 2 1 
1 3 2 3 
1

Editorial:
The solution of the problem can be found clearly in constructive way. An example for $$$n=5$$$: (1 2 1 3 1 4 1 5 (2 3 2 4 2 5 (3 4 3 5 (4 5 ()))) 1) where brackets mean that we call here some recursive function $$$calc$$$.
Since on each level of recursion we have only $$$O(n)$$$ elements and there $$$O(n)$$$ levels then the generation of the certificate is quite easy: if on the currect level of recursion we can skip the whole part — let's just skip it. Otherwise let's build this part. Anyway, the built part of the cycle will have only $$$O(n + (r - l))$$$ length so the whole algorithm has $$$O(n + (r - l))$$$ complexity.
The answer is lexicographically minimum by the construction, since on each level of recursion there is no way to build lexicographically smaller sequence.
Berstagram
Contest: 2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 1400
Tags: implementation

Polycarp recently signed up to a new social network Berstagram. He immediately published $$$n$$$ posts there. He assigned numbers from $$$1$$$ to $$$n$$$ to all posts and published them one by one. So, just after publishing Polycarp's news feed contained posts from $$$1$$$ to $$$n$$$ — the highest post had number $$$1$$$, the next one had number $$$2$$$, ..., the lowest post had number $$$n$$$.

After that he wrote down all likes from his friends. Likes were coming consecutively from the $$$1$$$-st one till the $$$m$$$-th one. You are given a sequence $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_j \le n$$$), where $$$a_j$$$ is the post that received the $$$j$$$-th like.

News feed in Berstagram works in the following manner. Let's assume the $$$j$$$-th like was given to post $$$a_j$$$. If this post is not the highest (first) one then it changes its position with the one above. If $$$a_j$$$ is the highest post nothing changes.

For example, if $$$n=3$$$, $$$m=5$$$ and $$$a=[3,2,1,3,3]$$$, then Polycarp's news feed had the following states:

- before the first like: $$$[1, 2, 3]$$$;
- after the first like: $$$[1, 3, 2]$$$;
- after the second like: $$$[1, 2, 3]$$$;
- after the third like: $$$[1, 2, 3]$$$;
- after the fourth like: $$$[1, 3, 2]$$$;
- after the fifth like: $$$[3, 1, 2]$$$.

Polycarp wants to know the highest (minimum) and the lowest (maximum) positions for each post. Polycarp considers all moments of time, including the moment "before all likes".

Input format:
The first line contains two integer numbers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 4 \cdot10^5$$$) — number of posts and number of likes.

The second line contains integers $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_j \le n$$$), where $$$a_j$$$ is the post that received the $$$j$$$-th like.

Output format:
Print $$$n$$$ pairs of integer numbers. The $$$i$$$-th line should contain the highest (minimum) and the lowest (maximum) positions of the $$$i$$$-th post. You should take into account positions at all moments of time: before all likes, after each like and after all likes. Positions are numbered from $$$1$$$ (highest) to $$$n$$$ (lowest).

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

Example input:
3 5
3 2 1 3 3

Example output:
1 2
2 3
1 3

Example input:
10 6
7 3 5 7 3 6

Example output:
1 2
2 3
1 3
4 7
4 5
6 7
5 7
8 8
9 9
10 10

Editorial:
The Feast and the Bus
Contest: 2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 1800
Tags: brute force, constructive algorithms, greedy, math

Employees of JebTrains are on their way to celebrate the 256-th day of the year! There are $$$n$$$ employees and $$$k$$$ teams in JebTrains. Each employee is a member of some (exactly one) team. All teams are numbered from $$$1$$$ to $$$k$$$. You are given an array of numbers $$$t_1, t_2, \dots, t_n$$$ where $$$t_i$$$ is the $$$i$$$-th employee's team number.

JebTrains is going to rent a single bus to get employees to the feast. The bus will take one or more rides. A bus can pick up an entire team or two entire teams. If three or more teams take a ride together they may start a new project which is considered unacceptable. It's prohibited to split a team, so all members of a team should take the same ride.

It is possible to rent a bus of any capacity $$$s$$$. Such a bus can take up to $$$s$$$ people on a single ride. The total cost of the rent is equal to $$$s \cdot r$$$ burles where $$$r$$$ is the number of rides. Note that it's impossible to rent two or more buses.

Help JebTrains to calculate the minimum cost of the rent, required to get all employees to the feast, fulfilling all the conditions above.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 5\cdot10^5, 1 \le k \le 8000$$$) — the number of employees and the number of teams in JebTrains. The second line contains a sequence of integers $$$t_1, t_2, \dots, t_n$$$, where $$$t_i$$$ ($$$1 \le t_i \le k$$$) is the $$$i$$$-th employee's team number. Every team contains at least one employee.

Output format:
Print the minimum cost of the rent.

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

Example input:
6 3
3 1 2 3 2 3

Example output:
6

Example input:
10 1
1 1 1 1 1 1 1 1 1 1

Example output:
10

Editorial:
Conference Problem
Contest: 2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 3000
Tags: dp

A large-scale conference on unnatural sciences is going to be held soon in Berland! In total, $$$n$$$ scientists from all around the world have applied. All of them have indicated a time segment when they will attend the conference: two integers $$$l_i$$$, $$$r_i$$$ — day of arrival and day of departure.

Also, some of the scientists have indicated their country, while some preferred not to. So, each scientist also has a value $$$c_i$$$, where:

- $$$c_i > 0$$$, if the scientist is coming from country $$$c_i$$$ (all countries are numbered from $$$1$$$ to $$$200$$$);
- $$$c_i = 0$$$, if the scientist preferred to not indicate the country.

Everyone knows that it is interesting and useful to chat with representatives of other countries! A participant of the conference will be upset if she will not meet people from other countries during the stay. It is possible to meet people during all time of stay, including the day of arrival and the day of departure.

Conference organizers need to be ready for the worst! They are interested in the largest number $$$x$$$, that it is possible that among all people attending the conference exactly $$$x$$$ will be upset.

Help the organizers to find the maximum number of upset scientists.

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

The first line of each test case contains integer $$$n$$$ ($$$1 \le n \le 500$$$) — the number of registered conference participants.

Next $$$n$$$ lines follow, each containing three integers $$$l_i$$$, $$$r_i$$$, $$$c_i$$$ ($$$1 \le l_i \le r_i \le 10^6$$$, $$$0 \le c_i \le 200$$$) — the day of arrival, the day of departure and the country (or the fact that it was not indicated) for the $$$i$$$-th participant.

The sum of $$$n$$$ among all test cases in the input does not exceed $$$500$$$.

Output format:
Output $$$t$$$ integers — maximum number of upset scientists for each test case.

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

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

Example output:
4
2

Editorial:
Data Center
Contest: 2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 800
Tags: brute force, implementation

You are developing a project to build a new data center. The data center will be a rectangle with an area of exactly $$$n$$$ square meters. Each side of the data center must be an integer.

Your goal is to minimize the impact of the external environment on the data center. For this reason, you want to minimize the length of the perimeter of the data center (that is, the sum of the lengths of its four sides).

What is the minimum perimeter of a rectangular data center with an area of exactly $$$n$$$ square meters, if the lengths of all its sides must be integers?

Input format:
The first and only line of the input contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), where $$$n$$$ is the area of the data center in square meters.

Output format:
Print the required minimum perimeter in meters.

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

Note:
In the first example, the required shape of the data center is $$$6\times6$$$ square. Its area is $$$36$$$ and the perimeter is $$$6+6+6+6=24$$$.

In the second example, the required shape of the data center is $$$1\times13$$$ rectangle. Its area is $$$13$$$ and the perimeter is $$$1+13+1+13=28$$$.

In the third example, the required shape of the data center is $$$1\times1$$$ square. Its area is $$$1$$$ and the perimeter is $$$1+1+1+1=4$$$.

Example input:
36

Example output:
24

Example input:
13

Example output:
28

Editorial:
Happy Birthday
Contest: 2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 1500
Tags: math

You have a set of birthday cake candles. Each of such candles represents a digit between $$$0$$$ and $$$9$$$, inclusive.

Example of birthday cake candles.

Let's denote the candle representing the digit $$$d$$$ as $$$d$$$-candle.

Your set contains $$$c_0$$$ instances of $$$0$$$-candles, $$$c_1$$$ instances of $$$1$$$-candles and so on. So, the total number of candles is $$$c_0+c_1+\dots+c_9$$$.

These digits are needed to wish your cat a happy birthday. For each birthday, starting with the first, you want to compose the age of the cat using the digits from the set.

Since you light candles for a very short time, candles don't have time to burn out. For this reason you can reuse candles an arbitrary number of times (therefore your set of candles never changes).

For example, if you have one instance of each digit (i.e. $$$c_0=c_1=\dots=c_9=1$$$), you can compose any number from $$$1$$$ to $$$10$$$ using this set, but you cannot compose $$$11$$$.

You have to determine the first birthday, on which you cannot compose the age of the cat using the candles from your set. In other words, find the minimum number $$$y$$$ such that all numbers from $$$1$$$ to $$$y-1$$$ can be composed by digits from your set, but $$$y$$$ cannot be composed.

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

The only line of each test case contains ten integer numbers $$$c_0, c_1, \dots, c_9$$$ ($$$0 \le c_i \le 10^5$$$) — the number of $$$0$$$-candles, $$$1$$$-candles, $$$2$$$-candles and so on.

It is guaranteed that the sum of all $$$c_i$$$ in the input does not exceed $$$10^6$$$.

Output format:
For each test case, output one integer in single line — the minimum age which cannot be composed by candles from your set. Please note that the age can be quite large (it may exceed the standard 64-bit integer types in your programming language).

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

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

Example output:
11
1
7
10

Editorial:
The Parade
Contest: 2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 1800
Tags: binary search, greedy

The Berland Army is preparing for a large military parade. It is already decided that the soldiers participating in it will be divided into $$$k$$$ rows, and all rows will contain the same number of soldiers.

Of course, not every arrangement of soldiers into $$$k$$$ rows is suitable. Heights of all soldiers in the same row should not differ by more than $$$1$$$. The height of each soldier is an integer between $$$1$$$ and $$$n$$$.

For each possible height, you know the number of soldiers having this height. To conduct a parade, you have to choose the soldiers participating in it, and then arrange all of the chosen soldiers into $$$k$$$ rows so that both of the following conditions are met:

- each row has the same number of soldiers,
- no row contains a pair of soldiers such that their heights differ by $$$2$$$ or more.

Calculate the maximum number of soldiers who can participate in the parade.

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

Each test case begins with a line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 30000$$$, $$$1 \le k \le 10^{12}$$$) — the number of different heights of soldiers and the number of rows of soldiers in the parade, respectively.

The second (and final) line of each test case contains $$$n$$$ integers $$$c_1$$$, $$$c_2$$$, ..., $$$c_n$$$ ($$$0 \le c_i \le 10^{12}$$$), where $$$c_i$$$ is the number of soldiers having height $$$i$$$ in the Berland Army.

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

Output format:
For each test case, print one integer — the maximum number of soldiers that can participate in the parade.

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

Note:
Explanations for the example test cases:

1. the heights of soldiers in the rows can be: $$$[3, 3, 3, 3]$$$, $$$[1, 2, 1, 1]$$$, $$$[1, 1, 1, 1]$$$, $$$[3, 3, 3, 3]$$$ (each list represents a row);
2. all soldiers can march in the same row;
3. $$$33$$$ soldiers with height $$$1$$$ in each of $$$3$$$ rows;
4. all soldiers can march in the same row;
5. all soldiers with height $$$2$$$ and $$$3$$$ can march in the same row.

Example input:
5
3 4
7 1 13
1 1
100
1 3
100
2 1
1000000000000 1000000000000
4 1
10 2 11 1

Example output:
16
100
99
2000000000000
13

Editorial:
Arrays
Contest: Codeforces Round 317 [AimFund Thanks-Round] (Div. 2)
Difficulty rating: 900
Tags: sortings

You are given two arrays A and B consisting of integers, sorted in non-decreasing order. Check whether it is possible to choose k numbers in array A and choose m numbers in array B so that any number chosen in the first array is strictly less than any number chosen in the second array.

Input format:
The first line contains two integers nA, nB (1 ≤ nA, nB ≤ 105), separated by a space — the sizes of arrays A and B, correspondingly.

The second line contains two integers k and m (1 ≤ k ≤ nA, 1 ≤ m ≤ nB), separated by a space.

The third line contains nA numbers a1, a2, ... anA ( - 109 ≤ a1 ≤ a2 ≤ ... ≤ anA ≤ 109), separated by spaces — elements of array A.

The fourth line contains nB integers b1, b2, ... bnB ( - 109 ≤ b1 ≤ b2 ≤ ... ≤ bnB ≤ 109), separated by spaces — elements of array B.

Output format:
Print "YES" (without the quotes), if you can choose k numbers in array A and m numbers in array B so that any number chosen in array A was strictly less than any number chosen in array B. Otherwise, print "NO" (without the quotes).

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

Note:
In the first sample test you can, for example, choose numbers 1 and 2 from array A and number 3 from array B (1 < 3 and 2 < 3).

In the second sample test the only way to choose k elements in the first array and m elements in the second one is to choose all numbers in both arrays, but then not all the numbers chosen in A will be less than all the numbers chosen in B: $$3 \neq 3$$.

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

Example output:
YES

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

Example output:
NO

Editorial:
In this problem one need to check whether it's possible to choose k element from array A and m elements from array B so that each of chosen element in A is less than each of chosen elements in B. If it's possible then it's possible to choose k smallest element in A and m largest element in B. That means that in particular, k-th smallest element of A is less than m-th largest element in B. So, if A[k] < B[n - m + 1] then the answer is "YES" and if not, then the answer is "NO"
Order Book
Contest: Codeforces Round 317 [AimFund Thanks-Round] (Div. 2)
Difficulty rating: 1300
Tags: data structures, greedy, implementation, sortings

In this task you need to process a set of stock exchange orders and use them to create order book.

An order is an instruction of some participant to buy or sell stocks on stock exchange. The order number i has price pi, direction di — buy or sell, and integer qi. This means that the participant is ready to buy or sell qi stocks at price pi for one stock. A value qi is also known as a volume of an order.

All orders with the same price p and direction d are merged into one aggregated order with price p and direction d. The volume of such order is a sum of volumes of the initial orders.

An order book is a list of aggregated orders, the first part of which contains sell orders sorted by price in descending order, the second contains buy orders also sorted by price in descending order.

An order book of depth s contains s best aggregated orders for each direction. A buy order is better if it has higher price and a sell order is better if it has lower price. If there are less than s aggregated orders for some direction then all of them will be in the final order book.

You are given n stock exhange orders. Your task is to print order book of depth s for these orders.

Input format:
The input starts with two positive integers n and s (1 ≤ n ≤ 1000, 1 ≤ s ≤ 50), the number of orders and the book depth.

Next n lines contains a letter di (either 'B' or 'S'), an integer pi (0 ≤ pi ≤ 105) and an integer qi (1 ≤ qi ≤ 104) — direction, price and volume respectively. The letter 'B' means buy, 'S' means sell. The price of any sell order is higher than the price of any buy order.

Output format:
Print no more than 2s lines with aggregated orders from order book of depth s. The output format for orders should be the same as in input.

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

Note:
Denote (x, y) an order with price x and volume y. There are 3 aggregated buy orders (10, 3), (20, 4), (25, 10) and two sell orders (50, 8), (40, 1) in the sample.

You need to print no more than two best orders for each direction, so you shouldn't print the order (10 3) having the worst price among buy orders.

Example input:
6 2
B 10 3
S 50 2
S 40 1
S 50 6
B 20 4
B 25 10

Example output:
S 50 8
S 40 1
B 25 10
B 20 4

Editorial:
First of all the problem may be solved for buy orders and sell orders separately.
The easiest soultion is to use structure like std::map or java.lang.TreeMap. To aggregate orders we just add volume to the corresponding map element: 'aggregated[price] += volume'.
After that we should extract lowest (or largest) element from map s times (or while it's not empty).
Complexity: O(nlogn).
It is also possible to solve the problem without data structres other than an array. You should just maintain at most s best orders in sorted order and when adding another order you insert it in appropriate place and move worse elements in linear time of s.
Complexity O(sn).