1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Homework
Contest: Codeforces Beta Round 79 (Div. 1 Only)
Difficulty rating: 1200
Tags: greedy

Once when Gerald studied in the first year at school, his teacher gave the class the following homework. She offered the students a string consisting of n small Latin letters; the task was to learn the way the letters that the string contains are written. However, as Gerald is too lazy, he has no desire whatsoever to learn those letters. That's why he decided to lose some part of the string (not necessarily a connected part). The lost part can consist of any number of segments of any length, at any distance from each other. However, Gerald knows that if he loses more than k characters, it will be very suspicious.

Find the least number of distinct characters that can remain in the string after no more than k characters are deleted. You also have to find any possible way to delete the characters.

Input format:
The first input data line contains a string whose length is equal to n (1 ≤ n ≤ 105). The string consists of lowercase Latin letters. The second line contains the number k (0 ≤ k ≤ 105).

Output format:
Print on the first line the only number m — the least possible number of different characters that could remain in the given string after it loses no more than k characters.

Print on the second line the string that Gerald can get after some characters are lost. The string should have exactly m distinct characters. The final string should be the subsequence of the initial string. If Gerald can get several different strings with exactly m distinct characters, print any of them.

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

Note:
In the first sample the string consists of five identical letters but you are only allowed to delete 4 of them so that there was at least one letter left. Thus, the right answer is 1 and any string consisting of characters "a" from 1 to 5 in length.

In the second sample you are allowed to delete 4 characters. You cannot delete all the characters, because the string has length equal to 7. However, you can delete all characters apart from "a" (as they are no more than four), which will result in the "aaaa" string.

In the third sample you are given a line whose length is equal to 8, and k = 10, so that the whole line can be deleted. The correct answer is 0 and an empty string.

Example input:
aaaaa
4

Example output:
1
aaaaa

Example input:
abacaba
4

Example output:
1
aaaa

Editorial:
Buses
Contest: Codeforces Beta Round 79 (Div. 1 Only)
Difficulty rating: 1700
Tags: binary search, data structures, dp

Little boy Gerald studies at school which is quite far from his house. That's why he has to go there by bus every day. The way from home to school is represented by a segment of a straight line; the segment contains exactly n + 1 bus stops. All of them are numbered with integers from 0 to n in the order in which they follow from Gerald's home. The bus stop by Gerald's home has number 0 and the bus stop by the school has number n.

There are m buses running between the house and the school: the i-th bus goes from stop si to ti (si < ti), visiting all the intermediate stops in the order in which they follow on the segment. Besides, Gerald's no idiot and he wouldn't get off the bus until it is still possible to ride on it closer to the school (obviously, getting off would be completely pointless). In other words, Gerald can get on the i-th bus on any stop numbered from si to ti - 1 inclusive, but he can get off the i-th bus only on the bus stop ti.

Gerald can't walk between the bus stops and he also can't move in the direction from the school to the house.

Gerald wants to know how many ways he has to get from home to school. Tell him this number. Two ways are considered different if Gerald crosses some segment between the stops on different buses. As the number of ways can be too much, find the remainder of a division of this number by 1000000007 (109 + 7).

Input format:
The first line contains two space-separated integers: n and m (1 ≤ n ≤ 109, 0 ≤ m ≤ 105). Then follow m lines each containing two integers si, ti. They are the numbers of starting stops and end stops of the buses (0 ≤ si < ti ≤ n).

Output format:
Print the only number — the number of ways to get to the school modulo 1000000007 (109 + 7).

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

Note:
The first test has the only variant to get to school: first on bus number one to the bus stop number one; then on bus number two to the bus stop number two.

In the second test no bus goes to the third bus stop, where the school is positioned. Thus, the correct answer is 0.

In the third test Gerald can either get or not on any of the first four buses to get closer to the school. Thus, the correct answer is 24 = 16.

Example input:
2 2
0 1
1 2

Example output:
1

Example input:
3 2
0 1
1 2

Example output:
0

Editorial:
Vectors
Contest: Codeforces Beta Round 79 (Div. 1 Only)
Difficulty rating: 2000
Tags: implementation, math

At a geometry lesson Gerald was given a task: to get vector B out of vector A. Besides, the teacher permitted him to perform the following operations with vector А:

- Turn the vector by 90 degrees clockwise.
- Add to the vector a certain vector C.

Operations could be performed in any order any number of times.

Can Gerald cope with the task?

Input format:
The first line contains integers x1 и y1 — the coordinates of the vector A ( - 108 ≤ x1, y1 ≤ 108). The second and the third line contain in the similar manner vectors B and C (their coordinates are integers; their absolute value does not exceed 108).

Output format:
Print "YES" (without the quotes) if it is possible to get vector B using the given operations. Otherwise print "NO" (without the quotes).

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

Example input:
0 0
1 1
0 1

Example output:
YES

Example input:
0 0
1 1
1 1

Example output:
YES

Editorial:
Candies and Stones
Contest: Codeforces Beta Round 79 (Div. 1 Only)
Difficulty rating: 2500
Tags: divide and conquer, dp

Little Gerald and his coach Mike play an interesting game. At the beginning of the game there is a pile consisting of n candies and a pile consisting of m stones. Gerald and Mike move in turns, Mike goes first. During his move Mike checks how many candies and stones Gerald has eaten. Let Gerald eat a candies and b stones. Then Mike awards Gerald f(a, b) prize points. Gerald during his move either eats a candy from the pile of candies or a stone from the pile of stones. As Mike sees that Gerald has eaten everything apart one candy and one stone, he awards points for the last time and the game ends. Gerald is not allowed to eat all the candies, and he is not allowed to eat all the stones too. Tell Gerald how to play to get the largest possible number of points: it is required to find one of the possible optimal playing strategies for Gerald.

Input format:
The first line contains three integers n, m, p (1 ≤ n, m ≤ 20000, 1 ≤ p ≤ 109). The second line contains n integers x0, x1, ..., xn - 1 (0 ≤ xi ≤ 20000). The third line contains m integers y0, y1, ..., ym - 1 (0 ≤ yi ≤ 20000). The value of f(a, b) is calculated as a remainder of the division of the sum xa + yb by number p.

Output format:
Print on the first line the only number: the maximal number of points Gerald can earn. Print on the second line a sting consisting of n + m - 2 characters, each of which is either a "C" or "S", the i-th character should be "C" if Gerald's i-th move should be eating a candy and "S" if he should eat a stone.

Constraints:
Time limit: 7.5 s
Memory limit: 45.0 MB

Note:
In the first test if Gerald's first move is eating a stone, he will receive a point for it and if he eats a candy, he will get zero pints. In any way Gerald will get 0 points before his first move, and 1 after his second one. This, the maximum number of points Gerald can get equals to 2, and for that he should first eat a stone, then a candy.

Example input:
2 2 10
0 0
0 1

Example output:
2
SC

Example input:
3 3 10
0 2 0
0 0 2

Example output:
10
CSSC

Editorial:
Elections
Contest: Codeforces Round 748 (Div. 3)
Difficulty rating: 800
Tags: math

The elections in which three candidates participated have recently ended. The first candidate received $$$a$$$ votes, the second one received $$$b$$$ votes, the third one received $$$c$$$ votes. For each candidate, solve the following problem: how many votes should be added to this candidate so that he wins the election (i.e. the number of votes for this candidate was strictly greater than the number of votes for any other candidate)?

Please note that for each candidate it is necessary to solve this problem independently, i.e. the added votes for any candidate do not affect the calculations when getting the answer for the other two candidates.

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 consists of one line containing three integers $$$a$$$, $$$b$$$, and $$$c$$$ ($$$0 \le a,b,c \le 10^9$$$).

Output format:
For each test case, output in a separate line three integers $$$A$$$, $$$B$$$, and $$$C$$$ ($$$A, B, C \ge 0$$$) separated by spaces — the answers to the problem for the first, second, and third candidate, respectively.

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

Example input:
5
0 0 0
10 75 15
13 13 17
1000 0 0
0 1000000000 0

Example output:
1 1 1
66 0 61
5 5 0
0 1001 1001
1000000001 0 1000000001

Editorial:
Let's solve the problem for the first candidate. To win the election, he needs to get at least $$$1$$$ more votes than every other candidate. Therefore, the first candidate needs to get at least $$$\max(b, c) + 1$$$ votes. If $$$a$$$ is already greater than this value, then you don't need to add any votes, otherwise, you need to add $$$\max(b, c) + 1 - a$$$ votes. So the answer for the first candidate is $$$\max(0, \max(b,c) + 1 - a)$$$.
Similarly, the answer for the second candidate is $$$\max(0, \max(a, c) + 1 - b)$$$, and, for the third one, the answer is $$$\max(0, \max(a, b) + 1 - c)$$$.
Make it Divisible by 25
Contest: Codeforces Round 748 (Div. 3)
Difficulty rating: 900
Tags: dfs and similar, dp, greedy, math, math

It is given a positive integer $$$n$$$. In $$$1$$$ move, one can select any single digit and remove it (i.e. one selects some position in the number and removes the digit located at this position). The operation cannot be performed if only one digit remains. If the resulting number contains leading zeroes, they are automatically removed.

E.g. if one removes from the number $$$32925$$$ the $$$3$$$-rd digit, the resulting number will be $$$3225$$$. If one removes from the number $$$20099050$$$ the first digit, the resulting number will be $$$99050$$$ (the $$$2$$$ zeroes going next to the first digit are automatically removed).

What is the minimum number of steps to get a number such that it is divisible by $$$25$$$ and positive? It is guaranteed that, for each $$$n$$$ occurring in the input, the answer exists. It is guaranteed that the number $$$n$$$ has no leading zeros.

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 consists of one line containing one integer $$$n$$$ ($$$25 \le n \le 10^{18}$$$). It is guaranteed that, for each $$$n$$$ occurring in the input, the answer exists. It is guaranteed that the number $$$n$$$ has no leading zeros.

Output format:
For each test case output on a separate line an integer $$$k$$$ ($$$k \ge 0$$$) — the minimum number of steps to get a number such that it is divisible by $$$25$$$ and positive.

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

Note:
In the first test case, it is already given a number divisible by $$$25$$$.

In the second test case, we can remove the digits $$$1$$$, $$$3$$$, and $$$4$$$ to get the number $$$75$$$.

In the third test case, it's enough to remove the last digit to get the number $$$325$$$.

In the fourth test case, we can remove the three last digits to get the number $$$50$$$.

In the fifth test case, it's enough to remove the digits $$$4$$$ and $$$7$$$.

Example input:
5
100
71345
3259
50555
2050047

Example output:
0
3
1
3
2

Editorial:
A number is divisible by $$$25$$$ if and only if its last two digits represent one of the following strings: "00", "25", "50", "75".
Let's solve for each string the following subtask: what is the minimum number of characters to be deleted so that the string becomes a suffix of the number. Then, choosing the minimum of the answers for all subtasks, we solve the whole problem.
Let's solve the subtask for a string "X Y" where 'X' and 'Y' are digits. We can do it using the following algorithm: let's delete the last digit of the number until it is equal to 'Y', then the second to last digit of the number until it is equal to 'X'. If it is not possible, then this subtask has no solution (i.e. its result will not affect the answer).
All are Same
Contest: Codeforces Round 748 (Div. 3)
Difficulty rating: 1100
Tags: math, number theory

This problem is a simplified version of D2, but it has significant differences, so read the whole statement.

Polycarp has an array of $$$n$$$ ($$$n$$$ is even) integers $$$a_1, a_2, \dots, a_n$$$. Polycarp conceived of a positive integer $$$k$$$. After that, Polycarp began performing the following operations on the array: take an index $$$i$$$ ($$$1 \le i \le n$$$) and reduce the number $$$a_i$$$ by $$$k$$$.

After Polycarp performed some (possibly zero) number of such operations, it turned out that all numbers in the array became the same. Find the maximum $$$k$$$ at which such a situation is possible, or print $$$-1$$$ if such a number can be arbitrarily large.

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

Each test case consists of two lines. The first line contains an even integer $$$n$$$ ($$$4 \le n \le 40$$$) ($$$n$$$ is even). The second line contains $$$n$$$ integers $$$a_1, a_2, \dots a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$).

It is guaranteed that the sum of all $$$n$$$ specified in the given test cases does not exceed $$$100$$$.

Output format:
For each test case output on a separate line an integer $$$k$$$ ($$$k \ge 1$$$) — the maximum possible number that Polycarp used in operations on the array, or $$$-1$$$, if such a number can be arbitrarily large.

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

Example input:
3
6
1 5 3 1 1 5
8
-1 0 1 -1 0 1 -1 0
4
100 -1000 -1000 -1000

Example output:
2
1
1100

Editorial:
$$$k$$$ can be arbitrarily large if and only if all numbers in the array are the same. In this case, we can choose any number $$$k$$$ and subtract it from all the numbers, for example, exactly once.
Suppose we fix some $$$k$$$. Let $$$q_i$$$ be the number of subtractions of the number $$$k$$$ from the number $$$a_i$$$. In this case, all numbers will be equal if and only if, for any two numbers $$$a_i$$$ and $$$a_j$$$ from the array, $$$a_i - k \cdot q_i = a_j - k\cdot q_j$$$. Let $$$q_{i_0}$$$ be the minimum of $$$q_i$$$. Then all numbers in the array become the same if for each index $$$i$$$ we subtract from $$$a_i$$$ $$$k$$$ not $$$q_i$$$, but $$$q_i - q_{i_0}$$$ times. Then we will never subtract $$$k$$$ from the element $$$a_{i_0}$$$. This means that there is always an element in the array from which we can never subtract $$$k$$$. This element is the minimum on the array. Then from $$$a_i$$$ we will subtract $$$k$$$ exactly $$$\frac{a_i - a_{i_0}}{k}$$$ times.
Thus, with the current $$$k$$$, it is possible to make all elements equal if and only if for all elements $$$a_i$$$ the value $$$a_i - a_{i_0}$$$ (where $$$a_{i_0}$$$ is the minimum on the array) is divisible by $$$k$$$. So, the maximum $$$k$$$ is the greatest common divisor of all values of $$$a_i - a_{i_0}$$$, $$$i = \overline{1, n}$$$.
Half of Same
Contest: Codeforces Round 748 (Div. 3)
Difficulty rating: 1900
Tags: brute force, math, number theory

This problem is a complicated version of D1, but it has significant differences, so read the whole statement.

Polycarp has an array of $$$n$$$ ($$$n$$$ is even) integers $$$a_1, a_2, \dots, a_n$$$. Polycarp conceived of a positive integer $$$k$$$. After that, Polycarp began performing the following operations on the array: take an index $$$i$$$ ($$$1 \le i \le n$$$) and reduce the number $$$a_i$$$ by $$$k$$$.

After Polycarp performed some (possibly zero) number of such operations, it turned out that at least half of the numbers in the array became the same. Find the maximum $$$k$$$ at which such a situation is possible, or print $$$-1$$$ if such a number can be arbitrarily large.

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

Each test case consists of two lines. The first line contains an even integer $$$n$$$ ($$$4 \le n \le 40$$$) ($$$n$$$ is even). The second line contains $$$n$$$ integers $$$a_1, a_2, \dots a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$).

It is guaranteed that the sum of all $$$n$$$ specified in the given test cases does not exceed $$$100$$$.

Output format:
For each test case output on a separate line an integer $$$k$$$ ($$$k \ge 1$$$) — the maximum possible number that Polycarp used in operations on the array, or $$$-1$$$, if such a number can be arbitrarily large.

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

Example input:
4
6
48 13 22 -15 16 35
8
-1 0 1 -1 0 1 -1 0
4
100 -1000 -1000 -1000
4
1 1 1 1

Example output:
13
2
-1
-1

Editorial:
$$$k$$$ can be arbitrarily large if and only if at least half of the numbers in the array are the same. In this case, we can choose any number $$$k$$$ and subtract it from all numbers, for example, exactly once.
Let's iterate over the element $$$a_{i_0}$$$, it will be the minimum among the numbers that we want to make the same. Let's calculate the number of numbers in the array that are equal to this element. If this number is at least $$$\frac{n}{2}$$$, then the answer is -1. Otherwise, we will iterate over numbers $$$a_i$$$ which are strictly greater than the selected minimum, and, for each number, we will iterate over the divisors of the number $$$a_i - a_{i_0}$$$. For each of the found divisors, let's calculate the number of $$$a_i$$$ for which this divisor was found. Among all such divisors for which the sum of the found number and the number of numbers equal to $$$a_{i_0}$$$ is greater than or equal to $$$\frac{n}{2}$$$, we will choose the maximum one. The greatest found divisor will be the desired $$$k$$$. This solution works in $$$O(n^2\times\sqrt{A})$$$ (where $$$A$$$ is the absolute value of the maximum on the array).
Message
Contest: Codeforces Round 110 (Div. 1)
Difficulty rating: 1700
Tags: brute force

Dr. Moriarty is about to send a message to Sherlock Holmes. He has a string s.

String p is called a substring of string s if you can read it starting from some position in the string s. For example, string "aba" has six substrings: "a", "b", "a", "ab", "ba", "aba".

Dr. Moriarty plans to take string s and cut out some substring from it, let's call it t. Then he needs to change the substring t zero or more times. As a result, he should obtain a fixed string u (which is the string that should be sent to Sherlock Holmes). One change is defined as making one of the following actions:

- Insert one letter to any end of the string.
- Delete one letter from any end of the string.
- Change one letter into any other one.

Moriarty is very smart and after he chooses some substring t, he always makes the minimal number of changes to obtain u.

Help Moriarty choose the best substring t from all substrings of the string s. The substring t should minimize the number of changes Moriarty should make to obtain the string u from it.

Input format:
The first line contains a non-empty string s, consisting of lowercase Latin letters. The second line contains a non-empty string u, consisting of lowercase Latin letters. The lengths of both strings are in the range from 1 to 2000, inclusive.

Output format:
Print the only integer — the minimum number of changes that Dr. Moriarty has to make with the string that you choose.

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

Note:
In the first sample Moriarty can take any substring of length 3, and it will be equal to the required message u, so Moriarty won't have to make any changes.

In the second sample you should take a substring consisting of characters from second to fourth ("bca") or from fifth to sixth ("bc"). Then you will only have to make one change: to change or to add the last character.

In the third sample the initial string s doesn't contain any character that the message should contain, so, whatever string you choose, you will have to make at least 7 changes to obtain the required message.

Example input:
aaaaa
aaa

Example output:
0

Example input:
abcabc
bcd

Example output:
1

Editorial:
Suspects
Contest: Codeforces Round 110 (Div. 1)
Difficulty rating: 1600
Tags: constructive algorithms, data structures, implementation

As Sherlock Holmes was investigating a crime, he identified n suspects. He knows for sure that exactly one of them committed the crime. To find out which one did it, the detective lines up the suspects and numbered them from 1 to n. After that, he asked each one: "Which one committed the crime?". Suspect number i answered either "The crime was committed by suspect number ai", or "Suspect number ai didn't commit the crime". Also, the suspect could say so about himself (ai = i).

Sherlock Holmes understood for sure that exactly m answers were the truth and all other answers were a lie. Now help him understand this: which suspect lied and which one told the truth?

Input format:
The first line contains two integers n and m (1 ≤ n ≤ 105, 0 ≤ m ≤ n) — the total number of suspects and the number of suspects who told the truth. Next n lines contain the suspects' answers. The i-th line contains either "+ai" (without the quotes), if the suspect number i says that the crime was committed by suspect number ai, or "-ai" (without the quotes), if the suspect number i says that the suspect number ai didn't commit the crime (ai is an integer, 1 ≤ ai ≤ n).

It is guaranteed that at least one suspect exists, such that if he committed the crime, then exactly m people told the truth.

Output format:
Print n lines. Line number i should contain "Truth" if suspect number i has told the truth for sure. Print "Lie" if the suspect number i lied for sure and print "Not defined" if he could lie and could tell the truth, too, depending on who committed the crime.

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

Note:
The first sample has the single person and he confesses to the crime, and Sherlock Holmes knows that one person is telling the truth. That means that this person is telling the truth.

In the second sample there are three suspects and each one denies his guilt. Sherlock Holmes knows that only two of them are telling the truth. Any one of them can be the criminal, so we don't know for any of them, whether this person is telling the truth or not.

In the third sample the second and the fourth suspect defend the first and the third one. But only one is telling the truth, thus, the first or the third one is the criminal. Both of them can be criminals, so the second and the fourth one can either be lying or telling the truth. The first and the third one are lying for sure as they are blaming the second and the fourth one.

Example input:
1 1
+1

Example output:
Truth

Example input:
3 2
-1
-2
-3

Example output:
Not defined
Not defined
Not defined

Editorial: