1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Just Add an Edge
Contest: Good Bye 2021: 2022 is NEAR
Difficulty rating: 3500
Tags: dfs and similar, dp, graphs

You are given a directed acyclic graph with $$$n$$$ vertices and $$$m$$$ edges. For all edges $$$a \to b$$$ in the graph, $$$a < b$$$ holds.

You need to find the number of pairs of vertices $$$x$$$, $$$y$$$, such that $$$x > y$$$ and after adding the edge $$$x \to y$$$ to the graph, it has a Hamiltonian path.

Input format:
The first line of input contains one integer $$$t$$$ ($$$1 \leq t \leq 5$$$): the number of test cases.

The next lines contains the descriptions of the test cases.

In the first line you are given two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 150\,000$$$, $$$0 \leq m \leq \min(150\,000, \frac{n(n-1)}{2})$$$): the number of vertices and edges in the graph.

Each of the next $$$m$$$ lines contains two integers $$$a$$$, $$$b$$$ ($$$1 \leq a < b \leq n$$$), specifying an edge $$$a \to b$$$ in the graph. No edge $$$a \to b$$$ appears more than once.

Output format:
For each test case, print one integer: the number of pairs of vertices $$$x$$$, $$$y$$$, $$$x > y$$$, such that after adding the edge $$$x \to y$$$ to the graph, it has a Hamiltonian path.

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

Note:
In the first example, any edge $$$x \to y$$$ such that $$$x > y$$$ is valid, because there already is a path $$$1 \to 2 \to 3$$$.

In the second example only the edge $$$4 \to 1$$$ is valid. There is a path $$$3 \to 4 \to 1 \to 2$$$ if this edge is added.

In the third example you can add edges $$$2 \to 1$$$, $$$3 \to 1$$$, $$$4 \to 1$$$, $$$4 \to 2$$$.

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

Example output:
3
1
4

Editorial:
First of all, we have to check whether there is a Hamiltonian path in the original graph. In this case, the number is $$${n \choose 2}$$$
Otherwise, addition of the edge $$$a \to b$$$ can only add a Hamiltonian path of the form:
1. $$$(1 \to \ldots \to a - 1) \to \ldots \to b$$$
2. $$$b \to a$$$
3. $$$a \to \ldots \to (b \to \ldots n)$$$
And these paths should be non-intersecting.
Where $$$(x \to \ldots \to y)$$$ means the default path $$$x \to (x+1) \to \ldots \to y$$$
Using this observation, it is easy to derive a $$$DP$$$ with two states: two last vertices on the chain, and we are only interested in the states where $$$x,x+1$$$ are in different chains.
$$$dp_{x,x+1}, dp_{x+1,x}$$$, we are interested in the number of valid pairs $$$(a-1,a)$$$ that you can reach from the valid pair $$$(b,b+1)$$$. Pair is valid if there is a hamilton path in the required direction. From here, we can get a solution in $$$O(nm)$$$, that could be optimized with bitset to $$$O(\frac{nm}{64})$$$.
But to make it linear, let's note that if there is no Hamiltonian path, then there is some edge $$$y \to (y+1)$$$ not present in the graph, and all the paths connecting the pairs oof vertices we are interested in are going through this edge. So instead of maintaining the set of all valid $$$(a,a+1)$$$, we can run DFS in two drections from $$$(y,y+1)$$$, and calculate the number of required pairs.
Keep XOR Low
Contest: Good Bye 2021: 2022 is NEAR
Difficulty rating: 3000
Tags: bitmasks, combinatorics, data structures, divide and conquer, dp, math

You are given an array $$$a_1, a_2, \ldots, a_n$$$ and an integer $$$x$$$.

Find the number of non-empty subsets of indices of this array $$$1 \leq b_1 < b_2 < \ldots < b_k \leq n$$$, such that for all pairs $$$(i, j)$$$ where $$$1 \leq i < j \leq k$$$, the inequality $$$a_{b_i} \oplus a_{b_j} \leq x$$$ is held. Here, $$$\oplus$$$ denotes the bitwise XOR operation. As the answer may be very large, output it modulo $$$998\,244\,353$$$.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$x$$$ ($$$1 \leq n \leq 150\,000$$$, $$$0 \leq x < 2^{30}$$$). Here, $$$n$$$ is the size of the array.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < 2^{30}$$$): the array itself.

Output format:
Print one integer: the number of non-empty subsets such that the bitwise XOR of every pair of elements is at most $$$x$$$, modulo $$$998\,244\,353$$$.

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

Example input:
4 2
0 1 2 3

Example output:
8

Example input:
3 6
4 2 2

Example output:
7

Editorial:
First of all, we should divide all elements into groups by the prefix before the leading bit $$$i$$$ of $$$x$$$, as elements from different groups will definitely yield invalid answers.
In one group, we either choose elements only from the group with the same bit $$$i$$$, then we can choose an artbirary subset. Or we need to solve the following problem:
• You are given two sequences $$$a,b$$$ of lengths $$$n,m$$$ and the current bit $$$i$$$.
• Choose any subset of $$$a \cup b$$$, such that in each sequence at least one element is chosen, and the bitwise XOR of any pair (ignoring bits above $$$i$$$) is at most $$$x$$$
To solve this problem, we need to look at the bit $$$i$$$ in $$$x$$$.
If it is set to zero, we need to recursively divide both arrays into $$$a_0, a_1, b_0, b_1$$$ according to the bits, and multiply the answers of $$$(a_0, b_0,i+1)$$$, and $$$(a_1, b_1, i+1)$$$.
Otherwise, let's note that $$$(a_0, b_1)$$$ and $$$(a_1, b_0)$$$ are independent, so we can multiply their answers and also add a bunch of simple combinatorial formulas in case none elements are chosen in one of these pairs.
The total complexity is $$$O(30n)$$$, as at each layer there are only $$$n$$$ elements in total.
A+B?
Contest: Codeforces Round 839 (Div. 3)
Difficulty rating: 800
Tags: implementation

You are given an expression of the form $$$a{+}b$$$, where $$$a$$$ and $$$b$$$ are integers from $$$0$$$ to $$$9$$$. You have to evaluate it and print the result.

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

Each test case consists of one line containing an expression of the form $$$a{+}b$$$ ($$$0 \le a, b \le 9$$$, both $$$a$$$ and $$$b$$$ are integers). The integers are not separated from the $$$+$$$ sign.

Output format:
For each test case, print one integer — the result of the expression.

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

Example input:
4
4+2
0+0
3+7
8+9

Example output:
6
0
10
17

Editorial:
There are multiple ways to solve this problem.
Most interpreted languages have some function that takes the string, evaluates it as code, and then returns the result. One of the examples is the eval function in Python. If the language you use supports something like that, you can read the input as a string and use it as the argument of such a function.
Suppose you use a language where this is impossible. There are still many approaches to this problem. The most straightforward one is to take the first and the last characters of the input string, calculate their ASCII codes, and then subtract the ASCII code of the character 0 from them to get these digits as integers, not as characters. Then you can just add them up and print the result.
Matrix Rotation
Contest: Codeforces Round 839 (Div. 3)
Difficulty rating: 800
Tags: brute force, implementation

You have a matrix $$$2 \times 2$$$ filled with distinct integers. You want your matrix to become beautiful. The matrix is beautiful if the following two conditions are satisfied:

- in each row, the first element is smaller than the second element;
- in each column, the first element is smaller than the second element.

You can perform the following operation on the matrix any number of times: rotate it clockwise by $$$90$$$ degrees, so the top left element shifts to the top right cell, the top right element shifts to the bottom right cell, and so on:

Determine if it is possible to make the matrix beautiful by applying zero or more operations.

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

Each test case consists of two lines. Each of those lines contains two integers — the elements of the corresponding row of the matrix. In each matrix, all four elements are distinct integers from $$$1$$$ to $$$100$$$.

Output format:
For each test case, print YES if the matrix can become beautiful, or NO otherwise. 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: 512.0 MB

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

Example output:
YES
YES
NO
YES
YES
NO

Editorial:
Sure, you can just implement the rotation operation and check all $$$4$$$ possible ways to rotate the matrix, but it's kinda boring. The model solution does the different thing.
If a matrix is beautiful, then its minimum is in the upper left corner, and its maximum is in the lower right corner (and vice versa). If you rotate it, the element from the upper left corner goes to the upper right corner, and the element from the lower right corner goes to the lower left corner — so these elements are still in the opposite corners. No matter how many times we rotate a beautiful matrix, its minimum and maximum elements will be in the opposite corners — and the opposite is true as well; if you have a $$$2 \times 2$$$ matrix with minimum and maximum elements in opposite corners, it can be rotated in such a way that it becomes beautiful.
So, all we need to check is that the minimum and the maximum elements are in the opposite corners. There are many ways to do it; in my opinion, the most elegant one is to read all four elements in an array of size $$$4$$$; then the opposite corners of the matrix correspond either to positions $$$0$$$ and $$$3$$$, or to positions $$$1$$$ and $$$2$$$ in this array. So, we check that the sum of positions of minimum and maximum is exactly $$$3$$$.
Different Differences
Contest: Codeforces Round 839 (Div. 3)
Difficulty rating: 1000
Tags: constructive algorithms, greedy, math

An array $$$a$$$ consisting of $$$k$$$ integers is strictly increasing if $$$a_1 < a_2 < \dots < a_k$$$. For example, the arrays $$$[1, 3, 5]$$$, $$$[1, 2, 3, 4]$$$, $$$[3, 5, 6]$$$ are strictly increasing; the arrays $$$[2, 2]$$$, $$$[3, 7, 5]$$$, $$$[7, 4, 3]$$$, $$$[1, 2, 2, 3]$$$ are not.

For a strictly increasing array $$$a$$$ of $$$k$$$ elements, let's denote the characteristic as the number of different elements in the array $$$[a_2 - a_1, a_3 - a_2, \dots, a_k - a_{k-1}]$$$. For example, the characteristic of the array $$$[1, 3, 4, 7, 8]$$$ is $$$3$$$ since the array $$$[2, 1, 3, 1]$$$ contains $$$3$$$ different elements: $$$2$$$, $$$1$$$ and $$$3$$$.

You are given two integers $$$k$$$ and $$$n$$$ ($$$k \le n$$$). Construct an increasing array of $$$k$$$ integers from $$$1$$$ to $$$n$$$ with maximum possible characteristic.

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

Each test case consists of one line containing two integers $$$k$$$ and $$$n$$$ ($$$2 \le k \le n \le 40$$$).

Output format:
For each test case, print $$$k$$$ integers — the elements of the strictly increasing array $$$a$$$ with the maximum possible characteristic. If there are multiple answers, print any of them.

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

Example input:
7
5 9
4 12
3 3
3 4
4 4
4 6
8 11

Example output:
1 3 4 7 8
2 4 7 12
1 2 3
1 3 4
1 2 3 4
2 4 5 6
1 2 3 5 6 7 8 11

Editorial:
We can transform the problem as follows. Let $$$d_i = a_{i+1} - a_i$$$. We need to find an array $$$[d_1, d_2, \dots, d_{k-1}]$$$ so that the sum of elements in it is not greater than $$$n-1$$$, all elements are positive integers, and the number of different elements is the maximum possible.
Suppose we need $$$f$$$ different elements in $$$d$$$. What can be the minimum possible sum of elements in $$$d$$$? It's easy to see that $$$d$$$ should have the following form: $$$[2, 3, 4, \dots, f, 1, 1, 1, \dots, 1]$$$. This array contains exactly $$$f$$$ different elements, these different elements are as small as possible (so their sum is as small as possible), and all duplicates are $$$1$$$'s. So, if the sum of this array is not greater than $$$n-1$$$, then it is possible to have the number of different elements in $$$d$$$ equal to $$$f$$$.
The rest is simple. We can iterate on $$$f$$$, find the maximum possible $$$f$$$, construct the difference array, and then use it to construct the array $$$a$$$ itself.
Snow Footprints
Contest: Codeforces Round 180 (Div. 2)
Difficulty rating: 1300
Tags: greedy, implementation

There is a straight snowy road, divided into n blocks. The blocks are numbered from 1 to n from left to right. If one moves from the i-th block to the (i + 1)-th block, he will leave a right footprint on the i-th block. Similarly, if one moves from the i-th block to the (i - 1)-th block, he will leave a left footprint on the i-th block. If there already is a footprint on the i-th block, the new footprint will cover the old one.

At the beginning, there were no footprints. Then polar bear Alice starts from the s-th block, makes a sequence of moves and ends in the t-th block. It is known that Alice never moves outside of the road.

You are given the description of Alice's footprints. Your task is to find a pair of possible values of s, t by looking at the footprints.

Input format:
The first line of the input contains integer n (3 ≤ n ≤ 1000).

The second line contains the description of the road — the string that consists of n characters. Each character will be either "." (a block without footprint), or "L" (a block with a left footprint), "R" (a block with a right footprint).

It's guaranteed that the given string contains at least one character not equal to ".". Also, the first and the last character will always be ".". It's guaranteed that a solution exists.

Output format:
Print two space-separated integers — the values of s and t. If there are several possible solutions you can print any of them.

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

Note:
The first test sample is the one in the picture.

Example input:
9
..RRLL...

Example output:
3 4

Example input:
11
.RRRLLLLL..

Example output:
7 5

Editorial:
Sail
Contest: Codeforces Round 180 (Div. 2)
Difficulty rating: 1200
Tags: brute force, greedy, implementation

The polar bears are going fishing. They plan to sail from (sx, sy) to (ex, ey). However, the boat can only sail by wind. At each second, the wind blows in one of these directions: east, south, west or north. Assume the boat is currently at (x, y).

- If the wind blows to the east, the boat will move to (x + 1, y).
- If the wind blows to the south, the boat will move to (x, y - 1).
- If the wind blows to the west, the boat will move to (x - 1, y).
- If the wind blows to the north, the boat will move to (x, y + 1).

Alternatively, they can hold the boat by the anchor. In this case, the boat stays at (x, y). Given the wind direction for t seconds, what is the earliest time they sail to (ex, ey)?

Input format:
The first line contains five integers t, sx, sy, ex, ey (1 ≤ t ≤ 105,  - 109 ≤ sx, sy, ex, ey ≤ 109). The starting location and the ending location will be different.

The second line contains t characters, the i-th character is the wind blowing direction at the i-th second. It will be one of the four possibilities: "E" (east), "S" (south), "W" (west) and "N" (north).

Output format:
If they can reach (ex, ey) within t seconds, print the earliest time they can achieve it. Otherwise, print "-1" (without quotes).

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

Note:
In the first sample, they can stay at seconds 1, 3, and move at seconds 2, 4.

In the second sample, they cannot sail to the destination.

Example input:
5 0 0 1 1
SESNW

Example output:
4

Example input:
10 5 3 3 6
NENSWESNEE

Example output:
-1

Editorial:
Beautiful Year
Contest: Codeforces Round 166 (Div. 2)
Difficulty rating: 800
Tags: brute force

It seems like the year of 2013 came only yesterday. Do you know a curious fact? The year of 2013 is the first year after the old 1987 with only distinct digits.

Now you are suggested to solve the following problem: given a year number, find the minimum year number which is strictly larger than the given one and has only distinct digits.

Input format:
The single line contains integer y (1000 ≤ y ≤ 9000) — the year number.

Output format:
Print a single integer — the minimum year number that is strictly larger than y and all it's digits are distinct. It is guaranteed that the answer exists.

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

Example input:
1987

Example output:
2013

Example input:
2013

Example output:
2014

Editorial:
Prime Matrix
Contest: Codeforces Round 166 (Div. 2)
Difficulty rating: 1300
Tags: binary search, brute force, math, number theory

You've got an n × m matrix. The matrix consists of integers. In one move, you can apply a single transformation to the matrix: choose an arbitrary element of the matrix and increase it by 1. Each element can be increased an arbitrary number of times.

You are really curious about prime numbers. Let us remind you that a prime number is a positive integer that has exactly two distinct positive integer divisors: itself and number one. For example, numbers 2, 3, 5 are prime and numbers 1, 4, 6 are not.

A matrix is prime if at least one of the two following conditions fulfills:

- the matrix has a row with prime numbers only;
- the matrix has a column with prime numbers only;

Your task is to count the minimum number of moves needed to get a prime matrix from the one you've got.

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

Each of the following n lines contains m integers — the initial matrix. All matrix elements are positive integers. All numbers in the initial matrix do not exceed 105.

The numbers in the lines are separated by single spaces.

Output format:
Print a single integer — the minimum number of moves needed to get a prime matrix from the one you've got. If you've got a prime matrix, print 0.

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

Note:
In the first sample you need to increase number 1 in cell (1, 1). Thus, the first row will consist of prime numbers: 2, 2, 3.

In the second sample you need to increase number 8 in cell (1, 2) three times. Thus, the second column will consist of prime numbers: 11, 2.

In the third sample you don't have to do anything as the second column already consists of prime numbers: 3, 2.

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

Example output:
1

Example input:
2 3
4 8 8
9 2 9

Example output:
3

Editorial:
Secret
Contest: Codeforces Round 166 (Div. 2)
Difficulty rating: 1500
Tags: constructive algorithms, implementation

The Greatest Secret Ever consists of n words, indexed by positive integers from 1 to n. The secret needs dividing between k Keepers (let's index them by positive integers from 1 to k), the i-th Keeper gets a non-empty set of words with numbers from the set Ui = (ui, 1, ui, 2, ..., ui, |Ui|). Here and below we'll presuppose that the set elements are written in the increasing order.

We'll say that the secret is safe if the following conditions are hold:

- for any two indexes i, j (1 ≤ i < j ≤ k) the intersection of sets Ui and Uj is an empty set;
- the union of sets U1, U2, ..., Uk is set (1, 2, ..., n);
- in each set Ui, its elements ui, 1, ui, 2, ..., ui, |Ui| do not form an arithmetic progression (in particular, |Ui| ≥ 3 should hold).

Let us remind you that the elements of set (u1, u2, ..., us) form an arithmetic progression if there is such number d, that for all i (1 ≤ i < s) fulfills ui + d = ui + 1. For example, the elements of sets (5), (1, 10) and (1, 5, 9) form arithmetic progressions and the elements of sets (1, 2, 4) and (3, 6, 8) don't.

Your task is to find any partition of the set of words into subsets U1, U2, ..., Uk so that the secret is safe. Otherwise indicate that there's no such partition.

Input format:
The input consists of a single line which contains two integers n and k (2 ≤ k ≤ n ≤ 106) — the number of words in the secret and the number of the Keepers. The numbers are separated by a single space.

Output format:
If there is no way to keep the secret safe, print a single integer "-1" (without the quotes). Otherwise, print n integers, the i-th of them representing the number of the Keeper who's got the i-th word of the secret.

If there are multiple solutions, print any of them.

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

Example input:
11 3

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

Example input:
5 2

Example output:
-1

Editorial:
Good Substrings
Contest: Codeforces Round 166 (Div. 2)
Difficulty rating: 1800
Tags: data structures, strings

You've got string s, consisting of small English letters. Some of the English letters are good, the rest are bad.

A substring s[l...r] (1 ≤ l ≤ r ≤ |s|) of string s  =  s1s2...s|s| (where |s| is the length of string s) is string  slsl + 1...sr.

The substring s[l...r] is good, if among the letters  sl, sl + 1, ..., sr there are at most k bad ones (look at the sample's explanation to understand it more clear).

Your task is to find the number of distinct good substrings of the given string s. Two substrings s[x...y] and s[p...q] are considered distinct if their content is different, i.e. s[x...y] ≠ s[p...q].

Input format:
The first line of the input is the non-empty string s, consisting of small English letters, the string's length is at most 1500 characters.

The second line of the input is the string of characters "0" and "1", the length is exactly 26 characters. If the i-th character of this string equals "1", then the i-th English letter is good, otherwise it's bad. That is, the first character of this string corresponds to letter "a", the second one corresponds to letter "b" and so on.

The third line of the input consists a single integer k (0 ≤ k ≤ |s|) — the maximum acceptable number of bad characters in a good substring.

Output format:
Print a single integer — the number of distinct good substrings of string s.

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

Note:
In the first example there are following good substrings: "a", "ab", "b", "ba", "bab".

In the second example there are following good substrings: "a", "aa", "ac", "b", "ba", "c", "ca", "cb".

Example input:
ababab
01000000000000000000000000
1

Example output:
5

Example input:
acbacbacaa
00000000000000000000000000
2

Example output:
8

Editorial: