1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Perfect Keyboard
Contest: Educational Codeforces Round 82 (Rated for Div. 2)
Difficulty rating: 1600
Tags: dfs and similar, greedy, implementation

Polycarp wants to assemble his own keyboard. Layouts with multiple rows are too complicated for him — his keyboard will consist of only one row, where all $$$26$$$ lowercase Latin letters will be arranged in some order.

Polycarp uses the same password $$$s$$$ on all websites where he is registered (it is bad, but he doesn't care). He wants to assemble a keyboard that will allow to type this password very easily. He doesn't like to move his fingers while typing the password, so, for each pair of adjacent characters in $$$s$$$, they should be adjacent on the keyboard. For example, if the password is abacaba, then the layout cabdefghi... is perfect, since characters a and c are adjacent on the keyboard, and a and b are adjacent on the keyboard. It is guaranteed that there are no two adjacent equal characters in $$$s$$$, so, for example, the password cannot be password (two characters s are adjacent).

Can you help Polycarp with choosing the perfect layout of the keyboard, if it is possible?

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

Then $$$T$$$ lines follow, each containing one string $$$s$$$ ($$$1 \le |s| \le 200$$$) representing the test case. $$$s$$$ consists of lowercase Latin letters only. There are no two adjacent equal characters in $$$s$$$.

Output format:
For each test case, do the following:

- if it is impossible to assemble a perfect keyboard, print NO (in upper case, it matters in this problem);
- otherwise, print YES (in upper case), and then a string consisting of $$$26$$$ lowercase Latin letters — the perfect layout. Each Latin letter should appear in this string exactly once. If there are multiple answers, print any of them.

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

Example input:
5
ababa
codedoca
abcda
zxzytyz
abcdefghijklmnopqrstuvwxyza

Example output:
YES
bacdefghijklmnopqrstuvwxyz
YES
edocabfghijklmnpqrstuvwxyz
NO
YES
xzytabcdefghijklmnopqrsuvw
NO

Editorial:
The problem can be solved using a greedy algorithm. We will maintain the current layout of the keyboard with letters that have already been encountered in the string, and the current position on the layout.
If the next letter of the string is already on the layout, it must be adjacent to the current one, otherwise there is no answer.
If there was no such letter yet, we can add it to the adjacent free position, if both of them is occupied, then there is no answer.
At the end, you have to add letters that were not in the string $$$s$$$.
Fill The Bag
Contest: Educational Codeforces Round 82 (Rated for Div. 2)
Difficulty rating: 1900
Tags: bitmasks, greedy

You have a bag of size $$$n$$$. Also you have $$$m$$$ boxes. The size of $$$i$$$-th box is $$$a_i$$$, where each $$$a_i$$$ is an integer non-negative power of two.

You can divide boxes into two parts of equal size. Your goal is to fill the bag completely.

For example, if $$$n = 10$$$ and $$$a = [1, 1, 32]$$$ then you have to divide the box of size $$$32$$$ into two parts of size $$$16$$$, and then divide the box of size $$$16$$$. So you can fill the bag with boxes of size $$$1$$$, $$$1$$$ and $$$8$$$.

Calculate the minimum number of divisions required to fill the bag of size $$$n$$$.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^{18}, 1 \le m \le 10^5$$$) — the size of bag and the number of boxes, respectively.

The second line of each test case contains $$$m$$$ integers $$$a_1, a_2, \dots , a_m$$$ ($$$1 \le a_i \le 10^9$$$) — the sizes of boxes. It is guaranteed that each $$$a_i$$$ is a power of two.

It is also guaranteed that sum of all $$$m$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case print one integer — the minimum number of divisions required to fill the bag of size $$$n$$$ (or $$$-1$$$, if it is impossible).

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

Example input:
3
10 3
1 32 1
23 4
16 1 4 1
20 5
2 1 16 1 8

Example output:
2
-1
0

Editorial:
If $$$\sum\limits_{i=1}^{n} a_i \ge n$$$, then the answer is YES, because the just can divide all boxes to size $$$1$$$ and then fill the bag. Otherwise the answer is NO.
If the answer is YES, let's calculate the minimum number of divisions. Let's consider all boxes from small to large. Presume that now we consider boxes of size $$$2^i$$$. Then there are three cases:
1. if in binary representation of $$$n$$$ the $$$i$$$-th bit is equal to $$$0$$$, then we don't need boxes of size $$$2^i$$$ and we can merge it into boxes of size $$$2^{i+1}$$$;
2. if in binary representation of $$$n$$$ the $$$i$$$-th bit is equal to $$$1$$$ and we have at most one box of size $$$2^i$$$, then we have to put it box in the bag and then merge the remaining boxes of size $$$2^i$$$ into boxes of size $$$2^{i+1}$$$;
3. if in binary representation of $$$n$$$ the $$$i$$$-th bit is equal to $$$1$$$ and we have not boxes of size $$$2^i$$$, then we have to divide the large box into box of size $$$2^i$$$ (let's presume that it's box of size $$$2^x$$$). After that we just continue this algorithm with box of size $$$2^x$$$.
Number of Components
Contest: Educational Codeforces Round 82 (Rated for Div. 2)
Difficulty rating: 2800
Tags: dsu, implementation

You are given a matrix $$$n \times m$$$, initially filled with zeroes. We define $$$a_{i, j}$$$ as the element in the $$$i$$$-th row and the $$$j$$$-th column of the matrix.

Two cells of the matrix are connected if they share a side, and the elements in these cells are equal. Two cells of the matrix belong to the same connected component if there exists a sequence $$$s_1$$$, $$$s_2$$$, ..., $$$s_k$$$ such that $$$s_1$$$ is the first cell, $$$s_k$$$ is the second cell, and for every $$$i \in [1, k - 1]$$$, $$$s_i$$$ and $$$s_{i + 1}$$$ are connected.

You are given $$$q$$$ queries of the form $$$x_i$$$ $$$y_i$$$ $$$c_i$$$ ($$$i \in [1, q]$$$). For every such query, you have to do the following:

1. replace the element $$$a_{x, y}$$$ with $$$c$$$;
2. count the number of connected components in the matrix.

There is one additional constraint: for every $$$i \in [1, q - 1]$$$, $$$c_i \le c_{i + 1}$$$.

Input format:
The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n, m \le 300$$$, $$$1 \le q \le 2 \cdot 10^6$$$) — the number of rows, the number of columns and the number of queries, respectively.

Then $$$q$$$ lines follow, each representing a query. The $$$i$$$-th line contains three integers $$$x_i$$$, $$$y_i$$$ and $$$c_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$, $$$1 \le c_i \le \max(1000, \lceil \frac{2 \cdot 10^6}{nm} \rceil)$$$). For every $$$i \in [1, q - 1]$$$, $$$c_i \le c_{i + 1}$$$.

Output format:
Print $$$q$$$ integers, the $$$i$$$-th of them should be equal to the number of components in the matrix after the first $$$i$$$ queries are performed.

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

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

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

Editorial:
Note that because of the low constraints on the number of colors, the problem can be solved independently for each color. Now you can divide the queries into two types: add a cell to the field and delete it. You have to maintain the number of components formed by added cells. Cell deletions will occur after all additions because of the condition $$$c_i \le c_{i+1}$$$.
The first part of the solution will be to calculate the number of components while adding new cells. This is a standard problem that can be solved using the DSU.
After that, we should note that if we consider the process of removing cells from the end, this process is similar to the process of adding. Therefore, we have to process delete requests from the end in the same way as add requests, only their contribution to the number of components will be opposite in sign.
Pasha and Hamsters
Contest: Coder-Strike 2014 - Finals (online edition, Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, implementation

Pasha has two hamsters: Arthur and Alexander. Pasha put n apples in front of them. Pasha knows which apples Arthur likes. Similarly, Pasha knows which apples Alexander likes. Pasha doesn't want any conflict between the hamsters (as they may like the same apple), so he decided to distribute the apples between the hamsters on his own. He is going to give some apples to Arthur and some apples to Alexander. It doesn't matter how many apples each hamster gets but it is important that each hamster gets only the apples he likes. It is possible that somebody doesn't get any apples.

Help Pasha distribute all the apples between the hamsters. Note that Pasha wants to distribute all the apples, not just some of them.

Input format:
The first line contains integers n, a, b (1 ≤ n ≤ 100; 1 ≤ a, b ≤ n) — the number of apples Pasha has, the number of apples Arthur likes and the number of apples Alexander likes, correspondingly.

The next line contains a distinct integers — the numbers of the apples Arthur likes. The next line contains b distinct integers — the numbers of the apples Alexander likes.

Assume that the apples are numbered from 1 to n. The input is such that the answer exists.

Output format:
Print n characters, each of them equals either 1 or 2. If the i-h character equals 1, then the i-th apple should be given to Arthur, otherwise it should be given to Alexander. If there are multiple correct answers, you are allowed to print any of them.

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

Example input:
4 2 3
1 2
2 3 4

Example output:
1 1 2 2

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

Example output:
1 1 1 1 1

Editorial:
Ideal Point
Contest: Educational Codeforces Round 143 (Rated for Div. 2)
Difficulty rating: 900
Tags: brute force, geometry, greedy

You are given $$$n$$$ one-dimensional segments (each segment is denoted by two integers — its endpoints).

Let's define the function $$$f(x)$$$ as the number of segments covering point $$$x$$$ (a segment covers the point $$$x$$$ if $$$l \le x \le r$$$, where $$$l$$$ is the left endpoint and $$$r$$$ is the right endpoint of the segment).

An integer point $$$x$$$ is called ideal if it belongs to more segments than any other integer point, i. e. $$$f(y) < f(x)$$$ is true for any other integer point $$$y$$$.

You are given an integer $$$k$$$. Your task is to determine whether it is possible to remove some (possibly zero) segments, so that the given point $$$k$$$ becomes ideal.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 50$$$).

Then $$$n$$$ lines follow, $$$i$$$-th line of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i, r_i \le 50$$$; $$$l_i \le r_i$$$) — the endpoints of the $$$i$$$-th segment.

Output format:
For each test case, print YES if it is possible to remove some (possibly zero) segments, so that the given point $$$k$$$ becomes ideal, 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 example, the point $$$3$$$ is already ideal (it is covered by three segments), so you don't have to delete anything.

In the fourth example, you can delete everything except the segment $$$[5, 5]$$$.

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

Example output:
YES
NO
NO
YES

Editorial:
First of all, let's delete all segments that do not cover the point $$$k$$$ (because they increase the value of the function $$$f$$$ at points other than $$$k$$$). If there are no segments left, then the answer is NO. Otherwise, all segments cover the point $$$k$$$. And it remains to check whether the point $$$k$$$ is the only point which is covered by all segments. Note that it does not make sense to delete any of the remaining segments, because if there are several points with maximum value of $$$f$$$, then deleting segments can only increase their number.
To check the number of points with the maximum value of $$$f$$$, you can iterate over $$$x$$$ from $$$1$$$ to $$$50$$$ and calculate $$$f(x)$$$, because of the small number of segments in the problem. A faster way is to check the size of the intersection of all segments. The left boundary of the intersection is $$$L = \max\limits_{i=1}^{n}{l_i}$$$, and the right boundary is $$$R = \min\limits_{i=1}^{n}{r_i}$$$; if $$$L = R$$$, then the point $$$k$$$ is ideal, otherwise it is not.
Binary Table (Easy Version)
Contest: Codeforces Round 684 (Div. 1)
Difficulty rating: 1500
Tags: constructive algorithms, implementation

This is the easy version of the problem. The difference between the versions is in the number of possible operations that can be made. You can make hacks if and only if you solved both versions of the problem.

You are given a binary table of size $$$n \times m$$$. This table consists of symbols $$$0$$$ and $$$1$$$.

You can make such operation: select $$$3$$$ different cells that belong to one $$$2 \times 2$$$ square and change the symbols in these cells (change $$$0$$$ to $$$1$$$ and $$$1$$$ to $$$0$$$).

Your task is to make all symbols in the table equal to $$$0$$$. You are allowed to make at most $$$3nm$$$ operations. You don't need to minimize the number of operations.

It can be proved that it is always possible.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 5000$$$) — the number of test cases. The next lines contain descriptions of test cases.

The first line of the description of each test case contains two integers $$$n$$$, $$$m$$$ ($$$2 \leq n, m \leq 100$$$).

Each of the next $$$n$$$ lines contains a binary string of length $$$m$$$, describing the symbols of the next row of the table.

It is guaranteed that the sum of $$$nm$$$ for all test cases does not exceed $$$20000$$$.

Output format:
For each test case print the integer $$$k$$$ ($$$0 \leq k \leq 3nm$$$) — the number of operations.

In the each of the next $$$k$$$ lines print $$$6$$$ integers $$$x_1, y_1, x_2, y_2, x_3, y_3$$$ ($$$1 \leq x_1, x_2, x_3 \leq n, 1 \leq y_1, y_2, y_3 \leq m$$$) describing the next operation. This operation will be made with three cells $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$, $$$(x_3, y_3)$$$. These three cells should be different. These three cells should belong into some $$$2 \times 2$$$ square.

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

Note:
In the first test case, it is possible to make only one operation with cells $$$(1, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$. After that, all symbols will be equal to $$$0$$$.

In the second test case:

- operation with cells $$$(2, 1)$$$, $$$(3, 1)$$$, $$$(3, 2)$$$. After it the table will be: 011001000
- operation with cells $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(2, 3)$$$. After it the table will be: 000000000

In the fifth test case:

- operation with cells $$$(1, 3)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$. After it the table will be: 010110
- operation with cells $$$(1, 2)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$. After it the table will be: 000000

Example input:
5
2 2
10
11
3 3
011
101
110
4 4
1111
0110
0110
1111
5 5
01011
11001
00010
11011
10000
2 3
011
101

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

Editorial:
Forbidden Integer
Contest: Educational Codeforces Round 151 (Rated for Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, implementation, math, number theory

You are given an integer $$$n$$$, which you want to obtain. You have an unlimited supply of every integer from $$$1$$$ to $$$k$$$, except integer $$$x$$$ (there are no integer $$$x$$$ at all).

You are allowed to take an arbitrary amount of each of these integers (possibly, zero). Can you make the sum of taken integers equal to $$$n$$$?

If there are multiple answers, print any of them.

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

The only line of each testcase contains three integers $$$n, k$$$ and $$$x$$$ ($$$1 \le x \le k \le n \le 100$$$).

Output format:
For each test case, in the first line, print "YES" or "NO" — whether you can take an arbitrary amount of each integer from $$$1$$$ to $$$k$$$, except integer $$$x$$$, so that their sum is equal to $$$n$$$.

If you can, the second line should contain a single integer $$$m$$$ — the total amount of taken integers. The third line should contain $$$m$$$ integers — each of them from $$$1$$$ to $$$k$$$, not equal to $$$x$$$, and their sum is $$$n$$$.

If there are multiple answers, print any of them.

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

Note:
Another possible answer for the first testcase is $$$[3, 3, 3, 1]$$$. Note that you don't have to minimize the amount of taken integers. There also exist other answers.

In the second testcase, you only have an unlimited supply of integer $$$2$$$. There is no way to get sum $$$5$$$ using only them.

In the fifth testcase, there are no integers available at all, so you can't get any positive sum.

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

Example output:
YES
6
3 1 1 1 1 3
NO
YES
2
2 2
YES
1
7
NO

Editorial:
The problem is about considering the least amount of cases possible. I propose the following options.
If $$$x \neq 1$$$, then you can always print $$$n$$$ ones. So the answer is YES.
If $$$k = 1$$$, then no integer is available, so the answer is NO.
If $$$k = 2$$$, then only $$$2$$$ is available, so you can only collect even $$$n$$$. So if it's odd, the answer is NO.
Otherwise, you can always collect $$$n$$$ with the following construction: if $$$n$$$ is even then take $$$2$$$, otherwise take $$$3$$$. Then take $$$\lfloor \frac{n}{2} \rfloor - 1$$$ twos. You can see that an even $$$n$$$ only uses twos, so it fits the previous check. If it's odd, then $$$k$$$ is at least $$$3$$$, so $$$3$$$ is allowed to take.
Overall complexity: $$$O(n)$$$ per testcase.
Square
Contest: Codeforces Round 920 (Div. 3)
Difficulty rating: 800
Tags: greedy, math

A square of positive (strictly greater than $$$0$$$) area is located on the coordinate plane, with sides parallel to the coordinate axes. You are given the coordinates of its corners, in random order. Your task is to find the area of the square.

Input format:
Each test consists of several testcases. The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of testcases. The following is a description of the testcases.

Each testcase contains four lines, each line contains two integers $$$x_i, y_i$$$ ($$$-1000\le x_i, y_i\le 1000$$$), coordinates of the corners of the square.

It is guaranteed that there is a square with sides parallel to the coordinate axes, with positive (strictly greater than $$$0$$$) area, with corners in given points.

Output format:
For each test case, print a single integer, the area of the square.

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

Example input:
3
1 2
4 5
1 5
4 2
-1 1
1 -1
1 1
-1 -1
45 11
45 39
17 11
17 39

Example output:
9
4
784

Editorial:
There are many ways to solve this problem, the simplest way is as follows. Let's find the minimum and maximum coordinate $$$x$$$ among all the corners of the square. The difference of these coordinates will give us the length of the square side $$$d = x_{max} - x_{min}$$$. After that, we can calculate the area of the square as $$$s = d^2$$$.
Very Different Array
Contest: Codeforces Round 920 (Div. 3)
Difficulty rating: 1100
Tags: data structures, greedy, sortings, two pointers

Petya has an array $$$a_i$$$ of $$$n$$$ integers. His brother Vasya became envious and decided to make his own array of $$$n$$$ integers.

To do this, he found $$$m$$$ integers $$$b_i$$$ ($$$m\ge n$$$), and now he wants to choose some $$$n$$$ integers of them and arrange them in a certain order to obtain an array $$$c_i$$$ of length $$$n$$$.

To avoid being similar to his brother, Vasya wants to make his array as different as possible from Petya's array. Specifically, he wants the total difference $$$D = \sum_{i=1}^{n} |a_i - c_i|$$$ to be as large as possible.

Help Vasya find the maximum difference $$$D$$$ he can obtain.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. This is followed by a description of the test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n\le m\le 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$1\le a_i\le 10^9$$$). The third line of each test case contains $$$m$$$ integers $$$b_i$$$ ($$$1\le b_i\le 10^9$$$).

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

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

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

Note:
In the first example, Vasya can, for example, create the array $$$(1, 5, 7, 2)$$$. Then the total difference will be $$$D = |6-1|+|1-5|+|2-7|+|4-2| = 5+4+5+2 = 16$$$.

In the second example, all the integers available to Vasya are equal to 1, so he can only create the array $$$(1, 1, 1)$$$, for which the difference $$$D = 0$$$.

In the third example, Vasya can, for example, create the array $$$(5, 4, 3, 2, 1)$$$. Then the total difference will be $$$D = |1-5|+|2-4|+|3-3|+|4-2|+|5-1| = 4+2+0+2+4 = 12$$$.

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

Example output:
16
0
12
11
10
23
15
25
7

Editorial:
Let's sort the array $$$a$$$ in ascending order, and the array $$$b$$$ in descending order. Notice that small elements of array $$$a$$$ need to be matched with large elements of array $$$b$$$ and vice versa. Thus, for some $$$k$$$, we need to take a prefix of array $$$b$$$ of length $$$k$$$ and a suffix of length $$$n-k$$$, and form array $$$c$$$ from them. We iterate over the value of $$$k$$$ from $$$0$$$ to $$$n$$$, and each time $$$k$$$ changes by 1, only one element of array $$$c$$$ changes, so we can recalculate the value of $$$D$$$ in $$$O(1)$$$. We select the maximum value of $$$D$$$ from the obtained values to get the answer. This solution works in $$$O(n)$$$ time plus the initial sorting in $$$O(n \log n)$$$.
There are other ways to solve the problem in the same time complexity.