1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Running Track
Contest: Codeforces Round 338 (Div. 2)
Difficulty rating: 2000
Tags: dp, greedy, strings, trees

A boy named Ayrat lives on planet AMI-1511. Each inhabitant of this planet has a talent. Specifically, Ayrat loves running, moreover, just running is not enough for him. He is dreaming of making running a real art.

First, he wants to construct the running track with coating t. On planet AMI-1511 the coating of the track is the sequence of colored blocks, where each block is denoted as the small English letter. Therefore, every coating can be treated as a string.

Unfortunately, blocks aren't freely sold to non-business customers, but Ayrat found an infinite number of coatings s. Also, he has scissors and glue. Ayrat is going to buy some coatings s, then cut out from each of them exactly one continuous piece (substring) and glue it to the end of his track coating. Moreover, he may choose to flip this block before glueing it. Ayrat want's to know the minimum number of coating s he needs to buy in order to get the coating t for his running track. Of course, he also want's to know some way to achieve the answer.

Input format:
First line of the input contains the string s — the coating that is present in the shop. Second line contains the string t — the coating Ayrat wants to obtain. Both strings are non-empty, consist of only small English letters and their length doesn't exceed 2100.

Output format:
The first line should contain the minimum needed number of coatings n or -1 if it's impossible to create the desired coating.

If the answer is not -1, then the following n lines should contain two integers xi and yi — numbers of ending blocks in the corresponding piece. If xi ≤ yi then this piece is used in the regular order, and if xi > yi piece is used in the reversed order. Print the pieces in the order they should be glued to get the string t.

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

Note:
In the first sample string "cbaabc" = "cba" + "abc".

In the second sample: "ayrat" = "a" + "yr" + "at".

Example input:
abc
cbaabc

Example output:
2
3 1
1 3

Example input:
aaabrytaaa
ayrat

Example output:
3
1 1
6 5
8 7

Editorial:
The idea is that if we can make a substring of string t from i to j(using k operations) then we can also make substrings from i + 1 to j and from i to j - 1 using k operations. So if we have already made some i-th prefix of t, we should try to update it using the longest possible substring. So let's search for it with O(n * m) complexity(here m is the lenth of the longest substring). Overall complexity is $$\mathcal{O}(\sum(m*n)) = \mathcal{O}((\sum m)*n) = \mathcal{O}(n*n)$$
Multipliers
Contest: Codeforces Round 338 (Div. 2)
Difficulty rating: 2000
Tags: math, number theory

Ayrat has number n, represented as it's prime factorization pi of size m, i.e. n = p1·p2·...·pm. Ayrat got secret information that that the product of all divisors of n taken modulo 109 + 7 is the password to the secret data base. Now he wants to calculate this value.

Input format:
The first line of the input contains a single integer m (1 ≤ m ≤ 200 000) — the number of primes in factorization of n.

The second line contains m primes numbers pi (2 ≤ pi ≤ 200 000).

Output format:
Print one integer — the product of all divisors of n modulo 109 + 7.

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

Note:
In the first sample n = 2·3 = 6. The divisors of 6 are 1, 2, 3 and 6, their product is equal to 1·2·3·6 = 36.

In the second sample 2·3·2 = 12. The divisors of 12 are 1, 2, 3, 4, 6 and 12. 1·2·3·4·6·12 = 1728.

Example input:
2
2 3

Example output:
36

Example input:
3
2 3 2

Example output:
1728

Editorial:
Обозначим d(x) — к-во делителей числа x, f(x) — произведение делителей числа. Пусть x = {p1}α1{p2}α2...{pn}αn, тогда d(x) = (α1 + 1)·(α2 + 1)... (αn + 1)
$$f(x) = x^{\frac{d(x)}{2}}$$. Есть $$\left\lfloor \frac{d(x)}{2} \right\rfloor$$ пар делителитей вида (x / c, c), $$c \leq \sqrt{x}$$, и если x — точный квадрат добавляется ещё 1 делитель : $$\sqrt{x}$$.
для простого m и a ≠ 0 верно $$a^{m-1} \equiv 1 (\bmod m) \Rightarrow a^x \equiv a^{x\% (m-1)} (\bmod m)$$
Можно заметь, что $$d(ab) = d(a)d(b), \quad f(ab) = f(a)^{d(b)}f(b)^{d(a)}, \quad f(p^k) = p^{\frac{k(k+1)}{2}}$$, если a и b взаимно простые.
Пользуясь этими свойствами нетрудно посчитать ответ:
Hexagons
Contest: Codeforces Round 338 (Div. 2)
Difficulty rating: 2100
Tags: binary search, implementation, math

Ayrat is looking for the perfect code. He decided to start his search from an infinite field tiled by hexagons. For convenience the coordinate system is introduced, take a look at the picture to see how the coordinates of hexagon are defined:

Ayrat is searching through the field. He started at point (0, 0) and is moving along the spiral (see second picture). Sometimes he forgets where he is now. Help Ayrat determine his location after n moves.

Input format:
The only line of the input contains integer n (0 ≤ n ≤ 1018) — the number of Ayrat's moves.

Output format:
Print two integers x and y — current coordinates of Ayrat coordinates.

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

Example input:
3

Example output:
-2 0

Example input:
7

Example output:
3 2

Editorial:
Let's see how the coordinates are changing while we move from current cell to one of the 6 adjastent cells - let's call this 6 typed of moves. If we know the number of moves of each type on our way, then we know the coordinates of the end of the way. We will divide the way into rings:  Let's count the number of moves of each type for the first ring. Next ring will have one more move of each type. Lenth of each ring = lenth of previous + 6. It is an arithmetic progression. Using well-known formulas and binary search we calculate the number of the last ring and overall lenth of previous rings. Now we have to brute-force 6 types of the last move and calculate the answer.
Bear and Friendship Condition
Contest: VK Cup 2017 - Round 1
Difficulty rating: 1500
Tags: dfs and similar, dsu, graphs

Bear Limak examines a social network. Its main functionality is that two members can become friends (then they can talk with each other and share funny pictures).

There are n members, numbered 1 through n. m pairs of members are friends. Of course, a member can't be a friend with themselves.

Let A-B denote that members A and B are friends. Limak thinks that a network is reasonable if and only if the following condition is satisfied: For every three distinct members (X, Y, Z), if X-Y and Y-Z then also X-Z.

For example: if Alan and Bob are friends, and Bob and Ciri are friends, then Alan and Ciri should be friends as well.

Can you help Limak and check if the network is reasonable? Print "YES" or "NO" accordingly, without the quotes.

Input format:
The first line of the input contain two integers n and m (3 ≤ n ≤ 150 000, $$0 \leq m \leq min(150\ 000, \frac{n \cdot (n-1)}{2})$$) — the number of members and the number of pairs of members that are friends.

The i-th of the next m lines contains two distinct integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi). Members ai and bi are friends with each other. No pair of members will appear more than once in the input.

Output format:
If the given network is reasonable, print "YES" in a single line (without the quotes). Otherwise, print "NO" in a single line (without the quotes).

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

Note:
The drawings below show the situation in the first sample (on the left) and in the second sample (on the right). Each edge represents two members that are friends. The answer is "NO" in the second sample because members (2, 3) are friends and members (3, 4) are friends, while members (2, 4) are not.

Example input:
4 3
1 3
3 4
1 4

Example output:
YES

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

Example output:
NO

Editorial:
The main observation is that you should print "YES" if the graph is a set of disjoint cliques (in each connected non-clique there is a triple of vertices X,Y,Z that X-Y and Y-Z but not X-Z). To check if each connected component is a clique, you can run dfs and count vertices and edges in the connected component — it's a clique if and only if $$edges = \frac{vertices \cdot (vertices - 1)}{2}$$.
Secrets
Contest: Codeforces Round 194 (Div. 1)
Difficulty rating: 1600
Tags: greedy

Gerald has been selling state secrets at leisure. All the secrets cost the same: n marks. The state which secrets Gerald is selling, has no paper money, only coins. But there are coins of all positive integer denominations that are powers of three: 1 mark, 3 marks, 9 marks, 27 marks and so on. There are no coins of other denominations. Of course, Gerald likes it when he gets money without the change. And all buyers respect him and try to give the desired sum without change, if possible. But this does not always happen.

One day an unlucky buyer came. He did not have the desired sum without change. Then he took out all his coins and tried to give Gerald a larger than necessary sum with as few coins as possible. What is the maximum number of coins he could get?

The formal explanation of the previous paragraph: we consider all the possible combinations of coins for which the buyer can not give Gerald the sum of n marks without change. For each such combination calculate the minimum number of coins that can bring the buyer at least n marks. Among all combinations choose the maximum of the minimum number of coins. This is the number we want.

Input format:
The single line contains a single integer n (1 ≤ n ≤ 1017).

Please, do not use the %lld specifier to read or write 64 bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output format:
In a single line print an integer: the maximum number of coins the unlucky buyer could have paid with.

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

Note:
In the first test case, if a buyer has exactly one coin of at least 3 marks, then, to give Gerald one mark, he will have to give this coin. In this sample, the customer can not have a coin of one mark, as in this case, he will be able to give the money to Gerald without any change.

In the second test case, if the buyer had exactly three coins of 3 marks, then, to give Gerald 4 marks, he will have to give two of these coins. The buyer cannot give three coins as he wants to minimize the number of coins that he gives.

Example input:
1

Example output:
1

Example input:
4

Example output:
2

Editorial:
Chips
Contest: Codeforces Round 194 (Div. 1)
Difficulty rating: 1800
Tags: greedy

Gerald plays the following game. He has a checkered field of size n × n cells, where m various cells are banned. Before the game, he has to put a few chips on some border (but not corner) board cells. Then for n - 1 minutes, Gerald every minute moves each chip into an adjacent cell. He moves each chip from its original edge to the opposite edge. Gerald loses in this game in each of the three cases:

- At least one of the chips at least once fell to the banned cell.
- At least once two chips were on the same cell.
- At least once two chips swapped in a minute (for example, if you stand two chips on two opposite border cells of a row with even length, this situation happens in the middle of the row).

In that case he loses and earns 0 points. When nothing like that happened, he wins and earns the number of points equal to the number of chips he managed to put on the board. Help Gerald earn the most points.

Input format:
The first line contains two space-separated integers n and m (2 ≤ n ≤ 1000, 0 ≤ m ≤ 105) — the size of the field and the number of banned cells. Next m lines each contain two space-separated integers. Specifically, the i-th of these lines contains numbers xi and yi (1 ≤ xi, yi ≤ n) — the coordinates of the i-th banned cell. All given cells are distinct.

Consider the field rows numbered from top to bottom from 1 to n, and the columns — from left to right from 1 to n.

Output format:
Print a single integer — the maximum points Gerald can earn in this game.

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

Note:
In the first test the answer equals zero as we can't put chips into the corner cells.

In the second sample we can place one chip into either cell (1, 2), or cell (3, 2), or cell (2, 1), or cell (2, 3). We cannot place two chips.

In the third sample we can only place one chip into either cell (2, 1), or cell (2, 4).

Example input:
3 1
2 2

Example output:
0

Example input:
3 0

Example output:
1

Editorial:
Lucky Tickets
Contest: Codeforces Round 194 (Div. 1)
Difficulty rating: 2700
Tags: brute force, constructive algorithms

Gerald has a friend, Pollard. Pollard is interested in lucky tickets (ticket is a sequence of digits). At first he thought that a ticket is lucky if between some its digits we can add arithmetic signs and brackets so that the result obtained by the arithmetic expression was number 100. But he quickly analyzed all such tickets and moved on to a more general question. Now he explores k-lucky tickets.

Pollard sais that a ticket is k-lucky if we can add arithmetic operation signs between its digits to the left or right of them (i.e., "+", "-", " × ") and brackets so as to obtain the correct arithmetic expression whose value would equal k. For example, ticket "224201016" is 1000-lucky as ( - 2 - (2 + 4)) × (2 + 0) + 1016 = 1000.

Pollard was so carried away by the lucky tickets that he signed up for a seminar on lucky tickets and, as far as Gerald knows, Pollard will attend it daily at 7 pm in some famous institute and will commute to it in the same tram for m days. In this tram tickets have eight digits. And Gerald wants to make a surprise for Pollard: each day Pollard will receive a tram k-lucky ticket. The conductor has already agreed to give Pollard certain tickets during all these m days and he only wants Gerald to tell him what kind of tickets to give out. In this regard, help Gerald pick exactly m distinct k-lucky tickets.

Input format:
The single line contains two integers k and m (0 ≤ k ≤ 104, 1 ≤ m ≤ 3·105).

Output format:
Print m lines. Each line must contain exactly 8 digits — the k-winning ticket. The tickets may begin with 0, all tickets must be distinct. If there are more than m distinct k-lucky tickets, print any m of them. It is guaranteed that at least m distinct k-lucky tickets exist. The tickets can be printed in any order.

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

Example input:
0 3

Example output:
00000000
00000001
00000002

Example input:
7 4

Example output:
00000007
00000016
00000017
00000018

Editorial:
Characteristics of Rectangles
Contest: Codeforces Round 194 (Div. 1)
Difficulty rating: 2100
Tags: binary search, bitmasks, brute force, implementation, sortings

Gerald found a table consisting of n rows and m columns. As a prominent expert on rectangular tables, he immediately counted the table's properties, that is, the minimum of the numbers in the corners of the table (minimum of four numbers). However, he did not like the final value — it seemed to be too small. And to make this value larger, he decided to crop the table a little: delete some columns on the left and some on the right, as well as some rows from the top and some from the bottom. Find what the maximum property of the table can be after such cropping. Note that the table should have at least two rows and at least two columns left in the end. The number of cropped rows or columns from each of the four sides can be zero.

Input format:
The first line contains two space-separated integers n and m (2 ≤ n, m ≤ 1000). The following n lines describe the table. The i-th of these lines lists the space-separated integers ai, 1, ai, 2, ..., ai, m (0 ≤ ai, j ≤ 109) — the m numbers standing in the i-th row of the table.

Output format:
Print the answer to the problem.

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

Note:
In the first test case Gerald cannot crop the table — table contains only two rows and only two columns.

In the second test case if we'll crop the table, the table will contain zero in some corner cell. Also initially it contains two zeros in the corner cells, so the answer is 0.

Example input:
2 2
1 2
3 4

Example output:
1

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

Example output:
0

Editorial:
Summer Earnings
Contest: Codeforces Round 194 (Div. 1)
Difficulty rating: 2500
Tags: binary search, bitmasks, brute force, geometry, sortings

Many schoolchildren look for a job for the summer, and one day, when Gerald was still a schoolboy, he also decided to work in the summer. But as Gerald was quite an unusual schoolboy, he found quite unusual work. A certain Company agreed to pay him a certain sum of money if he draws them three identical circles on a plane. The circles must not interfere with each other (but they may touch each other). He can choose the centers of the circles only from the n options granted by the Company. He is free to choose the radius of the circles himself (all three radiuses must be equal), but please note that the larger the radius is, the more he gets paid.

Help Gerald earn as much as possible.

Input format:
The first line contains a single integer n — the number of centers (3 ≤ n ≤ 3000). The following n lines each contain two integers xi, yi ( - 104 ≤ xi, yi ≤ 104) — the coordinates of potential circle centers, provided by the Company.

All given points are distinct.

Output format:
Print a single real number — maximum possible radius of circles. The answer will be accepted if its relative or absolute error doesn't exceed 10 - 6.

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

Example input:
3
0 1
1 0
1 1

Example output:
0.50000000000000000000

Example input:
7
2 -3
-2 -3
3 0
-3 -1
1 -2
2 -2
-1 0

Example output:
1.58113883008418980000

Editorial:
In-game Chat
Contest: Technocup 2021 - Elimination Round 3
Difficulty rating: 800
Tags: implementation

You have been assigned to develop a filter for bad messages in the in-game chat. A message is a string $$$S$$$ of length $$$n$$$, consisting of lowercase English letters and characters ')'. The message is bad if the number of characters ')' at the end of the string strictly greater than the number of remaining characters. For example, the string ")bc)))" has three parentheses at the end, three remaining characters, and is not considered bad.

Input format:
The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 100$$$). Description of the $$$t$$$ test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 100$$$). The second line of each test case contains a string $$$S$$$ of length $$$n$$$, consisting of lowercase English letters and characters ')'.

Output format:
For each of $$$t$$$ test cases, print "Yes" if the string is bad. Otherwise, print "No".

You can print each letter in any case (upper or lower).

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

Example input:
5
2
))
12
gl))hf))))))
9
gege)))))
14
)aa))b))))))))
1
)

Example output:
Yes
No
Yes
Yes
Yes

Editorial:
You should count the number of parentheses at the end of the string, suppose there are $$$x$$$ such parentheses. Then if $$$x > \frac{n}{2}$$$, message is bad. Note that you should divide $$$n$$$ by $$$2$$$ without rounding. Or you can compare $$$2 \cdot x$$$ and $$$n$$$ instead. If $$$2 \cdot x > n$$$, the message is bad.
Fair Numbers
Contest: Technocup 2021 - Elimination Round 3
Difficulty rating: 1000
Tags: brute force, number theory

We call a positive integer number fair if it is divisible by each of its nonzero digits. For example, $$$102$$$ is fair (because it is divisible by $$$1$$$ and $$$2$$$), but $$$282$$$ is not, because it isn't divisible by $$$8$$$. Given a positive integer $$$n$$$. Find the minimum integer $$$x$$$, such that $$$n \leq x$$$ and $$$x$$$ is fair.

Input format:
The first line contains number of test cases $$$t$$$ ($$$1 \leq t \leq 10^3$$$). Each of the next $$$t$$$ lines contains an integer $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$).

Output format:
For each of $$$t$$$ test cases print a single integer — the least fair number, which is not less than $$$n$$$.

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

Note:
Explanations for some test cases:

- In the first test case number $$$1$$$ is fair itself.
- In the second test case number $$$288$$$ is fair (it's divisible by both $$$2$$$ and $$$8$$$). None of the numbers from $$$[282, 287]$$$ is fair, because, for example, none of them is divisible by $$$8$$$.

Example input:
4
1
282
1234567890
1000000000000000000

Example output:
1
288
1234568040
1000000000000000000

Editorial:
Let's call a number super-fair if it is divisible by each of the numbers $$$1..9$$$. It is fair to say that super-fair numbers are also divisible by $$$LCM(1..9)$$$ which is equal to $$$2520$$$. The answer isn't larger than the nearest super-fair number, which means that you can increase the original $$$n$$$ by one until it becomes fair. We will determine if the number is fair by checking each of its digits separately.
Peaceful Rooks
Contest: Technocup 2021 - Elimination Round 3
Difficulty rating: 1700
Tags: dfs and similar, dsu, graphs

You are given a $$$n \times n$$$ chessboard. Rows and columns of the board are numbered from $$$1$$$ to $$$n$$$. Cell $$$(x, y)$$$ lies on the intersection of column number $$$x$$$ and row number $$$y$$$.

Rook is a chess piece, that can in one turn move any number of cells vertically or horizontally. There are $$$m$$$ rooks ($$$m < n$$$) placed on the chessboard in such a way that no pair of rooks attack each other. I.e. there are no pair of rooks that share a row or a column.

In one turn you can move one of the rooks any number of cells vertically or horizontally. Additionally, it shouldn't be attacked by any other rook after movement. What is the minimum number of moves required to place all the rooks on the main diagonal?

The main diagonal of the chessboard is all the cells $$$(i, i)$$$, where $$$1 \le i \le n$$$.

Input format:
The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^3$$$). Description of the $$$t$$$ test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ — size of the chessboard and the number of rooks ($$$2 \leq n \leq 10^5$$$, $$$1 \leq m < n$$$). Each of the next $$$m$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ — positions of rooks, $$$i$$$-th rook is placed in the cell $$$(x_i, y_i)$$$ ($$$1 \leq x_i, y_i \leq n$$$). It's guaranteed that no two rooks attack each other in the initial placement.

The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each of $$$t$$$ test cases print a single integer — the minimum number of moves required to place all the rooks on the main diagonal.

It can be proved that this is always possible.

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

Note:
Possible moves for the first three test cases:

1. $$$(2, 3) \to (2, 2)$$$
2. $$$(2, 1) \to (2, 3)$$$, $$$(1, 2) \to (1, 1)$$$, $$$(2, 3) \to (2, 2)$$$
3. $$$(2, 3) \to (2, 4)$$$, $$$(2, 4) \to (4, 4)$$$, $$$(3, 1) \to (3, 3)$$$, $$$(1, 2) \to (1, 1)$$$

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

Example output:
1
3
4
2

Editorial:
Consider rooks as edges in a graph. The position $$$(x, y)$$$ will correspond to an edge $$$(x \to y)$$$. From the condition that there're at most one edge exits leading from each vertex and at most one edge leading to each vertex, it follows that the graph decomposes into cycles, paths, and loops (edges of type $$$v \to v$$$).
What happens to the graph when we move the rook? The edge changes exactly one of its endpoints. By such operations, we must turn all edges into loops, and the constraint on the number of edges going in and out of a vertex must be satisfied. A path is quite easy to turn into loops, just start from one end. A cycle must first be turned into a path, which is always possible. We've only spent one extra move, it's not hard to see that this is optimal.
The answer is the number of rooks minus the number of loops plus the number of cycles.