1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Minimum Sum
Contest: Testing Round 14 (Unrated)
Difficulty rating: 1700
Tags: constructive algorithms, greedy, math

Petya has n positive integers a1, a2, ..., an.

His friend Vasya decided to joke and replaced all digits in Petya's numbers with a letters. He used the lowercase letters of the Latin alphabet from 'a' to 'j' and replaced all digits 0 with one letter, all digits 1 with another letter and so on. For any two different digits Vasya used distinct letters from 'a' to 'j'.

Your task is to restore Petya's numbers. The restored numbers should be positive integers without leading zeros. Since there can be multiple ways to do it, determine the minimum possible sum of all Petya's numbers after the restoration. It is guaranteed that before Vasya's joke all Petya's numbers did not have leading zeros.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 1 000) — the number of Petya's numbers.

Each of the following lines contains non-empty string si consisting of lowercase Latin letters from 'a' to 'j' — the Petya's numbers after Vasya's joke. The length of each string does not exceed six characters.

Output format:
Determine the minimum sum of all Petya's numbers after the restoration. The restored numbers should be positive integers without leading zeros. It is guaranteed that the correct restore (without leading zeros) exists for all given tests.

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

Note:
In the first example, you need to replace the letter 'a' with the digit 1, the letter 'b' with the digit 0, the letter 'd' with the digit 2, the letter 'e' with the digit 3, and the letter 'j' with the digit 4. So after the restoration numbers will look like [10, 23, 14]. The sum of them is equal to 47, which is the minimum possible sum of the numbers after the correct restoration.

In the second example the numbers after the restoration can look like: [120468, 3579, 2468, 10024, 3].

In the second example the numbers after the restoration can look like: [11, 22, 11].

Example input:
3
ab
de
aj

Example output:
47

Example input:
5
abcdef
ghij
bdef
accbd
g

Example output:
136542

Editorial:
Для решения данной задачи нужно воспользоваться жадными соображениями. Посчитаем следующее значение для каждой буквы. Пусть текущее число равно abcd. Тогда к значению буквы a нужно прибавить 103, к значению буквы b нужно прибавить 102, к значению буквы c прибавить 101, а к значению d прибавить 100.
Описанное действие нужно выполнить для каждой заданной строки. После этого нужно отсортировать буквы по невозрастанию посчитанных для них значений. Следуя жадным соображениям, буква с самым большим значением должна быть нулем. Если эта буква стоит вначале какой-то из заданных строк, то она должна быть единицей. Будем выполнять аналогичную операцию для остальных букв, при этом не забывая, что разным буквам должны быть назначены разные цифры, и то что буква, которая стоит вначале какой-то из строк, не может быть нулём.
Line to Cashier
Contest: Codeforces Round 239 (Div. 2)
Difficulty rating: 900
Tags: implementation

Little Vasya went to the supermarket to get some groceries. He walked about the supermarket for a long time and got a basket full of products. Now he needs to choose the cashier to pay for the products.

There are n cashiers at the exit from the supermarket. At the moment the queue for the i-th cashier already has ki people. The j-th person standing in the queue to the i-th cashier has mi, j items in the basket. Vasya knows that:

- the cashier needs 5 seconds to scan one item;
- after the cashier scans each item of some customer, he needs 15 seconds to take the customer's money and give him the change.

Of course, Vasya wants to select a queue so that he can leave the supermarket as soon as possible. Help him write a program that displays the minimum number of seconds after which Vasya can get to one of the cashiers.

Input format:
The first line contains integer n (1 ≤ n ≤ 100) — the number of cashes in the shop. The second line contains n space-separated integers: k1, k2, ..., kn (1 ≤ ki ≤ 100), where ki is the number of people in the queue to the i-th cashier.

The i-th of the next n lines contains ki space-separated integers: mi, 1, mi, 2, ..., mi, ki (1 ≤ mi, j ≤ 100) — the number of products the j-th person in the queue for the i-th cash has.

Output format:
Print a single integer — the minimum number of seconds Vasya needs to get to the cashier.

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

Note:
In the second test sample, if Vasya goes to the first queue, he gets to the cashier in 100·5 + 15 = 515 seconds. But if he chooses the second queue, he will need 1·5 + 2·5 + 2·5 + 3·5 + 4·15 = 100 seconds. He will need 1·5 + 9·5 + 1·5 + 3·15 = 100 seconds for the third one and 7·5 + 8·5 + 2·15 = 105 seconds for the fourth one. Thus, Vasya gets to the cashier quicker if he chooses the second or the third queue.

Example input:
1
1
1

Example output:
20

Example input:
4
1 4 3 2
100
1 2 2 3
1 9 1
7 8

Example output:
100

Editorial:
Garland
Contest: Codeforces Round 239 (Div. 2)
Difficulty rating: 1200
Tags: implementation

Once little Vasya read an article in a magazine on how to make beautiful handmade garland from colored paper. Vasya immediately went to the store and bought n colored sheets of paper, the area of each sheet is 1 square meter.

The garland must consist of exactly m pieces of colored paper of arbitrary area, each piece should be of a certain color. To make the garland, Vasya can arbitrarily cut his existing colored sheets into pieces. Vasya is not obliged to use all the sheets to make the garland.

Vasya wants the garland to be as attractive as possible, so he wants to maximize the total area of ​​m pieces of paper in the garland. Calculate what the maximum total area of ​​the pieces of paper in the garland Vasya can get.

Input format:
The first line contains a non-empty sequence of n (1 ≤ n ≤ 1000) small English letters ("a"..."z"). Each letter means that Vasya has a sheet of paper of the corresponding color.

The second line contains a non-empty sequence of m (1 ≤ m ≤ 1000) small English letters that correspond to the colors of the pieces of paper in the garland that Vasya wants to make.

Output format:
Print an integer that is the maximum possible total area of the pieces of paper in the garland Vasya wants to get or -1, if it is impossible to make the garland from the sheets he's got. It is guaranteed that the answer is always an integer.

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

Note:
In the first test sample Vasya can make an garland of area 6: he can use both sheets of color b, three (but not four) sheets of color a and cut a single sheet of color c in three, for example, equal pieces. Vasya can use the resulting pieces to make a garland of area 6.

In the second test sample Vasya cannot make a garland at all — he doesn't have a sheet of color z.

Example input:
aaabbac
aabbccac

Example output:
6

Example input:
a
z

Example output:
-1

Editorial:
Playing with Paper
Contest: Codeforces Round 296 (Div. 2)
Difficulty rating: 1100
Tags: implementation, math

One day Vasya was sitting on a not so interesting Maths lesson and making an origami from a rectangular a mm  ×  b mm sheet of paper (a > b). Usually the first step in making an origami is making a square piece of paper from the rectangular sheet by folding the sheet along the bisector of the right angle, and cutting the excess part.

After making a paper ship from the square piece, Vasya looked on the remaining (a - b) mm  ×  b mm strip of paper. He got the idea to use this strip of paper in the same way to make an origami, and then use the remainder (if it exists) and so on. At the moment when he is left with a square piece of paper, he will make the last ship from it and stop.

Can you determine how many ships Vasya will make during the lesson?

Input format:
The first line of the input contains two integers a, b (1 ≤ b < a ≤ 1012) — the sizes of the original sheet of paper.

Output format:
Print a single integer — the number of ships that Vasya will make.

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

Note:
Pictures to the first and second sample test.

Example input:
2 1

Example output:
2

Example input:
10 7

Example output:
6

Editorial:
Error Correct System
Contest: Codeforces Round 296 (Div. 2)
Difficulty rating: 1500
Tags: greedy

Ford Prefect got a job as a web developer for a small company that makes towels. His current work task is to create a search engine for the website of the company. During the development process, he needs to write a subroutine for comparing strings S and T of equal length to be "similar". After a brief search on the Internet, he learned about the Hamming distance between two strings S and T of the same length, which is defined as the number of positions in which S and T have different characters. For example, the Hamming distance between words "permanent" and "pergament" is two, as these words differ in the fourth and sixth letters.

Moreover, as he was searching for information, he also noticed that modern search engines have powerful mechanisms to correct errors in the request to improve the quality of search. Ford doesn't know much about human beings, so he assumed that the most common mistake in a request is swapping two arbitrary letters of the string (not necessarily adjacent). Now he wants to write a function that determines which two letters should be swapped in string S, so that the Hamming distance between a new string S and string T would be as small as possible, or otherwise, determine that such a replacement cannot reduce the distance between the strings.

Help him do this!

Input format:
The first line contains integer n (1 ≤ n ≤ 200 000) — the length of strings S and T.

The second line contains string S.

The third line contains string T.

Each of the lines only contains lowercase Latin letters.

Output format:
In the first line, print number x — the minimum possible Hamming distance between strings S and T if you swap at most one pair of letters in S.

In the second line, either print the indexes i and j (1 ≤ i, j ≤ n, i ≠ j), if reaching the minimum possible distance is possible by swapping letters on positions i and j, or print "-1 -1", if it is not necessary to swap characters.

If there are multiple possible answers, print any of them.

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

Note:
In the second test it is acceptable to print i = 2, j = 3.

Example input:
9
pergament
permanent

Example output:
1
4 6

Example input:
6
wookie
cookie

Example output:
1
-1 -1

Editorial:
Glass Carving
Contest: Codeforces Round 296 (Div. 2)
Difficulty rating: 1500
Tags: binary search, data structures, implementation

Leonid wants to become a glass carver (the person who creates beautiful artworks by cutting the glass). He already has a rectangular w mm  ×  h mm sheet of glass, a diamond glass cutter and lots of enthusiasm. What he lacks is understanding of what to carve and how.

In order not to waste time, he decided to practice the technique of carving. To do this, he makes vertical and horizontal cuts through the entire sheet. This process results in making smaller rectangular fragments of glass. Leonid does not move the newly made glass fragments. In particular, a cut divides each fragment of glass that it goes through into smaller fragments.

After each cut Leonid tries to determine what area the largest of the currently available glass fragments has. Since there appear more and more fragments, this question takes him more and more time and distracts him from the fascinating process.

Leonid offers to divide the labor — he will cut glass, and you will calculate the area of the maximum fragment after each cut. Do you agree?

Input format:
The first line contains three integers w, h, n (2 ≤ w, h ≤ 200 000, 1 ≤ n ≤ 200 000).

Next n lines contain the descriptions of the cuts. Each description has the form H y or V x. In the first case Leonid makes the horizontal cut at the distance y millimeters (1 ≤ y ≤ h - 1) from the lower edge of the original sheet of glass. In the second case Leonid makes a vertical cut at distance x (1 ≤ x ≤ w - 1) millimeters from the left edge of the original sheet of glass. It is guaranteed that Leonid won't make two identical cuts.

Output format:
After each cut print on a single line the area of the maximum available glass fragment in mm2.

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

Note:
Picture for the first sample test:

Example input:
4 3 4
H 2
V 2
V 3
V 1

Example output:
8
4
4
2

Example input:
7 6 5
H 4
V 3
V 5
H 2
V 1

Example output:
28
16
12
6
4

Editorial:
Clique Problem
Contest: Codeforces Round 296 (Div. 2)
Difficulty rating: 1800
Tags: data structures, dp, greedy, implementation, sortings

The clique problem is one of the most well-known NP-complete problems. Under some simplification it can be formulated as follows. Consider an undirected graph G. It is required to find a subset of vertices C of the maximum size such that any two of them are connected by an edge in graph G. Sounds simple, doesn't it? Nobody yet knows an algorithm that finds a solution to this problem in polynomial time of the size of the graph. However, as with many other NP-complete problems, the clique problem is easier if you consider a specific type of a graph.

Consider n distinct points on a line. Let the i-th point have the coordinate xi and weight wi. Let's form graph G, whose vertices are these points and edges connect exactly the pairs of points (i, j), such that the distance between them is not less than the sum of their weights, or more formally: |xi - xj| ≥ wi + wj.

Find the size of the maximum clique in such graph.

Input format:
The first line contains the integer n (1 ≤ n ≤ 200 000) — the number of points.

Each of the next n lines contains two numbers xi, wi (0 ≤ xi ≤ 109, 1 ≤ wi ≤ 109) — the coordinate and the weight of a point. All xi are different.

Output format:
Print a single number — the number of vertexes in the maximum clique of the given graph.

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

Note:
If you happen to know how to solve this problem without using the specific properties of the graph formulated in the problem statement, then you are able to get a prize of one million dollars!

The picture for the sample test.

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

Example output:
3

Editorial:
Shortest Cycle
Contest: Codeforces Round 580 (Div. 1)
Difficulty rating: 1900
Tags: bitmasks, brute force, graphs, shortest paths

You are given $$$n$$$ integer numbers $$$a_1, a_2, \dots, a_n$$$. Consider graph on $$$n$$$ nodes, in which nodes $$$i$$$, $$$j$$$ ($$$i\neq j$$$) are connected if and only if, $$$a_i$$$ AND $$$a_j\neq 0$$$, where AND denotes the bitwise AND operation.

Find the length of the shortest cycle in this graph or determine that it doesn't have cycles at all.

Input format:
The first line contains one integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — number of numbers.

The second line contains $$$n$$$ integer numbers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{18}$$$).

Output format:
If the graph doesn't have any cycles, output $$$-1$$$. Else output the length of the shortest cycle.

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

Note:
In the first example, the shortest cycle is $$$(9, 3, 6, 28)$$$.

In the second example, the shortest cycle is $$$(5, 12, 9)$$$.

The graph has no cycles in the third example.

Example input:
4
3 6 28 9

Example output:
4

Example input:
5
5 12 9 16 48

Example output:
3

Editorial:
The most important thing in this task is to notice that if any bit is contained at least $$$ 3 $$$ numbers, then they will form a cycle of length $$$ 3 $$$, and the answer is $$$ 3 $$$.
Suppose now that each bit is in no more than two numbers. It follows that each bit can be shared by at most one pair of numbers. From here we get that in the graph there are no more than $$$ 60 $$$ edges. Then in it you can find the shortest cycle in $$$ O (m ^ 2) $$$: for each edge between the vertices $$$ u $$$ and $$$ v $$$ we will try to remove it and find the shortest distance between the vertices $$$ u $$$, $$$ v $$$ in the resulting graph. If each time $$$ u $$$ and $$$ v $$$ turned out to be in different components, then there is no cycle in the graph, otherwise its length is $$$ 1 $$$ + the minimal of the distances found.
Asymptotics $$$ O (n \ log {10 ^ {18}} + 60 ^ 2) $$$.
Anton and Letters
Contest: Codeforces Round 253 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, implementation

Recently, Anton has found a set. The set consists of small English letters. Anton carefully wrote out all the letters from the set in one line, separated by a comma. He also added an opening curved bracket at the beginning of the line and a closing curved bracket at the end of the line.

Unfortunately, from time to time Anton would forget writing some letter and write it again. He asks you to count the total number of distinct letters in his set.

Input format:
The first and the single line contains the set of letters. The length of the line doesn't exceed 1000. It is guaranteed that the line starts from an opening curved bracket and ends with a closing curved bracket. Between them, small English letters are listed, separated by a comma. Each comma is followed by a space.

Output format:
Print a single number — the number of distinct letters in Anton's set.

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

Example input:
{a, b, c}

Example output:
3

Example input:
{b, a, b, a}

Example output:
2

Editorial:
Kolya and Tandem Repeat
Contest: Codeforces Round 253 (Div. 2)
Difficulty rating: 1500
Tags: brute force, implementation, strings

Kolya got string s for his birthday, the string consists of small English letters. He immediately added k more characters to the right of the string.

Then Borya came and said that the new string contained a tandem repeat of length l as a substring. How large could l be?

See notes for definition of a tandem repeat.

Input format:
The first line contains s (1 ≤ |s| ≤ 200). This string contains only small English letters. The second line contains number k (1 ≤ k ≤ 200) — the number of the added characters.

Output format:
Print a single number — the maximum length of the tandem repeat that could have occurred in the new string.

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

Note:
A tandem repeat of length 2n is string s, where for any position i (1 ≤ i ≤ n) the following condition fulfills: si = si + n.

In the first sample Kolya could obtain a string aabaab, in the second — aaabbbbbb, in the third — abracadabrabracadabra.

Example input:
aaba
2

Example output:
6

Example input:
aaabbbb
2

Example output:
6

Editorial:
Yes-Yes?
Contest: Codeforces Round  834 (Div. 3)
Difficulty rating: 800
Tags: implementation, strings

You talked to Polycarp and asked him a question. You know that when he wants to answer "yes", he repeats Yes many times in a row.

Because of the noise, you only heard part of the answer — some substring of it. That is, if he answered YesYes, then you could hear esY, YesYes, sYes, e, but you couldn't Yess, YES or se.

Determine if it is true that the given string $$$s$$$ is a substring of YesYesYes... (Yes repeated many times in a row).

Input format:
The first line of input data contains the singular $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the test.

Each test case is described by a single string of Latin letters $$$s$$$ ($$$1 \le |s| \le 50$$$) — the part of Polycarp's answer that you heard, where $$$|s|$$$ — is the length of the string $$$s$$$.

Output format:
Output $$$t$$$ lines, each of which is the answer to the corresponding test case. As an answer, output "YES" if the specified string $$$s$$$ is a substring of the string YesYesYes...Yes (the number of words Yes is arbitrary), and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

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

Example input:
12
YES
esYes
codeforces
es
se
YesY
esYesYesYesYesYesYe
seY
Yess
sY
o
Yes

Example output:
NO
YES
NO
YES
NO
YES
YES
NO
NO
YES
NO
YES

Editorial:
Note that it is enough to consider the string $$$full = $$$YesYes...Yes, where Yes is written $$$18$$$ times, since $$$18 \cdot 3 = 54$$$, and our substring $$$s$$$ has size $$$|s| \le 50$$$.
Then we just use the built-in function $$$find$$$ to find out if our string $$$s$$$ is a substring of the string $$$full$$$.
Lost Permutation
Contest: Codeforces Round  834 (Div. 3)
Difficulty rating: 800
Tags: math

A sequence of $$$n$$$ numbers is called a permutation if it contains all integers from $$$1$$$ to $$$n$$$ exactly once. For example, the sequences [$$$3, 1, 4, 2$$$], [$$$1$$$] and [$$$2,1$$$] are permutations, but [$$$1,2,1$$$], [$$$0,1$$$] and [$$$1,3,4$$$] — are not.

Polycarp lost his favorite permutation and found only some of its elements — the numbers $$$b_1, b_2, \dots b_m$$$. He is sure that the sum of the lost elements equals $$$s$$$.

Determine whether one or more numbers can be appended to the given sequence $$$b_1, b_2, \dots b_m$$$ such that the sum of the added numbers equals $$$s$$$, and the resulting new array is a permutation?

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

Then the descriptions of the test cases follow.

The first line of each test set contains two integers $$$m$$$ and $$$s$$$ ($$$1 \le m \le 50$$$, $$$1 \le s \le 1000$$$)—-the number of found elements and the sum of forgotten numbers.

The second line of each test set contains $$$m$$$ different integers $$$b_1, b_2 \dots b_m$$$ ($$$1 \le b_i \le 50$$$) — the elements Polycarp managed to find.

Output format:
Print $$$t$$$ lines, each of which is the answer to the corresponding test set. Print as the answer YES if you can append several elements to the array $$$b$$$, that their sum equals $$$s$$$ and the result will be a permutation. Output NO otherwise.

You can output the answer in any case (for example, yEs, yes, Yes and YES will be recognized as positive answer).

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

Note:
In the test case of the example, $$$m=3, s=13, b=[3,1,4]$$$. You can append to $$$b$$$ the numbers $$$6,2,5$$$, the sum of which is $$$6+2+5=13$$$. Note that the final array will become $$$[3,1,4,6,2,5]$$$, which is a permutation.

In the second test case of the example, $$$m=1, s=1, b=[1]$$$. You cannot append one or more numbers to $$$[1]$$$ such that their sum equals $$$1$$$ and the result is a permutation.

In the third test case of the example, $$$m=3, s=3, b=[1,4,2]$$$. You can append the number $$$3$$$ to $$$b$$$. Note that the resulting array will be $$$[1,4,2,3]$$$, which is a permutation.

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

Example output:
YES
NO
YES
NO
YES

Editorial:
Let us add to $$$s$$$ the sum of the elements of the array $$$b$$$ and try to find a suitable permutation. To do this, greedily add elements $$$1, 2, \dots, cnt$$$ until their sum is less than $$$s$$$. And at the end we will check that the sum has matched.
Also check that the maximal element from $$$b$$$: $$$max(b) \le cnt$$$, and that the total elements in $$$b$$$: $$$n \le cnt$$$.