1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Binary String Reconstruction
Contest: Educational Codeforces Round 94 (Rated for Div. 2)
Difficulty rating: 1500
Tags: 2-sat, brute force, constructive algorithms, greedy

Consider the following process. You have a binary string (a string where each character is either 0 or 1) $$$w$$$ of length $$$n$$$ and an integer $$$x$$$. You build a new binary string $$$s$$$ consisting of $$$n$$$ characters. The $$$i$$$-th character of $$$s$$$ is chosen as follows:

- if the character $$$w_{i-x}$$$ exists and is equal to 1, then $$$s_i$$$ is 1 (formally, if $$$i > x$$$ and $$$w_{i-x} = $$$ 1, then $$$s_i = $$$ 1);
- if the character $$$w_{i+x}$$$ exists and is equal to 1, then $$$s_i$$$ is 1 (formally, if $$$i + x \le n$$$ and $$$w_{i+x} = $$$ 1, then $$$s_i = $$$ 1);
- if both of the aforementioned conditions are false, then $$$s_i$$$ is 0.

You are given the integer $$$x$$$ and the resulting string $$$s$$$. Reconstruct the original string $$$w$$$.

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. The first line contains the resulting string $$$s$$$ ($$$2 \le |s| \le 10^5$$$, each character of $$$s$$$ is either 0 or 1). The second line contains one integer $$$x$$$ ($$$1 \le x \le |s| - 1$$$).

The total length of all strings $$$s$$$ in the input does not exceed $$$10^5$$$.

Output format:
For each test case, print the answer on a separate line as follows:

- if no string $$$w$$$ can produce the string $$$s$$$ at the end of the process, print $$$-1$$$;
- otherwise, print the binary string $$$w$$$ consisting of $$$|s|$$$ characters. If there are multiple answers, print any of them.

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

Example input:
3
101110
2
01
1
110
1

Example output:
111011
10
-1

Editorial:
At first, let's replace all elements of string $$$w$$$ by 1.
Now, let's consider all indices $$$i$$$ such that $$$s_i = 0$$$. If $$$s_i = 0$$$, then $$$w_{i - x}$$$ must be equal to 0 (if it exists) and $$$w_{i + x}$$$ must be equal to 0 (if it exists), so let's replace all such elements by 0.
And after let's perform the process described in statement on string $$$w$$$. If we get the string $$$s$$$, then we can print $$$w$$$ as the answer, otherwise the answer is $$$-1$$$.
Zigzags
Contest: Educational Codeforces Round 94 (Rated for Div. 2)
Difficulty rating: 1900
Tags: brute force, combinatorics, data structures, math, two pointers

You are given an array $$$a_1, a_2 \dots a_n$$$. Calculate the number of tuples $$$(i, j, k, l)$$$ such that:

- $$$1 \le i < j < k < l \le n$$$;
- $$$a_i = a_k$$$ and $$$a_j = a_l$$$;

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

The first line of each test case contains a single integer $$$n$$$ ($$$4 \le n \le 3000$$$) — the size of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the array $$$a$$$.

It's guaranteed that the sum of $$$n$$$ in one test doesn't exceed $$$3000$$$.

Output format:
For each test case, print the number of described tuples.

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

Note:
In the first test case, for any four indices $$$i < j < k < l$$$ are valid, so the answer is the number of tuples.

In the second test case, there are $$$2$$$ valid tuples:

- $$$(1, 2, 4, 6)$$$: $$$a_1 = a_4$$$ and $$$a_2 = a_6$$$;
- $$$(1, 3, 4, 6)$$$: $$$a_1 = a_4$$$ and $$$a_3 = a_6$$$.

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

Example output:
5
2

Editorial:
Let's iterate indices $$$j$$$ and $$$k$$$. For simplicity, for each $$$j$$$ we'll iterate $$$k$$$ in descending order.
To calculate the number of tuples for a fixed $$$(j, k)$$$ we just need the number of $$$i < j$$$ such that $$$a_i = a_k$$$ and the number of $$$l > k$$$ with $$$a_l = a_j$$$. We can maintain both values in two frequency arrays $$$cntLeft$$$ and $$$cntRight$$$, where $$$cntLeft[x]$$$ ($$$cntRight[x]$$$) is the number of $$$a_i = x$$$ for $$$i < j$$$ ($$$i > k$$$). It's easy to update $$$cntLeft$$$ ($$$cntRight$$$) when moving $$$j$$$ to $$$j + 1$$$ ($$$k$$$ to $$$k - 1$$$).
The time complexity is $$$O(n^2)$$$.
Buggy Sorting
Contest: Codeforces Round 151 (Div. 2)
Difficulty rating: 900
Tags: constructive algorithms, greedy, sortings

Little boy Valera studies an algorithm of sorting an integer array. After studying the theory, he went on to the practical tasks. As a result, he wrote a program that sorts an array of n integers a1, a2, ..., an in the non-decreasing order. The pseudocode of the program, written by Valera, is given below. The input of the program gets number n and array a.

But Valera could have made a mistake, because he hasn't yet fully learned the sorting algorithm. If Valera made a mistake in his program, you need to give a counter-example that makes his program work improperly (that is, the example that makes the program sort the array not in the non-decreasing order). If such example for the given value of n doesn't exist, print -1.

Input format:
You've got a single integer n (1 ≤ n ≤ 50) — the size of the sorted array.

Output format:
Print n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 100) — the counter-example, for which Valera's algorithm won't work correctly. If the counter-example that meets the described conditions is impossible to give, print -1.

If there are several counter-examples, consisting of n numbers, you are allowed to print any of them.

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

Example input:
1

Example output:
-1

Editorial:
Increase and Decrease
Contest: Codeforces Round 151 (Div. 2)
Difficulty rating: 1300
Tags: greedy, math

Polycarpus has an array, consisting of n integers a1, a2, ..., an. Polycarpus likes it when numbers in an array match. That's why he wants the array to have as many equal numbers as possible. For that Polycarpus performs the following operation multiple times:

- he chooses two elements of the array ai, aj (i ≠ j);
- he simultaneously increases number ai by 1 and decreases number aj by 1, that is, executes ai = ai + 1 and aj = aj - 1.

The given operation changes exactly two distinct array elements. Polycarpus can apply the described operation an infinite number of times.

Now he wants to know what maximum number of equal array elements he can get if he performs an arbitrary number of such operation. Help Polycarpus.

Input format:
The first line contains integer n (1 ≤ n ≤ 105) — the array size. The second line contains space-separated integers a1, a2, ..., an (|ai| ≤ 104) — the original array.

Output format:
Print a single integer — the maximum number of equal array elements he can get if he performs an arbitrary number of the given operation.

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

Example input:
2
2 1

Example output:
1

Example input:
3
1 4 1

Example output:
3

Editorial:
Beauty Pageant
Contest: Codeforces Round 151 (Div. 2)
Difficulty rating: 1600
Tags: brute force, constructive algorithms, greedy

General Payne has a battalion of n soldiers. The soldiers' beauty contest is coming up, it will last for k days. Payne decided that his battalion will participate in the pageant. Now he has choose the participants.

All soldiers in the battalion have different beauty that is represented by a positive integer. The value ai represents the beauty of the i-th soldier.

On each of k days Generals has to send a detachment of soldiers to the pageant. The beauty of the detachment is the sum of the beauties of the soldiers, who are part of this detachment. Payne wants to surprise the jury of the beauty pageant, so each of k days the beauty of the sent detachment should be unique. In other words, all k beauties of the sent detachments must be distinct numbers.

Help Payne choose k detachments of different beauties for the pageant. Please note that Payne cannot just forget to send soldiers on one day, that is, the detachment of soldiers he sends to the pageant should never be empty.

Input format:
The first line contains two integers n, k (1 ≤ n ≤ 50; 1 ≤ k ≤  $$\frac{n(n+1)}{2}$$) — the number of soldiers and the number of days in the pageant, correspondingly. The second line contains space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 107) — the beauties of the battalion soldiers.

It is guaranteed that Payne's battalion doesn't have two soldiers with the same beauty.

Output format:
Print k lines: in the i-th line print the description of the detachment that will participate in the pageant on the i-th day. The description consists of integer ci (1 ≤ ci ≤ n) — the number of soldiers in the detachment on the i-th day of the pageant and ci distinct integers p1, i, p2, i, ..., pci, i — the beauties of the soldiers in the detachment on the i-th day of the pageant. The beauties of the soldiers are allowed to print in any order.

Separate numbers on the lines by spaces. It is guaranteed that there is the solution that meets the problem conditions. If there are multiple solutions, print any of them.

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

Example input:
3 3
1 2 3

Example output:
1 1
1 2
2 3 2

Example input:
2 1
7 12

Example output:
1 12

Editorial:
Colorful Graph
Contest: Codeforces Round 151 (Div. 2)
Difficulty rating: 1600
Tags: brute force, dfs and similar, graphs

You've got an undirected graph, consisting of n vertices and m edges. We will consider the graph's vertices numbered with integers from 1 to n. Each vertex of the graph has a color. The color of the i-th vertex is an integer ci.

Let's consider all vertices of the graph, that are painted some color k. Let's denote a set of such as V(k). Let's denote the value of the neighbouring color diversity for color k as the cardinality of the set Q(k) = {cu :  cu ≠ k and there is vertex v belonging to set V(k) such that nodes v and u are connected by an edge of the graph}.

Your task is to find such color k, which makes the cardinality of set Q(k) maximum. In other words, you want to find the color that has the most diverse neighbours. Please note, that you want to find such color k, that the graph has at least one vertex with such color.

Input format:
The first line contains two space-separated integers n, m (1 ≤ n, m ≤ 105) — the number of vertices end edges of the graph, correspondingly. The second line contains a sequence of integers c1, c2, ..., cn (1 ≤ ci ≤ 105) — the colors of the graph vertices. The numbers on the line are separated by spaces.

Next m lines contain the description of the edges: the i-th line contains two space-separated integers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — the numbers of the vertices, connected by the i-th edge.

It is guaranteed that the given graph has no self-loops or multiple edges.

Output format:
Print the number of the color which has the set of neighbours with the maximum cardinality. It there are multiple optimal colors, print the color with the minimum number. Please note, that you want to find such color, that the graph has at least one vertex with such color.

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

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

Example output:
3

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

Example output:
2

Editorial:
Blood Cousins Return
Contest: Codeforces Round 151 (Div. 2)
Difficulty rating: 2400
Tags: binary search, data structures, dfs and similar, dp, sortings

Polycarpus got hold of a family tree. The found tree describes the family relations of n people, numbered from 1 to n. Every person in this tree has at most one direct ancestor. Also, each person in the tree has a name, the names are not necessarily unique.

We call the man with a number a a 1-ancestor of the man with a number b, if the man with a number a is a direct ancestor of the man with a number b.

We call the man with a number a a k-ancestor (k > 1) of the man with a number b, if the man with a number b has a 1-ancestor, and the man with a number a is a (k - 1)-ancestor of the 1-ancestor of the man with a number b.

In the tree the family ties do not form cycles. In other words there isn't a person who is his own direct or indirect ancestor (that is, who is an x-ancestor of himself, for some x, x > 0).

We call a man with a number a the k-son of the man with a number b, if the man with a number b is a k-ancestor of the man with a number a.

Polycarpus is very much interested in how many sons and which sons each person has. He took a piece of paper and wrote m pairs of numbers vi, ki. Help him to learn for each pair vi, ki the number of distinct names among all names of the ki-sons of the man with number vi.

Input format:
The first line of the input contains a single integer n (1 ≤ n ≤ 105) — the number of people in the tree. Next n lines contain the description of people in the tree. The i-th line contains space-separated string si and integer ri (0 ≤ ri ≤ n), where si is the name of the man with a number i, and ri is either the number of the direct ancestor of the man with a number i or 0, if the man with a number i has no direct ancestor.

The next line contains a single integer m (1 ≤ m ≤ 105) — the number of Polycarpus's records. Next m lines contain space-separated pairs of integers. The i-th line contains integers vi, ki (1 ≤ vi, ki ≤ n).

It is guaranteed that the family relationships do not form cycles. The names of all people are non-empty strings, consisting of no more than 20 lowercase English letters.

Output format:
Print m whitespace-separated integers — the answers to Polycarpus's records. Print the answers to the records in the order, in which the records occur in the input.

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

Example input:
6
pasha 0
gerald 1
gerald 1
valera 2
igor 3
olesya 1
5
1 1
1 2
1 3
3 1
6 1

Example output:
2
2
0
1
0

Example input:
6
valera 0
valera 1
valera 1
gerald 0
valera 4
kolya 4
7
1 1
1 2
2 1
2 2
4 1
5 1
6 1

Example output:
1
0
0
0
2
0
0

Editorial:
Brick Wall
Contest: Codeforces Round 922 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, greedy, implementation, math

A brick is a strip of size $$$1 \times k$$$, placed horizontally or vertically, where $$$k$$$ can be an arbitrary number that is at least $$$2$$$ ($$$k \ge 2$$$).

A brick wall of size $$$n \times m$$$ is such a way to place several bricks inside a rectangle $$$n \times m$$$, that all bricks lie either horizontally or vertically in the cells, do not cross the border of the rectangle, and that each cell of the $$$n \times m$$$ rectangle belongs to exactly one brick. Here $$$n$$$ is the height of the rectangle $$$n \times m$$$ and $$$m$$$ is the width. Note that there can be bricks with different values of k in the same brick wall.

The wall stability is the difference between the number of horizontal bricks and the number of vertical bricks. Note that if you used $$$0$$$ horizontal bricks and $$$2$$$ vertical ones, then the stability will be $$$-2$$$, not $$$2$$$.

What is the maximal possible stability of a wall of size $$$n \times m$$$?

It is guaranteed that under restrictions in the statement at least one $$$n \times m$$$ wall exists.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10\,000$$$), the number of test cases.

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n,\,m \le 10^4$$$).

Output format:
For each test case, print one integer, the maximum stability of a wall of size $$$n \times m$$$.

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

Note:
In the 1st test case, the maximum stability of $$$2$$$ is obtained by placing two horizontal bricks $$$1 \times 2$$$ one on top of the other.

In the 2nd test case, one can get the maximum stability of $$$28$$$ by placing $$$4$$$ horizontal bricks $$$1 \times 2$$$ in each of the $$$7$$$ rows.

Example input:
5
2 2
7 8
16 9
3 5
10000 10000

Example output:
2
28
64
6
50000000

Editorial:
The stability of the wall is the number of horizontal bricks minus the number of vertical bricks. Since a horizontal brick has a length of at least $$$2$$$, no more than $$$\lfloor\frac{m}{2}\rfloor$$$ horizontal bricks can be placed in one row. Therefore, the answer does not exceed $$$n \cdot \lfloor\frac{m}{2}\rfloor$$$. On the other hand, if horizontal bricks of length $$$2$$$ are placed in a row, and when $$$m$$$ is odd, the last brick has a length of $$$3$$$, then in each row there will be exactly $$$\lfloor\frac{m}{2}\rfloor$$$ horizontal bricks, and there will be no vertical bricks in the wall at all. This achieves the maximum stability of $$$n \cdot \lfloor\frac{m}{2}\rfloor$$$. The solution is one formula, so it works in $$$O(1)$$$ time.
Minimize Inversions
Contest: Codeforces Round 922 (Div. 2)
Difficulty rating: 900
Tags: constructive algorithms, data structures, greedy, implementation, sortings

You are given two permutations $$$a$$$ and $$$b$$$ of length $$$n$$$. A permutation is an array of $$$n$$$ elements from $$$1$$$ to $$$n$$$ where all elements are distinct. For example, an array [$$$2,1,3$$$] is a permutation, but [$$$0,1$$$] and [$$$1,3,1$$$] aren't.

You can (as many times as you want) choose two indices $$$i$$$ and $$$j$$$, then swap $$$a_i$$$ with $$$a_j$$$ and $$$b_i$$$ with $$$b_j$$$ simultaneously.

You hate inversions, so you want to minimize the total number of inversions in both permutations.

An inversion in a permutation $$$p$$$ is a pair of indices $$$(i, j)$$$ such that $$$i < j$$$ and $$$p_i > p_j$$$. For example, if $$$p=[3,1,4,2,5]$$$ then there are $$$3$$$ inversions in it (the pairs of indices are $$$(1,2)$$$, $$$(1,4)$$$ and $$$(3,4)$$$).

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 20\,000$$$) — the number of test cases.

Each test case consists of three lines. The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — the length of the permutations $$$a$$$ and $$$b$$$. The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — permutation $$$a$$$. The third line contains $$$b$$$ in a similar format.

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

Output format:
For each test case, output two permutations $$$a'$$$ and $$$b'$$$ (in the same format as in the input) — the permutations after all operations. The total number of inversions in $$$a'$$$ and $$$b'$$$ should be the minimum possible among all pairs of permutations that can be obtained using operations from the statement.

If there are multiple solutions, print any of them.

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

Note:
In the first test case, the minimum possible number of inversions is $$$10$$$.

In the second test case, we can sort both permutations at the same time. For this, the following operations can be done:

- Swap the elements in the positions $$$1$$$ and $$$3$$$ in both permutations. After the operation, $$$a =$$$ [$$$2,1,3$$$], $$$b =$$$ [$$$2,1,3$$$].
- Swap the elements in the positions $$$1$$$ and $$$2$$$. After the operations, $$$a$$$ and $$$b$$$ are sorted.

In the third test case, the minimum possible number of inversions is $$$7$$$.

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

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

Editorial:
Caterpillar on a Tree
Contest: Codeforces Round 922 (Div. 2)
Difficulty rating: 2500
Tags: dfs and similar, graphs, greedy, implementation, sortings, trees

The caterpillar decided to visit every node of the tree. Initially, it is sitting at the root.

The tree is represented as a rooted tree with the root at the node $$$1$$$. Each crawl to a neighboring node takes $$$1$$$ minute for the caterpillar.

And there is a trampoline under the tree. If the caterpillar detaches from the tree and falls onto the trampoline, it will end up at the root of the tree in $$$0$$$ seconds. But the trampoline is old and can withstand no more than $$$k$$$ caterpillar's falls.

What is the minimum time the caterpillar can take to visit all the nodes of the tree?

More formally, we need to find the minimum time required to visit all the nodes of the tree, if the caterpillar starts at the root (node $$$1$$$) and moves using two methods.

1. Crawl along an edge to one of the neighboring nodes: takes $$$1$$$ minute.
2. Teleport to the root: takes no time,  no new nodes become visited.

The second method (teleportation) can be used at most $$$k$$$ times. The caterpillar can finish the journey at any node.

Input format:
The first line of the input contains two integers: $$$n$$$ ($$$2 \le n \le 2\cdot 10^5$$$) — the number of nodes in the tree, and $$$k$$$ ($$$0 \le k \le 10^9$$$) — the maximum number of teleports to the root.

The second line contains $$$n-1$$$ integers $$$p_2$$$, $$$p_3$$$, ..., $$$p_n$$$ ($$$1 \le p_i \le n$$$) — the ancestors in the tree for nodes $$$2, 3, \ldots, n$$$; node $$$1$$$ is the root.

Output format:
Print a single number in a single line — the minimum number of minutes required to visit all the nodes of the tree.

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

Note:
The figure shows one of the ways to traverse the tree from the first test in 9 minutes.

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

Example output:
9

Example input:
4 0
4 4 1

Example output:
4

Editorial:
Permutation of Given
Contest: Codeforces Round 922 (Div. 2)
Difficulty rating: 2700
Tags: constructive algorithms, math

You were given only one number, $$$n$$$. It didn't seem interesting to you, so you wondered if it's possible to come up with an array of length $$$n$$$ consisting of non-zero integers, such that if each element of the array is replaced by the sum of its neighbors (the elements on the ends are replaced by their only neighbors), you obtain a permutation of the numbers in the original array.

Input format:
Each test case contains only one number, $$$n$$$ ($$$2 \leq n \leq 10^6$$$).

Output format:
If a solution exists, output "YES" (without quotes), followed by an array $$$a$$$ ($$$-10^9 \leq a_i \leq 10^9, a_i \neq 0$$$) that satisfies the condition of the problem. If there are multiple possible answers, output any of them.

If there is no suitable array, output "NO" (without quotes).

The words "YES" and "NO" can be output in any case, for example, "YES", "Yes", "yEs", and so on.

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

Note:
In the first test, the array [$$$1, 2, -2, -1$$$] is suitable, because if each element is replaced by the sum of its neighbors, the resulting array is [$$$2, -1, 1, -2$$$], which is a permutation of the original array.

In the second test, it can be shown that there is no solution.

Example input:
4

Example output:
YES
1 2 -2 -1

Example input:
5

Example output:
NO

Editorial: