1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Round Corridor
Contest: Codeforces Round 578 (Div. 2)
Difficulty rating: 1400
Tags: math, number theory

Amugae is in a very large round corridor. The corridor consists of two areas. The inner area is equally divided by $$$n$$$ sectors, and the outer area is equally divided by $$$m$$$ sectors. A wall exists between each pair of sectors of same area (inner or outer), but there is no wall between the inner area and the outer area. A wall always exists at the 12 o'clock position.

The inner area's sectors are denoted as $$$(1,1), (1,2), \dots, (1,n)$$$ in clockwise direction. The outer area's sectors are denoted as $$$(2,1), (2,2), \dots, (2,m)$$$ in the same manner. For a clear understanding, see the example image above.

Amugae wants to know if he can move from one sector to another sector. He has $$$q$$$ questions.

For each question, check if he can move between two given sectors.

Input format:
The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n, m \le 10^{18}$$$, $$$1 \le q \le 10^4$$$) — the number of sectors in the inner area, the number of sectors in the outer area and the number of questions.

Each of the next $$$q$$$ lines contains four integers $$$s_x$$$, $$$s_y$$$, $$$e_x$$$, $$$e_y$$$ ($$$1 \le s_x, e_x \le 2$$$; if $$$s_x = 1$$$, then $$$1 \le s_y \le n$$$, otherwise $$$1 \le s_y \le m$$$; constraints on $$$e_y$$$ are similar). Amague wants to know if it is possible to move from sector $$$(s_x, s_y)$$$ to sector $$$(e_x, e_y)$$$.

Output format:
For each question, print "YES" if Amugae can move from $$$(s_x, s_y)$$$ to $$$(e_x, e_y)$$$, and "NO" otherwise.

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

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

Note:
Example is shown on the picture in the statement.

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

Example output:
YES
NO
YES

Editorial:
Denote the corridor's length as $$$1$$$. Then, there is a wall at $$$(1, \frac{1}{n}), (1, \frac{2}{n}), \cdots, (1, \frac{n}{n}), (2, \frac{1}{m}), (2, \frac{2}{m}), \cdots (2, \frac{m}{m})$$$. For some value $$$x$$$, If there are walls at $$$(1, x)$$$ and $$$(2, x)$$$ at the same time, we can't move from $$$y$$$ to $$$z$$$ for $$$y \lt x$$$ and $$$z \gt x$$$. Let's call them a "dual wall."
Suppose $$$g = gcd(n, m)$$$. Then dual walls exist at $$$\frac{1}{g}, \frac{2}{g}, \cdots, \frac{g}{g} $$$. So we can make $$$g$$$ groups. We can move freely in the same group, and we can't move from one group to another group.For $$$x = 1$$$, $$$(1, 1), (1,2), \cdots, (1,\frac{n}{g})$$$ belong to group $$$1$$$, and $$$(1, \frac{n}{g} + 1), (1, \frac{n}{g} + 2), \cdots, (1, \frac{2n}{g})$$$ belong to group $$$2$$$, and so on. For $$$x = 2$$$, $$$(2, 1), (2, 2), \cdots, (2, \frac{m}{g})$$$ belong to group $$$1$$$, and $$$(2, \frac{m}{g} + 1), (2, \frac{m}{g} + 2), \cdots, (2, \frac{2m}{g})$$$ belong to group $$$2$$$, and so on.
For each query, print YES if $$$(sx, sy)$$$ and $$$(ex, ey)$$$ belong to the same group. Otherwise, print NO.
time complexity: $$$O(log(max(n,m)) + q)$$$
Reposts
Contest: VK Cup 2015 - Qualification Round 1
Difficulty rating: 1200
Tags: *special, dfs and similar, dp, graphs, trees

One day Polycarp published a funny picture in a social network making a poll about the color of his handle. Many of his friends started reposting Polycarp's joke to their news feed. Some of them reposted the reposts and so on.

These events are given as a sequence of strings "name1 reposted name2", where name1 is the name of the person who reposted the joke, and name2 is the name of the person from whose news feed the joke was reposted. It is guaranteed that for each string "name1 reposted name2" user "name1" didn't have the joke in his feed yet, and "name2" already had it in his feed by the moment of repost. Polycarp was registered as "Polycarp" and initially the joke was only in his feed.

Polycarp measures the popularity of the joke as the length of the largest repost chain. Print the popularity of Polycarp's joke.

Input format:
The first line of the input contains integer n (1 ≤ n ≤ 200) — the number of reposts. Next follow the reposts in the order they were made. Each of them is written on a single line and looks as "name1 reposted name2". All the names in the input consist of lowercase or uppercase English letters and/or digits and have lengths from 2 to 24 characters, inclusive.

We know that the user names are case-insensitive, that is, two names that only differ in the letter case correspond to the same social network user.

Output format:
Print a single integer — the maximum length of a repost chain.

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

Example input:
5
tourist reposted Polycarp
Petr reposted Tourist
WJMZBMR reposted Petr
sdya reposted wjmzbmr
vepifanov reposted sdya

Example output:
6

Example input:
6
Mike reposted Polycarp
Max reposted Polycarp
EveryOne reposted Polycarp
111 reposted Polycarp
VkCup reposted Polycarp
Codeforces reposted Polycarp

Example output:
2

Editorial:
Photo to Remember
Contest: VK Cup 2015 - Qualification Round 1
Difficulty rating: 1100
Tags: *special, data structures, dp, implementation

One day n friends met at a party, they hadn't seen each other for a long time and so they decided to make a group photo together.

Simply speaking, the process of taking photos can be described as follows. On the photo, each photographed friend occupies a rectangle of pixels: the i-th of them occupies the rectangle of width wi pixels and height hi pixels. On the group photo everybody stands in a line, thus the minimum pixel size of the photo including all the photographed friends, is W × H, where W is the total sum of all widths and H is the maximum height of all the photographed friends.

As is usually the case, the friends made n photos — the j-th (1 ≤ j ≤ n) photo had everybody except for the j-th friend as he was the photographer.

Print the minimum size of each made photo in pixels.

Input format:
The first line contains integer n (2 ≤ n ≤ 200 000) — the number of friends.

Then n lines follow: the i-th line contains information about the i-th friend. The line contains a pair of integers wi, hi (1 ≤ wi ≤ 10, 1 ≤ hi ≤ 1000) — the width and height in pixels of the corresponding rectangle.

Output format:
Print n space-separated numbers b1, b2, ..., bn, where bi — the total number of pixels on the minimum photo containing all friends expect for the i-th one.

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

Example input:
3
1 10
5 5
10 1

Example output:
75 110 60

Example input:
3
2 1
1 2
2 1

Example output:
6 4 6

Editorial:
Closest Equals
Contest: VK Cup 2015 - Qualification Round 1
Difficulty rating: 2000
Tags: *special, data structures

You are given sequence a1, a2, ..., an and m queries lj, rj (1 ≤ lj ≤ rj ≤ n). For each query you need to print the minimum distance between such pair of elements ax and ay (x ≠ y), that:

- both indexes of the elements lie within range [lj, rj], that is, lj ≤ x, y ≤ rj;
- the values of the elements are equal, that is ax = ay.

The text above understands distance as |x - y|.

Input format:
The first line of the input contains a pair of integers n, m (1 ≤ n, m ≤ 5·105) — the length of the sequence and the number of queries, correspondingly.

The second line contains the sequence of integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109).

Next m lines contain the queries, one per line. Each query is given by a pair of numbers lj, rj (1 ≤ lj ≤ rj ≤ n) — the indexes of the query range limits.

Output format:
Print m integers — the answers to each query. If there is no valid match for some query, please print -1 as an answer to this query.

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

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

Example output:
1
-1
2

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

Example output:
2
2
3
-1
2

Editorial:
DZY Loves Sequences
Contest: Codeforces Round #FF (Div. 1)
Difficulty rating: 1600
Tags: dp, implementation, two pointers

DZY has a sequence a, consisting of n integers.

We'll call a sequence ai, ai + 1, ..., aj (1 ≤ i ≤ j ≤ n) a subsegment of the sequence a. The value (j - i + 1) denotes the length of the subsegment.

Your task is to find the longest subsegment of a, such that it is possible to change at most one number (change one number to any integer you want) from the subsegment to make the subsegment strictly increasing.

You only need to output the length of the subsegment you find.

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

Output format:
In a single line print the answer to the problem — the maximum length of the required subsegment.

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

Note:
You can choose subsegment a2, a3, a4, a5, a6 and change its 3rd element (that is a4) to 4.

Example input:
6
7 2 3 1 5 6

Example output:
5

Editorial:
DZY Loves Modification
Contest: Codeforces Round #FF (Div. 1)
Difficulty rating: 2000
Tags: brute force, data structures, greedy

As we know, DZY loves playing games. One day DZY decided to play with a n × m matrix. To be more precise, he decided to modify the matrix with exactly k operations.

Each modification is one of the following:

1. Pick some row of the matrix and decrease each element of the row by p. This operation brings to DZY the value of pleasure equal to the sum of elements of the row before the decreasing.
2. Pick some column of the matrix and decrease each element of the column by p. This operation brings to DZY the value of pleasure equal to the sum of elements of the column before the decreasing.

DZY wants to know: what is the largest total value of pleasure he could get after performing exactly k modifications? Please, help him to calculate this value.

Input format:
The first line contains four space-separated integers n, m, k and p (1 ≤ n, m ≤ 103; 1 ≤ k ≤ 106; 1 ≤ p ≤ 100).

Then n lines follow. Each of them contains m integers representing aij (1 ≤ aij ≤ 103) — the elements of the current row of the matrix.

Output format:
Output a single integer — the maximum possible total pleasure value DZY could get.

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

Note:
For the first sample test, we can modify: column 2, row 2. After that the matrix becomes:

For the second sample test, we can modify: column 2, row 2, row 1, column 1, column 2. After that the matrix becomes:

Example input:
2 2 2 2
1 3
2 4

Example output:
11

Example input:
2 2 5 2
1 3
2 4

Example output:
11

Editorial:
DZY Loves Fibonacci Numbers
Contest: Codeforces Round #FF (Div. 1)
Difficulty rating: 2400
Tags: data structures, math, number theory

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

F1 = 1; F2 = 1; Fn = Fn - 1 + Fn - 2 (n > 2).

DZY loves Fibonacci numbers very much. Today DZY gives you an array consisting of n integers: a1, a2, ..., an. Moreover, there are m queries, each query has one of the two types:

1. Format of the query "1 l r". In reply to the query, you need to add Fi - l + 1 to each element ai, where l ≤ i ≤ r.
2. Format of the query "2 l r". In reply to the query you should output the value of $$\sum_{i=l}^{n}a_i$$ modulo 1000000009 (109 + 9).

Help DZY reply to all the queries.

Input format:
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 300000). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — initial array a.

Then, m lines follow. A single line describes a single query in the format given in the statement. It is guaranteed that for each query inequality 1 ≤ l ≤ r ≤ n holds.

Output format:
For each query of the second type, print the value of the sum on a single line.

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

Note:
After the first query, a = [2, 3, 5, 7].

For the second query, sum = 2 + 3 + 5 + 7 = 17.

After the third query, a = [2, 4, 6, 9].

For the fourth query, sum = 2 + 4 + 6 = 12.

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

Example output:
17
12

Editorial:
DZY Loves Games
Contest: Codeforces Round #FF (Div. 1)
Difficulty rating: 2800
Tags: math, matrices, probabilities

Today DZY begins to play an old game. In this game, he is in a big maze with n rooms connected by m corridors (each corridor allows to move in both directions). You can assume that all the rooms are connected with corridors directly or indirectly.

DZY has got lost in the maze. Currently he is in the first room and has k lives. He will act like the follows:

- Firstly he will randomly pick one of the corridors going from his current room. Each outgoing corridor has the same probability to be picked.
- Then he will go through the corridor and then the process repeats.

There are some rooms which have traps in them. The first room definitely has no trap, the n-th room definitely has a trap. Each time DZY enters one of these rooms, he will lost one life. Now, DZY knows that if he enters the n-th room with exactly 2 lives, firstly he will lost one live, but then he will open a bonus round. He wants to know the probability for him to open the bonus round. Please, help him.

Input format:
The first line contains three integers n, m, k (2 ≤ n ≤ 500; 1 ≤ m ≤ 105; 2 ≤ k ≤ 109).

The second line contains n integers, each of them is either 0 or 1. If the i-th number is 1, then the i-th room has a trap, otherwise it has not a trap. Please note, that the number of rooms with a trap is no more than 101. It is guaranteed that the first room has no trap, and the n-th room has a trap.

Then m lines follows. Each of them contains two integers ui, vi (1 ≤ ui, vi ≤ n; ui ≠ vi), meaning that current corridor connects two rooms ui and vi. It is guaranteed that the corridor system is connected.

Output format:
Print the only real number — the probability for DZY to open the bonus round. The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 4.

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

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

Example output:
0.25000000

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

Example output:
-0.00000000

Editorial:
DZY Loves Bridges
Contest: Codeforces Round #FF (Div. 1)
Difficulty rating: 3100
Tags: math, matrices

DZY owns 2m islands near his home, numbered from 1 to 2m. He loves building bridges to connect the islands. Every bridge he builds takes one day's time to walk across.

DZY has a strange rule of building the bridges. For every pair of islands u, v (u ≠ v), he has built 2k different bridges connecting them, where $$k = \max \left\{ k : 2^k | abs(u - v) \right\}$$ (a|b means b is divisible by a). These bridges are bidirectional.

Also, DZY has built some bridges connecting his home with the islands. Specifically, there are ai different bridges from his home to the i-th island. These are one-way bridges, so after he leaves his home he will never come back.

DZY decides to go to the islands for sightseeing. At first he is at home. He chooses and walks across one of the bridges connecting with his home, and arrives at some island. After that, he will spend t day(s) on the islands. Each day, he can choose to stay and rest, or to walk to another island across the bridge. It is allowed to stay at an island for more than one day. It's also allowed to cross one bridge more than once.

Suppose that right after the t-th day DZY stands at the i-th island. Let ans[i] be the number of ways for DZY to reach the i-th island after t-th day. Your task is to calculate ans[i] for each i modulo 1051131.

Input format:
To avoid huge input, we use the following way to generate the array a. You are given the first s elements of array: a1, a2, ..., as. All the other elements should be calculated by formula: ai = (101·ai - s + 10007) mod 1051131 (s < i ≤ 2m).

The first line contains three integers m, t, s (1 ≤ m ≤ 25; 1 ≤ t ≤ 1018; 1 ≤ s ≤ min(2m, 105)).

The second line contains s integers a1, a2, ..., as (1 ≤ ai ≤ 106).

Output format:
To avoid huge output, you only need to output xor-sum of all the answers for all i modulo 1051131 (1 ≤ i ≤ 2m), i.e. (ans[1] mod 1051131) xor (ans[2] mod 1051131) xor... xor (ans[n] mod 1051131).

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

Note:
In the first sample, ans = [6, 7, 6, 6].

If he wants to be at island 1 after one day, he has 6 different ways:

1. home —> 1 -(stay)-> 1
2. home —> 2 —> 1
3. home —> 3 —> 1
4. home —> 3 —> 1 (note that there are two different bridges between 1 and 3)
5. home —> 4 —> 1
6. home —> 4 —> 1 (note that there are two different bridges from home to 4)

In the second sample, (a1, a2, a3, a4, a5, a6, a7, a8) = (389094, 705719, 547193, 653800, 947499, 17024, 416654, 861849), ans = [235771, 712729, 433182, 745954, 139255, 935785, 620229, 644335].

Example input:
2 1 4
1 1 1 2

Example output:
1

Example input:
3 5 6
389094 705719 547193 653800 947499 17024

Example output:
556970

Editorial:
XXXXX
Contest: Codeforces Round 649 (Div. 2)
Difficulty rating: 1200
Tags: brute force, data structures, number theory, two pointers

Ehab loves number theory, but for some reason he hates the number $$$x$$$. Given an array $$$a$$$, find the length of its longest subarray such that the sum of its elements isn't divisible by $$$x$$$, or determine that such subarray doesn't exist.

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

Input format:
The first line contains an integer $$$t$$$ $$$(1 \le t \le 5)$$$ — the number of test cases you need to solve. The description of the test cases follows.

The first line of each test case contains 2 integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le x \le 10^4$$$) — the number of elements in the array $$$a$$$ and the number that Ehab hates.

The second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$0 \le a_i \le 10^4$$$) — the elements of the array $$$a$$$.

Output format:
For each testcase, print the length of the longest subarray whose sum isn't divisible by $$$x$$$. If there's no such subarray, print $$$-1$$$.

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

Note:
In the first test case, the subarray $$$[2,3]$$$ has sum of elements $$$5$$$, which isn't divisible by $$$3$$$.

In the second test case, the sum of elements of the whole array is $$$6$$$, which isn't divisible by $$$4$$$.

In the third test case, all subarrays have an even sum, so the answer is $$$-1$$$.

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

Example output:
2
3
-1

Editorial:
Most socially-distanced subsequence
Contest: Codeforces Round 649 (Div. 2)
Difficulty rating: 1300
Tags: greedy, two pointers

Given a permutation $$$p$$$ of length $$$n$$$, find its subsequence $$$s_1$$$, $$$s_2$$$, $$$\ldots$$$, $$$s_k$$$ of length at least $$$2$$$ such that:

- $$$|s_1-s_2|+|s_2-s_3|+\ldots+|s_{k-1}-s_k|$$$ is as big as possible over all subsequences of $$$p$$$ with length at least $$$2$$$.
- Among all such subsequences, choose the one whose length, $$$k$$$, is as small as possible.

If multiple subsequences satisfy these conditions, you are allowed to find any of them.

A sequence $$$a$$$ is a subsequence of an array $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deleting some (possibly, zero or all) elements.

A permutation of length $$$n$$$ is an array of length $$$n$$$ in which every element from $$$1$$$ to $$$n$$$ occurs exactly once.

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

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the length of the permutation $$$p$$$.

The second line of each test case contains $$$n$$$ integers $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_{n}$$$ ($$$1 \le p_i \le n$$$, $$$p_i$$$ are distinct) — the elements of the permutation $$$p$$$.

The sum of $$$n$$$ across the test cases doesn't exceed $$$10^5$$$.

Output format:
For each test case, the first line should contain the length of the found subsequence, $$$k$$$. The second line should contain $$$s_1$$$, $$$s_2$$$, $$$\ldots$$$, $$$s_k$$$ — its elements.

If multiple subsequences satisfy these conditions, you are allowed to find any of them.

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

Note:
In the first test case, there are $$$4$$$ subsequences of length at least $$$2$$$:

- $$$[3,2]$$$ which gives us $$$|3-2|=1$$$.
- $$$[3,1]$$$ which gives us $$$|3-1|=2$$$.
- $$$[2,1]$$$ which gives us $$$|2-1|=1$$$.
- $$$[3,2,1]$$$ which gives us $$$|3-2|+|2-1|=2$$$.

So the answer is either $$$[3,1]$$$ or $$$[3,2,1]$$$. Since we want the subsequence to be as short as possible, the answer is $$$[3,1]$$$.

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

Example output:
2
3 1 
3
1 4 2

Editorial:
Ehab and Prefix MEXs
Contest: Codeforces Round 649 (Div. 2)
Difficulty rating: 1600
Tags: brute force, constructive algorithms, greedy

Given an array $$$a$$$ of length $$$n$$$, find another array, $$$b$$$, of length $$$n$$$ such that:

- for each $$$i$$$ $$$(1 \le i \le n)$$$ $$$MEX(\{b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_i\})=a_i$$$.

The $$$MEX$$$ of a set of integers is the smallest non-negative integer that doesn't belong to this set.

If such array doesn't exist, determine this.

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

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$0 \le a_i \le i$$$) — the elements of the array $$$a$$$. It's guaranteed that $$$a_i \le a_{i+1}$$$ for $$$1\le i < n$$$.

Output format:
If there's no such array, print a single line containing $$$-1$$$.

Otherwise, print a single line containing $$$n$$$ integers $$$b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_n$$$ ($$$0 \le b_i \le 10^6$$$)

If there are multiple answers, print any.

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

Note:
In the second test case, other answers like $$$[1,1,1,0]$$$, for example, are valid.

Example input:
3
1 2 3

Example output:
0 1 2

Example input:
4
0 0 0 2

Example output:
1 3 4 0

Editorial: