1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Heist
Contest: Codeforces Round 509 (Div. 2)
Difficulty rating: 800
Tags: greedy, implementation, sortings

There was an electronic store heist last night.

All keyboards which were in the store yesterday were numbered in ascending order from some integer number $$$x$$$. For example, if $$$x = 4$$$ and there were $$$3$$$ keyboards in the store, then the devices had indices $$$4$$$, $$$5$$$ and $$$6$$$, and if $$$x = 10$$$ and there were $$$7$$$ of them then the keyboards had indices $$$10$$$, $$$11$$$, $$$12$$$, $$$13$$$, $$$14$$$, $$$15$$$ and $$$16$$$.

After the heist, only $$$n$$$ keyboards remain, and they have indices $$$a_1, a_2, \dots, a_n$$$. Calculate the minimum possible number of keyboards that have been stolen. The staff remember neither $$$x$$$ nor the number of keyboards in the store before the heist.

Input format:
The first line contains single integer $$$n$$$ $$$(1 \le n \le 1\,000)$$$ — the number of  keyboards in the store that remained after the heist.

The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^{9})$$$ — the indices of the remaining keyboards. The integers $$$a_i$$$ are given in arbitrary order and are pairwise distinct.

Output format:
Print the minimum possible number of keyboards that have been stolen if the staff remember neither $$$x$$$ nor the number of keyboards in the store before the heist.

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

Note:
In the first example, if $$$x=8$$$ then minimum number of stolen keyboards is equal to $$$2$$$. The keyboards with indices $$$9$$$ and $$$11$$$ were stolen during the heist.

In the second example, if $$$x=4$$$ then nothing was stolen during the heist.

Example input:
4
10 13 12 8

Example output:
2

Example input:
5
7 5 6 4 8

Example output:
0

Editorial:
Let $$$x$$$ — the minimal number from the given numbers and $$$y$$$ — the maximal. So we consider that $$$x$$$ and $$$y$$$ were minimal and maximal keyboard numbers before the heist. All given numbers are distinct, so the answer is $$$y - x + 1 - n$$$ (initial number of the keyboards is $$$(y - x + 1)$$$ minus the remaining number of keyboards $$$n$$$).
Buying a TV Set
Contest: Codeforces Round 509 (Div. 2)
Difficulty rating: 1000
Tags: math

Monocarp has decided to buy a new TV set and hang it on the wall in his flat. The wall has enough free space so Monocarp can buy a TV set with screen width not greater than $$$a$$$ and screen height not greater than $$$b$$$. Monocarp is also used to TV sets with a certain aspect ratio: formally, if the width of the screen is $$$w$$$, and the height of the screen is $$$h$$$, then the following condition should be met: $$$\frac{w}{h} = \frac{x}{y}$$$.

There are many different TV sets in the shop. Monocarp is sure that for any pair of positive integers $$$w$$$ and $$$h$$$ there is a TV set with screen width $$$w$$$ and height $$$h$$$ in the shop.

Monocarp isn't ready to choose the exact TV set he is going to buy. Firstly he wants to determine the optimal screen resolution. He has decided to try all possible variants of screen size. But he must count the number of pairs of positive integers $$$w$$$ and $$$h$$$, beforehand, such that $$$(w \le a)$$$, $$$(h \le b)$$$ and $$$(\frac{w}{h} = \frac{x}{y})$$$.

In other words, Monocarp wants to determine the number of TV sets having aspect ratio $$$\frac{x}{y}$$$, screen width not exceeding $$$a$$$, and screen height not exceeding $$$b$$$. Two TV sets are considered different if they have different screen width or different screen height.

Input format:
The first line contains four integers $$$a$$$, $$$b$$$, $$$x$$$, $$$y$$$ ($$$1 \le a, b, x, y \le 10^{18}$$$) — the constraints on the screen width and height, and on the aspect ratio.

Output format:
Print one integer — the number of different variants to choose TV screen width and screen height so that they meet the aforementioned constraints.

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

Note:
In the first example, there are $$$3$$$ possible variants: $$$(5, 3)$$$, $$$(10, 6)$$$, $$$(15, 9)$$$.

In the second example, there is no TV set meeting the constraints.

In the third example, there is only one variant: $$$(3, 2)$$$.

Example input:
17 15 5 3

Example output:
3

Example input:
14 16 7 22

Example output:
0

Editorial:
Firstly let's make $$$x$$$ and $$$y$$$ coprime. To do so, we calculate $$$g = gcd(x, y)$$$ and then divide both numbers by $$$g$$$.
Then the pair $$$(w, h)$$$ is included in the answer if the following conditions are met: $$$w \le a$$$, $$$h \le b$$$, and there exists some positive integer $$$k$$$ such that $$$w = kx$$$ and $$$h = ky$$$. Furthermore, each such pair is uniquely determined by this integer $$$k$$$. So we can reduce our task to counting the number of positive integers $$$k$$$ such that $$$kx \le a$$$ and $$$ky \le b$$$, and that is just $$$min(\lfloor \frac{a}{x} \rfloor, \lfloor \frac{b}{y} \rfloor)$$$.
Noldbach problem
Contest: Codeforces Beta Round 17
Difficulty rating: 1000
Tags: brute force, math, number theory

Nick is interested in prime numbers. Once he read about Goldbach problem. It states that every even integer greater than 2 can be expressed as the sum of two primes. That got Nick's attention and he decided to invent a problem of his own and call it Noldbach problem. Since Nick is interested only in prime numbers, Noldbach problem states that at least k prime numbers from 2 to n inclusively can be expressed as the sum of three integer numbers: two neighboring prime numbers and 1. For example, 19 = 7 + 11 + 1, or 13 = 5 + 7 + 1.

Two prime numbers are called neighboring if there are no other prime numbers between them.

You are to help Nick, and find out if he is right or wrong.

Input format:
The first line of the input contains two integers n (2 ≤ n ≤ 1000) and k (0 ≤ k ≤ 1000).

Output format:
Output YES if at least k prime numbers from 2 to n inclusively can be expressed as it was described above. Otherwise output NO.

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

Note:
In the first sample the answer is YES since at least two numbers can be expressed as it was described (for example, 13 and 19). In the second sample the answer is NO since it is impossible to express 7 prime numbers from 2 to 45 in the desired form.

Example input:
27 2

Example output:
YES

Example input:
45 7

Example output:
NO

Editorial:
Hierarchy
Contest: Codeforces Beta Round 17
Difficulty rating: 1500
Tags: dfs and similar, dsu, greedy, shortest paths

Nick's company employed n people. Now Nick needs to build a tree hierarchy of «supervisor-surbodinate» relations in the company (this is to say that each employee, except one, has exactly one supervisor). There are m applications written in the following form: «employee ai is ready to become a supervisor of employee bi at extra cost ci». The qualification qj of each employee is known, and for each application the following is true: qai > qbi.

Would you help Nick calculate the minimum cost of such a hierarchy, or find out that it is impossible to build it.

Input format:
The first input line contains integer n (1 ≤ n ≤ 1000) — amount of employees in the company. The following line contains n space-separated numbers qj (0 ≤ qj ≤ 106)— the employees' qualifications. The following line contains number m (0 ≤ m ≤ 10000) — amount of received applications. The following m lines contain the applications themselves, each of them in the form of three space-separated numbers: ai, bi and ci (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 106). Different applications can be similar, i.e. they can come from one and the same employee who offered to become a supervisor of the same person but at a different cost. For each application qai > qbi.

Output format:
Output the only line — the minimum cost of building such a hierarchy, or -1 if it is impossible to build it.

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

Note:
In the first sample one of the possible ways for building a hierarchy is to take applications with indexes 1, 2 and 4, which give 11 as the minimum total cost. In the second sample it is impossible to build the required hierarchy, so the answer is -1.

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

Example output:
11

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

Example output:
-1

Editorial:
Balance
Contest: Codeforces Beta Round 17
Difficulty rating: 2500
Tags: dp

Nick likes strings very much, he likes to rotate them, sort them, rearrange characters within a string... Once he wrote a random string of characters a, b, c on a piece of paper and began to perform the following operations:

- to take two adjacent characters and replace the second character with the first one,
- to take two adjacent characters and replace the first character with the second one

To understand these actions better, let's take a look at a string «abc». All of the following strings can be obtained by performing one of the described operations on «abc»: «bbc», «abb», «acc». Let's denote the frequency of a character for each of the characters a, b and c as the number of occurrences of this character in the string. For example, for string «abc»: |a| = 1, |b| = 1, |c| = 1, and for string «bbc»: |a| = 0, |b| = 2, |c| = 1.

While performing the described operations, Nick sometimes got balanced strings. Let's say that a string is balanced, if the frequencies of each character differ by at most 1. That is  - 1 ≤ |a| - |b| ≤ 1,  - 1 ≤ |a| - |c| ≤ 1 и  - 1 ≤ |b| - |c| ≤ 1.

Would you help Nick find the number of different balanced strings that can be obtained by performing the operations described above, perhaps multiple times, on the given string s. This number should be calculated modulo 51123987.

Input format:
The first line contains integer n (1 ≤ n ≤ 150) — the length of the given string s. Next line contains the given string s. The initial string can be balanced as well, in this case it should be counted too. The given string s consists only of characters a, b and c.

Output format:
Output the only number — the number of different balanced strings that can be obtained by performing the described operations, perhaps multiple times, on the given string s, modulo 51123987.

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

Note:
In the first sample it is possible to get 51 different strings through the described operations, but only 7 of them are balanced: «abca», «bbca», «bcca», «bcaa», «abcc», «abbc», «aabc». In the second sample: «abbc», «aabc», «abcc». In the third sample there is only one balanced string — «ab» itself.

Example input:
4
abca

Example output:
7

Example input:
4
abbc

Example output:
3

Editorial:
Notepad
Contest: Codeforces Beta Round 17
Difficulty rating: 2400
Tags: number theory

Nick is attracted by everything unconventional. He doesn't like decimal number system any more, and he decided to study other number systems. A number system with base b caught his attention. Before he starts studying it, he wants to write in his notepad all the numbers of length n without leading zeros in this number system. Each page in Nick's notepad has enough space for c numbers exactly. Nick writes every suitable number only once, starting with the first clean page and leaving no clean spaces. Nick never writes number 0 as he has unpleasant memories about zero divide.

Would you help Nick find out how many numbers will be written on the last page.

Input format:
The only input line contains three space-separated integers b, n and c (2 ≤ b < 10106, 1 ≤ n < 10106, 1 ≤ c ≤ 109). You may consider that Nick has infinite patience, endless amount of paper and representations of digits as characters. The numbers doesn't contain leading zeros.

Output format:
In the only line output the amount of numbers written on the same page as the last number.

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

Note:
In both samples there are exactly 4 numbers of length 3 in binary number system. In the first sample Nick writes 3 numbers on the first page and 1 on the second page. In the second sample all the 4 numbers can be written on the first page.

Example input:
2 3 3

Example output:
1

Example input:
2 3 4

Example output:
4

Editorial:
Palisection
Contest: Codeforces Beta Round 17
Difficulty rating: 2900
Tags: strings

In an English class Nick had nothing to do at all, and remembered about wonderful strings called palindromes. We should remind you that a string is called a palindrome if it can be read the same way both from left to right and from right to left. Here are examples of such strings: «eye», «pop», «level», «aba», «deed», «racecar», «rotor», «madam».

Nick started to look carefully for all palindromes in the text that they were reading in the class. For each occurrence of each palindrome in the text he wrote a pair — the position of the beginning and the position of the ending of this occurrence in the text. Nick called each occurrence of each palindrome he found in the text subpalindrome. When he found all the subpalindromes, he decided to find out how many different pairs among these subpalindromes cross. Two subpalindromes cross if they cover common positions in the text. No palindrome can cross itself.

Let's look at the actions, performed by Nick, by the example of text «babb». At first he wrote out all subpalindromes:

• «b» — 1..1

• «bab» — 1..3

• «a» — 2..2

• «b» — 3..3

• «bb» — 3..4

• «b» — 4..4

Then Nick counted the amount of different pairs among these subpalindromes that cross. These pairs were six:

1. 1..1 cross with 1..3

2. 1..3 cross with 2..2

3. 1..3 cross with 3..3

4. 1..3 cross with 3..4

5. 3..3 cross with 3..4

6. 3..4 cross with 4..4

Since it's very exhausting to perform all the described actions manually, Nick asked you to help him and write a program that can find out the amount of different subpalindrome pairs that cross. Two subpalindrome pairs are regarded as different if one of the pairs contains a subpalindrome that the other does not.

Input format:
The first input line contains integer n (1 ≤ n ≤ 2·106) — length of the text. The following line contains n lower-case Latin letters (from a to z).

Output format:
In the only line output the amount of different pairs of two subpalindromes that cross each other. Output the answer modulo 51123987.

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

Example input:
4
babb

Example output:
6

Example input:
2
aa

Example output:
2

Editorial:
Bits
Contest: Codeforces Round 276 (Div. 1)
Difficulty rating: 1700
Tags: bitmasks, constructive algorithms

Let's denote as $$\operatorname{popcount}(x)$$ the number of bits set ('1' bits) in the binary representation of the non-negative integer x.

You are given multiple queries consisting of pairs of integers l and r. For each query, find the x, such that l ≤ x ≤ r, and $$\operatorname{popcount}(x)$$ is maximum possible. If there are multiple such numbers find the smallest of them.

Input format:
The first line contains integer n — the number of queries (1 ≤ n ≤ 10000).

Each of the following n lines contain two integers li, ri — the arguments for the corresponding query (0 ≤ li ≤ ri ≤ 1018).

Output format:
For each query print the answer in a separate line.

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

Note:
The binary representations of numbers from 1 to 10 are listed below:

110 = 12

210 = 102

310 = 112

410 = 1002

510 = 1012

610 = 1102

710 = 1112

810 = 10002

910 = 10012

1010 = 10102

Example input:
3
1 2
2 4
1 10

Example output:
1
3
7

Editorial:
Maximum Value
Contest: Codeforces Round 276 (Div. 1)
Difficulty rating: 2100
Tags: binary search, math, sortings, two pointers

You are given a sequence a consisting of n integers. Find the maximum possible value of $$a_i \bmod a_j$$ (integer remainder of ai divided by aj), where 1 ≤ i, j ≤ n and ai ≥ aj.

Input format:
The first line contains integer n — the length of the sequence (1 ≤ n ≤ 2·105).

The second line contains n space-separated integers ai (1 ≤ ai ≤ 106).

Output format:
Print the answer to the problem.

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

Example input:
3
3 4 5

Example output:
2

Editorial:
Strange Sorting
Contest: Codeforces Round 276 (Div. 1)
Difficulty rating: 2600
Tags: implementation, math

How many specific orders do you know? Ascending order, descending order, order of ascending length, order of ascending polar angle... Let's have a look at another specific order: d-sorting. This sorting is applied to the strings of length at least d, where d is some positive integer. The characters of the string are sorted in following manner: first come all the 0-th characters of the initial string, then the 1-st ones, then the 2-nd ones and so on, in the end go all the (d - 1)-th characters of the initial string. By the i-th characters we mean all the character whose positions are exactly i modulo d. If two characters stand on the positions with the same remainder of integer division by d, their relative order after the sorting shouldn't be changed. The string is zero-indexed. For example, for string 'qwerty':

Its 1-sorting is the string 'qwerty' (all characters stand on 0 positions),

Its 2-sorting is the string 'qetwry' (characters 'q', 'e' and 't' stand on 0 positions and characters 'w', 'r' and 'y' are on 1 positions),

Its 3-sorting is the string 'qrwtey' (characters 'q' and 'r' stand on 0 positions, characters 'w' and 't' stand on 1 positions and characters 'e' and 'y' stand on 2 positions),

Its 4-sorting is the string 'qtwyer',

Its 5-sorting is the string 'qywert'.

You are given string S of length n and m shuffling operations of this string. Each shuffling operation accepts two integer arguments k and d and transforms string S as follows. For each i from 0 to n - k in the increasing order we apply the operation of d-sorting to the substring S[i..i + k - 1]. Here S[a..b] represents a substring that consists of characters on positions from a to b inclusive.

After each shuffling operation you need to print string S.

Input format:
The first line of the input contains a non-empty string S of length n, consisting of lowercase and uppercase English letters and digits from 0 to 9.

The second line of the input contains integer m – the number of shuffling operations (1 ≤ m·n ≤ 106).

Following m lines contain the descriptions of the operations consisting of two integers k and d (1 ≤ d ≤ k ≤ n).

Output format:
After each operation print the current state of string S.

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

Note:
Here is detailed explanation of the sample. The first modification is executed with arguments k = 4, d = 2. That means that you need to apply 2-sorting for each substring of length 4 one by one moving from the left to the right. The string will transform in the following manner:

qwerty  →  qewrty  →  qerwty  →  qertwy

Thus, string S equals 'qertwy' at the end of first query.

The second modification is executed with arguments k = 6, d = 3. As a result of this operation the whole string S is replaced by its 3-sorting:

qertwy  →  qtewry

The third modification is executed with arguments k = 5, d = 2.

qtewry  →  qertwy  →  qetyrw

Example input:
qwerty
3
4 2
6 3
5 2

Example output:
qertwy
qtewry
qetyrw

Editorial:
Kindergarten
Contest: Codeforces Round 276 (Div. 1)
Difficulty rating: 2400
Tags: data structures, dp, greedy

In a kindergarten, the children are being divided into groups. The teacher put the children in a line and associated each child with his or her integer charisma value. Each child should go to exactly one group. Each group should be a nonempty segment of consecutive children of a line. A group's sociability is the maximum difference of charisma of two children in the group (in particular, if the group consists of one child, its sociability equals a zero).

The teacher wants to divide the children into some number of groups in such way that the total sociability of the groups is maximum. Help him find this value.

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

The second line contains n integers ai — the charisma of the i-th child ( - 109 ≤ ai ≤ 109).

Output format:
Print the maximum possible total sociability of all groups.

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

Note:
In the first test sample one of the possible variants of an division is following: the first three children form a group with sociability 2, and the two remaining children form a group with sociability 1.

In the second test sample any division leads to the same result, the sociability will be equal to 0 in each group.

Example input:
5
1 2 3 1 2

Example output:
3

Example input:
3
3 3 3

Example output:
0

Editorial:
Sign on Fence
Contest: Codeforces Round 276 (Div. 1)
Difficulty rating: 2500
Tags: binary search, constructive algorithms, data structures

Bizon the Champion has recently finished painting his wood fence. The fence consists of a sequence of n panels of 1 meter width and of arbitrary height. The i-th panel's height is hi meters. The adjacent planks follow without a gap between them.

After Bizon painted the fence he decided to put a "for sale" sign on it. The sign will be drawn on a rectangular piece of paper and placed on the fence so that the sides of the sign are parallel to the fence panels and are also aligned with the edges of some panels. Bizon the Champion introduced the following constraints for the sign position:

1. The width of the sign should be exactly w meters.
2. The sign must fit into the segment of the fence from the l-th to the r-th panels, inclusive (also, it can't exceed the fence's bound in vertical direction).

The sign will be really pretty, So Bizon the Champion wants the sign's height to be as large as possible.

You are given the description of the fence and several queries for placing sign. For each query print the maximum possible height of the sign that can be placed on the corresponding segment of the fence with the given fixed width of the sign.

Input format:
The first line of the input contains integer n — the number of panels in the fence (1 ≤ n ≤ 105).

The second line contains n space-separated integers hi, — the heights of the panels (1 ≤ hi ≤ 109).

The third line contains an integer m — the number of the queries (1 ≤ m ≤ 105).

The next m lines contain the descriptions of the queries, each query is represented by three integers l, r and w (1 ≤ l ≤ r ≤ n, 1 ≤ w ≤ r - l + 1) — the segment of the fence and the width of the sign respectively.

Output format:
For each query print the answer on a separate line — the maximum height of the sign that can be put in the corresponding segment of the fence with all the conditions being satisfied.

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

Note:
The fence described in the sample looks as follows:

The possible positions for the signs for all queries are given below.

The optimal position of the sign for the first query.

The optimal position of the sign for the second query.

The optimal position of the sign for the third query.

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

Example output:
2
3
1

Editorial:
k-Multiple Free Set
Contest: Codeforces Round 168 (Div. 1)
Difficulty rating: 1500
Tags: binary search, greedy, sortings

A k-multiple free set is a set of integers where there is no pair of integers where one is equal to another integer multiplied by k. That is, there are no two integers x and y (x < y) from the set, such that y = x·k.

You're given a set of n distinct positive integers. Your task is to find the size of it's largest k-multiple free subset.

Input format:
The first line of the input contains two integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ 109). The next line contains a list of n distinct positive integers a1, a2, ..., an (1 ≤ ai ≤ 109).

All the numbers in the lines are separated by single spaces.

Output format:
On the only line of the output print the size of the largest k-multiple free subset of {a1, a2, ..., an}.

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

Note:
In the sample input one of the possible maximum 2-multiple free subsets is {4, 5, 6}.

Example input:
6 2
2 3 6 5 4 10

Example output:
3

Editorial: