1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Forbidden Subsequence
Contest: Codeforces Round 761 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, greedy, sortings, strings

You are given strings $$$S$$$ and $$$T$$$, consisting of lowercase English letters. It is guaranteed that $$$T$$$ is a permutation of the string abc.

Find string $$$S'$$$, the lexicographically smallest permutation of $$$S$$$ such that $$$T$$$ is not a subsequence of $$$S'$$$.

String $$$a$$$ is a permutation of string $$$b$$$ if the number of occurrences of each distinct character is the same in both strings.

A string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

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

The first line of each test case contains a string $$$S$$$ ($$$1 \le |S| \le 100$$$), consisting of lowercase English letters.

The second line of each test case contains a string $$$T$$$ that is a permutation of the string abc. (Hence, $$$|T| = 3$$$).

Note that there is no limit on the sum of $$$|S|$$$ across all test cases.

Output format:
For each test case, output a single string $$$S'$$$, the lexicographically smallest permutation of $$$S$$$ such that $$$T$$$ is not a subsequence of $$$S'$$$.

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

Note:
In the first test case, both aaaabbc and aaaabcb are lexicographically smaller than aaaacbb, but they contain abc as a subsequence.

In the second test case, abccc is the smallest permutation of cccba and does not contain acb as a subsequence.

In the third test case, bcdis is the smallest permutation of dbsic and does not contain bac as a subsequence.

Example input:
7
abacaba
abc
cccba
acb
dbsic
bac
abracadabra
abc
dddddddddddd
cba
bbc
abc
ac
abc

Example output:
aaaacbb
abccc
bcdis
aaaaacbbdrr
dddddddddddd
bbc
ac

Editorial:
If there are no occurrences of a, b or c in $$$S$$$, sort $$$S$$$ and output it.
Else, if $$$T \ne$$$ "abc", sort $$$S$$$ and output it.
Else, output all a, then all c, then all b, then the rest of the string sorted.
GCD Problem
Contest: Codeforces Round 761 (Div. 2)
Difficulty rating: 900
Tags: brute force, constructive algorithms, math, number theory

Given a positive integer $$$n$$$. Find three distinct positive integers $$$a$$$, $$$b$$$, $$$c$$$ such that $$$a + b + c = n$$$ and $$$\operatorname{gcd}(a, b) = c$$$, where $$$\operatorname{gcd}(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Description of the test cases follows.

The first and only line of each test case contains a single integer $$$n$$$ ($$$10 \le n \le 10^9$$$).

Output format:
For each test case, output three distinct positive integers $$$a$$$, $$$b$$$, $$$c$$$ satisfying the requirements. If there are multiple solutions, you can print any. We can show that an answer always exists.

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

Note:
In the first test case, $$$6 + 9 + 3 = 18$$$ and $$$\operatorname{gcd}(6, 9) = 3$$$.

In the second test case, $$$21 + 39 + 3 = 63$$$ and $$$\operatorname{gcd}(21, 39) = 3$$$.

In the third test case, $$$29 + 43 + 1 = 73$$$ and $$$\operatorname{gcd}(29, 43) = 1$$$.

Example input:
6
18
63
73
91
438
122690412

Example output:
6 9 3
21 39 3
29 43 1
49 35 7
146 219 73
28622 122661788 2

Editorial:
Key observation: there always exists a solution with $$$c = 1$$$ under the given constraints. We set $$$n \ge 10$$$ because there is no solution when $$$1 \le n \le 5$$$ or $$$n = 7$$$.
Solution 1: Brute force from $$$a = 2, 3, 4, \dots$$$ and calculate the value of $$$b$$$ ($$$b = n - a - 1$$$), then check whether $$$gcd(a, b) = 1$$$. It works, because you will find a prime number $$$p \le 29$$$ such that $$$n-1$$$ does not divide $$$p$$$.
Solution 2: Randomly choose $$$a$$$ and calculate $$$b$$$ ($$$b = n - a - 1$$$). Repeating that for enough times will eventually get you a pair of ($$$a, b$$$) such that $$$gcd(a, b) = 1$$$.
Solution 3: Constructive solution.
• When $$$n \equiv 0 \pmod 2$$$, output ($$$n-3, 2, 1$$$).
• When $$$n \equiv 1 \pmod 4$$$, output ($$$\left \lfloor \frac{n}{2} \right \rfloor -1, \left \lfloor \frac{n}{2} \right \rfloor +1, 1$$$).
• When $$$n \equiv 3 \pmod 4$$$, output ($$$\left \lfloor \frac{n}{2} \right \rfloor -2, \left \lfloor \frac{n}{2} \right \rfloor +2, 1$$$).
Replacement
Contest: Codeforces Beta Round 97 (Div. 1)
Difficulty rating: 1300
Tags: greedy, implementation, sortings

Little Petya very much likes arrays consisting of n integers, where each of them is in the range from 1 to 109, inclusive. Recently he has received one such array as a gift from his mother. Petya didn't like it at once. He decided to choose exactly one element from the array and replace it with another integer that also lies in the range from 1 to 109, inclusive. It is not allowed to replace a number with itself or to change no number at all.

After the replacement Petya sorted the array by the numbers' non-decreasing. Now he wants to know for each position: what minimum number could occupy it after the replacement and the sorting.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 105), which represents how many numbers the array has. The next line contains n space-separated integers — the array's description. All elements of the array lie in the range from 1 to 109, inclusive.

Output format:
Print n space-separated integers — the minimum possible values of each array element after one replacement and the sorting are performed.

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

Example input:
5
1 2 3 4 5

Example output:
1 1 2 3 4

Example input:
5
2 3 4 5 6

Example output:
1 2 3 4 5

Editorial:
Rectangle and Square
Contest: Codeforces Beta Round 97 (Div. 1)
Difficulty rating: 1600
Tags: brute force, geometry, math

Little Petya very much likes rectangles and especially squares. Recently he has received 8 points on the plane as a gift from his mother. The points are pairwise distinct. Petya decided to split them into two sets each containing 4 points so that the points from the first set lay at the vertexes of some square and the points from the second set lay at the vertexes of a rectangle. Each point of initial 8 should belong to exactly one set. It is acceptable for a rectangle from the second set was also a square. If there are several partitions, Petya will be satisfied by any of them. Help him find such partition. Note that the rectangle and the square from the partition should have non-zero areas. The sides of the figures do not have to be parallel to the coordinate axes, though it might be the case.

Input format:
You are given 8 pairs of integers, a pair per line — the coordinates of the points Petya has. The absolute value of all coordinates does not exceed 104. It is guaranteed that no two points coincide.

Output format:
Print in the first output line "YES" (without the quotes), if the desired partition exists. In the second line output 4 space-separated numbers — point indexes from the input, which lie at the vertexes of the square. The points are numbered starting from 1. The numbers can be printed in any order. In the third line print the indexes of points lying at the vertexes of a rectangle in the similar format. All printed numbers should be pairwise distinct.

If the required partition does not exist, the first line should contain the word "NO" (without the quotes), after which no output is needed.

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

Note:
Pay attention to the third example: the figures do not necessarily have to be parallel to the coordinate axes.

Example input:
0 0
10 11
10 0
0 11
1 1
2 2
2 1
1 2

Example output:
YES
5 6 7 8
1 2 3 4

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

Example output:
NO

Editorial:
Zero-One
Contest: Codeforces Beta Round 97 (Div. 1)
Difficulty rating: 1900
Tags: constructive algorithms, games, greedy

Little Petya very much likes playing with little Masha. Recently he has received a game called "Zero-One" as a gift from his mother. Petya immediately offered Masha to play the game with him.

Before the very beginning of the game several cards are lain out on a table in one line from the left to the right. Each card contains a digit: 0 or 1. Players move in turns and Masha moves first. During each move a player should remove a card from the table and shift all other cards so as to close the gap left by the removed card. For example, if before somebody's move the cards on the table formed a sequence 01010101, then after the fourth card is removed (the cards are numbered starting from 1), the sequence will look like that: 0100101.

The game ends when exactly two cards are left on the table. The digits on these cards determine the number in binary notation: the most significant bit is located to the left. Masha's aim is to minimize the number and Petya's aim is to maximize it.

An unpleasant accident occurred before the game started. The kids spilled juice on some of the cards and the digits on the cards got blurred. Each one of the spoiled cards could have either 0 or 1 written on it. Consider all possible variants of initial arrangement of the digits (before the juice spilling). For each variant, let's find which two cards are left by the end of the game, assuming that both Petya and Masha play optimally. An ordered pair of digits written on those two cards is called an outcome. Your task is to find the set of outcomes for all variants of initial digits arrangement.

Input format:
The first line contains a sequence of characters each of which can either be a "0", a "1" or a "?". This sequence determines the initial arrangement of cards on the table from the left to the right. The characters "?" mean that the given card was spoiled before the game. The sequence's length ranges from 2 to 105, inclusive.

Output format:
Print the set of outcomes for all possible initial digits arrangements. Print each possible outcome on a single line. Each outcome should be represented by two characters: the digits written on the cards that were left by the end of the game. The outcomes should be sorted lexicographically in ascending order (see the first sample).

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

Note:
In the first sample all 16 variants of numbers arrangement are possible. For the variant 0000 the outcome is 00. For the variant 1111 the outcome is 11. For the variant 0011 the outcome is 01. For the variant 1100 the outcome is 10. Regardless of outcomes for all other variants the set which we are looking for will contain all 4 possible outcomes.

In the third sample only 2 variants of numbers arrangement are possible: 111 and 101. For the variant 111 the outcome is 11. For the variant 101 the outcome is 01, because on the first turn Masha can remove the first card from the left after which the game will end.

Example input:
????

Example output:
00
01
10
11

Example input:
1010

Example output:
10

Editorial:
Cycle
Contest: Codeforces Beta Round 97 (Div. 1)
Difficulty rating: 2500
Tags: brute force, dfs and similar, implementation

Little Petya very much likes rectangular tables that consist of characters "0" and "1". Recently he has received one such table as a gift from his mother. The table contained n rows and m columns. The rows are numbered from top to bottom from 1 to n, the columns are numbered from the left to the right from 1 to m. Petya immediately decided to find the longest cool cycle whatever it takes.

A cycle is a sequence of pairwise distinct cells where each two consecutive cells have a common side; besides, the first cell has a common side with the last cell. A cycle is called cool if it fulfills all the following conditions simultaneously:

- The cycle entirely consists of the cells that contain "1".
- Each cell that belongs to the cycle, has a common side with exactly two other cells that belong to the cycle.
- Each cell of the table that contains "1" either belongs to the cycle or is positioned outside of it (see definition below).

To define the notion of "outside" formally, let's draw a cycle on a plane. Let each cell of the cycle (i, j) (i is the row number, j is the column number) correspond to the point (i, j) on the coordinate plane. Let a straight line segment join each pair of points that correspond to the cells belonging to the cycle and sharing a side. Thus, we will get a closed polyline that has no self-intersections and self-touches. The polyline divides the plane into two connected parts: the part of an infinite area and the part of a finite area. It is considered that cell (r, c) lies outside of the cycle if it does not belong to the cycle and the corresponding point on the plane with coordinates (r, c) lies in the part with the infinite area.

Help Petya to find the length of the longest cool cycle in the table. The cycle length is defined as the number of cells that belong to the cycle.

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 1000) — the number of rows and columns in the table, respectively. Each of the following n lines contains m characters. Each character can be either "0" or "1".

Output format:
Print a single number — the length of the longest cool cycle in the table. If such cycles do not exist, print 0.

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

Note:
In the first example there's only one cycle and it is cool.

In the second sample there's no cycle at all.

In the third sample there are two cool cycles: their lengths are 12 and 24.

In the fourth sample there also is only one cycle but it isn't cool as there's a cell containing "1" inside this cycle.

Example input:
3 3
111
101
111

Example output:
8

Example input:
5 5
01010
10101
01010
10101
01010

Example output:
0

Editorial:
Weak Subsequence
Contest: Codeforces Beta Round 97 (Div. 1)
Difficulty rating: 3000
Tags: combinatorics

Little Petya very much likes strings. Recently he has received a voucher to purchase a string as a gift from his mother. The string can be bought in the local shop. One can consider that the shop has all sorts of strings over the alphabet of fixed size. The size of the alphabet is equal to k. However, the voucher has a string type limitation: specifically, the voucher can be used to purchase string s if the length of string's longest substring that is also its weak subsequence (see the definition given below) equals w.

String a with the length of n is considered the weak subsequence of the string s with the length of m, if there exists such a set of indexes 1 ≤ i1 < i2 < ... < in ≤ m, that has the following two properties:

- ak = sik for all k from 1 to n;
- there exists at least one such k (1 ≤ k < n), for which ik + 1 – ik > 1.

Petya got interested how many different strings are available for him to purchase in the shop. As the number of strings can be very large, please find it modulo 1000000007 (109 + 7). If there are infinitely many such strings, print "-1".

Input format:
The first line contains two integers k (1 ≤ k ≤ 106) and w (2 ≤ w ≤ 109) — the alphabet size and the required length of the maximum substring that also is the weak subsequence, correspondingly.

Output format:
Print a single number — the number of strings Petya can buy using the voucher, modulo 1000000007 (109 + 7). If there are infinitely many such strings, print "-1" (without the quotes).

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

Note:
In the first sample Petya can buy the following strings: aaa, aab, abab, abb, abba, baa, baab, baba, bba, bbb.

Example input:
2 2

Example output:
10

Example input:
3 5

Example output:
1593

Editorial:
Ksusha and Array
Contest: Croc Champ 2013 - Round 2 (Div. 2 Edition)
Difficulty rating: 1000
Tags: brute force, number theory, sortings

Ksusha is a beginner coder. Today she starts studying arrays. She has array a1, a2, ..., an, consisting of n positive integers.

Her university teacher gave her a task. Find such number in the array, that all array elements are divisible by it. Help her and find the number!

Input format:
The first line contains integer n (1 ≤ n ≤ 105), showing how many numbers the array has. The next line contains integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the array elements.

Output format:
Print a single integer — the number from the array, such that all array elements are divisible by it. If such number doesn't exist, print -1.

If there are multiple answers, you are allowed to print any of them.

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

Example input:
3
2 2 4

Example output:
2

Example input:
5
2 1 3 1 6

Example output:
1

Editorial:
Ksusha the Squirrel
Contest: Croc Champ 2013 - Round 2 (Div. 2 Edition)
Difficulty rating: 900
Tags: brute force, implementation

Ksusha the Squirrel is standing at the beginning of a straight road, divided into n sectors. The sectors are numbered 1 to n, from left to right. Initially, Ksusha stands in sector 1.

Ksusha wants to walk to the end of the road, that is, get to sector n. Unfortunately, there are some rocks on the road. We know that Ksusha hates rocks, so she doesn't want to stand in sectors that have rocks.

Ksusha the squirrel keeps fit. She can jump from sector i to any of the sectors i + 1, i + 2, ..., i + k.

Help Ksusha! Given the road description, say if she can reach the end of the road (note, she cannot stand on a rock)?

Input format:
The first line contains two integers n and k (2 ≤ n ≤ 3·105, 1 ≤ k ≤ 3·105). The next line contains n characters — the description of the road: the i-th character equals ".", if the i-th sector contains no rocks. Otherwise, it equals "#".

It is guaranteed that the first and the last characters equal ".".

Output format:
Print "YES" (without the quotes) if Ksusha can reach the end of the road, otherwise print "NO" (without the quotes).

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

Example input:
2 1
..

Example output:
YES

Example input:
5 2
.#.#.

Example output:
YES

Editorial:
Berland Crossword
Contest: Educational Codeforces Round 105 (Rated for Div. 2)
Difficulty rating: 1400
Tags: bitmasks, brute force, greedy, implementation

Berland crossword is a puzzle that is solved on a square grid with $$$n$$$ rows and $$$n$$$ columns. Initially all the cells are white.

To solve the puzzle one has to color some cells on the border of the grid black in such a way that:

- exactly $$$U$$$ cells in the top row are black;
- exactly $$$R$$$ cells in the rightmost column are black;
- exactly $$$D$$$ cells in the bottom row are black;
- exactly $$$L$$$ cells in the leftmost column are black.

Note that you can color zero cells black and leave every cell white.

Your task is to check if there exists a solution to the given puzzle.

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

Then the descriptions of $$$t$$$ testcases follow.

The only line of each testcase contains $$$5$$$ integers $$$n, U, R, D, L$$$ ($$$2 \le n \le 100$$$; $$$0 \le U, R, D, L \le n$$$).

Output format:
For each testcase print "YES" if the solution exists and "NO" otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES are all recognized as positive answer).

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

Note:
Here are possible solutions to testcases $$$1$$$, $$$2$$$ and $$$4$$$:

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

Example output:
YES
YES
NO
YES

Editorial:
Consider some corner of the picture. If it's colored black, then it contributes to counts to both of the adjacent sides. Otherwise, it contributes to none. All the remaining cells can contribute only to the side they are on. There are $$$n-2$$$ of such cells on each side.
So let's try all $$$2^4$$$ options of coloring the corners. After fixing the colors of the corners, we can calculate the number of cells that have to be colored on each side. That is calculated by taking the initial requirement and subtracting the adjacent colored corners from it. If any of the numbers is below $$$0$$$ or above $$$n-2$$$ then that corner coloring doesn't work. Otherwise, you can always color the cells in some way.
Overall complexity: $$$O(1)$$$ per testcase.
Beautiful Sequence
Contest: Codeforces Round 604 (Div. 1)
Difficulty rating: 1900
Tags: brute force, constructive algorithms, greedy

An integer sequence is called beautiful if the difference between any two consecutive numbers is equal to $$$1$$$. More formally, a sequence $$$s_1, s_2, \ldots, s_{n}$$$ is beautiful if $$$|s_i - s_{i+1}| = 1$$$ for all $$$1 \leq i \leq n - 1$$$.

Trans has $$$a$$$ numbers $$$0$$$, $$$b$$$ numbers $$$1$$$, $$$c$$$ numbers $$$2$$$ and $$$d$$$ numbers $$$3$$$. He wants to construct a beautiful sequence using all of these $$$a + b + c + d$$$ numbers.

However, it turns out to be a non-trivial task, and Trans was not able to do it. Could you please help Trans?

Input format:
The only input line contains four non-negative integers $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$ ($$$0 < a+b+c+d \leq 10^5$$$).

Output format:
If it is impossible to construct a beautiful sequence satisfying the above constraints, print "NO" (without quotes) in one line.

Otherwise, print "YES" (without quotes) in the first line. Then in the second line print $$$a + b + c + d$$$ integers, separated by spaces — a beautiful sequence. There should be $$$a$$$ numbers equal to $$$0$$$, $$$b$$$ numbers equal to $$$1$$$, $$$c$$$ numbers equal to $$$2$$$ and $$$d$$$ numbers equal to $$$3$$$.

If there are multiple answers, you can print any of them.

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

Note:
In the first test, it is easy to see, that the sequence is beautiful because the difference between any two consecutive numbers is equal to $$$1$$$. Also, there are exactly two numbers, equal to $$$0$$$, $$$1$$$, $$$2$$$ and exactly one number, equal to $$$3$$$.

It can be proved, that it is impossible to construct beautiful sequences in the second and third tests.

Example input:
2 2 2 1

Example output:
YES
0 1 0 1 2 3 2

Example input:
1 2 3 4

Example output:
NO

Editorial:
Firstly, let's arrange even numbers. It is optimal to arrange those numbers as $$$0, 0, 0,\ldots,0,2, 2, \ldots 2$$$. Because we can place number $$$1$$$ anywhere while number $$$3$$$ only between two numbers $$$2$$$ or at the end beside a number $$$2$$$. So we need to maximize the number of positions where we can place number $$$3$$$. The above gives us an optimal way. The next step is to place the remaining numbers $$$1, 3$$$. Inserting them in internal positions first then at the ends later.
Base on the above argument, we can do as following way that eliminates corner case issues:
Starting from a number (try all possible value $$$0, 1, 2, 3$$$). At any moment, if $$$x$$$ is the last element and there is at least number $$$x - 1$$$ remains, we append $$$x - 1$$$ otherwise we append $$$x + 1$$$ or stop if there is no $$$x + 1$$$ left. If we manage to use all numbers then we have a beautiful sequence and answer is 'YES'.