1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Conveyor Belts
Contest: Codeforces Round 863 (Div. 3)
Difficulty rating: 1000
Tags: implementation, math

Conveyor matrix $$$m_n$$$ is matrix of size $$$n \times n$$$, where $$$n$$$ is an even number. The matrix consists of concentric ribbons moving clockwise.

In other words, the conveyor matrix for $$$n = 2$$$ is simply a matrix $$$2 \times 2$$$, whose cells form a cycle of length $$$4$$$ clockwise. For any natural $$$k \ge 2$$$, the matrix $$$m_{2k}$$$ is obtained by adding to the matrix $$$m_{2k - 2}$$$ an outer layer forming a clockwise cycle.

The conveyor matrix $$$8 \times 8$$$.

You are standing in a cell with coordinates $$$x_1, y_1$$$ and you want to get into a cell with coordinates $$$x_2, y_2$$$. A cell has coordinates $$$x, y$$$ if it is located at the intersection of the $$$x$$$th row and the $$$y$$$th column.

Standing on some cell, every second you will move to the cell next in the direction of movement of the tape on which you are. You can also move to a neighboring cell by spending one unit of energy. Movements happen instantly and you can make an unlimited number of them at any time.

Your task is to find the minimum amount of energy that will have to be spent to get from the cell with coordinates $$$x_1, y_1$$$ to the cell with coordinates $$$x_2, y_2$$$.

For example, $$$n=8$$$ initially you are in a cell with coordinates $$$1,3$$$ and you want to get into a cell with coordinates $$$6, 4$$$. You can immediately make $$$2$$$ movements, once you are in a cell with coordinates $$$3, 3$$$, and then after $$$8$$$ seconds you will be in the right cell.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — the number of test cases.

The descriptions of the test cases follow.

The description of each test case consists of one string containing five integers $$$n$$$, $$$x_1$$$, $$$y_1$$$, $$$x_2$$$ and $$$y_2$$$ ($$$1 \le x_1, y_1, x_2, y_2 \le n \le 10^9$$$) — matrix size and the coordinates of the start and end cells. It is guaranteed that the number $$$n$$$ is even.

Output format:
For each test case, print one integer in a separate line — the minimum amount of energy that will have to be spent to get from the cell with coordinates $$$x_1, y_1$$$ to the cell with coordinates $$$x_2, y_2$$$.

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

Example input:
5
2 1 1 2 2
4 1 4 3 3
8 1 3 4 6
100 10 20 50 100
1000000000 123456789 987654321 998244353 500000004

Example output:
0
1
2
9
10590032

Editorial:
Note that the conveyor matrix $$$n \times n$$$ consists of $$$n$$$ cycles, through each of which we can move without wasting energy. Now you need to find the distance between the cycles where the start and end cells are located. In one step from any cycle, you can go either to the cycle that is closer to the edge of the matrix, or to the cycle that is further from the edge of the matrix. It turns out that it is enough to find on which cycles there are cells on the edge and take their difference modulo.
Living Sequence
Contest: Codeforces Round 863 (Div. 3)
Difficulty rating: 1500
Tags: binary search, dp, math, number theory

In Japan, the number $$$4$$$ reads like death, so Bob decided to build a live sequence. Living sequence $$$a$$$ contains all natural numbers that do not contain the digit $$$4$$$. $$$a = [1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, \ldots]$$$.

For example, the number $$$1235$$$ is part of the sequence $$$a$$$, but the numbers $$$4321$$$, $$$443$$$ are not part of the sequence $$$a$$$.

Bob realized that he does not know how to quickly search for a particular number by the position $$$k$$$ in the sequence, so he asks for your help.

For example, if Bob wants to find the number at position $$$k = 4$$$ (indexing from $$$1$$$), you need to answer $$$a_k = 5$$$.

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

In the only line of each test case, there is a single integer $$$k$$$ ($$$1 \le k \le 10^{12}$$$) — the position Bob is interested in.

Output format:
For each test case, print on a separate line the number $$$a_k$$$ in indexing with $$$1$$$.

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

Example input:
7
3
5
22
10
100
12345
827264634912

Example output:
3
6
25
11
121
18937
2932285320890

Editorial:
Note that any number in the sequence can be made up of $$$9$$$ possible digits (all digits except $$$4$$$). Then let's find the first digit of the answer, notice that it is just $$$x$$$ or $$$x+1$$$, where $$$x \cdot 9^{l-1} \le k$$$ (where $$$l$$$ — the length of the number we're looking for) and $$$x$$$ — the maximum. Note that $$$x$$$ simply corresponds to a digit in the base-$$$9$$$ numeral system.
Why is this so? Because without the first digit we can assemble any numbers with $$$9$$$ possible digits, and we can put the digits $$$0...x$$$ except $$$4$$$ in the first place. Thus, in the answer, the first digit will be $$$x$$$ if $$$x < 4$$$ and $$$x+1$$$ if $$$x \ge 4$$$.
Note that once the first digit is determined, the rest can be found the same way, since the prefix does not affect anything.
Vlad and the Nice Paths (easy version)
Contest: Codeforces Round 863 (Div. 3)
Difficulty rating: 2100
Tags: combinatorics, dp, math

This is an easy version of the problem, it differs from the hard one only by constraints on $$$n$$$ and $$$k$$$.

Vlad found a row of $$$n$$$ tiles and the integer $$$k$$$. The tiles are indexed from left to right and the $$$i$$$-th tile has the color $$$c_i$$$. After a little thought, he decided what to do with it.

You can start from any tile and jump to any number of tiles right, forming the path $$$p$$$. Let's call the path $$$p$$$ of length $$$m$$$ nice if:

- $$$p$$$ can be divided into blocks of length exactly $$$k$$$, that is, $$$m$$$ is divisible by $$$k$$$;
- $$$c_{p_1} = c_{p_2} = \ldots = c_{p_k}$$$;
- $$$c_{p_{k+1}} = c_{p_{k+2}} = \ldots = c_{p_{2k}}$$$;
- $$$\ldots$$$
- $$$c_{p_{m-k+1}} = c_{p_{m-k+2}} = \ldots = c_{p_{m}}$$$;

Your task is to find the number of nice paths of maximum length. Since this number may be too large, print it modulo $$$10^9 + 7$$$.

Input format:
The first line of each test contains the integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100$$$) — the number of tiles in a row and the length of the block.

The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, c_3, \dots, c_n$$$ ($$$1 \le c_i \le n$$$) — tile colors.

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

Output format:
Print $$$t$$$ numbers, each of which is the answer to the corresponding test case — the number of nice paths of maximum length modulo $$$10^9 + 7$$$.

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

Note:
In the first sample, it is impossible to make a nice path with a length greater than $$$0$$$.

In the second sample, we are interested in the following paths:

- $$$1 \rightarrow 3 \rightarrow 4 \rightarrow 5$$$
- $$$2 \rightarrow 4 \rightarrow 5 \rightarrow 7$$$
- $$$1 \rightarrow 3 \rightarrow 5 \rightarrow 7$$$
- $$$1 \rightarrow 3 \rightarrow 4 \rightarrow 7$$$

In the third example, any path of length $$$8$$$ is nice.

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

Example output:
1
4
165
3
1

Editorial:
Let's use the dynamic programming. Let $$$dp[i][j]$$$ be the number of paths on the prefix $$$i$$$ of $$$j$$$ blocks of the same color. To make transitions in such dynamics, for the position $$$i$$$, we will iterate over the position $$$p$$$ in which the block started. Denote as $$$s$$$ the number of the same elements as $$$c_i$$$ and $$$c_p$$$ between them, then such a transition creates $$$dp[p-1][j-1] \cdot C_{k-2}^{s}$$$ combinations. This solution works in $$$O(n^3)$$$ complexity.
Vlad and the Nice Paths (hard version)
Contest: Codeforces Round 863 (Div. 3)
Difficulty rating: 2200
Tags: binary search, combinatorics, data structures, dp, math, two pointers

This is hard version of the problem, it differs from the easy one only by constraints on $$$n$$$ and $$$k$$$.

Vlad found a row of $$$n$$$ tiles and the integer $$$k$$$. The tiles are indexed from left to right and the $$$i$$$-th tile has the color $$$c_i$$$. After a little thought, he decided what to do with it.

You can start from any tile and jump to any number of tiles right, forming the path $$$p$$$. Let's call the path $$$p$$$ of length $$$m$$$ nice if:

- $$$p$$$ can be divided into blocks of length exactly $$$k$$$, that is, $$$m$$$ is divisible by $$$k$$$;
- $$$c_{p_1} = c_{p_2} = \ldots = c_{p_k}$$$;
- $$$c_{p_{k+1}} = c_{p_{k+2}} = \ldots = c_{p_{2k}}$$$;
- $$$\ldots$$$
- $$$c_{p_{m-k+1}} = c_{p_{m-k+2}} = \ldots = c_{p_{m}}$$$;

Your task is to find the number of nice paths of maximum length. Since this number may be too large, print it modulo $$$10^9 + 7$$$.

Input format:
The first line of each test contains the integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 5000$$$) — the number of tiles in a row and the length of the block.

The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, c_3, \dots, c_n$$$ ($$$1 \le c_i \le n$$$) — tile colors.

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

Output format:
Print $$$t$$$ numbers, each of which is the answer to the corresponding test case — the number of nice paths of maximum length modulo $$$10^9 + 7$$$.

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

Note:
In the first sample, it is impossible to make a nice path with a length greater than $$$0$$$.

In the second sample, we are interested in the following paths:

- $$$1 \rightarrow 3 \rightarrow 4 \rightarrow 5$$$
- $$$2 \rightarrow 4 \rightarrow 5 \rightarrow 7$$$
- $$$1 \rightarrow 3 \rightarrow 5 \rightarrow 7$$$
- $$$1 \rightarrow 3 \rightarrow 4 \rightarrow 7$$$

In the third example, any path of length $$$8$$$ is nice.

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

Example output:
1
4
165
3
1

Editorial:
To solve the hard version, let's modify the simple version solution. Note that the $$$j$$$ parameter can be discarded, since we only need paths of maximum length on each prefix. Now, as $$$dp[i]$$$, we denote a pair of the number of maximum paths and the number of blocks in them. For the position $$$i$$$, we will find the position closest to the left, from which we can start a block, and so we will find out what is the maximum for $$$i$$$. We will update $$$dp[i]$$$ until the maximum of the position being sorted is suitable for us.
Best Permutation
Contest: Educational Codeforces Round 135 (Rated for Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, greedy

Let's define the value of the permutation $$$p$$$ of $$$n$$$ integers $$$1$$$, $$$2$$$, ..., $$$n$$$ (a permutation is an array where each element from $$$1$$$ to $$$n$$$ occurs exactly once) as follows:

- initially, an integer variable $$$x$$$ is equal to $$$0$$$;
- if $$$x < p_1$$$, then add $$$p_1$$$ to $$$x$$$ (set $$$x = x + p_1$$$), otherwise assign $$$0$$$ to $$$x$$$;
- if $$$x < p_2$$$, then add $$$p_2$$$ to $$$x$$$ (set $$$x = x + p_2$$$), otherwise assign $$$0$$$ to $$$x$$$;
- ...
- if $$$x < p_n$$$, then add $$$p_n$$$ to $$$x$$$ (set $$$x = x + p_n$$$), otherwise assign $$$0$$$ to $$$x$$$;
- the value of the permutation is $$$x$$$ at the end of this process.

For example, for $$$p = [4, 5, 1, 2, 3, 6]$$$, the value of $$$x$$$ changes as follows: $$$0, 4, 9, 0, 2, 5, 11$$$, so the value of the permutation is $$$11$$$.

You are given an integer $$$n$$$. Find a permutation $$$p$$$ of size $$$n$$$ with the maximum possible value among all permutations of size $$$n$$$. If there are several such permutations, you can print any of them.

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

The only line of each test case contains one integer $$$n$$$ ($$$4 \le n \le 100$$$).

Output format:
For each test case, print $$$n$$$ integers — the permutation $$$p$$$ of size $$$n$$$ with the maximum possible value among all permutations of size $$$n$$$.

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

Example input:
3
4
5
6

Example output:
2 1 3 4
1 2 3 4 5
4 5 1 2 3 6

Editorial:
Let $$$x_i$$$ be the value of the variable $$$x$$$ after $$$i$$$ steps. Note that $$$x_{n-1}$$$ should be less than $$$p_n$$$ for $$$x_n$$$ to be not equal to $$$0$$$. It means that $$$x_n$$$ does not exceed $$$2p_n - 1$$$. It turns out that for $$$n \ge 4$$$ there is always a permutation such that $$$x_n$$$ is equal to $$$2n - 1$$$.
The only thing left is to find out how to build such a permutation. There are many suitable permutations, let's consider one of the possible options. For an even $$$n$$$, a suitable permutation is $$$[2, 1, 4, 3, \ dots, n - 2, n - 3, n - 1, n]$$$. You can see that $$$x$$$ in such a permutation changes as follows: $$$[0, 2, 0, 4, 0, \dots, n - 2, 0, n - 1, 2n - 1]$$$. For an odd $$$n$$$, there is a similar permutation $$$[1, 3, 2, 5, 4, \dots, n - 2, n - 3, n - 1, n]$$$, where $$$x$$$ changes as follows: $$$[0, 1, 4, 0, 5, 0, \dots, n-2, 0, n - 1, 2n - 1]$$$.
Polo the Penguin and Segments
Contest: Codeforces Round 177 (Div. 2)
Difficulty rating: 1100
Tags: brute force, implementation

Little penguin Polo adores integer segments, that is, pairs of integers [l; r] (l ≤ r).

He has a set that consists of n integer segments: [l1; r1], [l2; r2], ..., [ln; rn]. We know that no two segments of this set intersect. In one move Polo can either widen any segment of the set 1 unit to the left or 1 unit to the right, that is transform [l; r] to either segment [l - 1; r], or to segment [l; r + 1].

The value of a set of segments that consists of n segments [l1; r1], [l2; r2], ..., [ln; rn] is the number of integers x, such that there is integer j, for which the following inequality holds, lj ≤ x ≤ rj.

Find the minimum number of moves needed to make the value of the set of Polo's segments divisible by k.

Input format:
The first line contains two integers n and k (1 ≤ n, k ≤ 105). Each of the following n lines contain a segment as a pair of integers li and ri ( - 105 ≤ li ≤ ri ≤ 105), separated by a space.

It is guaranteed that no two segments intersect. In other words, for any two integers i, j (1 ≤ i < j ≤ n) the following inequality holds, min(ri, rj) < max(li, lj).

Output format:
In a single line print a single integer — the answer to the problem.

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

Example input:
2 3
1 2
3 4

Example output:
2

Example input:
3 7
1 2
3 3
4 7

Example output:
0

Editorial:
Polo the Penguin and Matrix
Contest: Codeforces Round 177 (Div. 2)
Difficulty rating: 1400
Tags: brute force, dp, implementation, sortings, ternary search

Little penguin Polo has an n × m matrix, consisting of integers. Let's index the matrix rows from 1 to n from top to bottom and let's index the columns from 1 to m from left to right. Let's represent the matrix element on the intersection of row i and column j as aij.

In one move the penguin can add or subtract number d from some matrix element. Find the minimum number of moves needed to make all matrix elements equal. If the described plan is impossible to carry out, say so.

Input format:
The first line contains three integers n, m and d (1 ≤ n, m ≤ 100, 1 ≤ d ≤ 104) — the matrix sizes and the d parameter. Next n lines contain the matrix: the j-th integer in the i-th row is the matrix element aij (1 ≤ aij ≤ 104).

Output format:
In a single line print a single integer — the minimum number of moves the penguin needs to make all matrix elements equal. If that is impossible, print "-1" (without the quotes).

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

Example input:
2 2 2
2 4
6 8

Example output:
4

Example input:
1 2 7
6 7

Example output:
-1

Editorial:
Measuring Lengths in Baden
Contest: Codeforces Testing Round 2
Difficulty rating: 1400
Tags: math

Lengths are measures in Baden in inches and feet. To a length from centimeters it is enough to know that an inch equals three centimeters in Baden and one foot contains 12 inches.

You are given a length equal to n centimeters. Your task is to convert it to feet and inches so that the number of feet was maximum. The result should be an integer rounded to the closest value containing an integral number of inches.

Note that when you round up, 1 cm rounds up to 0 inches and 2 cm round up to 1 inch.

Input format:
The only line contains an integer n (1 ≤ n ≤ 10000).

Output format:
Print two non-negative space-separated integers a and b, where a is the numbers of feet and b is the number of inches.

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

Example input:
42

Example output:
1 2

Example input:
5

Example output:
0 2

Editorial:
Simple XML
Contest: Codeforces Testing Round 2
Difficulty rating: 1000
Tags: implementation

Let's define a string <x> as an opening tag, where x is any small letter of the Latin alphabet. Each opening tag matches a closing tag of the type </x>, where x is the same letter.

Tegs can be nested into each other: in this case one opening and closing tag pair is located inside another pair.

Let's define the notion of a XML-text:

- an empty string is a XML-text
- if s is a XML-text, then s'=<a>+s+</a> also is a XML-text, where a is any small Latin letter
- if s1, s2 are XML-texts, then s1+s2 also is a XML-text

You are given a XML-text (it is guaranteed that the text is valid), your task is to print in the following form:

- each tag (opening and closing) is located on a single line
- print before the tag 2 * h spaces, where h is the level of the tag's nestedness.

Input format:
The input data consists on the only non-empty string — the XML-text, its length does not exceed 1000 characters. It is guaranteed that the text is valid. The text contains no spaces.

Output format:
Print the given XML-text according to the above-given rules.

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

Example input:
<a><b><c></c></b></a>

Example output:
<a>
<b>
<c>
</c>
</b>
</a>

Example input:
<a><b></b><d><c></c></d></a>

Example output:
<a>
<b>
</b>
<d>
<c>
</c>
</d>
</a>

Editorial:
Hobbits' Party
Contest: Codeforces Testing Round 2
Difficulty rating: 1600
Tags: constructive algorithms, greedy

Everyone knows that hobbits love to organize all sorts of parties and celebrations. There are n hobbits living in the Shire. They decided to organize the Greatest Party (GP) that would last for several days. Next day the hobbits wrote a guest list, some non-empty set containing all the inhabitants of the Shire. To ensure that everybody enjoy themselves and nobody gets bored, for any two days (say, days A and B) of the GP there existed at least one hobbit, invited to come on day A and on day B. However, to ensure that nobody has a row, for any three different days A, B, C there shouldn't be a hobbit invited on days A, B and C. The Shire inhabitants are keen on keeping the GP going for as long as possible. Your task is given number n, to indicate the GP's maximum duration and the guest lists for each day.

Input format:
The first line contains an integer n (3 ≤ n ≤ 10000), representing the number of hobbits.

Output format:
In the first output line print a number k — the maximum duration of GP in days. Then on k lines print the guest lists, (the guests should be separated by spaces). Print each guest list on the single line. Each list can contain an arbitrary positive number of hobbits. The hobbits are numbered with integers from 1 to n.

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

Example input:
4

Example output:
3
1 2
1 3
2 3

Example input:
5

Example output:
3
1 2
1 3
2 3

Editorial:
Two progressions
Contest: Codeforces Testing Round 2
Difficulty rating: 2200
Tags: constructive algorithms, greedy

An arithmetic progression is such a non-empty sequence of numbers where the difference between any two successive numbers is constant. This constant number is called common difference. For example, the sequence 3, 7, 11, 15 is an arithmetic progression. The definition implies that any sequences whose length equals 1 or 2 are arithmetic and all sequences whose length equals 0 are non-arithmetic.

You are given a sequence of different integers a1, a2, ..., an. You should either split it into two arithmetic progressions or find out that the operation is impossible to perform. Splitting assigns each member of the given sequence to one of two progressions, but the relative order of numbers does not change. Splitting is an inverse operation to merging.

Input format:
The first line contains a positive integer n (2 ≤ n ≤ 30000), n is the length of the given sequence. The second line contains elements of the given sequence a1, a2, ..., an ( - 108 ≤ ai ≤ 108). The elements of the progression are different integers.

Output format:
Print the required arithmetic progressions, one per line. The progressions can be positioned in any order. Each progression should contain at least one number. If there's no solution, then print "No solution" (without the quotes)in the only line of the input file. If there are several solutions, print any of them.

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

Note:
In the second sample another solution is also possible (number three can be assigned to the second progression): 1, 2 and 3, -2, -7.

Example input:
6
4 1 2 7 3 10

Example output:
1 2 3
4 7 10

Example input:
5
1 2 3 -2 -7

Example output:
1 2 3
-2 -7

Editorial:
MST Company
Contest: Codeforces Testing Round 2
Difficulty rating: 2400
Tags: binary search, graphs

The MST (Meaningless State Team) company won another tender for an important state reform in Berland.

There are n cities in Berland, some pairs of the cities are connected by roads. Each road has its price. One can move along any road in any direction. The MST team should carry out the repair works on some set of roads such that one can get from any city to any other one moving only along the repaired roads. Moreover, this set should contain exactly k capital roads (that is, the roads that start or finish in the capital). The number of the capital is 1.

As the budget has already been approved, the MST Company will profit by finding the set with minimum lengths of roads.

Input format:
The first input line contains three integers n, m, k (1 ≤ n ≤ 5000;0 ≤ m ≤ 105;0 ≤ k < 5000), where n is the number of cities in the country, m is the number of roads in the country, k is the number of capital roads in the required set. Then m lines enumerate the roads in question. Each road is specified by three numbers ai, bi, wi (1 ≤ ai, bi ≤ n; 1 ≤ w ≤ 105), where ai, bi are the numbers of cities linked by a road and wi is its length.

Between each pair of cities no more than one road exists. There are no roads that start and finish in one city. The capital's number is 1.

Output format:
In the first line print the number of roads in the required set. The second line should contain the numbers of roads included in the sought set. If the sought set does not exist, print -1.

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

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

Example output:
3
1 5 2

Editorial: