1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Ilya and Roads
Contest: Codeforces Round 186 (Div. 2)
Difficulty rating: 2100
Tags: dp

Everything is great about Ilya's city, except the roads. The thing is, the only ZooVille road is represented as n holes in a row. We will consider the holes numbered from 1 to n, from left to right.

Ilya is really keep on helping his city. So, he wants to fix at least k holes (perharps he can fix more) on a single ZooVille road.

The city has m building companies, the i-th company needs ci money units to fix a road segment containing holes with numbers of at least li and at most ri. The companies in ZooVille are very greedy, so, if they fix a segment containing some already fixed holes, they do not decrease the price for fixing the segment.

Determine the minimum money Ilya will need to fix at least k holes.

Input format:
The first line contains three integers n, m, k (1 ≤ n ≤ 300, 1 ≤ m ≤ 105, 1 ≤ k ≤ n). The next m lines contain the companies' description. The i-th line contains three integers li, ri, ci (1 ≤ li ≤ ri ≤ n, 1 ≤ ci ≤ 109).

Output format:
Print a single integer — the minimum money Ilya needs to fix at least k holes.

If it is impossible to fix at least k holes, print -1.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

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

Example input:
10 4 6
7 9 11
6 9 13
7 7 7
3 5 6

Example output:
17

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

Example output:
2

Editorial:
Ilya and Two Numbers
Contest: Codeforces Round 186 (Div. 2)
Difficulty rating: 2300
Tags: constructive algorithms, data structures, dsu, greedy

Ilya has recently taken up archaeology. He's recently found two numbers, written in the m-based notation. Each of the found numbers consisted of exactly n digits. Ilya immediately started looking for information about those numbers. He learned that the numbers are part of a cyphered code and the one who can decypher it can get the greatest treasure.

After considerable research Ilya understood that to decypher the code, he should do the following:

- Rearrange digits in the first number in some manner. Similarly, rearrange digits in the second number in some manner. As a result of this operation, the numbers can get leading zeroes.
- Add numbers, digit by digit, modulo m. In other words, we need to get the third number of length n, each digit of the number is the sum of the respective numbers of the found numbers. For example, suppose there are two numbers recorded in the ternary notation, 001210 and 012111, then if you add them to each other digit by digit modulo 3, you will get number 010021.
- The key to the code is the maximum possible number that can be obtained in the previous step.

Help Ilya, find the key to the code.

Input format:
The first line contains two integers n, m (1 ≤ n, m ≤ 105, m > 1). The second line contains the first found number, the third line contains the second found number.

The numbers are recorded as a sequence of digits in the m-based notation. Each digit is an integer from 0 to m - 1. The digits in the line are written in the order from the most significant digits to the least significant ones.

The given numbers can contain leading zeroes.

Output format:
Print n m-base digits. The resulting third number written in the m-based notation. Print the digits in the order from the most significant digits to the least significant ones.

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

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

Example output:
6 4 2 1

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

Example output:
4 4 4 3 2

Editorial:
Turing Tape
Contest: Codeforces Beta Round 96 (Div. 1)
Difficulty rating: 1300
Tags: implementation

INTERCAL is the oldest of esoteric programming languages. One of its many weird features is the method of character-based output, known as Turing Tape method. It converts an array of unsigned 8-bit integers into a sequence of characters to print, using the following method.

The integers of the array are processed one by one, starting from the first. Processing i-th element of the array is done in three steps:

1. The 8-bit binary notation of the ASCII-code of the previous printed character is reversed. When the first element of the array is processed, the result of this step is considered to be 0.

2. The i-th element of the array is subtracted from the result of the previous step modulo 256.

3. The binary notation of the result of the previous step is reversed again to produce ASCII-code of the i-th character to be printed.

You are given the text printed using this method. Restore the array used to produce this text.

Input format:
The input will consist of a single line text which contains the message printed using the described method. String text will contain between 1 and 100 characters, inclusive. ASCII-code of each character of text will be between 32 (space) and 126 (tilde), inclusive.

Output format:
Output the initial array, which was used to produce text, one integer per line.

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

Note:
Let's have a closer look at the beginning of the example. The first character is "H" with ASCII-code 72 = 010010002. Its reverse is 000100102 = 18, and this number should become the result of the second step of processing. The result of the first step is considered to be 0, so the first element of the array has to be (0 - 18) mod 256 = 238, where a mod b is the remainder of division of a by b.

Example input:
Hello, World!

Example output:
238
108
112
0
64
194
48
26
244
168
24
16
162

Editorial:
Logo Turtle
Contest: Codeforces Beta Round 96 (Div. 1)
Difficulty rating: 1800
Tags: dp

A lot of people associate Logo programming language with turtle graphics. In this case the turtle moves along the straight line and accepts commands "T" ("turn around") and "F" ("move 1 unit forward").

You are given a list of commands that will be given to the turtle. You have to change exactly n commands from the list (one command can be changed several times). How far from the starting point can the turtle move after it follows all the commands of the modified list?

Input format:
The first line of input contains a string commands — the original list of commands. The string commands contains between 1 and 100 characters, inclusive, and contains only characters "T" and "F".

The second line contains an integer n (1 ≤ n ≤ 50) — the number of commands you have to change in the list.

Output format:
Output the maximum distance from the starting point to the ending point of the turtle's path. The ending point of the turtle's path is turtle's coordinate after it follows all the commands of the modified list.

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

Note:
In the first example the best option is to change the second command ("T") to "F" — this way the turtle will cover a distance of 2 units.

In the second example you have to change two commands. One of the ways to cover maximal distance of 6 units is to change the fourth command and first or last one.

Example input:
FT
1

Example output:
2

Example input:
FFFTFFF
2

Example output:
6

Editorial:
Constants in the language of Shakespeare
Contest: Codeforces Beta Round 96 (Div. 1)
Difficulty rating: 2100
Tags: constructive algorithms, dp, greedy

Shakespeare is a widely known esoteric programming language in which programs look like plays by Shakespeare, and numbers are given by combinations of ornate epithets. In this problem we will have a closer look at the way the numbers are described in Shakespeare.

Each constant in Shakespeare is created from non-negative powers of 2 using arithmetic operations. For simplicity we'll allow only addition and subtraction and will look for a representation of the given number which requires a minimal number of operations.

You are given an integer n. You have to represent it as n = a1 + a2 + ... + am, where each of ai is a non-negative power of 2, possibly multiplied by -1. Find a representation which minimizes the value of m.

Input format:
The only line of input contains a positive integer n, written as its binary notation. The length of the notation is at most 106. The first digit of the notation is guaranteed to be 1.

Output format:
Output the required minimal m. After it output m lines. Each line has to be formatted as "+2^x" or "-2^x", where x is the power coefficient of the corresponding term. The order of the lines doesn't matter.

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

Example input:
1111

Example output:
2
+2^4
-2^0

Example input:
1010011

Example output:
4
+2^0
+2^1
+2^4
+2^6

Editorial:
Bits of merry old England
Contest: Codeforces Beta Round 96 (Div. 1)
Difficulty rating: 2700
Tags: flows, graphs

Another feature of Shakespeare language is that the variables are named after characters of plays by Shakespeare, and all operations on them (value assignment, output etc.) look like a dialog with other characters. New values of variables are defined in a rather lengthy way, so a programmer should try to minimize their usage.

You have to print the given sequence of n integers. To do this, you have m variables and two types of operations on them:

- variable=integer
- print(variable)

Any of the m variables can be used as variable. Variables are denoted by lowercase letters between "a" and "z", inclusive. Any integer number can be used as integer.

Let's say that the penalty for using first type of operations equals to the number of set bits in the number integer. There is no penalty on using second type of operations. Find and output the program which minimizes the penalty for printing the given sequence of numbers.

Input format:
The first line of input contains integers n and m (1 ≤ n ≤ 250, 1 ≤ m ≤ 26). The second line contains the sequence to be printed. Each element of the sequence is an integer between 1 and 109, inclusive. The sequence has to be printed in the given order (from left to right).

Output format:
Output the number of lines in the optimal program and the optimal penalty. Next, output the program itself, one command per line. If there are several programs with minimal penalty, output any of them (you have only to minimize the penalty).

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

Example input:
7 2
1 2 2 4 2 1 2

Example output:
11 4
b=1
print(b)
a=2
print(a)
print(a)
b=4
print(b)
print(a)
b=1
print(b)
print(a)

Example input:
6 3
1 2 3 1 2 3

Example output:
9 4
c=1
print(c)
b=2
print(b)
a=3
print(a)
print(c)
print(b)
print(a)

Editorial:
Kalindrome Array
Contest: Codeforces Global Round 17
Difficulty rating: 1100
Tags: greedy, two pointers

An array $$$[b_1, b_2, \ldots, b_m]$$$ is a palindrome, if $$$b_i = b_{m+1-i}$$$ for each $$$i$$$ from $$$1$$$ to $$$m$$$. Empty array is also a palindrome.

An array is called kalindrome, if the following condition holds:

- It's possible to select some integer $$$x$$$ and delete some of the elements of the array equal to $$$x$$$, so that the remaining array (after gluing together the remaining parts) is a palindrome.

Note that you don't have to delete all elements equal to $$$x$$$, and you don't have to delete at least one element equal to $$$x$$$.

For example :

- $$$[1, 2, 1]$$$ is kalindrome because you can simply not delete a single element.
- $$$[3, 1, 2, 3, 1]$$$ is kalindrome because you can choose $$$x = 3$$$ and delete both elements equal to $$$3$$$, obtaining array $$$[1, 2, 1]$$$, which is a palindrome.
- $$$[1, 2, 3]$$$ is not kalindrome.

You are given an array $$$[a_1, a_2, \ldots, a_n]$$$. Determine if $$$a$$$ is kalindrome or not.

Input format:
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$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — elements of the array.

It's guaranteed that the sum of $$$n$$$ over all test cases won't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print YES if $$$a$$$ is kalindrome and NO otherwise. You can print each letter in any case.

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

Note:
In the first test case, array $$$[1]$$$ is already a palindrome, so it's a kalindrome as well.

In the second test case, we can choose $$$x = 2$$$, delete the second element, and obtain array $$$[1]$$$, which is a palindrome.

In the third test case, it's impossible to obtain a palindrome.

In the fourth test case, you can choose $$$x = 4$$$ and delete the fifth element, obtaining $$$[1, 4, 4, 1]$$$. You also can choose $$$x = 1$$$, delete the first and the fourth elements, and obtain $$$[4, 4, 4]$$$.

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

Example output:
YES
YES
NO
YES

Editorial:
If the array is already a palindrome the answer is Yes. Otherwise, let's find the minimum $$$i$$$ that $$$a_i \neq a_{n + 1 - i}$$$.
We can prove that we have to remove either $$$a_i$$$ or $$$a_{n + 1 - i}$$$ in order the make the array palindrome.
Imagine it's possible to make the array palindrome by removing all appearances of $$$x$$$. $$$x \neq a_i, a_{n + 1 - i}$$$
The number of appearances of $$$x$$$ before $$$i$$$ is equal to the number of appearances of $$$x$$$ after $$$n + 1 - i$$$. So in order to make the array palindrome, $$$a_i$$$ must be equal to $$$a_{n + 1 - i}$$$.
So we just have to check if the array will be palindrome after removing all appearances of $$$a_i$$$ or after removing all appearances of $$$a_{n + 1 - i}$$$.
Time complexity: $$$\mathcal{O}(n)$$$
Keshi Is Throwing a Party
Contest: Codeforces Global Round 17
Difficulty rating: 1600
Tags: binary search, greedy

Keshi is throwing a party and he wants everybody in the party to be happy.

He has $$$n$$$ friends. His $$$i$$$-th friend has $$$i$$$ dollars.

If you invite the $$$i$$$-th friend to the party, he will be happy only if at most $$$a_i$$$ people in the party are strictly richer than him and at most $$$b_i$$$ people are strictly poorer than him.

Keshi wants to invite as many people as possible. Find the maximum number of people he can invite to the party so that every invited person would be happy.

Input format:
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$$$ $$$(1\le n\le 2 \cdot 10^5)$$$ — the number of Keshi's friends.

The $$$i$$$-th of the following $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ $$$(0 \le a_i, b_i < n)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case print the maximum number of people Keshi can invite.

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

Note:
In the first test case, he invites the first and the second person. If he invites all of them, the third person won't be happy because there will be more than $$$1$$$ person poorer than him.

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

Example output:
2
1
2

Editorial:
Take a look at this greedy approach.
Let $$$p_i$$$ be the $$$i$$$-th poorest invited person.($$$p_i < p_{i + 1}$$$)
Find the poorest person $$$v$$$ that $$$x - 1 - a_v \le 0 \le b_v$$$. We will invite this person so $$$p_1 = v$$$.
For each $$$2 \le i \le x$$$ find the poorest person $$$v$$$ that $$$v > p_{i - 1}$$$ and $$$x - 1 - a_v \le i - 1 \le b_v$$$ this means that person $$$v$$$ can be the $$$i$$$-th poorest invited person.
Imagine we fail to find $$$x$$$ people but there is a way to do so. The solution chooses $$$s_1, s_2, \ldots, s_x$$$.
for each $$$i$$$ we chose the minimum $$$p_i$$$ possible, therefor $$$p_i \le s_i$$$. But if our algorithm fails there must exist an index $$$i$$$ that $$$p_i > s_i$$$.
So our algorithm is correct.
Time complexity: $$$\mathcal{O}(n\log n)$$$
Add Plus Minus Sign
Contest: Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 800
Tags: constructive algorithms, math

AquaMoon has a string $$$a$$$ consisting of only $$$0$$$ and $$$1$$$. She wants to add $$$+$$$ and $$$-$$$ between all pairs of consecutive positions to make the absolute value of the resulting expression as small as possible. Can you help her?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2\,000$$$)  – the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 100$$$) — the length of $$$a$$$.

The second line of each test case contains a string $$$a$$$ of length $$$n$$$, consisting of only $$$0$$$ and $$$1$$$.

Output format:
For each test case, output a string of length $$$n - 1$$$ consisting of $$$-$$$ and $$$+$$$ on a separate line. If there is more than one assignment of signs that produces the smallest possible absolute value, any of them is accepted.

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

Note:
In the first test case, we can get the expression $$$1 - 1 = 0$$$, with absolute value $$$0$$$.

In the second test case, we can get the expression $$$0 + 1 - 1 + 0 + 1 = 1$$$, with absolute value $$$1$$$.

In the third test case, we can get the expression $$$1 + 0 + 0 + 0 - 1 = 0$$$, with absolute value $$$0$$$.

Example input:
3
2
11
5
01101
5
10001

Example output:
-
+-++
+++-

Editorial:
The answer is the number of 1s modulo 2.
We can get that by adding $$$-$$$ before the 2nd, 4th, $$$\dots$$$ 1 and $$$+$$$ before the 3rd, 5th, $$$\cdots$$$ 1.
Ice and Fire
Contest: Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 1300
Tags: constructive algorithms, dp, greedy

Little09 and his friends are playing a game. There are $$$n$$$ players, and the temperature value of the player $$$i$$$ is $$$i$$$.

The types of environment are expressed as $$$0$$$ or $$$1$$$. When two players fight in a specific environment, if its type is $$$0$$$, the player with a lower temperature value in this environment always wins; if it is $$$1$$$, the player with a higher temperature value in this environment always wins. The types of the $$$n-1$$$ environments form a binary string $$$s$$$ with a length of $$$n-1$$$.

If there are $$$x$$$ players participating in the game, there will be a total of $$$x-1$$$ battles, and the types of the $$$x-1$$$ environments will be the first $$$x-1$$$ characters of $$$s$$$. While there is more than one player left in the tournament, choose any two remaining players to fight. The player who loses will be eliminated from the tournament. The type of the environment of battle $$$i$$$ is $$$s_i$$$.

For each $$$x$$$ from $$$2$$$ to $$$n$$$, answer the following question: if all players whose temperature value does not exceed $$$x$$$ participate in the game, how many players have a chance to win?

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t \le 10^3$$$)  — 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\leq n\leq 2\cdot 10^5$$$)  — the number of players.

The second line of each test case contains a binary string $$$s$$$ with a length $$$n-1$$$.

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

Output format:
For each test case output $$$n-1$$$ integers  — for each $$$x$$$ from $$$2$$$ to $$$n$$$, output the number of players that have a chance to win.

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

Note:
In the first test case, for $$$x=2$$$ and $$$x=3$$$, only the player whose temperature value is $$$1$$$ can be the winner. For $$$x=4$$$, the player whose temperature value is $$$2,3,4$$$ can be the winner.

Example input:
2
4
001
4
101

Example output:
1 1 3 
1 2 3

Editorial:
We define $$$f_i$$$ to mean that the maximum $$$x$$$ satisfies $$$s_{i-x+1}=s_{i-x+2}=...=s_{i}$$$.
It can be proved that for $$$x$$$ players, $$$f_{x-1}$$$ players are bound to lose and the rest have a chance to win. So the answer to the first $$$i$$$ games is $$$ans_i=i-f_i+1$$$.
Same Count One
Contest: Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 1600
Tags: brute force, constructive algorithms, greedy, implementation, two pointers

ChthollyNotaSeniorious received a special gift from AquaMoon: $$$n$$$ binary arrays of length $$$m$$$. AquaMoon tells him that in one operation, he can choose any two arrays and any position $$$pos$$$ from $$$1$$$ to $$$m$$$, and swap the elements at positions $$$pos$$$ in these arrays.

He is fascinated with this game, and he wants to find the minimum number of operations needed to make the numbers of $$$1$$$s in all arrays the same. He has invited you to participate in this interesting game, so please try to find it!

If it is possible, please output specific exchange steps in the format described in the output section. Otherwise, please output $$$-1$$$.

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 2\cdot 10^4$$$)  — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$2 \leq m \leq 10^5$$$).

The $$$i$$$-th of the following $$$n$$$ lines contains $$$m$$$ integers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ $$$(0 \le a_{i, j} \le 1)$$$  — the elements of the $$$i$$$-th array.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, if the objective is not achievable, output $$$-1$$$.

Otherwise, in the first line output $$$k$$$ $$$(0 \le k \le mn)$$$  — the minimum number of operations required.

The $$$i$$$-th of the following $$$k$$$ lines should contain $$$3$$$ integers, $$$x_i, y_i, z_i$$$ $$$(1 \le x_i, y_i \le n, 1 \le z_i \le m)$$$, which describe an operation that swap $$$a_{x_i, z_i}, a_{y_i, z_i}$$$: swap the $$$z_i$$$-th number of the $$$x_i$$$-th and $$$y_i$$$-th arrays.

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

Note:
In the first test case, it's enough to do a single operation: to swap the first element in the second and the first rows. The arrays will become $$$[0, 1, 1, 0], [1, 0, 1, 0], [1, 0, 0, 1]$$$, each of them contains exactly two $$$1$$$s.

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

Example output:
1
2 1 1
1
4 2 2
-1

Editorial:
Considering that we need to make the number of $$$1$$$s in each array the same, we should calculate the sum of $$$1$$$s, and every array has $$$\frac{sum}{n}$$$ $$$1$$$s. Because only the same position of two different arrays can be selected for exchange each time, for a position $$$pos$$$ , we traverse each array each time. If the number of $$$1$$$s in this array is not enough, then we need to turn some $$$0$$$s into $$$1$$$s; If the number of $$$1$$$s in this array is more than we need, then some $$$1$$$s should be turned into $$$0$$$s. It can be proved that as long as the total number of $$$1$$$s is a multiple of n, the number of $$$1$$$s in each array can be made the same through exchange.