1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Fancy Fence
Contest: Codeforces Round 165 (Div. 2)
Difficulty rating: 1100
Tags: geometry, implementation, math

Emuskald needs a fence around his farm, but he is too lazy to build it himself. So he purchased a fence-building robot.

He wants the fence to be a regular polygon. The robot builds the fence along a single path, but it can only make fence corners at a single angle a.

Will the robot be able to build the fence Emuskald wants? In other words, is there a regular polygon which angles are equal to a?

Input format:
The first line of input contains an integer t (0 < t < 180) — the number of tests. Each of the following t lines contains a single integer a (0 < a < 180) — the angle the robot can make corners at measured in degrees.

Output format:
For each test, output on a single line "YES" (without quotes), if the robot can build a fence Emuskald wants, and "NO" (without quotes), if it is impossible.

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

Note:
In the first test case, it is impossible to build the fence, since there is no regular polygon with angle $$30^\circ$$.

In the second test case, the fence is a regular triangle, and in the last test case — a square.

Example input:
3
30
60
90

Example output:
NO
YES
YES

Editorial:
Multithreading
Contest: Codeforces Round 165 (Div. 2)
Difficulty rating: 1400
Tags: data structures, greedy, implementation

Emuskald is addicted to Codeforces, and keeps refreshing the main page not to miss any changes in the "recent actions" list. He likes to read thread conversations where each thread consists of multiple messages.

Recent actions shows a list of n different threads ordered by the time of the latest message in the thread. When a new message is posted in a thread that thread jumps on the top of the list. No two messages of different threads are ever posted at the same time.

Emuskald has just finished reading all his opened threads and refreshes the main page for some more messages to feed his addiction. He notices that no new threads have appeared in the list and at the i-th place in the list there is a thread that was at the ai-th place before the refresh. He doesn't want to waste any time reading old messages so he wants to open only threads with new messages.

Help Emuskald find out the number of threads that surely have new messages. A thread x surely has a new message if there is no such sequence of thread updates (posting messages) that both conditions hold:

1. thread x is not updated (it has no new messages);
2. the list order 1, 2, ..., n changes to a1, a2, ..., an.

Input format:
The first line of input contains an integer n, the number of threads (1 ≤ n ≤ 105). The next line contains a list of n space-separated integers a1, a2, ..., an where ai (1 ≤ ai ≤ n) is the old position of the i-th thread in the new list. It is guaranteed that all of the ai are distinct.

Output format:
Output a single integer — the number of threads that surely contain a new message.

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

Note:
In the first test case, threads 2 and 5 are placed before the thread 1, so these threads must contain new messages. Threads 1, 3 and 4 may contain no new messages, if only threads 2 and 5 have new messages.

In the second test case, there may be no new messages at all, since the thread order hasn't changed.

In the third test case, only thread 1 can contain no new messages.

Example input:
5
5 2 1 3 4

Example output:
2

Example input:
3
1 2 3

Example output:
0

Editorial:
Sereja and Periods
Contest: Codeforces Round 187 (Div. 1)
Difficulty rating: 2000
Tags: binary search, dfs and similar, strings

Let's introduce the designation $$[x,n] = x + x + \cdots + x = \sum_{i=1}^{n} x$$, where x is a string, n is a positive integer and operation " + " is the string concatenation operation. For example, [abc, 2] = abcabc.

We'll say that string s can be obtained from string t, if we can remove some characters from string t and obtain string s. For example, strings ab and aсba can be obtained from string xacbac, and strings bx and aaa cannot be obtained from it.

Sereja has two strings, w = [a, b] and q = [c, d]. He wants to find such maximum integer p (p > 0), that [q, p] can be obtained from string w.

Input format:
The first line contains two integers b, d (1 ≤ b, d ≤ 107). The second line contains string a. The third line contains string c. The given strings are not empty and consist of lowercase English letters. Their lengths do not exceed 100.

Output format:
In a single line print an integer — the largest number p. If the required value of p doesn't exist, print 0.

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

Example input:
10 3
abab
bab

Example output:
3

Editorial:
Sereja and Subsequences
Contest: Codeforces Round 187 (Div. 1)
Difficulty rating: 2000
Tags: data structures, dp

Sereja has a sequence that consists of n positive integers, a1, a2, ..., an.

First Sereja took a piece of squared paper and wrote all distinct non-empty non-decreasing subsequences of sequence a. Then for each sequence written on the squared paper, Sereja wrote on a piece of lines paper all sequences that do not exceed it.

A sequence of positive integers x = x1, x2, ..., xr doesn't exceed a sequence of positive integers y = y1, y2, ..., yr, if the following inequation holds: x1 ≤ y1, x2 ≤ y2, ..., xr ≤ yr.

Now Sereja wonders, how many sequences are written on the lines piece of paper. Help Sereja, find the required quantity modulo 1000000007 (109 + 7).

Input format:
The first line contains integer n (1 ≤ n ≤ 105). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 106).

Output format:
In the single line print the answer to the problem modulo 1000000007 (109 + 7).

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

Example input:
1
42

Example output:
42

Example input:
3
1 2 2

Example output:
13

Editorial:
Sereja and Straight Lines
Contest: Codeforces Round 187 (Div. 1)
Difficulty rating: 2500
Tags: binary search, data structures, geometry, sortings, two pointers

Sereja placed n points on a plane. Now Sereja wants to place on the plane two straight lines, intersecting at a right angle, so that one of the straight lines intersect the Ox axis at an angle of 45 degrees and the maximum distance from the points to the straight lines were minimum.

In this problem we consider the distance between points (x1, y1) and (x2, y2) equal |x1 - x2| + |y1 - y2|. The distance between the point and the straight lines is the minimum distance from the point to some point belonging to one of the lines.

Help Sereja, find the maximum distance from the points to the optimally located straight lines.

Input format:
The first line contains integer n (1 ≤ n ≤ 105). Next n lines contain the coordinates of the lines. The i-th line contains two integers xi, yi (|xi|, |yi| ≤ 109).

Output format:
In a single line print a real number — the answer to the problem. Your answer will be considered correct iff its absolute or relative error doesn't exceed 10 - 6.

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

Example input:
4
0 0
2 0
0 2
2 2

Example output:
0.000000000000000

Example input:
4
1 0
0 1
2 1
1 2

Example output:
1.000000000000000

Editorial:
Sereja and Squares
Contest: Codeforces Round 187 (Div. 1)
Difficulty rating: 2900
Tags: dp

Sereja painted n points on the plane, point number i (1 ≤ i ≤ n) has coordinates (i, 0). Then Sereja marked each point with a small or large English letter. Sereja don't like letter "x", so he didn't use it to mark points. Sereja thinks that the points are marked beautifully if the following conditions holds:

- all points can be divided into pairs so that each point will belong to exactly one pair;
- in each pair the point with the lesser abscissa will be marked with a small English letter and the point with the larger abscissa will be marked with the same large English letter;
- if we built a square on each pair, the pair's points will be the square's opposite points and the segment between them will be the square's diagonal, then among the resulting squares there won't be any intersecting or touching ones.

Little Petya erased some small and all large letters marking the points. Now Sereja wonders how many ways are there to return the removed letters so that the points were marked beautifully.

Input format:
The first line contains integer n the number of points (1 ≤ n ≤ 105). The second line contains a sequence consisting of n small English letters and question marks — the sequence of letters, that mark points, in order of increasing x-coordinate of points. Question marks denote the points without letters (Petya erased them). It is guaranteed that the input string doesn't contain letter "x".

Output format:
In a single line print the answer to the problem modulo 4294967296. If there is no way to return the removed letters, print number 0.

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

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

Example input:
4
a???

Example output:
50

Example input:
4
abc?

Example output:
0

Editorial:
Reorder
Contest: Codeforces Round 678 (Div. 2)
Difficulty rating: 800
Tags: math

For a given array $$$a$$$ consisting of $$$n$$$ integers and a given integer $$$m$$$ find if it is possible to reorder elements of the array $$$a$$$ in such a way that $$$\sum_{i=1}^{n}{\sum_{j=i}^{n}{\frac{a_j}{j}}}$$$ equals $$$m$$$? It is forbidden to delete elements as well as insert new elements. Please note that no rounding occurs during division, for example, $$$\frac{5}{2}=2.5$$$.

Input format:
The first line contains a single integer $$$t$$$ — the number of test cases ($$$1 \le t \le 100$$$). The test cases follow, each in two lines.

The first line of a test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 100$$$, $$$0 \le m \le 10^6$$$). The second line contains integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — the elements of the array.

Output format:
For each test case print "YES", if it is possible to reorder the elements of the array in such a way that the given formula gives the given value, and "NO" otherwise.

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

Note:
In the first test case one of the reorders could be $$$[1, 2, 5]$$$. The sum is equal to $$$(\frac{1}{1} + \frac{2}{2} + \frac{5}{3}) + (\frac{2}{2} + \frac{5}{3}) + (\frac{5}{3}) = 8$$$. The brackets denote the inner sum $$$\sum_{j=i}^{n}{\frac{a_j}{j}}$$$, while the summation of brackets corresponds to the sum over $$$i$$$.

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

Example output:
YES
NO

Editorial:
You can notice that the $$$ i $$$-th number in the array will be included in the sum $$$i$$$ times, which means that the value $$$ \frac {a_i} {i} $$$ will add $$$ a_i $$$ to the sum. That is, the permutation of the elements does not affect the required sum, and therefore it is enough to check whether the sum of the array elements is equal to the given number.
Prime Square
Contest: Codeforces Round 678 (Div. 2)
Difficulty rating: 900
Tags: constructive algorithms, math

Sasha likes investigating different math objects, for example, magic squares. But Sasha understands that magic squares have already been studied by hundreds of people, so he sees no sense of studying them further. Instead, he invented his own type of square — a prime square.

A square of size $$$n \times n$$$ is called prime if the following three conditions are held simultaneously:

- all numbers on the square are non-negative integers not exceeding $$$10^5$$$;
- there are no prime numbers in the square;
- sums of integers in each row and each column are prime numbers.

Sasha has an integer $$$n$$$. He asks you to find any prime square of size $$$n \times n$$$. Sasha is absolutely sure such squares exist, so just help him!

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

Each of the next $$$t$$$ lines contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$) — the required size of a square.

Output format:
For each test case print $$$n$$$ lines, each containing $$$n$$$ integers — the prime square you built. If there are multiple answers, print any.

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

Example input:
2
4
2

Example output:
4 6 8 1
4 9 9 9
4 10 10 65
1 4 4 4
1 1
1 1

Editorial:
First, note that the numbers 0 and 1 are not prime. Now let's try to build a square from only these numbers. To begin with, fill in the main and secondary diagonal of the square with ones.
If $$$n$$$ is even, then the sum in each row and each column is $$$2$$$ (prime number), and we have met the condition.
If $$$n$$$ is odd, then the sum in the row with the number $$$ \frac {n + 1} {2} $$$ and in the column with the number $$$ \frac {n + 1} {2} $$$ will be equal to one. To fix this, add ones to the cells $$$ (\frac {n} {2}, \frac {n + 1} {2}) $$$ and $$$ (\frac {n + 1} {2}, \frac {n + 1} {2} + 1) $$$. As a result, the sum in columns and rows will be equal to two or three, and we have fulfilled the condition of the problem.
Binary Search
Contest: Codeforces Round 678 (Div. 2)
Difficulty rating: 1500
Tags: binary search, combinatorics

Andrey thinks he is truly a successful developer, but in reality he didn't know about the binary search algorithm until recently. After reading some literature Andrey understood that this algorithm allows to quickly find a certain number $$$x$$$ in an array. For an array $$$a$$$ indexed from zero, and an integer $$$x$$$ the pseudocode of the algorithm is as follows:

Note that the elements of the array are indexed from zero, and the division is done in integers (rounding down).

Andrey read that the algorithm only works if the array is sorted. However, he found this statement untrue, because there certainly exist unsorted arrays for which the algorithm find $$$x$$$!

Andrey wants to write a letter to the book authors, but before doing that he must consider the permutations of size $$$n$$$ such that the algorithm finds $$$x$$$ in them. A permutation of size $$$n$$$ is an array consisting of $$$n$$$ distinct integers between $$$1$$$ and $$$n$$$ in arbitrary order.

Help Andrey and find the number of permutations of size $$$n$$$ which contain $$$x$$$ at position $$$pos$$$ and for which the given implementation of the binary search algorithm finds $$$x$$$ (returns true). As the result may be extremely large, print the remainder of its division by $$$10^9+7$$$.

Input format:
The only line of input contains integers $$$n$$$, $$$x$$$ and $$$pos$$$ ($$$1 \le x \le n \le 1000$$$, $$$0 \le pos \le n - 1$$$) — the required length of the permutation, the number to search, and the required position of that number, respectively.

Output format:
Print a single number — the remainder of the division of the number of valid permutations by $$$10^9+7$$$.

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

Note:
All possible permutations in the first test case: $$$(2, 3, 1, 4)$$$, $$$(2, 4, 1, 3)$$$, $$$(3, 2, 1, 4)$$$, $$$(3, 4, 1, 2)$$$, $$$(4, 2, 1, 3)$$$, $$$(4, 3, 1, 2)$$$.

Example input:
4 1 2

Example output:
6

Example input:
123 42 24

Example output:
824071958

Editorial:
Let's simulate a binary search algorithm. Initially, we have the required position $$$pos$$$. For the next $$$middle$$$ position in the binary search, we can determine exactly whether the next number at this position should be greater or less than $$$x$$$. For all other positions, the values can be eiteher greater or less than $$$x$$$. As a result of the simulation of the algorithm, we have $$$cntBig$$$ positions at which numbers must be greater than $$$x$$$ and $$$ cntLess $$$ positions at which numbers must be less than $$$x$$$. Let the large numbers be $$$hasBig$$$, and the smaller ones $$$hasLess$$$. Now let's count the number of ways to place large numbers in $$$cntBig$$$ positions using the formula $$$C(hasBig, cntBig) \cdot cntBig!$$$.
Let's calculate in a similar way for smaller numbers, and the product of the resulting results will be the answer to the problem.
Complicated Computations
Contest: Codeforces Round 678 (Div. 2)
Difficulty rating: 2400
Tags: binary search, data structures, two pointers

In this problem MEX of a certain array is the smallest positive integer not contained in this array.

Everyone knows this definition, including Lesha. But Lesha loves MEX, so he comes up with a new problem involving MEX every day, including today.

You are given an array $$$a$$$ of length $$$n$$$. Lesha considers all the non-empty subarrays of the initial array and computes MEX for each of them. Then Lesha computes MEX of the obtained numbers.

An array $$$b$$$ is a subarray of an array $$$a$$$, if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possible none or all) elements from the beginning and several (possibly none or all) elements from the end. In particular, an array is a subarray of itself.

Lesha understands that the problem is very interesting this time, but he doesn't know how to solve it. Help him and find the MEX of MEXes of all the subarrays!

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the array.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of the array.

Output format:
Print a single integer — the MEX of MEXes of all subarrays.

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

Example input:
3
1 3 2

Example output:
3

Example input:
5
1 4 3 1 2

Example output:
6

Editorial:
Let's iterate over the answer. Let the current answer be $$$ x $$$, then we can get it only when there are no subarrays, whose MEX is $$$ x $$$. Note that we need to check the MEX of the subarrays that are between all occurrences of $$$ x $$$. This can be done, for example, using a segment tree, processing its occurrences in order. A number for which MEX is not found will be the answer.
Sum Over Subsets
Contest: Codeforces Round 678 (Div. 2)
Difficulty rating: 2800
Tags: combinatorics, math, number theory

You are given a multiset $$$S$$$. Over all pairs of subsets $$$A$$$ and $$$B$$$, such that:

- $$$B \subset A$$$;
- $$$|B| = |A| - 1$$$;
- greatest common divisor of all elements in $$$A$$$ is equal to one;

find the sum of $$$\sum_{x \in A}{x} \cdot \sum_{x \in B}{x}$$$, modulo $$$998\,244\,353$$$.

Input format:
The first line contains one integer $$$m$$$ ($$$1 \le m \le 10^5$$$): the number of different values in the multiset $$$S$$$.

Each of the next $$$m$$$ lines contains two integers $$$a_i$$$, $$$freq_i$$$ ($$$1 \le a_i \le 10^5, 1 \le freq_i \le 10^9$$$). Element $$$a_i$$$ appears in the multiset $$$S$$$ $$$freq_i$$$ times. All $$$a_i$$$ are different.

Output format:
Print the required sum, modulo $$$998\,244\,353$$$.

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

Note:
A multiset is a set where elements are allowed to coincide. $$$|X|$$$ is the cardinality of a set $$$X$$$, the number of elements in it.

$$$A \subset B$$$: Set $$$A$$$ is a subset of a set $$$B$$$.

In the first example $$$B=\{1\}, A=\{1,2\}$$$ and $$$B=\{2\}, A=\{1, 2\}$$$ have a product equal to $$$1\cdot3 + 2\cdot3=9$$$. Other pairs of $$$A$$$ and $$$B$$$ don't satisfy the given constraints.

Example input:
2
1 1
2 1

Example output:
9

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

Example output:
1207

Editorial:
Let's calculate the required product of the sums $$$ans_i$$$ for the sets, the greatest common divisor of the elements of which is $$$i$$$. First, let's select all the elements that are divisible by $$$i$$$. To find only those sets whose GCD is exactly $$$i$$$, one can find the product of the sums for all subsets and subtract the answers of all $$$ans_j$$$ such that $$$i<j$$$ and $$$i$$$ divides $$$j$$$ without a remainder. To find the products of all subsets of a set of $$$ k $$$ elements, consider two cases:
• the product $$$ a_i \cdot a_i $$$ will be counted $$$ 2^{k-2} \cdot (k - 1) $$$ times. Each element in the set $$$ A $$$ can be removed and this will add the product $$$ a_i^2 $$$. The number of elements $$$ k - 1 $$$ and the number, select the rest of the subset $$$ 2 ^ {k-2} $$$;
• the product $$$ a_i \cdot a_j $$$ will be counted $$$ 2 ^ {k-3} \cdot (k - 2) + 2 ^ {k-2} $$$. The first term is similar to the example above. And the second is obtained if $$$ a_i $$$ is removed from the set $$$ A $$$ - the number of ways to choose a subset of $$$ k - 2 $$$ elements is $$$ 2 ^ {k-2} $$$.
Chess Placing
Contest: Educational Codeforces Round 44 (Rated for Div. 2)
Difficulty rating: 1100
Tags: implementation

You are given a chessboard of size 1 × n. It is guaranteed that n is even. The chessboard is painted like this: "BWBW...BW".

Some cells of the board are occupied by the chess pieces. Each cell contains no more than one chess piece. It is known that the total number of pieces equals to $$\frac{\pi}{2}$$.

In one step you can move one of the pieces one cell to the left or to the right. You cannot move pieces beyond the borders of the board. You also cannot move pieces to the cells that are already occupied.

Your task is to place all the pieces in the cells of the same color using the minimum number of moves (all the pieces must occupy only the black cells or only the white cells after all the moves are made).

Input format:
The first line of the input contains one integer n (2 ≤ n ≤ 100, n is even) — the size of the chessboard.

The second line of the input contains $$\frac{\pi}{2}$$ integer numbers $${ \hat { p } } _ { 1 }, { \hat { p } } _ { 2 }, \ldots, { \hat { p } } _ { \frac { n } { 2 } }$$ (1 ≤ pi ≤ n) — initial positions of the pieces. It is guaranteed that all the positions are distinct.

Output format:
Print one integer — the minimum number of moves you have to make to place all the pieces in the cells of the same color.

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

Note:
In the first example the only possible strategy is to move the piece at the position 6 to the position 5 and move the piece at the position 2 to the position 3. Notice that if you decide to place the pieces in the white cells the minimum number of moves will be 3.

In the second example the possible strategy is to move $$5 \rightarrow 9$$ in 4 moves, then $$4 \rightarrow 7$$ in 3 moves, $$3 \rightarrow 5$$ in 2 moves and $$2\rightarrow3$$ in 1 move.

Example input:
6
1 2 6

Example output:
2

Example input:
10
1 2 3 4 5

Example output:
10

Editorial:
Firstly let's sort our array p (pay the attention that there are $$\frac{\pi}{2}$$ elements in this array, not n). Then for 0-indexed array p answer will be equal to $${\mathrm {min}}\left(\sum _{i=0}^{n/2-1}|p_{i}-(i\cdot 2+1)|,\ \sum _{i=0}^{n/2-1}|p_{i}-(i\cdot 2+2)|\right)$$, where |a - b| is an absolute value of difference between a and b.