1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Case of Fake Numbers
Contest: Codeforces Round 310 (Div. 2)
Difficulty rating: 1100
Tags: brute force, implementation

Andrewid the Android is a galaxy-famous detective. He is now investigating a case of frauds who make fake copies of the famous Stolp's gears, puzzles that are as famous as the Rubik's cube once was.

Its most important components are a button and a line of n similar gears. Each gear has n teeth containing all numbers from 0 to n - 1 in the counter-clockwise order. When you push a button, the first gear rotates clockwise, then the second gear rotates counter-clockwise, the the third gear rotates clockwise an so on.

Besides, each gear has exactly one active tooth. When a gear turns, a new active tooth is the one following after the current active tooth according to the direction of the rotation. For example, if n = 5, and the active tooth is the one containing number 0, then clockwise rotation makes the tooth with number 1 active, or the counter-clockwise rotating makes the tooth number 4 active.

Andrewid remembers that the real puzzle has the following property: you can push the button multiple times in such a way that in the end the numbers on the active teeth of the gears from first to last form sequence 0, 1, 2, ..., n - 1. Write a program that determines whether the given puzzle is real or fake.

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

The second line contains n digits a1, a2, ..., an (0 ≤ ai ≤ n - 1) — the sequence of active teeth: the active tooth of the i-th gear contains number ai.

Output format:
In a single line print "Yes" (without the quotes), if the given Stolp's gears puzzle is real, and "No" (without the quotes) otherwise.

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

Note:
In the first sample test when you push the button for the first time, the sequence of active teeth will be 2 2 1, when you push it for the second time, you get 0 1 2.

Example input:
3
1 0 0

Example output:
Yes

Example input:
5
4 2 1 4 3

Example output:
Yes

Editorial:
If you press the button n times the gears will return to the initial state. So the simplest solution is just to simulate pressing the button for n times: if the gears are real then after several steps the active teeth sequence will be 0, 1, 2, ..., n - 1.
Au Pont Rouge
Contest: VK Cup 2019-2020 - Elimination Round (Engine)
Difficulty rating: 2800
Tags: binary search, dp, strings

VK just opened its second HQ in St. Petersburg! Side of its office building has a huge string $$$s$$$ written on its side. This part of the office is supposed to be split into $$$m$$$ meeting rooms in such way that meeting room walls are strictly between letters on the building. Obviously, meeting rooms should not be of size 0, but can be as small as one letter wide. Each meeting room will be named after the substring of $$$s$$$ written on its side.

For each possible arrangement of $$$m$$$ meeting rooms we ordered a test meeting room label for the meeting room with lexicographically minimal name. When delivered, those labels got sorted backward lexicographically.

What is printed on $$$k$$$th label of the delivery?

Input format:
In the first line, you are given three integer numbers $$$n, m, k$$$ — length of string $$$s$$$, number of planned meeting rooms to split $$$s$$$ into and number of the interesting label ($$$2 \le n \le 1\,000; 1 \le m \le 1\,000; 1 \le k \le 10^{18}$$$).

Second input line has string $$$s$$$, consisting of $$$n$$$ lowercase english letters.

For given $$$n, m, k$$$ there are at least $$$k$$$ ways to split $$$s$$$ into $$$m$$$ substrings.

Output format:
Output single string – name of meeting room printed on $$$k$$$-th label of the delivery.

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

Note:
In the first example, delivery consists of the labels "aba", "ab", "a".

In the second example, delivery consists of $$$3060$$$ labels. The first label is "aupontrougevkof" and the last one is "a".

Example input:
4 2 1
abac

Example output:
aba

Example input:
19 5 1821
aupontrougevkoffice

Example output:
au

Editorial:
Let's list all distinct substrings, sort them and make a binary search. Now, we need to count number of ways to make minimal string no more then given one. Let's count inverse value — number of wat to make minimal string greater. It could be done by quadratic dynamic programming $$$dp_{pos, count}$$$ — number of ways to split suffix starting at pos to count string all of which are greater then given value. Let's find first position where suffix differs which given string. If next character in suffix is smaller, no part can start here and answer is zero. Otherwise, any longer part is acceptable, so we need to find $$$\sum\limits_{i > lcp(S, s[pos:])}{dp_{i, count-1}}$$$, which can be done in O(1) time by suffix sums and precalculating lcp for all pairs of suffixes. Later can by done by another quadratic dynamic programming. lcp of two suffix is equal to 0 if first letter differs, and equal to lcp of two smaller suffixes +1 otherwise.
Tourism
Contest: VK Cup 2019-2020 - Elimination Round (Engine)
Difficulty rating: 2300
Tags: dp, graphs, probabilities

Masha lives in a country with $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$. She lives in the city number $$$1$$$.

There is a direct train route between each pair of distinct cities $$$i$$$ and $$$j$$$, where $$$i \neq j$$$. In total there are $$$n(n-1)$$$ distinct routes. Every route has a cost, cost for route from $$$i$$$ to $$$j$$$ may be different from the cost of route from $$$j$$$ to $$$i$$$.

Masha wants to start her journey in city $$$1$$$, take exactly $$$k$$$ routes from one city to another and as a result return to the city $$$1$$$. Masha is really careful with money, so she wants the journey to be as cheap as possible. To do so Masha doesn't mind visiting a city multiple times or even taking the same route multiple times.

Masha doesn't want her journey to have odd cycles. Formally, if you can select visited by Masha city $$$v$$$, take odd number of routes used by Masha in her journey and return to the city $$$v$$$, such journey is considered unsuccessful.

Help Masha to find the cheapest (with minimal total cost of all taken routes) successful journey.

Input format:
First line of input had two integer numbers $$$n,k$$$ ($$$2 \leq n \leq 80; 2 \leq k \leq 10$$$): number of cities in the country and number of routes in Masha's journey. It is guaranteed that $$$k$$$ is even.

Next $$$n$$$ lines hold route descriptions: $$$j$$$-th number in $$$i$$$-th line represents the cost of route from $$$i$$$ to $$$j$$$ if $$$i \neq j$$$, and is 0 otherwise (there are no routes $$$i \to i$$$). All route costs are integers from $$$0$$$ to $$$10^8$$$.

Output format:
Output a single integer — total cost of the cheapest Masha's successful journey.

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

Example input:
5 8
0 1 2 2 0
0 0 1 1 2
0 1 0 0 0
2 1 1 0 0
2 0 1 2 0

Example output:
2

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

Example output:
3

Editorial:
There are two different solutions possible.
First, one is to fix all even vertices in the path. It can be done in $$$O(n^{k/2 - 1})$$$ time. If it's done, we need to join them by the minimal path of length 2, not going through these vertices. It can be done by precalculating 6 minimal paths of length 2 between each pair of vertices and ignoring no more than 5 best ones until good one found.
Another solution is a randomized one. Let's color all vertices in 2 colors in a random way. We can find the best path which is consistent with given coloring in $$$O(k \cdot E)$$$ time using dynamic programming. With probability $$$\frac{1}{512}$$$ best path overall is consistent with coloring. So, if one repeats this operation $$$512 \cdot 20$$$ time, probability of fail would be about $$$\left(\frac{511}{512}\right)^{512 \cdot 20} \approx e^{-20} \approx 2\cdot 10^{-9}$$$.
Choosing Teams
Contest: Codeforces Round 246 (Div. 2)
Difficulty rating: 800
Tags: greedy, implementation, sortings

The Saratov State University Olympiad Programmers Training Center (SSU OPTC) has n students. For each student you know the number of times he/she has participated in the ACM ICPC world programming championship. According to the ACM ICPC rules, each person can participate in the world championship at most 5 times.

The head of the SSU OPTC is recently gathering teams to participate in the world championship. Each team must consist of exactly three people, at that, any person cannot be a member of two or more teams. What maximum number of teams can the head make if he wants each team to participate in the world championship with the same members at least k times?

Input format:
The first line contains two integers, n and k (1 ≤ n ≤ 2000; 1 ≤ k ≤ 5). The next line contains n integers: y1, y2, ..., yn (0 ≤ yi ≤ 5), where yi shows the number of times the i-th person participated in the ACM ICPC world championship.

Output format:
Print a single number — the answer to the problem.

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

Note:
In the first sample only one team could be made: the first, the fourth and the fifth participants.

In the second sample no teams could be created.

In the third sample two teams could be created. Any partition into two teams fits.

Example input:
5 2
0 4 5 1 0

Example output:
1

Example input:
6 4
0 1 2 3 4 5

Example output:
0

Editorial:
Football Kit
Contest: Codeforces Round 246 (Div. 2)
Difficulty rating: 1200
Tags: brute force, greedy, implementation

Consider a football tournament where n teams participate. Each team has two football kits: for home games, and for away games. The kit for home games of the i-th team has color xi and the kit for away games of this team has color yi (xi ≠ yi).

In the tournament, each team plays exactly one home game and exactly one away game with each other team (n(n - 1) games in total). The team, that plays the home game, traditionally plays in its home kit. The team that plays an away game plays in its away kit. However, if two teams has the kits of the same color, they cannot be distinguished. In this case the away team plays in its home kit.

Calculate how many games in the described tournament each team plays in its home kit and how many games it plays in its away kit.

Input format:
The first line contains a single integer n (2 ≤ n ≤ 105) — the number of teams. Next n lines contain the description of the teams. The i-th line contains two space-separated numbers xi, yi (1 ≤ xi, yi ≤ 105; xi ≠ yi) — the color numbers for the home and away kits of the i-th team.

Output format:
For each team, print on a single line two space-separated integers — the number of games this team is going to play in home and away kits, correspondingly. Print the answers for the teams in the order they appeared in the input.

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

Example input:
2
1 2
2 1

Example output:
2 0
2 0

Example input:
3
1 2
2 1
1 3

Example output:
3 1
4 0
2 2

Editorial:
Prime Swaps
Contest: Codeforces Round 246 (Div. 2)
Difficulty rating: 1800
Tags: greedy, sortings

You have an array a[1], a[2], ..., a[n], containing distinct integers from 1 to n. Your task is to sort this array in increasing order with the following operation (you may need to apply it multiple times):

- choose two indexes, i and j (1 ≤ i < j ≤ n; (j - i + 1) is a prime number);
- swap the elements on positions i and j; in other words, you are allowed to apply the following sequence of assignments: tmp = a[i], a[i] = a[j], a[j] = tmp (tmp is a temporary variable).

You do not need to minimize the number of used operations. However, you need to make sure that there are at most 5n operations.

Input format:
The first line contains integer n (1 ≤ n ≤ 105). The next line contains n distinct integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n).

Output format:
In the first line, print integer k (0 ≤ k ≤ 5n) — the number of used operations. Next, print the operations. Each operation must be printed as "i j" (1 ≤ i < j ≤ n; (j - i + 1) is a prime).

If there are multiple answers, you can print any of them.

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

Example input:
3
3 2 1

Example output:
1
1 3

Example input:
2
1 2

Example output:
0

Editorial:
Prefixes and Suffixes
Contest: Codeforces Round 246 (Div. 2)
Difficulty rating: 2000
Tags: dp, string suffix structures, strings, two pointers

You have a string s = s1s2...s|s|, where |s| is the length of string s, and si its i-th character.

Let's introduce several definitions:

- A substring s[i..j] (1 ≤ i ≤ j ≤ |s|) of string s is string sisi + 1...sj.
- The prefix of string s of length l (1 ≤ l ≤ |s|) is string s[1..l].
- The suffix of string s of length l (1 ≤ l ≤ |s|) is string s[|s| - l + 1..|s|].

Your task is, for any prefix of string s which matches a suffix of string s, print the number of times it occurs in string s as a substring.

Input format:
The single line contains a sequence of characters s1s2...s|s| (1 ≤ |s| ≤ 105) — string s. The string only consists of uppercase English letters.

Output format:
In the first line, print integer k (0 ≤ k ≤ |s|) — the number of prefixes that match a suffix of string s. Next print k lines, in each line print two integers li ci. Numbers li ci mean that the prefix of the length li matches the suffix of length li and occurs in string s as a substring ci times. Print pairs li ci in the order of increasing li.

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

Example input:
ABACABA

Example output:
3
1 4
3 2
7 1

Example input:
AAA

Example output:
3
1 3
2 2
3 1

Editorial:
Square Tiling
Contest: Codeforces Round 246 (Div. 2)
Difficulty rating: 2300
Tags: constructive algorithms, greedy

You have an n × m rectangle table, its cells are not initially painted. Your task is to paint all cells of the table. The resulting picture should be a tiling of the table with squares. More formally:

- each cell must be painted some color (the colors are marked by uppercase Latin letters);
- we will assume that two cells of the table are connected if they are of the same color and share a side; each connected region of the table must form a square.

Given n and m, find lexicographically minimum coloring of the table that meets the described properties.

Input format:
The first line contains two integers, n and m (1 ≤ n, m ≤ 100).

Output format:
Print lexicographically minimum coloring of the table that meets the described conditions.

One coloring (let's call it X) is considered lexicographically less than the other one (let's call it Y), if:

- consider all the table cells from left to right and from top to bottom (first, the first cell in the first row, then the second cell in the first row and so on);
- let's find in this order the first cell that has distinct colors in two colorings;
- the letter that marks the color of the cell in X, goes alphabetically before the letter that marks the color of the cell in Y.

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

Example input:
1 3

Example output:
ABA

Example input:
2 2

Example output:
AA
AA

Editorial:
Morning run
Contest: Croc Champ 2013 - Finals
Difficulty rating: 2000

People like to be fit. That's why many of them are ready to wake up at dawn, go to the stadium and run. In this problem your task is to help a company design a new stadium.

The city of N has a shabby old stadium. Many people like it and every morning thousands of people come out to this stadium to run. The stadium can be represented as a circle, its length is exactly l meters with a marked start line. However, there can't be simultaneous start in the morning, so exactly at 7, each runner goes to his favorite spot on the stadium and starts running from there. Note that not everybody runs in the same manner as everybody else. Some people run in the clockwise direction, some of them run in the counter-clockwise direction. It mostly depends on the runner's mood in the morning, so you can assume that each running direction is equiprobable for each runner in any fixed morning.

The stadium is tiny and is in need of major repair, for right now there only is one running track! You can't get too playful on a single track, that's why all runners keep the same running speed — exactly 1 meter per a time unit. Nevertheless, the runners that choose different directions bump into each other as they meet.

The company wants to design a new stadium, but they first need to know how bad the old one is. For that they need the expectation of the number of bumpings by t time units after the running has begun. Help the company count the required expectation. Note that each runner chooses a direction equiprobably, independently from the others and then all runners start running simultaneously at 7 a.m. Assume that each runner runs for t time units without stopping. Consider the runners to bump at a certain moment if at that moment they found themselves at the same point in the stadium. A pair of runners can bump more than once.

Input format:
The first line of the input contains three integers n, l, t (1 ≤ n ≤ 106, 1 ≤ l ≤ 109, 1 ≤ t ≤ 109). The next line contains n distinct integers a1, a2, ..., an (0 ≤ a1 < a2 < ... < an < l), here ai is the clockwise distance from the start line to the i-th runner's starting position.

Output format:
Print a single real number — the answer to the problem with absolute or relative error of at most 10 - 6.

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

Note:
There are two runners in the first example. If the first runner run clockwise direction, then in 1 time unit he will be 1m away from the start line. If the second runner run counter-clockwise direction then in 1 time unit he will be also 1m away from the start line. And it is the only possible way to meet. We assume that each running direction is equiprobable, so the answer for the example is equal to 0.5·0.5 = 0.25.

Example input:
2 5 1
0 2

Example output:
0.2500000000

Example input:
3 7 3
0 1 6

Example output:
1.5000000000

Editorial:
Context Advertising
Contest: Croc Champ 2013 - Finals
Difficulty rating: 2100
Tags: dp, two pointers

Advertising has become part of our routine. And now, in the era of progressive technologies, we need your ideas to make advertising better!

In this problem we'll look at a simplified version of context advertising. You've got a text, consisting of exactly n words. A standard advertising banner has exactly r lines, each line can contain at most c characters. The potential customer always likes it when they can see lots of advertising, so you should determine which maximum number of consecutive words from the text can be written on the banner. Single words in one line of the banner should be separated by spaces. You are allowed to insert more than one space at once. Note that you are not allowed to break the words, that is, each word in the text must occupy exactly one line in the banner. Besides, you cannot change the word order, that is, if you read the banner text consecutively, from top to bottom and from left to right, you should get some consecutive part of the advertisement text.

More formally, the statement can be written like that. Let's say that all words are indexed from 1 to n in the order in which they occur in the advertisement text. Then you have to choose all words, starting from some i-th one and ending with some j-th one (1 ≤ i ≤ j ≤ n), so that all of them could be written on the banner. There must be as many words as possible. See the samples for clarifications.

Input format:
The first input line contains three integers n, r, c (1 ≤ n, r, c ≤ 106; r × c ≤ 106). The next line contains a text, consisting of n words. The words consist only of lowercase English letters and are not empty. The words in the lines are separated by single spaces. The total number of characters in all words doesn't exceed 5·106.

Output format:
Print at most r lines, in each line print at most c characters — the optimal advertisement banner. If there are multiple advertisement banners, print any of them.

Note that some lines of the banner can be empty. You are allowed not to print such lines.

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

Example input:
9 4 12
this is a sample text for croc final round

Example output:
this is a
sample text
for croc
final round

Example input:
9 1 9
this is a sample text for croc final round

Example output:
this is a

Editorial:
Memory for Arrays
Contest: Croc Champ 2013 - Finals
Difficulty rating: 1900

You get to work and turn on the computer. You start coding and give little thought to the RAM role in the whole process. In this problem your task is to solve one of the problems you encounter in your computer routine.

We'll consider the RAM as a sequence of cells that can contain data. Some cells already contain some data, some are empty. The empty cells form the so-called memory clusters. Thus, a memory cluster is a sequence of some consecutive empty memory cells.

You have exactly n memory clusters, the i-th cluster consists of ai cells. You need to find memory for m arrays in your program. The j-th array takes 2bj consecutive memory cells. There possibly isn't enough memory for all m arrays, so your task is to determine what maximum number of arrays can be located in the available memory clusters. Of course, the arrays cannot be divided between the memory clusters. Also, no cell can belong to two arrays.

Input format:
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 106). The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109). The next line contains m integers b1, b2, ..., bm (1 ≤ 2bi ≤ 109).

Output format:
Print a single integer — the answer to the problem.

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

Note:
In the first example you are given memory clusters with sizes 8, 4, 3, 2, 2 and arrays with sizes 8, 4, 4. There are few ways to obtain an answer equals 2: you can locate array with size 8 to the cluster with size 8, and one of the arrays with size 4 to the cluster with size 4. Another way is to locate two arrays with size 4 to the one cluster with size 8.

In the second example you are given 10 memory clusters with size 1 and 6 arrays with size 1. You can choose any 6 clusters and locate all given arrays to them.

Example input:
5 3
8 4 3 2 2
3 2 2

Example output:
2

Example input:
10 6
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0

Example output:
6

Editorial:
Tennis Rackets
Contest: Croc Champ 2013 - Finals
Difficulty rating: 2700

Professional sport is more than hard work. It also is the equipment, designed by top engineers. As an example, let's take tennis. Not only should you be in great shape, you also need an excellent racket! In this problem your task is to contribute to the development of tennis and to help to design a revolutionary new concept of a racket!

The concept is a triangular racket. Ant it should be not just any triangle, but a regular one. As soon as you've chosen the shape, you need to stretch the net. By the time you came the rocket had n holes drilled on each of its sides. The holes divide each side into equal n + 1 parts. At that, the m closest to each apex holes on each side are made for better ventilation only and you cannot stretch the net through them. The next revolutionary idea as to stretch the net as obtuse triangles through the holes, so that for each triangle all apexes lay on different sides. Moreover, you need the net to be stretched along every possible obtuse triangle. That's where we need your help — help us to count the number of triangles the net is going to consist of.

Two triangles are considered to be different if their pictures on the fixed at some position racket are different.

Input format:
The first and the only input line contains two integers n, m $$( 1 \leq n \leq 3 2 0 0 0, 0 \leq m \leq \frac { n } { 2 } )$$.

Output format:
Print a single number — the answer to the problem.

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

Note:
For the following picture n = 8, m = 2. White circles are the holes for ventilation, red circles — holes for net stretching. One of the possible obtuse triangles is painted red.

Example input:
3 0

Example output:
9

Example input:
4 0

Example output:
24

Editorial: