1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Median
Contest: Codeforces Round 113 (Div. 2)
Difficulty rating: 1500
Tags: greedy, math, sortings

A median in an array with the length of n is an element which occupies position number $$\left\lfloor \frac{n+1}{2} \right\rfloor$$ after we sort the elements in the non-decreasing order (the array elements are numbered starting with 1). A median of an array (2, 6, 1, 2, 3) is the number 2, and a median of array (0, 96, 17, 23) — the number 17.

We define an expression $$\left[\frac{a}{b}\right]$$ as the integer part of dividing number a by number b.

One day Vasya showed Petya an array consisting of n integers and suggested finding the array's median. Petya didn't even look at the array and said that it equals x. Petya is a very honest boy, so he decided to add several numbers to the given array so that the median of the resulting array would be equal to x.

Petya can add any integers from 1 to 105 to the array, including the same numbers. Of course, he can add nothing to the array. If a number is added multiple times, then we should consider it the number of times it occurs. It is not allowed to delete of change initial numbers of the array.

While Petya is busy distracting Vasya, your task is to find the minimum number of elements he will need.

Input format:
The first input line contains two space-separated integers n and x (1 ≤ n ≤ 500, 1 ≤ x ≤ 105) — the initial array's length and the required median's value. The second line contains n space-separated numbers — the initial array. The elements of the array are integers from 1 to 105. The array elements are not necessarily different.

Output format:
Print the only integer — the minimum number of elements Petya needs to add to the array so that its median equals x.

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

Note:
In the first sample we can add number 9 to array (10, 20, 30). The resulting array (9, 10, 20, 30) will have a median in position $$\left\lfloor \frac{4+1}{2} \right\rfloor = 2$$, that is, 10.

In the second sample you should add numbers 4, 5, 5, 5. The resulting array has median equal to 4.

Example input:
3 10
10 20 30

Example output:
1

Example input:
3 4
1 2 3

Example output:
4

Editorial:
Shoe Store
Contest: Codeforces Round 113 (Div. 2)
Difficulty rating: 2500
Tags: dp, graph matchings, greedy, sortings, two pointers

The warehouse in your shop has n shoe pairs. Each pair is characterized by two integers: its price ci and its size si. We know that on this very day all numbers si are different, that is, there is no more than one pair of each size.

The shop has m customers who came at the same time. The customer number i has di money and the size of his feet equals li. The customer number i can buy the pair number j, if cj ≤ di, and also if li = sj or li = sj - 1; that is, it is necessary that he has enough money to pay for the shoes. It is also necessary that the size of his feet equals to or is less by 1 than the size of the shoes he chooses.

Your task is to sell some customers pairs of shoes (a pair per person) so as to maximize the sum of the sold pairs cj that is, the profit. It is guaranteed that each customer buys no more than one pair and each pair will be bought by no more than one customer.

Input format:
The first input line contains the only integer n (1 ≤ n ≤ 105) — the number of shoe pairs in the warehouse. Then n lines contain the descriptions of pairs of shoes as two integers ci and si (1 ≤ ci, si ≤ 109), the numbers are separated by a space. It is guaranteed that all numbers si are different.

The next line contains an integer m (1 ≤ m ≤ 105) — the number of customers in the shop. Next m lines contain the customers' descriptions as two integers di and li (1 ≤ di, li ≤ 109), the numbers are separated by a space.

Output format:
In the first line print the only integer — the maximum profit you can get from selling shoes. In the second line print an integer k — the number of shoe pairs you will sell. In the following k lines print the descriptions of the sold pairs — two space-separated integers where the first number is the customer's number and the second number is the number of the shoes the customer will buy.

You can print pairs of numbers "the customer's number and the shoes' number" in any order, the customers and the pairs of shoes are numbered starting from 1 in the order in which they are given in the input. If there are several optimal answers, you are allowed to print any of them.

Please do not use the %lld specificator to read or write 64-bit numbers in С++. It is preferred to use the cin, cout streams or the %I64d specificator instead.

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

Example input:
3
10 1
30 2
20 3
2
20 1
20 2

Example output:
30
2
2 3
1 1

Example input:
3
10 4
20 5
30 6
2
70 4
50 5

Example output:
50
2
2 3
1 2

Editorial:
Tetrahedron
Contest: Codeforces Round 113 (Div. 2)
Difficulty rating: 1500
Tags: dp, math, matrices

You are given a tetrahedron. Let's mark its vertices with letters A, B, C and D correspondingly.

An ant is standing in the vertex D of the tetrahedron. The ant is quite active and he wouldn't stay idle. At each moment of time he makes a step from one vertex to another one along some edge of the tetrahedron. The ant just can't stand on one place.

You do not have to do much to solve the problem: your task is to count the number of ways in which the ant can go from the initial vertex D to itself in exactly n steps. In other words, you are asked to find out the number of different cyclic paths with the length of n from vertex D to itself. As the number can be quite large, you should print it modulo 1000000007 (109 + 7).

Input format:
The first line contains the only integer n (1 ≤ n ≤ 107) — the required length of the cyclic path.

Output format:
Print the only integer — the required number of ways modulo 1000000007 (109 + 7).

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

Note:
The required paths in the first sample are:

- D - A - D
- D - B - D
- D - C - D

Example input:
2

Example output:
3

Example input:
4

Example output:
21

Editorial:
Doors and Keys
Contest: Educational Codeforces Round 123 (Rated for Div. 2)
Difficulty rating: 800
Tags: implementation

The knight is standing in front of a long and narrow hallway. A princess is waiting at the end of it.

In a hallway there are three doors: a red door, a green door and a blue door. The doors are placed one after another, however, possibly in a different order. To proceed to the next door, the knight must first open the door before.

Each door can be only opened with a key of the corresponding color. So three keys: a red key, a green key and a blue key — are also placed somewhere in the hallway. To open the door, the knight should first pick up the key of its color.

The knight has a map of the hallway. It can be transcribed as a string, consisting of six characters:

- R, G, B — denoting red, green and blue doors, respectively;
- r, g, b — denoting red, green and blue keys, respectively.

Each of these six characters appears in the string exactly once.

The knight is standing at the beginning of the hallway — on the left on the map.

Given a map of the hallway, determine if the knight can open all doors and meet the princess at the end of the hallway.

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

Each testcase consists of a single string. Each character is one of R, G, B (for the doors), r, g, b (for the keys), and each of them appears exactly once.

Output format:
For each testcase, print YES if the knight can open all doors. Otherwise, print NO.

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

Note:
In the first testcase, the knight first collects all keys, then opens all doors with them.

In the second testcase, there is a red door right in front of the knight, but he doesn't have a key for it.

In the third testcase, the key to each door is in front of each respective door, so the knight collects the key and uses it immediately three times.

In the fourth testcase, the knight can't open the blue door.

Example input:
4
rgbBRG
RgbrBG
bBrRgG
rgRGBb

Example output:
YES
NO
YES
NO

Editorial:
The necessary and sufficient condition is the following: for each color the key should appear before the door.
Necessary is easy to show: if there is a key after a door, this door can't be opened.
Sufficient can be shown the following way. If there are no closed doors left, the knight has reached the princess. Otherwise, consider the first door the knight encounters. He has a key for this door, so he opens it. We remove both the key and the door from the string and proceed to the case with one less door.
Overall complexity: $$$O(1)$$$.
Anti-Fibonacci Permutation
Contest: Educational Codeforces Round 123 (Rated for Div. 2)
Difficulty rating: 800
Tags: brute force, constructive algorithms, implementation

Let's call a permutation $$$p$$$ of length $$$n$$$ anti-Fibonacci if the condition $$$p_{i-2} + p_{i-1} \ne p_i$$$ holds for all $$$i$$$ ($$$3 \le i \le n$$$). Recall that the permutation is the array of length $$$n$$$ which contains each integer from $$$1$$$ to $$$n$$$ exactly once.

Your task is for a given number $$$n$$$ print $$$n$$$ distinct anti-Fibonacci permutations of length $$$n$$$.

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

The single line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 50$$$).

Output format:
For each test case, print $$$n$$$ lines. Each line should contain an anti-Fibonacci permutation of length $$$n$$$. In each test case, you cannot print any permutation more than once.

If there are multiple answers, print any of them. It can be shown that it is always possible to find $$$n$$$ different anti-Fibonacci permutations of size $$$n$$$ under the constraints of the problem.

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

Example input:
2
4
3

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

Editorial:
Let's consider one of the possible solutions. Let's put the first element in the $$$x$$$-th permutation equal to $$$x$$$, and sort all the other elements in descending order. Thus, we get permutations of the form: $$$[1, n, n-1, \dots, 2]$$$, $$$[2, n, n-1, \dots, 1]$$$, ..., $$$[n, n-1, n-2, \dots, 1]$$$. In such a construction $$$p_{i-1} > p_i$$$ for all $$$i$$$ ($$$3 \le i \le n$$$), and hence $$$p_{i-2} + p_{i-1} > p_i$$$.
Cross Coloring
Contest: Educational Codeforces Round 123 (Rated for Div. 2)
Difficulty rating: 1700
Tags: data structures, implementation, math

There is a sheet of paper that can be represented with a grid of size $$$n \times m$$$: $$$n$$$ rows and $$$m$$$ columns of cells. All cells are colored in white initially.

$$$q$$$ operations have been applied to the sheet. The $$$i$$$-th of them can be described as follows:

- $$$x_i$$$ $$$y_i$$$ — choose one of $$$k$$$ non-white colors and color the entire row $$$x_i$$$ and the entire column $$$y_i$$$ in it. The new color is applied to each cell, regardless of whether the cell was colored before the operation.

The sheet after applying all $$$q$$$ operations is called a coloring. Two colorings are different if there exists at least one cell that is colored in different colors.

How many different colorings are there? Print the number modulo $$$998\,244\,353$$$.

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

The first line of the testcase contains four integers $$$n, m, k$$$ and $$$q$$$ ($$$1 \le n, m, k, q \le 2 \cdot 10^5$$$) — the size of the sheet, the number of non-white colors and the number of operations.

The $$$i$$$-th of the following $$$q$$$ lines contains a description of the $$$i$$$-th operation — two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \le n$$$; $$$1 \le y_i \le m$$$) — the row and the column the operation is applied to.

The sum of $$$q$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each testcase, print a single integer — the number of different colorings modulo $$$998\,244\,353$$$.

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

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

Example output:
3
4

Editorial:
Let's take a look at a final coloring. Each cell has some color. There exist cells such that there were no operation in their row and their column. They are left white, and they don't affect the answer.
All other cells are colored in one of $$$k$$$ colors. For each cell $$$(x, y)$$$ there is a query that has been the last one to color this cell (it covered row $$$x$$$, column $$$y$$$ or both of them). So all cells that have the same query as the last one will have the same color. Since the color for each query is chosen independently, the number of colorings will be $$$k$$$ to the power of the number of queries that have at least one cell belong to them.
How to determine if a query has at least one cell. This is true unless one of these things happen afterwards:
• both its row and its column are recolored;
• all rows are recolored;
• all columns are recolored.
So the solution is to process the queries backwards. Maintain the set of colored rows and colored columns. For each query, check the conditions. If none hold, multiply the answer by $$$k$$$.
Overall complexity: $$$O(q \log (n + m))$$$ or $$$O(q)$$$ per testcase.
Diverse Game
Contest: Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, greedy, implementation

Petr, watching Sergey's stream, came up with a matrix $$$a$$$, consisting of $$$n$$$ rows and $$$m$$$ columns (the number in the $$$i$$$-th row and $$$j$$$-th column is denoted as $$$a_{i, j}$$$), which contains all integers from $$$1$$$ to $$$n \cdot m$$$. But he didn't like the arrangement of the numbers, and now he wants to come up with a new matrix $$$b$$$, consisting of $$$n$$$ rows and $$$m$$$ columns, which will also contain all integers from $$$1$$$ to $$$n \cdot m$$$, such that for any $$$1 \leq i \leq n, 1 \leq j \leq m$$$ it holds that $$$a_{i, j} \ne b_{i, j}$$$.

You are given the matrix $$$a$$$, construct any matrix $$$b$$$ that meets Petr's requirements, or determine that it is impossible.

Hurry up! Otherwise, he will donate all his money to the stream in search of an answer to his question.

Input format:
Each test consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10$$$) — the number of rows and columns of matrix $$$a$$$.

The next $$$n$$$ lines contain $$$m$$$ integers each, describing matrix $$$a$$$. The $$$i$$$-th of these lines contains the elements of matrix $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$.

It is guaranteed that all numbers in matrix $$$a$$$ are distinct and $$$1 \leq a_{i, j} \leq n \cdot m$$$.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$5 \cdot 10^4$$$.

Output format:
For each test case, output $$$n \cdot m$$$ integers — any suitable matrix $$$b$$$, or $$$-1$$$ if such a matrix does not exist.

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

Note:
In the first test case, there is only one element in the matrix, so matrix $$$b$$$ is the only matrix and it does not fit.

In the second test case $$$a_{1, 1} = 2 \neq 1 = b_{1, 1}$$$, $$$a_{2, 1} = 1 \neq 2 = b_{2, 1}$$$.

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

Example output:
-1
1 
2 
4 5 3 1 2 
6 7 8 5 
2 3 4 1 
8 3 9 
7 5 6 
2 1 4

Editorial:
If $$$n = m = 1$$$, then there is only one possible matrix, so the answer is $$$-1$$$. Otherwise, at least one of the numbers $$$n, m$$$ is greater than $$$1$$$, then one of the solutions is, for example, a matrix $$$a$$$ with cyclically shifted rows (if $$$m > 1$$$) or columns (if $$$n > 1$$$).
Hungry Games
Contest: Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)
Difficulty rating: 1600
Tags: binary search, dp, two pointers

Yaroslav is playing a computer game, and at one of the levels, he encountered $$$n$$$ mushrooms arranged in a row. Each mushroom has its own level of toxicity; the $$$i$$$-th mushroom from the beginning has a toxicity level of $$$a_i$$$. Yaroslav can choose two integers $$$1 \le l \le r \le n$$$, and then his character will take turns from left to right to eat mushrooms from this subsegment one by one, i.e., the mushrooms with numbers $$$l, l+1, l+2, \ldots, r$$$.

The character has a toxicity level $$$g$$$, initially equal to $$$0$$$. The computer game is defined by the number $$$x$$$ — the maximum toxicity level at any given time. When eating a mushroom with toxicity level $$$k$$$, the following happens:

1. The toxicity level of the character is increased by $$$k$$$.
2. If $$$g \leq x$$$, the process continues; otherwise, $$$g$$$ becomes zero and the process continues.

Yaroslav became interested in how many ways there are to choose the values of $$$l$$$ and $$$r$$$ such that the final value of $$$g$$$ is not zero. Help Yaroslav find this number!

Input format:
Each test consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains two integers $$$n$$$, $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 1 \le x \le 10^9$$$) — the number of mushrooms and the maximum toxicity level.

The second line of each test case contains $$$n$$$ numbers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single number — the number of subsegments such that the final value of $$$g$$$ will not be zero.

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

Note:
In the first test case, the subsegments $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(3, 3)$$$, $$$(3, 4)$$$ and $$$(4, 4)$$$ are suitable.

In the second test case, non-zero $$$g$$$ will remain only on the subsegments $$$(1, 1)$$$ and $$$(2, 2)$$$.

In the third test case, on the only possible subsegment, $$$g$$$ will be zero.

Example input:
5
4 2
1 1 1 1
3 2
1 2 3
1 6
10
6 3
1 2 1 4 3 8
5 999999999
999999999 999999998 1000000000 1000000000 500000000

Example output:
8
2
0
10
7

Editorial:
We'll solve the problem by dynamic programming. Let $$$dp[i]$$$ — the number of good subsegments with left boundary at $$$i$$$. We will count $$$dp$$$ from the end, for each $$$i$$$ we will find such a minimum $$$j$$$ that the sum on the subsegment $$$[i; j]$$$ is greater than $$$x$$$. If there is no such $$$j$$$, then all right bounds are good, otherwise $$$dp[i] = dp[j + 1] + j - i$$$. To search for $$$j$$$, we can use a binary search on prefix sums. The answer will be the sum of all $$$dp$$$.
Wooden Game
Contest: Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)
Difficulty rating: 2000
Tags: bitmasks, greedy, math, trees

You are given a forest of $$$k$$$ rooted trees$$$^{\text{∗}}$$$. Lumberjack Timofey wants to cut down the entire forest by applying the following operation:

- Select a subtree$$$^{\text{†}}$$$ of any vertex of one of the trees and remove it from the tree.

Timofey loves bitwise operations, so he wants the bitwise OR of the sizes of the subtrees he removed to be maximum. Help him and find the maximum result he can obtain.

Input format:
Each test consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains a single integer $$$k$$$ ($$$1 \leq k \leq 10^6$$$) — the number of trees in the forest.

This is followed by a description of each of the $$$k$$$ trees:

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — the size of the tree. The vertices of the tree are numbered with integers from $$$1$$$ to $$$n$$$. The root of the tree is vertex number $$$1$$$.

The second line contains $$$n - 1$$$ integers $$$p_2, p_3, \ldots p_n$$$ ($$$1 \leq p_i < i$$$), where $$$p_i$$$ — the parent of vertex $$$i$$$.

It is guaranteed that the sum of $$$k$$$ and $$$n$$$ for all sets of input data does not exceed $$$10^6$$$.

Output format:
For each test case, output a single integer — the maximum result that can be obtained.

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

Note:
In the second test case, the trees look like this:

The first operation removes the entire second tree.

The second operation removes vertex $$$4$$$ from the first tree.

The third operation removes the first tree. The result is $$$6|1|3 = 7$$$ ($$$|$$$ denotes bitwise OR).

In the third test case, the entire tree needs to be removed.

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

Example output:
1
7
10

Editorial:
We know that the maximal result from one tree is the size of this tree (see hints), but we can make every number from $$$1$$$ to the size of the tree. To do that, we can delete leaves until we have the needed value.
So the remaining problem is to find the maximal OR if we can choose numbers from $$$1$$$ to $$$a_i$$$. For every bit, let's count the number of $$$a_i$$$, where this bit is set. Find the highest bit which is set in more than one number. Obviously, we can make a suffix of $$$1$$$-s from this position. Before this position we need to set bits that are set in one of $$$a_i$$$.