1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Travel to Bertown
Contest: Kotlin Heroes: Episode 7
Tags: *special, implementation, math

Vika has decided to go on a trip to Bertown. She comes to Bertown on the $$$k$$$-th day. Vika does not want to spend money on hotels, fortunately she has $$$n$$$ friends who live in Bertown and allow Vika to stay at their houses. The $$$i$$$-th friend told Vika that she could stay at their house from the $$$l_i$$$-th day till the $$$r_i$$$-th day, inclusive.

Vika decided that she would stay at no more than one friend's house. Help Vika determine the maximum number of days that she will be able to stay in Bertown.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 100$$$) — the number of Vika's friends and the day when Vika comes to Bertown.

Then follow $$$n$$$ lines, each containing two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 100$$$) denoting the period when Vika can stay at the $$$i$$$-th friend's house.

Output format:
For each test case, output a single integer — the maximum number of days that Vika can stay in Bertown (or $$$0$$$ if none of Vika's friends can host her on day $$$k$$$).

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

Note:
In the first example, Vika can stay at the $$$2$$$-nd friend's house from $$$3$$$-rd to $$$6$$$-th day.

In the second example, none of Vika's friends can host her on the $$$4$$$-th day.

In the third example, Vika can stay at the $$$1$$$-st friend's house, but only for the $$$4$$$-th day.

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

Example output:
4
0
1

Editorial:
To solve this problem, we can use an approach similar to finding the maximum element in the array. Initialize the answer with $$$0$$$, then run a loop for $$$i$$$ from $$$1$$$ to $$$n$$$. In this loop, if $$$k$$$ belongs to the segment $$$[l_i, r_i]$$$, then the answer should be updated with the value $$$r_i - k + 1$$$.
String Searching
Contest: Kotlin Heroes: Episode 7
Tags: *special, hashing

You are given an array $$$s$$$ consisting of $$$n$$$ different strings. Each string consists of $$$m$$$ lowercase Latin letters.

You have to respond to $$$q$$$ queries. Each query contains a string $$$t$$$ of length $$$m+1$$$. Count the number of indices $$$i$$$, such that the string $$$t$$$ can be obtained from the string $$$s_i$$$, if it is allowed to insert one letter in an arbitrary position.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le m \le 10$$$) — the number of strings in the array and the length of each string.

The following $$$n$$$ lines contain strings $$$s_i$$$. All of the given strings are different.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries.

The following $$$q$$$ lines contain query strings $$$t$$$ of length $$$m + 1$$$.

Output format:
For each query, print the number of indices $$$i$$$, such that a string from the query can be obtained from the string $$$s_i$$$, if it is allowed to insert one letter in an arbitrary position.

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

Note:
Explanation of the first test of the example:

- the string a can be transformed into aa by inserting one letter;
- both strings a and c can be transformed into ca by inserting one letter;
- neither a nor c can be transformed into mm by inserting one letter;
- c can be transformed into cf by inserting one letter.

Example input:
2 1
a
c
4
aa
ca
mm
cf

Example output:
1
2
0
1

Example input:
6 3
dba
abd
cbb
ada
add
bdd
5
ccbb
abdd
adba
bada
dddd

Example output:
1
3
2
1
0

Editorial:
To answer a query, it is enough to iterate over a character we delete from the string given in the query, and then check whether the resulting string is in the given set of strings (which should be stored in some associative data structure, for example, in a Set). Note that if deleting different positions can lead to identical strings, you have to count these strings once (i. e., if the query is aaa, then the string aa should be counted $$$1$$$ time, not $$$3$$$); it can be done by storing all strings we can obtain by deleting one character in another Set, since it removes duplicate elements.
Binary String Partition
Contest: Kotlin Heroes: Episode 7
Tags: *special, binary search, greedy

Let's call a string $$$t$$$ consisting of characters 0 and/or 1 beautiful, if either the number of occurrences of character 0 in this string does not exceed $$$k$$$, or the number of occurrences of characters 1 in this string does not exceed $$$k$$$ (or both). For example, if $$$k = 3$$$, the strings 101010, 111, 0, 00000, 1111111000 are beautiful, and the strings 1111110000, 01010101 are not beautiful.

You are given a string $$$s$$$. You have to divide it into the minimum possible number of beautiful strings, i. e., find a sequence of strings $$$t_1, t_2, \dots, t_m$$$ such that every $$$t_i$$$ is beautiful, $$$t_1 + t_2 + \dots + t_m = s$$$ (where $$$+$$$ is the concatenation operator), and $$$m$$$ is minimum possible.

For every $$$k$$$ from $$$1$$$ to $$$|s|$$$, find the minimum possible number of strings such that $$$s$$$ can be divided into them (i. e. the minimum possible $$$m$$$ in the partition).

Input format:
The only line contains one string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$). Each character of $$$s$$$ is either 0 or 1.

Output format:
Print $$$|s|$$$ integers. The $$$i$$$-th integer should be equal to the minimum number of strings in the partition of $$$s$$$, when $$$k = i$$$.

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

Example input:
00100010

Example output:
2 1 1 1 1 1 1 1

Example input:
1001011100

Example output:
3 2 2 2 1 1 1 1 1 1

Editorial:
We will solve the problem for each value of $$$k$$$ separately.
Note that there is an optimal partition where all $$$t_i$$$ (except the last one) contain exactly $$$k$$$ zeros or ones. Using this fact, we can find in which position the next block $$$t_i$$$ will end. The current block $$$t_i$$$ should end before it contains at least $$$k+1$$$ zeros and at least $$$k+1$$$ ones. To quickly find this position, you can use a binary search with prefix sums, or save all the positions of zeros (ones) in a separate array. Such a solution will work for $$$O(m)$$$ or $$$O(m \log{n})$$$ (depending on whether binary search is used), where $$$m$$$ is the number of strings in the partition.
For each $$$k$$$, the value of $$$m$$$ does not exceed $$$\frac{n}{2k+1}$$$ (because there are at least $$$2k+1$$$ elements in each block). This means that the sum of $$$m$$$ for all $$$k$$$ does not exceed $$$\sum\limits_{k=1}^{n} \frac{n}{k}$$$, which is estimated as $$$O(n \log{n})$$$, which means that the entire solution works for $$$O(n \log{n})$$$ or $$$O(n \log^2{n})$$$.
Submatrices
Contest: Kotlin Heroes: Episode 7
Tags: *special, bitmasks, data structures, dp

You are given matrix $$$s$$$ that contains $$$n$$$ rows and $$$m$$$ columns. Each element of a matrix is one of the $$$5$$$ first Latin letters (in upper case).

For each $$$k$$$ ($$$1 \le k \le 5$$$) calculate the number of submatrices that contain exactly $$$k$$$ different letters. Recall that a submatrix of matrix $$$s$$$ is a matrix that can be obtained from $$$s$$$ after removing several (possibly zero) first rows, several (possibly zero) last rows, several (possibly zero) first columns, and several (possibly zero) last columns. If some submatrix can be obtained from $$$s$$$ in two or more ways, you have to count this submatrix the corresponding number of times.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 800$$$).

Then $$$n$$$ lines follow, each containing the string $$$s_i$$$ ($$$|s_i| = m$$$) — $$$i$$$-th row of the matrix.

Output format:
For each $$$k$$$ ($$$1 \le k \le 5$$$) print one integer — the number of submatrices that contain exactly $$$k$$$ different letters.

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

Example input:
2 3
ABB
ABA

Example output:
9 9 0 0 0

Example input:
6 6
EDCECE
EDDCEB
ACCECC
BAEEDC
DDDDEC
DDAEAD

Example output:
56 94 131 103 57

Editorial:
Let's iterate through the subset of the first $$$5$$$ letters and count the number of submatrices that contain only letters from this subset. To do this, create a matrix $$$a$$$ of size $$$n \times m$$$, where $$$a_{i, j} = 1$$$ if $$$s_{i, j}$$$ belongs to the fixed subset, and $$$0$$$ otherwise. Now, you have to calculate the number of submatrices that consist only of $$$1$$$'s in this matrix.
This can be calculated as follows. Let's iterate over the row $$$i$$$, it will be the lower boundary of the submatrix. Denote $$$d_j$$$ as the maximum value such that all $$$a_{k, j} = 1$$$ for $$$k \in (i - d_j, i]$$$ (build an array of these values). Using this array, let's calculate $$$l_j$$$ — the closest position to the left where the value in the array $$$d$$$ is strictly less than $$$d_j$$$, and $$$r_j$$$ — the closest position to the right where the value in the array $$$d$$$ is not greater than $$$d_j$$$. Then the number of unit submatrices where $$$i$$$ is the lower bound is $$$\sum\limits_{j=1}^{m} (j - l_j) * (r_j - j) * d_j$$$.
Thus, we have counted all the answers for subsets of letters, but these values are not exactly what we need to print (for example, if the submatrix contained $$$2$$$ different letters, then it will be taken into account in subsets of $$$3$$$, $$$4$$$ and $$$5$$$ letters that include these $$$2$$$ letters), but this is easy to fix with an approach similar to inclusion-exclusion. The final complexity of the solution is $$$O (2^5nm)$$$.
Divisible by Seven
Contest: Codeforces Round 221 (Div. 1)
Difficulty rating: 1600
Tags: math, number theory

You have number a, whose decimal representation quite luckily contains digits 1, 6, 8, 9. Rearrange the digits in its decimal representation so that the resulting number will be divisible by 7.

Number a doesn't contain any leading zeroes and contains digits 1, 6, 8, 9 (it also can contain another digits). The resulting number also mustn't contain any leading zeroes.

Input format:
The first line contains positive integer a in the decimal record. It is guaranteed that the record of number a contains digits: 1, 6, 8, 9. Number a doesn't contain any leading zeroes. The decimal representation of number a contains at least 4 and at most 106 characters.

Output format:
Print a number in the decimal notation without leading zeroes — the result of the permutation.

If it is impossible to rearrange the digits of the number a in the required manner, print 0.

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

Example input:
1689

Example output:
1869

Example input:
18906

Example output:
18690

Editorial:
Maximum Submatrix 2
Contest: Codeforces Round 221 (Div. 1)
Difficulty rating: 1600
Tags: data structures, dp, implementation, sortings

You are given a matrix consisting of digits zero and one, its size is n × m. You are allowed to rearrange its rows. What is the maximum area of the submatrix that only consists of ones and can be obtained in the given problem by the described operations?

Let's assume that the rows of matrix a are numbered from 1 to n from top to bottom and the columns are numbered from 1 to m from left to right. A matrix cell on the intersection of the i-th row and the j-th column can be represented as (i, j). Formally, a submatrix of matrix a is a group of four integers d, u, l, r (1 ≤ d ≤ u ≤ n; 1 ≤ l ≤ r ≤ m). We will assume that the submatrix contains cells (i, j) (d ≤ i ≤ u; l ≤ j ≤ r). The area of the submatrix is the number of cells it contains.

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 5000). Next n lines contain m characters each — matrix a. Matrix a only contains characters: "0" and "1". Note that the elements of the matrix follow without any spaces in the lines.

Output format:
Print a single integer — the area of the maximum obtained submatrix. If we cannot obtain a matrix of numbers one, print 0.

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

Example input:
1 1
1

Example output:
1

Example input:
2 2
10
11

Example output:
2

Editorial:
Tree and Queries
Contest: Codeforces Round 221 (Div. 1)
Difficulty rating: 2400
Tags: data structures, dfs and similar, trees

You have a rooted tree consisting of n vertices. Each vertex of the tree has some color. We will assume that the tree vertices are numbered by integers from 1 to n. Then we represent the color of vertex v as cv. The tree root is a vertex with number 1.

In this problem you need to answer to m queries. Each query is described by two integers vj, kj. The answer to query vj, kj is the number of such colors of vertices x, that the subtree of vertex vj contains at least kj vertices of color x.

You can find the definition of a rooted tree by the following link: http://en.wikipedia.org/wiki/Tree_(graph_theory).

Input format:
The first line contains two integers n and m (2 ≤ n ≤ 105; 1 ≤ m ≤ 105). The next line contains a sequence of integers c1, c2, ..., cn (1 ≤ ci ≤ 105). The next n - 1 lines contain the edges of the tree. The i-th line contains the numbers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — the vertices connected by an edge of the tree.

Next m lines contain the queries. The j-th line contains two integers vj, kj (1 ≤ vj ≤ n; 1 ≤ kj ≤ 105).

Output format:
Print m integers — the answers to the queries in the order the queries appear in the input.

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

Note:
A subtree of vertex v in a rooted tree with root r is a set of vertices {u : dist(r, v) + dist(v, u) = dist(r, u)}. Where dist(x, y) is the length (in edges) of the shortest path between vertices x and y.

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

Example output:
2
2
1
0
1

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

Example output:
4

Editorial:
Red and Black Tree
Contest: Codeforces Round 221 (Div. 1)
Difficulty rating: 3000
Tags: dp, implementation, math

You have a weighted tree, consisting of n vertices. Each vertex is either painted black or is painted red. A red and black tree is called beautiful, if for any its vertex we can find a black vertex at distance at most x.

The distance between two nodes is the shortest path between them.

You have a red and black tree. Your task is to make it beautiful in the minimum number of color swap operations. In one color swap operation, you can choose two vertices of different colors and paint each of them the other color. In other words, if you choose a red vertex p and a black vertex q, then in one operation you are allowed to paint p black and paint q red.

Print the minimum number of required actions.

Input format:
The first line contains two integers n and x (2 ≤ n ≤ 500; 1 ≤ x ≤ 109). The next line contains n integers, each of them is either a zero or one. If the i-th number equals 1, then vertex i of the tree is black, otherwise vertex i is red. Next n - 1 lines contain the tree edges. The j-th line contains integers uj vj wj (1 ≤ uj, vj ≤ n; uj ≠ vj; 1 ≤ wj ≤ 109) which means that the tree has an edge of weight wj between vertices vj and uj.

Assume that the tree vertices are numbered from 1 to n.

Output format:
Print a single integer — the minimum number of required swap operations.

If it is impossible to get a beautiful tree at any number of operations, print -1.

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

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

Example output:
1

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

Example output:
-1

Editorial:
Anti-Tetris
Contest: ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2800
Tags: constructive algorithms, graphs, shortest paths

Let us consider the game "Sticky Tetris". In this game, there is a field of $$$n \times m$$$ squares. Tiles appear on the field and the player can move the tiles.

Each tile is a $$$4$$$-connected set of at most $$$7$$$ squares.

Each new tile appears in any position that fits inside the field, does not intersect any other tile, and the top cell of the tile is at the top row of the field. The player can move the tile left, right, and down, and at any moment the tile must still entirely fit inside the field and must not intersect other tiles. The player can stop the tile at any position at any time. After that, it cannot be moved. Since this is "Sticky Tetris," the tile will not fall once stopped.

You are given a final configuration of a "Sticky Tetris" game. You need to restore a sequence of steps that leads to that configuration if it exists.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 50$$$) — the size of the playing field.

The next $$$n$$$ lines contain a string of $$$m$$$ characters each. Each character could be either a '.', or lowercase English letter. Connected components of the same letter correspond to a single tile. Each tile consists of at most $$$7$$$ squares.

Output format:
If there is no solution, print $$$-1$$$.

Otherwise, print $$$k$$$ — the number of different tiles that are placed on the field.

On the next $$$k$$$ lines print the sequence of steps for each of the tiles in the order they are placed.

Each line consists of a number $$$x$$$ followed by a string with steps. $$$x$$$ ($$$1 \le x \le m$$$) is the starting column of the leftmost square in the top row of the tile. The string consists of characters 'L' (for left), 'R' (for right), and 'D' (for down), describing the path of that tile, ending with a single character 'S' (for stop). The final position of the tile determines which tile is being placed. The string with steps can have at most $$$n \cdot m + 1$$$ characters.

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

Example input:
3 2
aa
ab
aa

Example output:
2
2 DS
1 S

Example input:
5 6
....dd
.ccccd
.cbbdd
.aab.a
aabbaa

Example output:
5
2 DDDS
4 DDLS
6 DDDS
2 DS
5 S

Editorial:
Building Forest Trails
Contest: ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2800
Tags: data structures, dsu

There are $$$n$$$ villages lying equidistant on a circle in the middle of a thick, impassable forest. From ancient times, it was impossible to move from one village to another, but technical progress has changed a lot. Now, there is a technology to build passable trails in the forest.

The building process consists of $$$m$$$ events. Each event is either building a trail or querying if two villages are connected. Trails are built as straight lines connecting two villages. After a trail is built, anybody can walk along the trail from one village to another.

Moreover, if two trails cross, anybody can turn at the intersection, and if other trails leave a village you have just reached, they can also be used to walk along. So, for example, if villages are numbered $$$1$$$ to $$$6$$$ in the order around the circle, and there are trails $$$1$$$ to $$$3$$$, $$$2$$$ to $$$4$$$, and $$$4$$$ to $$$6$$$, then all villages, except the $$$5$$$-th, are reachable from the $$$1$$$-st village.

Given a list of $$$m$$$ events, for each query, find if two given villages are reachable from each other at that moment.

Input format:
The first line contains two integers $$$n$$$ ($$$2 \le n \le 2\cdot 10^5$$$) and $$$m$$$ ($$$1 \le m \le 3\cdot 10^5$$$) — the number of villages and the number of events respectively.

Next $$$m$$$ lines contain events. Each event description consists of three integers $$$e$$$ ($$$e$$$ is $$$1$$$ or $$$2$$$), $$$v$$$ ($$$1 \le v \le n$$$), and $$$u$$$ ($$$1 \le u \le n$$$, $$$u \ne v$$$). If $$$e = 1$$$, then the event is building a trail between villages $$$v$$$ and $$$u$$$. If $$$e = 2$$$, then the event is a query if the villages $$$v$$$ and $$$u$$$ are connected. It is guaranteed that each trail is built at most once.

Villages are numbered $$$1$$$ to $$$n$$$ in clockwise order around the circle.

Output format:
For each query print one character '0' if villages are not reachable, and '1' if villages are reachable from each other. Print answers for all queries as a single string in one line.

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

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

Example output:
011110

Example input:
2 5
2 1 2
2 2 1
1 1 2
2 1 2
2 2 1

Example output:
0011

Editorial:
Cactus Lady and her Cing
Contest: ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 3500

Cactus lady loves her cactuses very much. Especially she likes a small cactus named Cing. Cing can be seen as a connected undirected graph in which every vertex lies on at most one simple cycle. Intuitively, a cactus is a generalization of a tree where some cycles are allowed. Multiedges (multiple edges between a pair of vertices) and loops (edges that connect a vertex to itself) are not allowed.

She bought a special grid for her special little cactus Cing. This grid can be represented as a graph consisting of two paths of length $$$400\,000$$$, $$$u_{(0, -200\,000)} - u_{(0, -199\,999)} - \ldots - u_{(0, 200\,000)}$$$ and $$$u_{(1, -200\,000)} - u_{(1, -199\,999)} - \ldots - u_{(1, 200\,000)}$$$, connected together by $$$400\,001$$$ edges $$$(u_{(0, i)}, u_{(1, i)})$$$ for each $$$i$$$. In other words, a grid can be seen as a ladder.

Cactus lady wants to know whether she can embed Cing into this grid, i.e., map each vertex of the cactus onto a separate vertex of the grid while each edge of the cactus will be mapped onto some edge of the grid.

Input format:
The first line contains an integer $$$t$$$ — the number of test cases.

Each test case begins with a line containing two integers $$$n$$$ and $$$m$$$ — the number of vertices and the number of edges in a given cactus, respectively ($$$1 \le n \le 200\,000$$$; $$$0 \le m \le 250\,000$$$).

Each of the following $$$m$$$ lines contains two integers $$$v$$$ and $$$u$$$, describing the edges of the cactus ($$$1 \le v, u \le n, u \ne v$$$).

The total sum of all $$$n$$$ in the input doesn't exceed $$$200\,000$$$.

Output format:
Print an answer for each test case in the same order the cases appear in the input.

For each test case print "No" in the first line, if no layout exists.

Otherwise print "Yes" in the first line, and the following $$$n$$$ lines describing the layout. The $$$i$$$-th of these $$$n$$$ lines should contain two integers $$$x_i$$$ and $$$y_i$$$, the location of the $$$i$$$-th vertex ($$$0 \le x_i \le 1$$$; $$$-200\,000 \le y_i \le 200\,000$$$).

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

Note:
Empty lines between test cases are for clarity. In real test cases there are no empty lines.

In these notes, we consider the embeddings for tests 2 and 4.

We start with the embedding for test 2.

Here goes the embedding for test 4.

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

8 7
1 2
3 2
2 4
4 5
4 6
6 7
6 8

5 4
1 2
1 3
1 4
1 5

8 9
1 2
2 3
3 4
1 4
4 5
5 6
6 7
7 8
5 8

10 10
1 2
2 3
3 4
4 5
5 6
6 1
3 7
4 8
1 9
6 10

Example output:
Yes
0 0
0 1
1 1
1 2
Yes
0 3
1 3
1 4
1 2
0 2
1 1
0 1
1 0
No
Yes
0 0
1 0
1 1
0 1
0 2
0 3
1 3
1 2
Yes
1 1
1 2
1 3
0 3
0 2
0 1
1 4
0 4
1 0
0 0

Editorial: