1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Trails (Easy)
Contest: Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)
Difficulty rating: 1800
Tags: dp

Harry Potter is hiking in the Alps surrounding Lake Geneva. In this area there are $$$m$$$ cabins, numbered 1 to $$$m$$$. Each cabin is connected, with one or more trails, to a central meeting point next to the lake. Each trail is either short or long. Cabin $$$i$$$ is connected with $$$s_i$$$ short trails and $$$l_i$$$ long trails to the lake.

Each day, Harry walks a trail from the cabin where he currently is to Lake Geneva, and then from there he walks a trail to any of the $$$m$$$ cabins (including the one he started in). However, as he has to finish the hike in a day, at least one of the two trails has to be short.

How many possible combinations of trails can Harry take if he starts in cabin 1 and walks for $$$n$$$ days?

Give the answer modulo $$$10^9 + 7$$$.

Input format:
The first line contains the integers $$$m$$$ and $$$n$$$.

The second line contains $$$m$$$ integers, $$$s_1, \dots, s_m$$$, where $$$s_i$$$ is the number of short trails between cabin $$$i$$$ and Lake Geneva.

The third and last line contains $$$m$$$ integers, $$$l_1, \dots, l_m$$$, where $$$l_i$$$ is the number of long trails between cabin $$$i$$$ and Lake Geneva.

We have the following constraints:

$$$0 \le s_i, l_i \le 10^3$$$.

$$$1 \le m \le 10^2$$$.

$$$1 \le n \le 10^3$$$.

Output format:
The number of possible combinations of trails, modulo $$$10^9 + 7$$$.

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

Example input:
3 2
1 0 1
0 1 1

Example output:
18

Editorial:
Let $$$t_i := s_i + l_i$$$. The number of possible paths between cabin $$$i$$$ and cabin $$$j$$$ is $$$t_i t_j - l_i l_j$$$.
Let $$$\mathbf{v}_{k,i}$$$ be the number of paths that ends in cabin $$$i$$$ after walking for $$$k$$$ days. We then have $$$$$$ \mathbf{v}_{0,1} = 1, \\ \mathbf{v}_{0,i} = 0 \text{ for } i \neq 1, $$$$$$ and $$$$$$ \mathbf{v}_{k+1,i} = \sum_{j = 1}^{m} (t_i t_j - l_i l_j) \mathbf{v}_{k,j}. $$$$$$ Thus, we can compute $$$(\mathbf{v}_{k+1,1}, \dots, \mathbf{v}_{k+1,m})$$$ from $$$(\mathbf{v}_{k,1}, \dots, \mathbf{v}_{k,m})$$$ in $$$\mathcal{O}(m^2)$$$ time using this formula. We do this $$$n$$$ times to get $$$(\mathbf{v}_{n,1}, \dots, \mathbf{v}_{n, m})$$$. The solution to the problem is now $$$$$$ \mathbf{v}_{n,1} + \dots + \mathbf{v}_{n,m}. $$$$$$ The total running complexity is $$$\mathcal{O}(n m^2)$$$.
Trails (Medium)
Contest: Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)
Difficulty rating: 2000
Tags: dp, matrices

Harry Potter is hiking in the Alps surrounding Lake Geneva. In this area there are $$$m$$$ cabins, numbered 1 to $$$m$$$. Each cabin is connected, with one or more trails, to a central meeting point next to the lake. Each trail is either short or long. Cabin $$$i$$$ is connected with $$$s_i$$$ short trails and $$$l_i$$$ long trails to the lake.

Each day, Harry walks a trail from the cabin where he currently is to Lake Geneva, and then from there he walks a trail to any of the $$$m$$$ cabins (including the one he started in). However, as he has to finish the hike in a day, at least one of the two trails has to be short.

How many possible combinations of trails can Harry take if he starts in cabin 1 and walks for $$$n$$$ days?

Give the answer modulo $$$10^9 + 7$$$.

Input format:
The first line contains the integers $$$m$$$ and $$$n$$$.

The second line contains $$$m$$$ integers, $$$s_1, \dots, s_m$$$, where $$$s_i$$$ is the number of short trails between cabin $$$i$$$ and Lake Geneva.

The third and last line contains $$$m$$$ integers, $$$l_1, \dots, l_m$$$, where $$$l_i$$$ is the number of long trails between cabin $$$i$$$ and Lake Geneva.

We have the following constraints:

$$$0 \le s_i, l_i \le 10^3$$$.

$$$1 \le m \le 10^2$$$.

$$$1 \le n \le 10^9$$$.

Output format:
The number of possible combinations of trails, modulo $$$10^9 + 7$$$.

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

Example input:
3 2
1 0 1
0 1 1

Example output:
18

Editorial:
Let $$$t_i := s_i + l_i$$$. The number of possible paths between cabin $$$i$$$ and cabin $$$j$$$ is $$$t_i t_j - l_i l_j$$$.
Let $$$\mathbf{v}_{k}$$$ be the vector whose $$$i$$$th entry is the number of paths that ends in cabin $$$i$$$ after walking for $$$k$$$ days. We then have $$$$$$ \mathbf{v}_0 = (1, 0, \dots, 0), $$$$$$ and $$$$$$ (\mathbf{v}_{k+1})_i = \sum_{j = 1}^{m} (t_i t_j - l_i l_j) (\mathbf{v}_{k})_j. $$$$$$ Let $$$A$$$ be the $$$(m \times m)$$$–matrix given by $$$$$$ A_{i,j} = t_i t_j - l_i l_j. $$$$$$ Then the formula for $$$\mathbf{v}_{k+1}$$$ can be rewritten as $$$$$$ \mathbf{v}_{k+1} = A \mathbf{v}_k. $$$$$$ Hence, $$$$$$ \mathbf{v}_n = A^n \mathbf{v}_0. $$$$$$ Now, we can compute $$$A^n$$$ in $$$\mathcal{O}(\log(n) m^3)$$$ time using the following recursive formula.
1. Compute $$$B := A^{\lfloor n/2 \rfloor}$$$
2. If $$$n$$$ is even: Return $$$B^2$$$
3. Else: Return $$$B^2 A$$$
The solution to the problem is now $$$$$$ (\mathbf{v}_n)_1 + \dots + (\mathbf{v}_n)_m. $$$$$$ The total running complexity is $$$\mathcal{O}(\log(n) m^3)$$$.
Four Segments
Contest: 2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules)
Difficulty rating: 800
Tags: greedy

Monocarp wants to draw four line segments on a sheet of paper. He wants the $$$i$$$-th segment to have its length equal to $$$a_i$$$ ($$$1 \le i \le 4$$$). These segments can intersect with each other, and each segment should be either horizontal or vertical.

Monocarp wants to draw the segments in such a way that they enclose a rectangular space, and the area of that rectangular space should be maximum possible.

For example, if Monocarp wants to draw four segments with lengths $$$1$$$, $$$2$$$, $$$3$$$ and $$$4$$$, he can do it the following way:

Here, Monocarp has drawn segments $$$AB$$$ (with length $$$1$$$), $$$CD$$$ (with length $$$2$$$), $$$BC$$$ (with length $$$3$$$) and $$$EF$$$ (with length $$$4$$$). He got a rectangle $$$ABCF$$$ with area equal to $$$3$$$ that is enclosed by the segments.

Calculate the maximum area of a rectangle Monocarp can enclose with four segments.

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

Each test case consists of a single line containing four integers $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, $$$a_4$$$ ($$$1 \le a_i \le 10^4$$$) — the lengths of the segments Monocarp wants to draw.

Output format:
For each test case, print one integer — the maximum area of a rectangle Monocarp can enclose with four segments (it can be shown that the answer is always an integer).

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

Note:
The first test case of the example is described in the statement.

For the second test case, Monocarp can draw the segments $$$AB$$$, $$$BC$$$, $$$CD$$$ and $$$DA$$$ as follows:

Here, Monocarp has drawn segments $$$AB$$$ (with length $$$5$$$), $$$BC$$$ (with length $$$5$$$), $$$CD$$$ (with length $$$5$$$) and $$$DA$$$ (with length $$$5$$$). He got a rectangle $$$ABCD$$$ with area equal to $$$25$$$ that is enclosed by the segments.

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

Example output:
3
25
3
2000

Editorial:
Suppose the values of $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, $$$a_4$$$ are sorted in non-descending order. Then the shorter side of the rectangle cannot be longer than $$$a_1$$$, because one of the sides must be formed by a segment of length $$$a_1$$$. Similarly, the longer side of the rectangle cannot be longer than $$$a_3$$$, because there should be at least two segments with length not less than the length of the longer side. So, the answer cannot be greater than $$$a_1 \cdot a_3$$$.
It's easy to construct the rectangle with exactly this area by drawing the following segments:
• from $$$(0, 0)$$$ to $$$(a_1, 0)$$$;
• from $$$(0, a_3)$$$ to $$$(a_2, a_3)$$$;
• from $$$(0, 0)$$$ to $$$(0, a_3)$$$;
• from $$$(a_1, 0)$$$ to $$$(a_1, a_4)$$$.
So, the solution is to sort the sequence $$$[a_1, a_2, a_3, a_4]$$$, and then print $$$a_1 \cdot a_3$$$.
Coins
Contest: Educational Codeforces Round 146 (Rated for Div. 2)
Difficulty rating: 800
Tags: implementation, math

In Berland, there are two types of coins, having denominations of $$$2$$$ and $$$k$$$ burles.

Your task is to determine whether it is possible to represent $$$n$$$ burles in coins, i. e. whether there exist non-negative integers $$$x$$$ and $$$y$$$ such that $$$2 \cdot x + k \cdot y = n$$$.

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

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^{18}$$$; $$$k \ne 2$$$).

Output format:
For each test case, print YES if it is possible to represent $$$n$$$ burles in coins; otherwise, print NO. You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

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

Note:
In the first test case, you can take one coin with denomination $$$2$$$ and one coin with denomination $$$k = 3$$$.

In the second test case, you can take three coins with denomination $$$2$$$. Alternatively, you can take six coins with denomination $$$k = 1$$$.

In the third test case, there is no way to represent $$$7$$$ burles.

In the fourth test case, you can take one coin with denomination $$$k = 8$$$.

Example input:
4
5 3
6 1
7 4
8 8

Example output:
YES
YES
NO
YES

Editorial:
Note that $$$2$$$ coins with denomination $$$k$$$ can be replaced with $$$k$$$ coins with denomination $$$2$$$. So, if the answer exists, then there is also such a set of coins, where there is no more than one coin with denomination $$$k$$$. Therefore, it is enough to iterate through the number of coins with denomination $$$k$$$ (from $$$0$$$ to $$$1$$$) and check that the remaining number is non-negative and even (i. e. it can be represented as some number of coins with denomination $$$2$$$).
Comparing Two Long Integers
Contest: Educational Codeforces Round 5
Difficulty rating: 900
Tags: implementation, strings

You are given two very long integers a, b (leading zeroes are allowed). You should check what number a or b is greater or determine that they are equal.

The input size is very large so don't use the reading of symbols one by one. Instead of that use the reading of a whole line or token.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java. Don't use the function input() in Python2 instead of it use the function raw_input().

Input format:
The first line contains a non-negative integer a.

The second line contains a non-negative integer b.

The numbers a, b may contain leading zeroes. Each of them contains no more than 106 digits.

Output format:
Print the symbol "<" if a < b and the symbol ">" if a > b. If the numbers are equal print the symbol "=".

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

Example input:
9
10

Example output:
<

Example input:
11
10

Example output:
>

Editorial:
Dinner with Emma
Contest: Educational Codeforces Round 5
Difficulty rating: 1000
Tags: games, greedy

Jack decides to invite Emma out for a dinner. Jack is a modest student, he doesn't want to go to an expensive restaurant. Emma is a girl with high taste, she prefers elite places.

Munhattan consists of n streets and m avenues. There is exactly one restaurant on the intersection of each street and avenue. The streets are numbered with integers from 1 to n and the avenues are numbered with integers from 1 to m. The cost of dinner in the restaurant at the intersection of the i-th street and the j-th avenue is cij.

Jack and Emma decide to choose the restaurant in the following way. Firstly Emma chooses the street to dinner and then Jack chooses the avenue. Emma and Jack makes their choice optimally: Emma wants to maximize the cost of the dinner, Jack wants to minimize it. Emma takes into account that Jack wants to minimize the cost of the dinner. Find the cost of the dinner for the couple in love.

Input format:
The first line contains two integers n, m (1 ≤ n, m ≤ 100) — the number of streets and avenues in Munhattan.

Each of the next n lines contains m integers cij (1 ≤ cij ≤ 109) — the cost of the dinner in the restaurant on the intersection of the i-th street and the j-th avenue.

Output format:
Print the only integer a — the cost of the dinner for Jack and Emma.

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

Note:
In the first example if Emma chooses the first or the third streets Jack can choose an avenue with the cost of the dinner 1. So she chooses the second street and Jack chooses any avenue. The cost of the dinner is 2.

In the second example regardless of Emma's choice Jack can choose a restaurant with the cost of the dinner 1.

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

Example output:
2

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

Example output:
1

Editorial:
The Labyrinth
Contest: Educational Codeforces Round 5
Difficulty rating: 1600
Tags: dfs and similar

You are given a rectangular field of n × m cells. Each cell is either empty or impassable (contains an obstacle). Empty cells are marked with '.', impassable cells are marked with '*'. Let's call two empty cells adjacent if they share a side.

Let's call a connected component any non-extendible set of cells such that any two of them are connected by the path of adjacent cells. It is a typical well-known definition of a connected component.

For each impassable cell (x, y) imagine that it is an empty cell (all other cells remain unchanged) and find the size (the number of cells) of the connected component which contains (x, y). You should do it for each impassable cell independently.

The answer should be printed as a matrix with n rows and m columns. The j-th symbol of the i-th row should be "." if the cell is empty at the start. Otherwise the j-th symbol of the i-th row should contain the only digit —- the answer modulo 10. The matrix should be printed without any spaces.

To make your output faster it is recommended to build the output as an array of n strings having length m and print it as a sequence of lines. It will be much faster than writing character-by-character.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

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

Each of the next n lines contains m symbols: "." for empty cells, "*" for impassable cells.

Output format:
Print the answer as a matrix as described above. See the examples to precise the format of the output.

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

Note:
In first example, if we imagine that the central cell is empty then it will be included to component of size 5 (cross). If any of the corner cell will be empty then it will be included to component of size 3 (corner).

Example input:
3 3
*.*
.*.
*.*

Example output:
3.3
.5.
3.3

Example input:
4 5
**..*
..***
.*.*.
*.*.*

Example output:
46..3
..732
.6.4.
5.4.3

Editorial:
Longest k-Good Segment
Contest: Educational Codeforces Round 5
Difficulty rating: 1600
Tags: binary search, data structures, two pointers

The array a with n integers is given. Let's call the sequence of one or more consecutive elements in a segment. Also let's call the segment k-good if it contains no more than k different values.

Find any longest k-good segment.

As the input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

Input format:
The first line contains two integers n, k (1 ≤ k ≤ n ≤ 5·105) — the number of elements in a and the parameter k.

The second line contains n integers ai (0 ≤ ai ≤ 106) — the elements of the array a.

Output format:
Print two integers l, r (1 ≤ l ≤ r ≤ n) — the index of the left and the index of the right ends of some k-good longest segment. If there are several longest segments you can print any of them. The elements in a are numbered from 1 to n from left to right.

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

Example input:
5 5
1 2 3 4 5

Example output:
1 5

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

Example output:
3 7

Editorial:
Sum of Remainders
Contest: Educational Codeforces Round 5
Difficulty rating: 2200
Tags: implementation, math, number theory

Calculate the value of the sum: n mod 1 + n mod 2 + n mod 3 + ... + n mod m. As the result can be very large, you should print the value modulo 109 + 7 (the remainder when divided by 109 + 7).

The modulo operator a mod b stands for the remainder after dividing a by b. For example 10 mod 3 = 1.

Input format:
The only line contains two integers n, m (1 ≤ n, m ≤ 1013) — the parameters of the sum.

Output format:
Print integer s — the value of the required sum modulo 109 + 7.

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

Example input:
3 4

Example output:
4

Example input:
4 4

Example output:
1

Editorial:
Expensive Strings
Contest: Educational Codeforces Round 5
Difficulty rating: 2700
Tags: data structures, sortings, string suffix structures, strings

You are given n strings ti. Each string has cost ci.

Let's define the function of string $$s : f(s) = \sum_{i=1}^{n} c_i \cdot p_{s,i} \cdot |s|$$, where ps, i is the number of occurrences of s in ti, |s| is the length of the string s. Find the maximal value of function f(s) over all strings.

Note that the string s is not necessarily some string from t.

Input format:
The first line contains the only integer n (1 ≤ n ≤ 105) — the number of strings in t.

Each of the next n lines contains contains a non-empty string ti. ti contains only lowercase English letters.

It is guaranteed that the sum of lengths of all strings in t is not greater than 5·105.

The last line contains n integers ci ( - 107 ≤ ci ≤ 107) — the cost of the i-th string.

Output format:
Print the only integer a — the maximal value of the function f(s) over all strings s. Note one more time that the string s is not necessarily from t.

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

Example input:
2
aa
bb
2 1

Example output:
4

Example input:
2
aa
ab
2 1

Example output:
5

Editorial:
Volatile Kite
Contest: VK Cup 2017 - Round 2
Difficulty rating: 1800
Tags: geometry

You are given a convex polygon P with n distinct vertices p1, p2, ..., pn. Vertex pi has coordinates (xi, yi) in the 2D plane. These vertices are listed in clockwise order.

You can choose a real number D and move each vertex of the polygon a distance of at most D from their original positions.

Find the maximum value of D such that no matter how you move the vertices, the polygon does not intersect itself and stays convex.

Input format:
The first line has one integer n (4 ≤ n ≤ 1 000) — the number of vertices.

The next n lines contain the coordinates of the vertices. Line i contains two integers xi and yi ( - 109 ≤ xi, yi ≤ 109) — the coordinates of the i-th vertex. These points are guaranteed to be given in clockwise order, and will form a strictly convex polygon (in particular, no three consecutive points lie on the same straight line).

Output format:
Print one real number D, which is the maximum real number such that no matter how you move the vertices, the polygon stays convex.

Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely, let's assume that your answer is a and the answer of the jury is b. The checker program will consider your answer correct if $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$.

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

Note:
Here is a picture of the first sample

Here is an example of making the polygon non-convex.

This is not an optimal solution, since the maximum distance we moved one point is  ≈ 0.4242640687, whereas we can make it non-convex by only moving each point a distance of at most  ≈ 0.3535533906.

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

Example output:
0.3535533906

Example input:
6
5 0
10 0
12 -4
10 -8
5 -8
3 -4

Example output:
1.0000000000

Editorial:
First, let's restate the problem as the minimum distance D needed to make the polygon nonconvex. We can notice we can achieve this by by changing one angle of the polygon nonconvex. So, that involves moving at most 3 points. Let's take a look at the following picture:

Here, A,B,C denote consecutive vertices on our polygon. The circle represents the area that each point can be moved to (once we fix our distance), and we want to choose red points that lie in or on the circle such that they form an obtuse angle.
We can see that this is possible as long as the radius exceeds half the distance between segment AC and point B. Thus, we just need to compute the minimum such distance for all such consecutive three points on our polygon.
To compute the distance between a segment and a point, consider this link: https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line#Line_defined_by_two_points In particular, it is the cross product between (B-A) and (C-A) divided by the length of segment AC.
Vulnerable Kerbals
Contest: VK Cup 2017 - Round 2
Difficulty rating: 2300
Tags: constructive algorithms, dp, graphs, math, number theory

You are given an integer m, and a list of n distinct integers between 0 and m - 1.

You would like to construct a sequence satisfying the properties:

- Each element is an integer between 0 and m - 1, inclusive.
- All prefix products of the sequence modulo m are distinct.
- No prefix product modulo m appears as an element of the input list.
- The length of the sequence is maximized.

Construct any sequence satisfying the properties above.

Input format:
The first line of input contains two integers n and m (0 ≤ n < m ≤ 200 000) — the number of forbidden prefix products and the modulus.

If n is non-zero, the next line of input contains n distinct integers between 0 and m - 1, the forbidden prefix products. If n is zero, this line doesn't exist.

Output format:
On the first line, print the number k, denoting the length of your sequence.

On the second line, print k space separated integers, denoting your sequence.

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

Note:
For the first case, the prefix products of this sequence modulo m are [1, 2, 3, 4, 0].

For the second case, the prefix products of this sequence modulo m are [3, 7, 4, 6, 8, 0].

Example input:
0 5

Example output:
5
1 2 4 3 0

Example input:
3 10
2 9 1

Example output:
6
3 9 2 9 8 0

Editorial:
Let's consider a directed graph with m nodes, labeled from 1 to m, where there is an edge between nodes i and node j if there exists a number x such that $$i x \equiv j \mod m$$.
Now, we can notice there is an edge between node i and node j if and only if gcd(n, i) divides gcd(n, j).
So, there are two directed edges between two nodes i and j if and only if gcd(n, i) = gcd(n, j). So, these form some directed cliques in our graphs.
We can also notice that this happens to form the SCC decomposition of our graph (i.e. condensation). So this problem reduces to finding the heaviest path in a DAG with weights on nodes. The nodes in this dag correspond to divisors of n, and the weight corresponds to the number of allowed numbers with that gcd.