1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Serial Time!
Contest: Codeforces Beta Round 56
Difficulty rating: 1400
Tags: dfs and similar, dsu

The Cereal Guy's friend Serial Guy likes to watch soap operas. An episode is about to start, and he hasn't washed his plate yet. But he decided to at least put in under the tap to be filled with water. The plate can be represented by a parallelepiped k × n × m, that is, it has k layers (the first layer is the upper one), each of which is a rectangle n × m with empty squares ('.') and obstacles ('#'). The water can only be present in the empty squares. The tap is positioned above the square (x, y) of the first layer, it is guaranteed that this square is empty. Every minute a cubical unit of water falls into the plate. Find out in how many minutes the Serial Guy should unglue himself from the soap opera and turn the water off for it not to overfill the plate. That is, you should find the moment of time when the plate is absolutely full and is going to be overfilled in the next moment.

Note: the water fills all the area within reach (see sample 4). Water flows in each of the 6 directions, through faces of 1 × 1 × 1 cubes.

Input format:
The first line contains three numbers k, n, m (1 ≤ k, n, m ≤ 10) which are the sizes of the plate. Then follow k rectangles consisting of n lines each containing m characters '.' or '#', which represents the "layers" of the plate in the order from the top to the bottom. The rectangles are separated by empty lines (see the samples). The last line contains x and y (1 ≤ x ≤ n, 1 ≤ y ≤ m) which are the tap's coordinates. x is the number of the line and y is the number of the column. Lines of each layer are numbered from left to right by the integers from 1 to n, columns of each layer are numbered from top to bottom by the integers from 1 to m.

Output format:
The answer should contain a single number, showing in how many minutes the plate will be filled.

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

Example input:
1 1 1
.
1 1

Example output:
1

Example input:
2 1 1
.
#
1 1

Example output:
1

Editorial:
Mushroom Strife
Contest: Codeforces Beta Round 56
Difficulty rating: 2100
Tags: brute force, dfs and similar

Pasha and Akim were making a forest map — the lawns were the graph's vertexes and the roads joining the lawns were its edges. They decided to encode the number of laughy mushrooms on every lawn in the following way: on every edge between two lawns they wrote two numbers, the greatest common divisor (GCD) and the least common multiple (LCM) of the number of mushrooms on these lawns. But one day Pasha and Akim had an argument about the laughy mushrooms and tore the map. Pasha was left with just some part of it, containing only m roads. Your task is to help Pasha — use the map he has to restore the number of mushrooms on every lawn. As the result is not necessarily unique, help Pasha to restore any one or report that such arrangement of mushrooms does not exist. It is guaranteed that the numbers on the roads on the initial map were no less that 1 and did not exceed 106.

Input format:
The first line contains two numbers n and m ($$1 \leq n \leq 100, 0 \leq m \leq \frac{n(n-1)}{2}$$) which are the numbers of lawns and roads we know about. Each of the following m lines contains four numbers which are the numbers of lawns the road connects, the GCD and the LCM of the numbers of mushrooms on these lawns (1 ≤ GCD, LCM ≤ 106).

It is guaranteed, that no road connects lawn to itself, and no two lawns are connected by more than one road.

Output format:
The answer should contain "YES" or "NO" on the first line, saying whether it is possible or not to perform the arrangement. If the answer is "YES", print on the following line n numbers which are the numbers of mushrooms on the corresponding lawns.

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

Example input:
1 0

Example output:
YES
1

Example input:
2 1
1 2 1 3

Example output:
YES
1 3

Editorial:
Savior
Contest: Codeforces Beta Round 56
Difficulty rating: 2500
Tags: brute force, dsu, math

Misha decided to help Pasha and Akim be friends again. He had a cunning plan — to destroy all the laughy mushrooms. He knows that the laughy mushrooms can easily burst when they laugh. Mushrooms grow on the lawns. There are a[t] mushrooms on the t-th lawn.

Misha knows that the lawns where the mushrooms grow have a unique ability. A lawn (say, i) can transfer laugh to other lawn (say, j) if there exists an integer (say, b) such, that some permutation of numbers a[i], a[j] and b is a beautiful triple (i ≠ j). A beautiful triple is such three pairwise coprime numbers x, y, z, which satisfy the following condition: x2 + y2 = z2.

Misha wants to know on which minimal number of lawns he should laugh for all the laughy mushrooms to burst.

Input format:
The first line contains one integer n (1 ≤ n ≤ 106) which is the number of lawns. The next line contains n integers ai which are the number of mushrooms on the i-lawn (1 ≤ ai ≤ 107). All the numbers are different.

Output format:
Print a single number — the minimal number of lawns on which Misha should laugh for all the mushrooms to burst.

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

Example input:
1
2

Example output:
1

Example input:
2
1 2

Example output:
2

Editorial:
Mushroom Gnomes
Contest: Codeforces Beta Round 56
Difficulty rating: 2600
Tags: math, matrices

Once upon a time in the thicket of the mushroom forest lived mushroom gnomes. They were famous among their neighbors for their magic mushrooms. Their magic nature made it possible that between every two neighboring mushrooms every minute grew another mushroom with the weight equal to the sum of weights of two neighboring ones.

The mushroom gnomes loved it when everything was in order, that's why they always planted the mushrooms in one line in the order of their weights' increasing. Well... The gnomes planted the mushrooms and went to eat. After x minutes they returned and saw that new mushrooms had grown up, so that the increasing order had been violated. The gnomes replanted all the mushrooms in the correct order, that is, they sorted the mushrooms in the order of the weights' increasing. And went to eat again (those gnomes were quite big eaters). What total weights modulo p will the mushrooms have in another y minutes?

Input format:
The first line contains four integers n, x, y, p (1 ≤ n ≤ 106, 0 ≤ x, y ≤ 1018, x + y > 0, 2 ≤ p ≤ 109) which represent the number of mushrooms, the number of minutes after the first replanting, the number of minutes after the second replanting and the module. The next line contains n integers ai which represent the mushrooms' weight in the non-decreasing order (0 ≤ ai ≤ 109).

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).

Output format:
The answer should contain a single number which is the total weights of the mushrooms modulo p in the end after x + y minutes.

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

Example input:
2 1 0 657276545
1 2

Example output:
6

Example input:
2 1 1 888450282
1 2

Example output:
14

Editorial:
Divisibility
Contest: Testing Round 12
Difficulty rating: 1600
Tags: math

Find the number of k-divisible numbers on the segment [a, b]. In other words you need to find the number of such integer values x that a ≤ x ≤ b and x is divisible by k.

Input format:
The only line contains three space-separated integers k, a and b (1 ≤ k ≤ 1018; - 1018 ≤ a ≤ b ≤ 1018).

Output format:
Print the required number.

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

Example input:
1 1 10

Example output:
10

Example input:
2 -4 4

Example output:
5

Editorial:
Restaurant
Contest: Testing Round 12
Difficulty rating: 1600
Tags: dp, greedy, sortings

A restaurant received n orders for the rental. Each rental order reserve the restaurant for a continuous period of time, the i-th order is characterized by two time values — the start time li and the finish time ri (li ≤ ri).

Restaurant management can accept and reject orders. What is the maximal number of orders the restaurant can accept?

No two accepted orders can intersect, i.e. they can't share even a moment of time. If one order ends in the moment other starts, they can't be accepted both.

Input format:
The first line contains integer number n (1 ≤ n ≤ 5·105) — number of orders. The following n lines contain integer values li and ri each (1 ≤ li ≤ ri ≤ 109).

Output format:
Print the maximal number of orders that can be accepted.

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

Example input:
2
7 11
4 7

Example output:
1

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

Example output:
3

Editorial:
Subsequences
Contest: Testing Round 12
Difficulty rating: 1900
Tags: data structures, dp

For the given sequence with n different elements find the number of increasing subsequences with k + 1 elements. It is guaranteed that the answer is not greater than 8·1018.

Input format:
First line contain two integer values n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ 10) — the length of sequence and the number of elements in increasing subsequences.

Next n lines contains one integer ai (1 ≤ ai ≤ n) each — elements of sequence. All values ai are different.

Output format:
Print one integer — the answer to the problem.

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

Example input:
5 2
1
2
3
5
4

Example output:
7

Editorial:
Neko Finds Grapes
Contest: Codeforces Round 554 (Div. 2)
Difficulty rating: 800
Tags: greedy, implementation, math

On a random day, Neko found $$$n$$$ treasure chests and $$$m$$$ keys. The $$$i$$$-th chest has an integer $$$a_i$$$ written on it and the $$$j$$$-th key has an integer $$$b_j$$$ on it. Neko knows those chests contain the powerful mysterious green Grapes, thus Neko wants to open as many treasure chests as possible.

The $$$j$$$-th key can be used to unlock the $$$i$$$-th chest if and only if the sum of the key number and the chest number is an odd number. Formally, $$$a_i + b_j \equiv 1 \pmod{2}$$$. One key can be used to open at most one chest, and one chest can be opened at most once.

Find the maximum number of chests Neko can open.

Input format:
The first line contains integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$) — the number of chests and the number of keys.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the numbers written on the treasure chests.

The third line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 10^9$$$) — the numbers written on the keys.

Output format:
Print the maximum number of chests you can open.

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

Note:
In the first example, one possible way to unlock $$$3$$$ chests is as follows:

- Use first key to unlock the fifth chest,
- Use third key to unlock the second chest,
- Use fourth key to unlock the first chest.

In the second example, you can use the only key to unlock any single chest (note that one key can't be used twice).

In the third example, no key can unlock the given chest.

Example input:
5 4
9 14 6 2 11
8 4 7 20

Example output:
3

Example input:
5 1
2 4 6 8 10
5

Example output:
1

Editorial:
The most important observation is that:
• Key with odd id can only be used to unlock chest with even id
• Key with even id can only be used to unlock chest with odd id
Let:
• $$$c_0, c_1$$$ be the number of chests with even and odd id, respectively
• $$$k_0, k_1$$$ be the number of keys with even and odd id, respectively
With $$$c_0$$$ even-id chests and $$$k_1$$$ odd-id keys, you can unlock at most $$$\min(c_0, k_1)$$$ chests.
With $$$c_1$$$ odd-id chests and $$$k_0$$$ even-id keys, you can unlock at most $$$\min(c_1, k_0)$$$ chests.
Therefore, the final answer is $$$\min(c_0, k_1) + \min(c_1, k_0)$$$.
Complexity: $$$O(n + m)$$$
Neko does Maths
Contest: Codeforces Round 554 (Div. 2)
Difficulty rating: 1800
Tags: brute force, math, number theory

Neko loves divisors. During the latest number theory lesson, he got an interesting exercise from his math teacher.

Neko has two integers $$$a$$$ and $$$b$$$. His goal is to find a non-negative integer $$$k$$$ such that the least common multiple of $$$a+k$$$ and $$$b+k$$$ is the smallest possible. If there are multiple optimal integers $$$k$$$, he needs to choose the smallest one.

Given his mathematical talent, Neko had no trouble getting Wrong Answer on this problem. Can you help him solve it?

Input format:
The only line contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^9$$$).

Output format:
Print the smallest non-negative integer $$$k$$$ ($$$k \ge 0$$$) such that the lowest common multiple of $$$a+k$$$ and $$$b+k$$$ is the smallest possible.

If there are many possible integers $$$k$$$ giving the same value of the least common multiple, print the smallest one.

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

Note:
In the first test, one should choose $$$k = 2$$$, as the least common multiple of $$$6 + 2$$$ and $$$10 + 2$$$ is $$$24$$$, which is the smallest least common multiple possible.

Example input:
6 10

Example output:
2

Example input:
21 31

Example output:
9

Editorial:
The $$$lcm(a + k, b + k)$$$ is equal to $$$\frac{(a + k) \cdot (b + k)}{\gcd(a + k, b + k)}$$$. In fact, there are not much possible values for the denominator of this fraction.
Without losing generality, let's assume $$$a \le b$$$. Applying one step of Euclid's algorithm we can see, that $$$\gcd(a + k, b + k) = \gcd(b - a, a + k)$$$.
So the $$$\gcd$$$ is a divisor of $$$b - a$$$. Let's iterate over all divisors $$$q$$$ of $$$b - a$$$. That also means that $$$a \pmod{q} = b \pmod{q}$$$. In case $$$a \pmod{q} = 0$$$, we can use $$$k = 0$$$. Otherwise, the corresponding $$$k$$$ should be $$$q - a \pmod{q}$$$. Lastly, we need to check whether the value of $$$lcm(a + k, b + k)$$$ is the smallest found so far.
Also, one has to be careful when dealing with $$$k = 0$$$ answer, which was the reason why many solutions got WA 63.
The complexity is $$$O(\sqrt{b - a})$$$.
Neko and Aki's Prank
Contest: Codeforces Round 554 (Div. 2)
Difficulty rating: 2100
Tags: dp, greedy, trees

Neko is playing with his toys on the backyard of Aki's house. Aki decided to play a prank on him, by secretly putting catnip into Neko's toys. Unfortunately, he went overboard and put an entire bag of catnip into the toys...

It took Neko an entire day to turn back to normal. Neko reported to Aki that he saw a lot of weird things, including a trie of all correct bracket sequences of length $$$2n$$$.

The definition of correct bracket sequence is as follows:

- The empty sequence is a correct bracket sequence,
- If $$$s$$$ is a correct bracket sequence, then $$$(\,s\,)$$$ is a correct bracket sequence,
- If $$$s$$$ and $$$t$$$ are a correct bracket sequence, then $$$st$$$ is also a correct bracket sequence.

For example, the strings "(())", "()()" form a correct bracket sequence, while ")(" and "((" not.

Aki then came up with an interesting problem: What is the size of the maximum matching (the largest set of edges such that there are no two edges with a common vertex) in this trie? Since the answer can be quite large, print it modulo $$$10^9 + 7$$$.

Input format:
The only line contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$).

Output format:
Print exactly one integer — the size of the maximum matching in the trie. Since the answer can be quite large, print it modulo $$$10^9 + 7$$$.

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

Note:
The pictures below illustrate tries in the first two examples (for clarity, the round brackets are replaced with angle brackets). The maximum matching is highlighted with blue.

Example input:
1

Example output:
1

Example input:
2

Example output:
3

Editorial:
Note, that many subtrees of the trie are equal. Basically, if we consider two vertices on the same depth and having the same balance from root to them (that is, the number of opening brackets minus the number of closing brackets), than their subtrees will be entirely same. For example, the subtrees after following $$$((())$$$, $$$()()($$$ and $$$(())($$$ are all the same.
We will use this observation to consider the tree in "compressed" form. Clearly, this way there are only $$$O(n^2)$$$ different vertices types (basically a vertex is described by $$$(depth, balance)$$$).
Now let's get back to finding a maximum matching in the tree. There are two approaches to this problem. One of them is greedy. Basically if you find a matching in a tree you can always greedily take the edge between a leaf and its parent (since this adds one edge to the answer and destroys at most one edge you would've chosen).
This idea can transform into the following algorithm (for the problem of the maximum matching in the tree). Do a dynamic programming on the subtrees, the result of $$$dp[v]$$$ is a pair of "number of edges taken in subtree, whether the root of this subtree is free (so we can start a new edge upwards)".
Combining this with the idea that there are little ($$$n^2$$$) number of vertex types, we get a dp solution.
Neko Rules the Catniverse (Large Version)
Contest: Codeforces Round 554 (Div. 2)
Difficulty rating: 3000
Tags: bitmasks, dp, matrices

This problem is same as the previous one, but has larger constraints.

Aki is playing a new video game. In the video game, he will control Neko, the giant cat, to fly between planets in the Catniverse.

There are $$$n$$$ planets in the Catniverse, numbered from $$$1$$$ to $$$n$$$. At the beginning of the game, Aki chooses the planet where Neko is initially located. Then Aki performs $$$k - 1$$$ moves, where in each move Neko is moved from the current planet $$$x$$$ to some other planet $$$y$$$ such that:

- Planet $$$y$$$ is not visited yet.
- $$$1 \leq y \leq x + m$$$ (where $$$m$$$ is a fixed constant given in the input)

This way, Neko will visit exactly $$$k$$$ different planets. Two ways of visiting planets are called different if there is some index $$$i$$$ such that, the $$$i$$$-th planet visited in the first way is different from the $$$i$$$-th planet visited in the second way.

What is the total number of ways to visit $$$k$$$ planets this way? Since the answer can be quite large, print it modulo $$$10^9 + 7$$$.

Input format:
The only line contains three integers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le k \le \min(n, 12)$$$, $$$1 \le m \le 4$$$) — the number of planets in the Catniverse, the number of planets Neko needs to visit and the said constant $$$m$$$.

Output format:
Print exactly one integer — the number of different ways Neko can visit exactly $$$k$$$ planets. Since the answer can be quite large, print it modulo $$$10^9 + 7$$$.

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

Note:
In the first example, there are $$$4$$$ ways Neko can visit all the planets:

- $$$1 \rightarrow 2 \rightarrow 3$$$
- $$$2 \rightarrow 3 \rightarrow 1$$$
- $$$3 \rightarrow 1 \rightarrow 2$$$
- $$$3 \rightarrow 2 \rightarrow 1$$$

In the second example, there are $$$9$$$ ways Neko can visit exactly $$$2$$$ planets:

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

In the third example, with $$$m = 4$$$, Neko can visit all the planets in any order, so there are $$$5! = 120$$$ ways Neko can visit all the planets.

In the fourth example, Neko only visit exactly $$$1$$$ planet (which is also the planet he initially located), and there are $$$100$$$ ways to choose the starting planet for Neko.

Example input:
3 3 1

Example output:
4

Example input:
4 2 1

Example output:
9

Editorial:
The core idea is similar to F1, however there is one crucial observation.
We can see that all DP transitions are just linear transformations, thus we can construct a transition matrix of size $$$k \cdot 2^m$$$, then use fast matrix exponentiation as a replacement of the original DP transitions.
Total complexity: $$$\mathcal{O} \left( \log(n) \cdot {\left( k \cdot 2^m \right)}^3 \right)$$$.
Holidays
Contest: Codeforces Round 350 (Div. 2)
Difficulty rating: 900
Tags: brute force, constructive algorithms, greedy, math

On the planet Mars a year lasts exactly n days (there are no leap years on Mars). But Martians have the same weeks as earthlings — 5 work days and then 2 days off. Your task is to determine the minimum possible and the maximum possible number of days off per year on Mars.

Input format:
The first line of the input contains a positive integer n (1 ≤ n ≤ 1 000 000) — the number of days in a year on Mars.

Output format:
Print two integers — the minimum possible and the maximum possible number of days off per year on Mars.

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

Note:
In the first sample there are 14 days in a year on Mars, and therefore independently of the day a year starts with there will be exactly 4 days off .

In the second sample there are only 2 days in a year on Mars, and they can both be either work days or days off.

Example input:
14

Example output:
4 4

Example input:
2

Example output:
0 2

Editorial:
Game of Robots
Contest: Codeforces Round 350 (Div. 2)
Difficulty rating: 1000
Tags: implementation

In late autumn evening n robots gathered in the cheerful company of friends. Each robot has a unique identifier — an integer from 1 to 109.

At some moment, robots decided to play the game "Snowball". Below there are the rules of this game. First, all robots stand in a row. Then the first robot says his identifier. After that the second robot says the identifier of the first robot and then says his own identifier. Then the third robot says the identifier of the first robot, then says the identifier of the second robot and after that says his own. This process continues from left to right until the n-th robot says his identifier.

Your task is to determine the k-th identifier to be pronounced.

Input format:
The first line contains two positive integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ min(2·109, n·(n + 1) / 2).

The second line contains the sequence id1, id2, ..., idn (1 ≤ idi ≤ 109) — identifiers of roborts. It is guaranteed that all identifiers are different.

Output format:
Print the k-th pronounced identifier (assume that the numeration starts from 1).

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

Note:
In the first sample identifiers of robots will be pronounced in the following order: 1, 1, 2. As k = 2, the answer equals to 1.

In the second test case identifiers of robots will be pronounced in the following order: 10, 10, 4, 10, 4, 18, 10, 4, 18, 3. As k = 5, the answer equals to 4.

Example input:
2 2
1 2

Example output:
1

Example input:
4 5
10 4 18 3

Example output:
4

Editorial: