1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Queue
Contest: Codeforces Round 101 (Div. 2)
Difficulty rating: 1800
Tags: constructive algorithms, greedy, sortings

In the Main Berland Bank n people stand in a queue at the cashier, everyone knows his/her height hi, and the heights of the other people in the queue. Each of them keeps in mind number ai — how many people who are taller than him/her and stand in queue in front of him.

After a while the cashier has a lunch break and the people in the queue seat on the chairs in the waiting room in a random order.

When the lunch break was over, it turned out that nobody can remember the exact order of the people in the queue, but everyone remembers his number ai.

Your task is to restore the order in which the people stood in the queue if it is possible. There may be several acceptable orders, but you need to find any of them. Also, you need to print a possible set of numbers hi — the heights of people in the queue, so that the numbers ai are correct.

Input format:
The first input line contains integer n — the number of people in the queue (1 ≤ n ≤ 3000). Then n lines contain descriptions of the people as "namei ai" (one description on one line), where namei is a non-empty string consisting of lowercase Latin letters whose length does not exceed 10 characters (the i-th person's name), ai is an integer (0 ≤ ai ≤ n - 1), that represents the number of people who are higher and stand in the queue in front of person i. It is guaranteed that all names are different.

Output format:
If there's no acceptable order of the people in the queue, print the single line containing "-1" without the quotes. Otherwise, print in n lines the people as "namei hi", where hi is the integer from 1 to 109 (inclusive), the possible height of a man whose name is namei. Print the people in the order in which they stand in the queue, starting from the head of the queue and moving to its tail. Numbers hi are not necessarily unique.

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

Example input:
4
a 0
b 2
c 0
d 0

Example output:
a 150
c 170
d 180
b 160

Example input:
4
vasya 0
petya 1
manya 3
dunay 3

Example output:
-1

Editorial:
Clearing Up
Contest: Codeforces Round 101 (Div. 2)
Difficulty rating: 2300
Tags: constructive algorithms, dp, dsu, graphs

After Santa Claus and his assistant Elf delivered all the presents and made all the wishes come true, they returned to the North Pole and found out that it is all covered with snow. Both of them were quite tired and they decided only to remove the snow from the roads connecting huts. The North Pole has n huts connected with m roads. One can go along the roads in both directions.

The Elf offered to split: Santa Claus will clear up the wide roads and the Elf will tread out the narrow roads. For each road they decided who will clear it: Santa Claus or the Elf. To minimize the efforts they decided to clear the road so as to fulfill both those conditions:

- between any two huts should exist exactly one simple path along the cleared roads;
- Santa Claus and the Elf should clear the same number of roads.

At this point Santa Claus and his assistant Elf wondered which roads should they clear up?

Input format:
The first input line contains two positive integers n and m (1 ≤ n ≤ 103, 1 ≤ m ≤ 105) — the number of huts and the number of roads. Then follow m lines, each of them contains a road description: the numbers of huts it connects — x and y (1 ≤ x, y ≤ n) and the person responsible for clearing out this road ("S" — for the Elf or "M" for Santa Claus). It is possible to go on each road in both directions. Note that there can be more than one road between two huts and a road can begin and end in the same hut.

Output format:
Print "-1" without the quotes if it is impossible to choose the roads that will be cleared by the given rule. Otherwise print in the first line how many roads should be cleared and in the second line print the numbers of those roads (the roads are numbered from 1 in the order of occurrence in the input). It is allowed to print the numbers of the roads in any order. Each number should be printed exactly once. As you print the numbers, separate them with spaces.

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

Note:
A path is called simple if all huts on it are pairwise different.

Example input:
1 2
1 1 S
1 1 M

Example output:
0

Example input:
3 3
1 2 S
1 3 M
2 3 S

Example output:
2
2 1

Editorial:
Mike's Sequence
Contest: April Fools Day Contest 2022
Tags: *special, divide and conquer, implementation, math

You won't find this sequence on OEIS.

Input format:
One integer $$$r$$$ ($$$-45 \le r \le 2999$$$).

Output format:
One integer.

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

Example input:
2999

Example output:
3000

Editorial:
The sequence is simply the rating thresholds for Codeforces. For a given rating $$$x$$$, output the minimum rating for the next rank
Pōja Verdon
Contest: April Fools Day Contest 2022
Tags: *special, implementation, math

Aenar has an array $$$a$$$ consisting of $$$n$$$ integers.

Input format:
The first line is the integer $$$n$$$ ($$$1 \le n \le 100$$$).

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$0 \le a_i \le 3979$$$) — the contents of the array.

Output format:
Output a single number.

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

Editorial:
Aenar Targaryen was a dragonlord of Valyria (an empire from a A Song of Ice and Fire) who moved his family to Westeros right before Valyria was destroyed.
"pōja" means "their" and "verdon" means "sum" (or "amount" based on context) in High Valyrian.
In a nutshell: Print the sum of the array.
Is it rated - 3
Contest: April Fools Day Contest 2022
Tags: *special, combinatorics, dp, math

Input format:
The first line contains a string $$$S$$$.

The second line contains an integer $$$X$$$.

Constraints

- $$$|S|=3$$$
- $$$0 \le X \le 10^9$$$
- The input is guaranteed to be valid.

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

Editorial:
The capital variable letters and the "constraints" section are designed to mimic how atcoder.jp formats their problem statements.
The problem is asking whether the Atcoder contest (ABC,ARC,AGC) is rated for a rating $$$X$$$. (Note that the judge ignores Atcoder's heuristic contests for simplicity).
• ABC's are rated for $$$[0,1999]$$$
• ARC's are rated for $$$[0,2799]$$$
• AGC's are rated for $$$[1200,\infty]$$$
Are You Safe?
Contest: April Fools Day Contest 2022
Tags: *special, implementation

Seven boys and seven girls from Athens were brought before King Minos. The evil king laughed and said "I hope you enjoy your stay in Crete".

With a loud clang, the doors behind them shut, and darkness reigned. The terrified children huddled together. In the distance they heard a bellowing, unholy roar.

Bravely, they advanced forward, to their doom.

Input format:
$$$n$$$ ($$$1 \le n \le 100$$$) — the dimensions of the labyrinth.

Each of the next $$$n$$$ lines contains a string of lowercase English letters of length $$$n$$$.

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

Example input:
10
atzxcodera
mzhappyayc
mineodteri
trxesonaac
mtollexcxc
hjikeoutlc
eascripsni
rgvymnjcxm
onzazwswwg
geothermal

Example output:
YES

Editorial:
Perhaps you recognize the story of the minotaur? Less known is the hero who saved the kids from the minotaur: his name was Theseus [thee-see-us].
The problem is just a word search (horizontal, vertical, diagonal) for "theseus". You should only go in the forward direction when you search for a word.
BONUS: The grid contains other clues embedded in it. Perhaps you can find "esoteric", "java", and "script" (hints for problem G). You might be able to find "atcoder" (hint for problem D). Also "hero" (hinting at Theseus for this problem).
There are also some red herring words out there.
In Every Generation...
Contest: April Fools Day Contest 2022
Tags: *special, strings

In every generation there is a Chosen One. She alone will stand against the vampires, the demons, and the forces of darkness. She is the Slayer. — Joss Whedon

Input format:
A string $$$s$$$ ($$$3 \le |s| \le 7$$$) consisting of lowercase English letters.

Output format:
A single string. If there is no answer, print "none" (without the quotes).

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

Example input:
tourist

Example output:
ooggqjx

Editorial:
The quote is from the well known TV series Buffy the Vampire Slayer.
Perhaps you notice the lengths of the words "buffy", "the", "vampire", "slayer" are unique integers in the set {3,5,6,7}.
Given the string $$$s$$$, simply do a forward shift with the target word of the same length. For example, "ccccc" is paired with "buffy" which goes to "dwhha".
However, if the length of $$$s$$$ is $$$4$$$, the answer is "none".
Six Characters
Contest: April Fools Day Contest 2022
Tags: *special, constructive algorithms, strings

Aenar should go to the string's home.

Input format:
A string consisting of only $$$6$$$ letters.

Output format:
A string consisting of only $$$6$$$ characters.

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

Note:
If many answers are possible, the jury will still only accept one!

Editorial:
The April Fool's Contests love of esoteric programming languages, combined with the reference to "six characters", will quickly lead you to JSFuck.
The six characters is a pun: the input is a string of length 6 like "abcdef", but the output is a string of any (reasonable) length consisting of only 6 characters: [, ], (, ), !, and +.
Brief research will demonstrate a mapping from each english letter to a JSFuck string. Note that the optimal mapping will make your solution file approximately 12KB in size, well within the 64KB requirement of Codeforces.
However, the mapping from each letter to javascript is not unique! However, the legend mentions that Aenar needs to go to the string's "home". JSFuck's home website is https://jsfuck.com.
Cross-Language Program
Contest: April Fools Day Contest 2022
Tags: *special, constructive algorithms

Write a program that is compilable simultaneously in two languages: C++ (GCC 10.3.1, -std=c++11) and FreePascal (3.0.4).

It absolutely does not matter what this program does, the only requirement is that it successfully compiles into an executable file in both C++ and Pascal.

Please use the language Text to submit your solution. Just choose Text as a language in the submission form.

The submitted file can't exceed 2048 bytes. It should compile fast on both compilers.

Input format:
No input.

Output format:
No output.

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

Editorial:
Difference Array
Contest: Codeforces Round 808 (Div. 1)
Difficulty rating: 1900
Tags: brute force, data structures, implementation, sortings

You are given an array $$$a$$$ consisting of $$$n$$$ non-negative integers. It is guaranteed that $$$a$$$ is sorted from small to large.

For each operation, we generate a new array $$$b_i=a_{i+1}-a_{i}$$$ for $$$1 \le i < n$$$. Then we sort $$$b$$$ from small to large, replace $$$a$$$ with $$$b$$$, and decrease $$$n$$$ by $$$1$$$.

After performing $$$n-1$$$ operations, $$$n$$$ becomes $$$1$$$. You need to output the only integer in array $$$a$$$ (that is to say, you need to output $$$a_1$$$).

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

The first line of each test case contains one integer $$$n$$$ ($$$2\le n\le 10^5$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$0\le a_1\le \ldots\le a_n \le 5\cdot 10^5$$$) — the array $$$a$$$.

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

Output format:
For each test case, output the answer on a new line.

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

Note:
To simplify the notes, let $$$\operatorname{sort}(a)$$$ denote the array you get by sorting $$$a$$$ from small to large.

In the first test case, $$$a=[1,10,100]$$$ at first. After the first operation, $$$a=\operatorname{sort}([10-1,100-10])=[9,90]$$$. After the second operation, $$$a=\operatorname{sort}([90-9])=[81]$$$.

In the second test case, $$$a=[4,8,9,13]$$$ at first. After the first operation, $$$a=\operatorname{sort}([8-4,9-8,13-9])=[1,4,4]$$$. After the second operation, $$$a=\operatorname{sort}([4-1,4-4])=[0,3]$$$. After the last operation, $$$a=\operatorname{sort}([3-0])=[3]$$$.

Example input:
5
3
1 10 100
4
4 8 9 13
5
0 0 0 8 13
6
2 4 8 16 32 64
7
0 0 0 0 0 0 0

Example output:
81
3
1
2
0

Editorial:
Let's prove that the brute-force solution (considering zeros differently) can pass.
Define $$$S=\sum\limits_{i=1}^{n} a_i$$$ and it changes when an operation is performed.
After sorting the array $$$a$$$ and ignoring $$$0$$$ s, the fact
$$$$$$ \begin{aligned} n-1+a_n &\le S & (a_i \ge 1)\\ n-1 &\le S - a_n \end{aligned} $$$$$$
is always true.
And after performing one operation, $$$S = a_n-a_1\le a_n$$$.
So in each operation, you cost $$$O(n \log n)$$$ time to sort the new array and decrease $$$S$$$ by at least $$$n-1$$$.
After the first operation, $$$S$$$ is $$$O(a_n)$$$. The complexity is $$$O(A \log A)$$$, where $$$A=\max\{n,a_n\}$$$.
Fox and Number Game
Contest: Codeforces Round 228 (Div. 2)
Difficulty rating: 1000
Tags: greedy, math

Fox Ciel is playing a game with numbers now.

Ciel has n positive integers: x1, x2, ..., xn. She can do the following operation as many times as needed: select two different indexes i and j such that xi > xj hold, and then apply assignment xi = xi - xj. The goal is to make the sum of all numbers as small as possible.

Please help Ciel to find this minimal sum.

Input format:
The first line contains an integer n (2 ≤ n ≤ 100). Then the second line contains n integers: x1, x2, ..., xn (1 ≤ xi ≤ 100).

Output format:
Output a single integer — the required minimal sum.

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

Note:
In the first example the optimal way is to do the assignment: x2 = x2 - x1.

In the second example the optimal sequence of operations is: x3 = x3 - x2, x2 = x2 - x1.

Example input:
2
1 2

Example output:
2

Example input:
3
2 4 6

Example output:
6

Editorial:
Fox and Cross
Contest: Codeforces Round 228 (Div. 2)
Difficulty rating: 1100
Tags: greedy, implementation

Fox Ciel has a board with n rows and n columns. So, the board consists of n × n cells. Each cell contains either a symbol '.', or a symbol '#'.

A cross on the board is a connected set of exactly five cells of the board that looks like a cross. The picture below shows how it looks.

Ciel wants to draw several (may be zero) crosses on the board. Each cross must cover exactly five cells with symbols '#', and any cell with symbol '#' must belong to some cross. No two crosses can share a cell.

Please, tell Ciel if she can draw the crosses in the described way.

Input format:
The first line contains an integer n (3 ≤ n ≤ 100) — the size of the board.

Each of the next n lines describes one row of the board. The i-th line describes the i-th row of the board and consists of n characters. Each character is either a symbol '.', or a symbol '#'.

Output format:
Output a single line with "YES" if Ciel can draw the crosses in the described way. Otherwise output a single line with "NO".

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

Note:
In example 1, you can draw two crosses. The picture below shows what they look like.

In example 2, the board contains 16 cells with '#', but each cross contains 5. Since 16 is not a multiple of 5, so it's impossible to cover all.

Example input:
5
.#...
####.
.####
...#.
.....

Example output:
YES

Example input:
4
####
####
####
####

Example output:
NO

Editorial:
Mathematical Addition
Contest: Technocup 2022 - Elimination Round 2
Difficulty rating: 800
Tags: math

Ivan decided to prepare for the test on solving integer equations. He noticed that all tasks in the test have the following form:

- You are given two positive integers $$$u$$$ and $$$v$$$, find any pair of integers (not necessarily positive) $$$x$$$, $$$y$$$, such that: $$$$$$\frac{x}{u} + \frac{y}{v} = \frac{x + y}{u + v}.$$$$$$
- The solution $$$x = 0$$$, $$$y = 0$$$ is forbidden, so you should find any solution with $$$(x, y) \neq (0, 0)$$$.

Please help Ivan to solve some equations of this form.

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

The only line of each test case contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq 10^9$$$) — the parameters of the equation.

Output format:
For each test case print two integers $$$x$$$, $$$y$$$ — a possible solution to the equation. It should be satisfied that $$$-10^{18} \leq x, y \leq 10^{18}$$$ and $$$(x, y) \neq (0, 0)$$$.

We can show that an answer always exists. If there are multiple possible solutions you can print any.

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

Note:
In the first test case: $$$\frac{-1}{1} + \frac{1}{1} = 0 = \frac{-1 + 1}{1 + 1}$$$.

In the second test case: $$$\frac{-4}{2} + \frac{9}{3} = 1 = \frac{-4 + 9}{2 + 3}$$$.

In the third test case: $$$\frac{-18}{3} + \frac{50}{5} = 4 = \frac{-18 + 50}{3 + 5}$$$.

In the fourth test case: $$$\frac{-4}{6} + \frac{9}{9} = \frac{1}{3} = \frac{-4 + 9}{6 + 9}$$$.

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

Example output:
-1 1
-4 9
-18 50
-4 9

Editorial:
We have the equation: $$$\frac{x}{u} + \frac{y}{v} =\frac{x +y}{u+ v}.$$$
Let's multiply the left and right parts by $$$u*v*(u + v)$$$.
Received: $$$x * v * (u + v) + y * u * (u + v) = (x + y) * u * v$$$.
After opening the brackets and simplifying, we have: $$$x *v^2 + y*u^2 = 0$$$.
One of the solutions to this equation is $$$x = -u^2$$$, $$$y = v^2$$$
Two Arrays
Contest: Technocup 2022 - Elimination Round 2
Difficulty rating: 900
Tags: greedy, math, sortings

You are given two arrays of integers $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_n$$$.

Let's define a transformation of the array $$$a$$$:

1. Choose any non-negative integer $$$k$$$ such that $$$0 \le k \le n$$$.
2. Choose $$$k$$$ distinct array indices $$$1 \le i_1 < i_2 < \ldots < i_k \le n$$$.
3. Add $$$1$$$ to each of $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$, all other elements of array $$$a$$$ remain unchanged.
4. Permute the elements of array $$$a$$$ in any order.

Is it possible to perform some transformation of the array $$$a$$$ exactly once, so that the resulting array is equal to $$$b$$$?

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the size of arrays $$$a$$$ and $$$b$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-100 \le a_i \le 100$$$).

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$-100 \le b_i \le 100$$$).

Output format:
For each test case, print "YES" (without quotes) if it is possible to perform a transformation of the array $$$a$$$, so that the resulting array is equal to $$$b$$$. Print "NO" (without quotes) otherwise.

You can print each letter in any case (upper or lower).

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

Note:
In the first test case, we can make the following transformation:

- Choose $$$k = 2$$$.
- Choose $$$i_1 = 1$$$, $$$i_2 = 2$$$.
- Add $$$1$$$ to $$$a_1$$$ and $$$a_2$$$. The resulting array is $$$[0, 2, 0]$$$.
- Swap the elements on the second and third positions.

In the second test case there is no suitable transformation.

In the third test case we choose $$$k = 0$$$ and do not change the order of elements.

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

Example output:
YES
NO
YES

Editorial:
Let's sort the arrays first.
Let's check the two smallest elements in the arrays and investigate their behavior. First, obviously, if $$$a_1 + 1 < b_1$$$ (as nothing can be matched with $$$a_1$$$) or $$$a_1 > b_1$$$ (as nothing can be matched with $$$b_1$$$) the answer is No. Then, it's possible that $$$a_1 = b_1 = x$$$. In this case, we have to have at least one $$$x$$$ in the array $$$a$$$ at the end. Hence, we can leave $$$a_1$$$ untouched, as it already suits to $$$b_1$$$. It's also possible that $$$a_1 + 1 = b_1$$$. Here we have to increase $$$a_1$$$ by $$$1$$$. In both cases, the task is reduced to the smallest one.
Going to the exact solution from this logic, we just have to sort both arrays and check that for each $$$1 \leq i \leq n$$$ it's $$$a_i = b_i$$$ or $$$a_i + 1 = b_i$$$.
The complexity of the solution is $$$O(n log(n))$$$.
Eligible Segments
Contest: Technocup 2022 - Elimination Round 2
Difficulty rating: 3200
Tags: geometry

You are given $$$n$$$ distinct points $$$p_1, p_2, \ldots, p_n$$$ on the plane and a positive integer $$$R$$$.

Find the number of pairs of indices $$$(i, j)$$$ such that $$$1 \le i < j \le n$$$, and for every possible $$$k$$$ ($$$1 \le k \le n$$$) the distance from the point $$$p_k$$$ to the segment between points $$$p_i$$$ and $$$p_j$$$ is at most $$$R$$$.

Input format:
The first line contains two integers $$$n$$$, $$$R$$$ ($$$1 \le n \le 3000$$$, $$$1 \le R \le 10^5$$$) — the number of points and the maximum distance between a point and a segment.

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$, $$$y_i$$$ ($$$-10^5 \le x_i, y_i \le 10^5$$$) that define the $$$i$$$-th point $$$p_i=(x_i, y_i)$$$. All points are distinct.

It is guaranteed that the answer does not change if the parameter $$$R$$$ is changed by at most $$$10^{-2}$$$.

Output format:
Print the number of suitable pairs $$$(i, j)$$$.

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

Note:
In the first example, the only pair of points $$$(-3, 0)$$$, $$$(3, 0)$$$ is suitable. The distance to the segment between these points from the points $$$(0, 1)$$$ and $$$(0, -1)$$$ is equal to $$$1$$$, which is less than $$$R=2$$$.

In the second example, all possible pairs of points are eligible.

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

Example output:
1

Example input:
3 3
1 -1
-1 -1
0 1

Example output:
3

Editorial:
The distance from point $$$P$$$ to segment $$$[AB]$$$ is equal to the maximum of the distance from point $$$P$$$ to ray $$$[AB)$$$ and the distance from point $$$P$$$ to ray $$$[BA)$$$.
Let's fix a point $$$P_i$$$. Now we have to find all points $$$P_j$$$ such that distance from every point $$$P_k (1 \le k \le n)$$$ to the ray $$$[P_i, P_j)$$$ is less than $$$R$$$.
For every point $$$P_k$$$ let's build two tangents from point $$$P_i$$$ to the circle with the center in the point $$$P_k$$$ and radius $$$R$$$. These tangents form an angle $$$A_k$$$. The distance from the point $$$P_k (1 \le k \le n)$$$ to the ray $$$[P_i, P_j)$$$ is less than $$$R$$$ iff the ray $$$[P_i, P_j)$$$ lies inside the angle $$$A_k$$$. So we can build all these angles $$$A_k$$$ and intersect them, after that, we only have to check that the ray $$$[P_i, P_j)$$$ lies inside the intersection of all angles for all $$$1 \le j \le n$$$.
Time complexity: $$$O(n^2)$$$.