1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Matrix Walk
Contest: Educational Codeforces Round 40 (Rated for Div. 2)
Difficulty rating: 1700
Tags: implementation

There is a matrix A of size x × y filled with integers. For every $$i \in [1..x]$$, $$j \in [1..y]$$ Ai, j = y(i - 1) + j. Obviously, every integer from [1..xy] occurs exactly once in this matrix.

You have traversed some path in this matrix. Your path can be described as a sequence of visited cells a1, a2, ..., an denoting that you started in the cell containing the number a1, then moved to the cell with the number a2, and so on.

From the cell located in i-th line and j-th column (we denote this cell as (i, j)) you can move into one of the following cells:

1. (i + 1, j) — only if i < x;
2. (i, j + 1) — only if j < y;
3. (i - 1, j) — only if i > 1;
4. (i, j - 1) — only if j > 1.

Notice that making a move requires you to go to an adjacent cell. It is not allowed to stay in the same cell. You don't know x and y exactly, but you have to find any possible values for these numbers such that you could start in the cell containing the integer a1, then move to the cell containing a2 (in one step), then move to the cell containing a3 (also in one step) and so on. Can you choose x and y so that they don't contradict with your sequence of moves?

Input format:
The first line contains one integer number n (1 ≤ n ≤ 200000) — the number of cells you visited on your path (if some cell is visited twice, then it's listed twice).

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the integers in the cells on your path.

Output format:
If all possible values of x and y such that 1 ≤ x, y ≤ 109 contradict with the information about your path, print NO.

Otherwise, print YES in the first line, and in the second line print the values x and y such that your path was possible with such number of lines and columns in the matrix. Remember that they must be positive integers not exceeding 109.

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

Note:
The matrix and the path on it in the first test looks like this:

Also there exist multiple correct answers for both the first and the third examples.

Example input:
8
1 2 3 6 9 8 5 2

Example output:
YES
3 3

Example input:
6
1 2 1 2 5 3

Example output:
NO

Editorial:
You can notice that moves of kind (i - 1, j) and (i + 1, j) are changing value x to x - m and x + m. Thus, you can determine m by checking adjacent nodes in the path. The answer is YES if there are one or zero distinct values of differences not counting difference of 1.
You can also set n to arbitrary big value, it doesn't really matter until you can fit all values. 109 will work just fine.
Finally, knowing n and m, simulate the process and check that all moves are valid.
Overall complexity: O(n).
Fight Against Traffic
Contest: Educational Codeforces Round 40 (Rated for Div. 2)
Difficulty rating: 1600
Tags: dfs and similar, graphs, shortest paths

Little town Nsk consists of n junctions connected by m bidirectional roads. Each road connects two distinct junctions and no two roads connect the same pair of junctions. It is possible to get from any junction to any other junction by these roads. The distance between two junctions is equal to the minimum possible number of roads on a path between them.

In order to improve the transportation system, the city council asks mayor to build one new road. The problem is that the mayor has just bought a wonderful new car and he really enjoys a ride from his home, located near junction s to work located near junction t. Thus, he wants to build a new road in such a way that the distance between these two junctions won't decrease.

You are assigned a task to compute the number of pairs of junctions that are not connected by the road, such that if the new road between these two junctions is built the distance between s and t won't decrease.

Input format:
The firt line of the input contains integers n, m, s and t (2 ≤ n ≤ 1000, 1 ≤ m ≤ 1000, 1 ≤ s, t ≤ n, s ≠ t) — the number of junctions and the number of roads in Nsk, as well as the indices of junctions where mayors home and work are located respectively. The i-th of the following m lines contains two integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi), meaning that this road connects junctions ui and vi directly. It is guaranteed that there is a path between any two junctions and no two roads connect the same pair of junctions.

Output format:
Print one integer — the number of pairs of junctions not connected by a direct road, such that building a road between these two junctions won't decrease the distance between junctions s and t.

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

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

Example output:
0

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

Example output:
5

Editorial:
Let's use bfs to calculate the smallest distances to all vertices from the vertex s and from the vertex t. These will be ds[i] and dt[i] for all i.
ds[t] = dt[s] = D is the the current smallest distance between s and t. What you need is to iterate over all pairs (u, v) and check if the edge between them doesn't exist and neither (ds[u] + dt[v] + 1) nor (ds[v] + dt[u] + 1) is smaller than D.
Overall complexity: O(n2).
Water Taps
Contest: Educational Codeforces Round 40 (Rated for Div. 2)
Difficulty rating: 2000
Tags: binary search, greedy, sortings

Consider a system of n water taps all pouring water into the same container. The i-th water tap can be set to deliver any amount of water from 0 to ai ml per second (this amount may be a real number). The water delivered by i-th tap has temperature ti.

If for every $$i \in [1,n]$$ you set i-th tap to deliver exactly xi ml of water per second, then the resulting temperature of water will be $$\frac{\sum_{i=1}^{n} x_{i} t_{i}}{\sum_{i=1}^{n} x_{i}}$$ (if $$\sum_{i=1}^{n} x_i = 0$$, then to avoid division by zero we state that the resulting water temperature is 0).

You have to set all the water taps in such a way that the resulting temperature is exactly T. What is the maximum amount of water you may get per second if its temperature has to be T?

Input format:
The first line contains two integers n and T (1 ≤ n ≤ 200000, 1 ≤ T ≤ 106) — the number of water taps and the desired temperature of water, respectively.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 106) where ai is the maximum amount of water i-th tap can deliver per second.

The third line contains n integers t1, t2, ..., tn (1 ≤ ti ≤ 106) — the temperature of water each tap delivers.

Output format:
Print the maximum possible amount of water with temperature exactly T you can get per second (if it is impossible to obtain water with such temperature, then the answer is considered to be 0).

Your answer is considered correct if its absolute or relative error doesn't exceed 10 - 6.

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

Example input:
2 100
3 10
50 150

Example output:
6.000000000000000

Example input:
3 9
5 5 30
6 6 10

Example output:
40.000000000000000

Editorial:
The following greedy strategy work. Let's turn all the taps at full power. If total temperature is greater than T then we would like to decrease power on some taps with higher temperature. We want to decrease as low power as possible, so we should prioritize taps with the highest temperature. Sort all taps by temperature and find the total power on suffix you should decrease to have equal temperatures. This can be done with binary search. The same works for smaller initial temperature.
Overall complexity: $$O(n \log n)$$.
Runner's Problem
Contest: Educational Codeforces Round 40 (Rated for Div. 2)
Difficulty rating: 2100
Tags: dp, matrices, sortings

You are running through a rectangular field. This field can be represented as a matrix with 3 rows and m columns. (i, j) denotes a cell belonging to i-th row and j-th column.

You start in (2, 1) and have to end your path in (2, m). From the cell (i, j) you may advance to:

- (i - 1, j + 1) — only if i > 1,
- (i, j + 1), or
- (i + 1, j + 1) — only if i < 3.

However, there are n obstacles blocking your path. k-th obstacle is denoted by three integers ak, lk and rk, and it forbids entering any cell (ak, j) such that lk ≤ j ≤ rk.

You have to calculate the number of different paths from (2, 1) to (2, m), and print it modulo 109 + 7.

Input format:
The first line contains two integers n and m (1 ≤ n ≤ 104, 3 ≤ m ≤ 1018) — the number of obstacles and the number of columns in the matrix, respectively.

Then n lines follow, each containing three integers ak, lk and rk (1 ≤ ak ≤ 3, 2 ≤ lk ≤ rk ≤ m - 1) denoting an obstacle blocking every cell (ak, j) such that lk ≤ j ≤ rk. Some cells may be blocked by multiple obstacles.

Output format:
Print the number of different paths from (2, 1) to (2, m), taken modulo 109 + 7. If it is impossible to get from (2, 1) to (2, m), then the number of paths is 0.

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

Example input:
2 5
1 3 4
2 2 3

Example output:
2

Editorial:
There is a simple dynamic programming solution that works in O(m). Let's try to improve it.
Firstly, if there are no obstacles in some column i and we have calculated the number of paths to every cell of the previous column, then we may get the values in column i by multiplying the vector of values in column i - 1 by the following matrix:
$${ \left( \begin{array} { l l l } { 1 } & { 1 } & { 0 } \\ { 1 } & { 1 } & { 1 } \\ { 0 } & { 1 } & { 1 } \end{array} \right) }$$
Then we may use binary exponentiation to skip long segments without obstacles in O(logk), where k is the length of the segment.
Let's try to modify this matrix if we have to forbid some rows. All we need to change is to set every value in i-th row to 0 if i-th row is forbidden. So we may skip long segments not only if they don't contain any obstacles, but also if the set of forbidden rows doesn't change on this segment.
So the solution is the following: divide the whole matrix into 2n + 1 segments by the endpoints of the obstacles, then in every segment the set of forbidden rows doesn't change (so we can skip it using fast matrix exponentiation).
Castle Defense
Contest: Educational Codeforces Round 40 (Rated for Div. 2)
Difficulty rating: 2000
Tags: binary search, data structures, greedy, two pointers

Today you are going to lead a group of elven archers to defend the castle that is attacked by an army of angry orcs. Three sides of the castle are protected by impassable mountains and the remaining side is occupied by a long wall that is split into n sections. At this moment there are exactly ai archers located at the i-th section of this wall. You know that archer who stands at section i can shoot orcs that attack section located at distance not exceeding r, that is all such sections j that |i - j| ≤ r. In particular, r = 0 means that archers are only capable of shooting at orcs who attack section i.

Denote as defense level of section i the total number of archers who can shoot at the orcs attacking this section. Reliability of the defense plan is the minimum value of defense level of individual wall section.

There is a little time left till the attack so you can't redistribute archers that are already located at the wall. However, there is a reserve of k archers that you can distribute among wall sections in arbitrary way. You would like to achieve maximum possible reliability of the defence plan.

Input format:
The first line of the input contains three integers n, r and k (1 ≤ n ≤ 500 000, 0 ≤ r ≤ n, 0 ≤ k ≤ 1018) — the number of sections of the wall, the maximum distance to other section archers can still shoot and the number of archers yet to be distributed along the wall. The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 109) — the current number of archers at each section.

Output format:
Print one integer — the maximum possible value of defense plan reliability, i.e. the maximum possible value of minimum defense level if we distribute k additional archers optimally.

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

Example input:
5 0 6
5 4 3 4 9

Example output:
5

Example input:
4 2 0
1 2 3 4

Example output:
6

Editorial:
Firstly, if we may obtain reliability at least x, then we may obtain reliability not less than x - 1 with the same number of archers. So we may use binary search and check whether we may obtain reliability at least x.
How can we check it? Let's find the leftmost section such that its defense level is less than x. Let its index be i. We obviously have to add some archers controlling this section, and since every section to the left of it is already controlled, the best option where to add archers is the section with index min(i + r, n). After we added enough archers, we move to next section such that its defense level is less than x and do the same. If we run out of archers without protecting all the sections, then it's impossible to obtain reliability x.
To do checking in O(n), we may use prefix sums or "sliding window" technique.
Yet Another String Matching Problem
Contest: Educational Codeforces Round 40 (Rated for Div. 2)
Difficulty rating: 2200
Tags: fft, math

Suppose you have two strings s and t, and their length is equal. You may perform the following operation any number of times: choose two different characters c1 and c2, and replace every occurence of c1 in both strings with c2. Let's denote the distance between strings s and t as the minimum number of operations required to make these strings equal. For example, if s is abcd and t is ddcb, the distance between them is 2 — we may replace every occurence of a with b, so s becomes bbcd, and then we may replace every occurence of b with d, so both strings become ddcd.

You are given two strings S and T. For every substring of S consisting of |T| characters you have to determine the distance between this substring and T.

Input format:
The first line contains the string S, and the second — the string T (1 ≤ |T| ≤ |S| ≤ 125000). Both strings consist of lowercase Latin letters from a to f.

Output format:
Print |S| - |T| + 1 integers. The i-th of these integers must be equal to the distance between the substring of S beginning at i-th index with length |T| and the string T.

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

Example input:
abcdefa
ddcb

Example output:
2 3 3 3

Editorial:
Unfortunately, it seems we failed to eliminate bitset solutions.
The approach in our model solution is the following:
Firstly, let's try to find some "naive" solution for calculating the distance between two strings. We may build an undirected graph where vertices represent letters, and edges represent that one letter must be transformed into another. Then all letters in the same component should become one letter, so the answer is the number of distinct letters minus the number of components.
Then let's get back to original problem. For every substring of S we have to find which letters have to be merged to make it equal with T. This can be done with the help of FFT: to find all positions in substrings of S with character a that coincide with occurences of b in T, we may compute a convolution of two following arrays: set 1 to every position in S where occurs a, and to every position in T where b occurs (all other elements should be 0). After trying these convolutions for every pair of different characters, we compute the answer for every substring using DFS (or any other method).
Triangle
Contest: Codeforces Round 239 (Div. 1)
Difficulty rating: 1600
Tags: brute force, geometry, implementation, math

There is a right triangle with legs of length a and b. Your task is to determine whether it is possible to locate the triangle on the plane in such a way that none of its sides is parallel to the coordinate axes. All the vertices must have integer coordinates. If there exists such a location, you have to output the appropriate coordinates of vertices.

Input format:
The first line contains two integers a, b (1 ≤ a, b ≤ 1000), separated by a single space.

Output format:
In the first line print either "YES" or "NO" (without the quotes) depending on whether the required location exists. If it does, print in the next three lines three pairs of integers — the coordinates of the triangle vertices, one pair per line. The coordinates must be integers, not exceeding 109 in their absolute value.

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

Example input:
1 1

Example output:
NO

Example input:
5 5

Example output:
YES
2 1
5 5
-2 4

Editorial:
Long Path
Contest: Codeforces Round 239 (Div. 1)
Difficulty rating: 1600
Tags: dp, implementation

One day, little Vasya found himself in a maze consisting of (n + 1) rooms, numbered from 1 to (n + 1). Initially, Vasya is at the first room and to get out of the maze, he needs to get to the (n + 1)-th one.

The maze is organized as follows. Each room of the maze has two one-way portals. Let's consider room number i (1 ≤ i ≤ n), someone can use the first portal to move from it to room number (i + 1), also someone can use the second portal to move from it to room number pi, where 1 ≤ pi ≤ i.

In order not to get lost, Vasya decided to act as follows.

- Each time Vasya enters some room, he paints a cross on its ceiling. Initially, Vasya paints a cross at the ceiling of room 1.
- Let's assume that Vasya is in room i and has already painted a cross on its ceiling. Then, if the ceiling now contains an odd number of crosses, Vasya uses the second portal (it leads to room pi), otherwise Vasya uses the first portal.

Help Vasya determine the number of times he needs to use portals to get to room (n + 1) in the end.

Input format:
The first line contains integer n (1 ≤ n ≤ 103) — the number of rooms. The second line contains n integers pi (1 ≤ pi ≤ i). Each pi denotes the number of the room, that someone can reach, if he will use the second portal in the i-th room.

Output format:
Print a single number — the number of portal moves the boy needs to go out of the maze. As the number can be rather large, print it modulo 1000000007 (109 + 7).

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

Example input:
2
1 2

Example output:
4

Example input:
4
1 1 2 3

Example output:
20

Editorial:
Curious Array
Contest: Codeforces Round 239 (Div. 1)
Difficulty rating: 2500
Tags: brute force, combinatorics, implementation, math

You've got an array consisting of n integers: a[1], a[2], ..., a[n]. Moreover, there are m queries, each query can be described by three integers li, ri, ki. Query li, ri, ki means that we should add $${ \binom { j - l _ { i } + k _ { i } } { k _ { i } } }$$ to each element a[j], where li ≤ j ≤ ri.

Record $${ \frac { y } { x } }$$ means the binomial coefficient, or the number of combinations from y elements into groups of x elements.

You need to fulfil consecutively all queries and then print the final array.

Input format:
The first line contains integers n, m (1 ≤ n, m ≤ 105).

The second line contains n integers a[1], a[2], ..., a[n] (0 ≤ ai ≤ 109) — the initial array.

Next m lines contain queries in the format li, ri, ki — to all elements of the segment li... ri add number $${ \binom { j - l _ { i } + k _ { i } } { k _ { i } } }$$ (1 ≤ li ≤ ri ≤ n; 0 ≤ k ≤ 100).

Output format:
Print n integers: the i-th number is the value of element a[i] after all the queries. As the values can be rather large, print them modulo 1000000007 (109 + 7).

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

Example input:
5 1
0 0 0 0 0
1 5 0

Example output:
1 1 1 1 1

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

Example output:
2 4 6 8 10 7 3 6 10 15

Editorial:
Largest Submatrix 3
Contest: Codeforces Round 239 (Div. 1)
Difficulty rating: 2700
Tags: dp, hashing

You are given matrix a of size n × m, its elements are integers. We will assume that the rows of the matrix are numbered from top to bottom from 1 to n, the columns are numbered from left to right from 1 to m. We will denote the element on the intersecting of the i-th row and the j-th column as aij.

We'll call submatrix i1, j1, i2, j2 (1 ≤ i1 ≤ i2 ≤ n; 1 ≤ j1 ≤ j2 ≤ m) such elements aij of the given matrix that i1 ≤ i ≤ i2 AND j1 ≤ j ≤ j2. We'll call the area of the submatrix number (i2 - i1 + 1)·(j2 - j1 + 1). We'll call a submatrix inhomogeneous, if all its elements are distinct.

Find the largest (in area) inhomogenous submatrix of the given matrix.

Input format:
The first line contains two integers n, m (1 ≤ n, m ≤ 400) — the number of rows and columns of the matrix, correspondingly.

Each of the next n lines contains m integers aij (1 ≤ aij ≤ 160000) — the elements of the matrix.

Output format:
Print a single integer — the area of the optimal inhomogenous submatrix.

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

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

Example output:
6

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

Example output:
4

Editorial:
k-d-sequence
Contest: Codeforces Round 239 (Div. 1)
Difficulty rating: 3100
Tags: data structures

We'll call a sequence of integers a good k-d sequence if we can add to it at most k numbers in such a way that after the sorting the sequence will be an arithmetic progression with difference d.

You got hold of some sequence a, consisting of n integers. Your task is to find its longest contiguous subsegment, such that it is a good k-d sequence.

Input format:
The first line contains three space-separated integers n, k, d (1 ≤ n ≤ 2·105; 0 ≤ k ≤ 2·105; 0 ≤ d ≤ 109). The second line contains n space-separated integers: a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the actual sequence.

Output format:
Print two space-separated integers l, r (1 ≤ l ≤ r ≤ n) show that sequence al, al + 1, ..., ar is the longest subsegment that is a good k-d sequence.

If there are multiple optimal answers, print the one with the minimum value of l.

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

Note:
In the first test sample the answer is the subsegment consisting of numbers 2, 8, 6 — after adding number 4 and sorting it becomes sequence 2, 4, 6, 8 — the arithmetic progression with difference 2.

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

Example output:
3 5

Editorial:
EhAb AnD gCd
Contest: Codeforces Round 628 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, greedy, number theory

You are given a positive integer $$$x$$$. Find any such $$$2$$$ positive integers $$$a$$$ and $$$b$$$ such that $$$GCD(a,b)+LCM(a,b)=x$$$.

As a reminder, $$$GCD(a,b)$$$ is the greatest integer that divides both $$$a$$$ and $$$b$$$. Similarly, $$$LCM(a,b)$$$ is the smallest integer such that both $$$a$$$ and $$$b$$$ divide it.

It's guaranteed that the solution always exists. If there are several such pairs $$$(a, b)$$$, you can output any of them.

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

Each testcase consists of one line containing a single integer, $$$x$$$ $$$(2 \le x \le 10^9)$$$.

Output format:
For each testcase, output a pair of positive integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^9)$$$ such that $$$GCD(a,b)+LCM(a,b)=x$$$. It's guaranteed that the solution always exists. If there are several such pairs $$$(a, b)$$$, you can output any of them.

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

Note:
In the first testcase of the sample, $$$GCD(1,1)+LCM(1,1)=1+1=2$$$.

In the second testcase of the sample, $$$GCD(6,4)+LCM(6,4)=2+12=14$$$.

Example input:
2
2
14

Example output:
1 1
6 4

Editorial: