1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Consecutive Points Segment
Contest: Educational Codeforces Round 127 (Rated for Div. 2)
Difficulty rating: 1000
Tags: brute force, math, sortings

You are given $$$n$$$ points with integer coordinates on a coordinate axis $$$OX$$$. The coordinate of the $$$i$$$-th point is $$$x_i$$$. All points' coordinates are distinct and given in strictly increasing order.

For each point $$$i$$$, you can do the following operation no more than once: take this point and move it by $$$1$$$ to the left or to the right (i..e., you can change its coordinate $$$x_i$$$ to $$$x_i - 1$$$ or to $$$x_i + 1$$$). In other words, for each point, you choose (separately) its new coordinate. For the $$$i$$$-th point, it can be either $$$x_i - 1$$$, $$$x_i$$$ or $$$x_i + 1$$$.

Your task is to determine if you can move some points as described above in such a way that the new set of points forms a consecutive segment of integers, i. e. for some integer $$$l$$$ the coordinates of points should be equal to $$$l, l + 1, \ldots, l + n - 1$$$.

Note that the resulting points should have distinct coordinates.

You have to answer $$$t$$$ independent test cases.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of points in the set $$$x$$$.

The second line of the test case contains $$$n$$$ integers $$$x_1 < x_2 < \ldots < x_n$$$ ($$$1 \le x_i \le 10^6$$$), where $$$x_i$$$ is the coordinate of the $$$i$$$-th point.

It is guaranteed that the points are given in strictly increasing order (this also means that all coordinates are distinct). It is also guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Output format:
For each test case, print the answer — if the set of points from the test case can be moved to form a consecutive segment of integers, print YES, otherwise print NO.

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

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

Example output:
YES
YES
NO
YES
YES

Editorial:
We can see that the answer is YES if and only if there are no more than two gaps of length $$$1$$$ between the given points. If there is no gap, the answer is obviously YES. If there is only one gap of length $$$1$$$, we can just move the left (or the right) part of the set to this gap. When there are two gaps, we can move the part before the first gap to the right and the part after the second gap to the left. Of course, if there is a gap of length at least $$$3$$$ (or multiple gaps with the total length $$$3$$$), we can't move the points from the left and the right part to satisfy the middle gap.
Time complexity: $$$O(n)$$$.
A + B
Contest: Surprise Language Round 5
Difficulty rating: 1600
Tags: *special

You are given two integers A and B. Calculate their sum and output it without leading zeros.

Input format:
Two lines of input data contain integers A and B (1 ≤ A, B ≤ 105).

Output format:
Output A + B without leading zeros.

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

Note:
The code provided in the post about the round doesn't solve the task.

Example input:
12
3

Example output:
15

Example input:
100
5

Example output:
105

Editorial:
Binary notation
Contest: Surprise Language Round 5
Difficulty rating: 1800
Tags: *special

You are given a positive integer n. Output its binary notation.

Input format:
The only line of input data contains an integer n (1 ≤ n ≤ 106).

Output format:
Output the binary notation of n (without any leading zeros).

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

Note:
In the first example 5 = 1 * 22 + 0 * 21 + 1 * 20.

Example input:
5

Example output:
101

Example input:
13

Example output:
1101

Editorial:
Caesar Cipher
Contest: Surprise Language Round 5
Difficulty rating: 2200
Tags: *special

Caesar cipher is one of the simplest encryption techniques. To transform the original message into encrypted one using key k, one has to replace each letter with a letter which is k positions later in the alphabet (if this takes the position beyond Z, the rest of it is counted from the start of the alphabet). In a more formal way, if letters of the alphabet are enumerated starting with 0, the result of encryption for character x will be $$(x+k) \mod 26$$ (26 is the number of letters in the Latin alphabet).

You are given the original message and the encryption key k. Output the resulting cipher.

Input format:
The first line of input contains the original message — a sequence uppercase Latin letters («A»-«Z»). The length of the message is from 1 to 10, inclusive.

The second line contains an integer k (0 ≤ k ≤ 25).

Output format:
Output the result of encryption.

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

Example input:
CODEFORCES
5

Example output:
HTIJKTWHJX

Example input:
WIXYZILWYM
6

Example output:
CODEFORCES

Editorial:
Date Change
Contest: Surprise Language Round 5
Difficulty rating: 2000
Tags: *special

You are given a date in "DD.MM.YYYY" ("day.month.year") format and a number of days shift you have to add to this date. Output the resulting date.

Input format:
The first line of input contains the date in "DD.MM.YYYY" format: two digits for day (with leading zero if needed), dot, two digits for month (with leading zero if needed), dot, four digits for year. The notation is guaranteed to give a valid date between 1980 and 2020, inclusive.

The second line contains an integer shift ( - 1000 ≤ shift ≤ 1000).

Output format:
Output a date equal to the given one + shift days, in the same format "DD.MM.YYYY".

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

Note:
When manipulating the dates, take into account leap years; don't care about time zones/daylight saving time.

Example input:
10.02.2012
12

Example output:
22.02.2012

Example input:
01.02.2010
-40

Example output:
23.12.2009

Editorial:
Euclidean Distance
Contest: Surprise Language Round 5
Difficulty rating: 2100
Tags: *special

You are given a multiset of points on the plane with integer coordinates. Find the maximum distance between two points from this multiset.

Input format:
The first line of input contains the number of points n (2 ≤ n ≤ 50). Next, n pairs of lines follow, each describing a single point: the first line contains x-coordinate, the second one — the y-coordinate ( - 50 ≤ x, y ≤ 50). Some of the points can have identical coordinates.

Output format:
Output the maximum distance between two points from this multiset. The answer is considered to be correct if its absolute or relative error does not exceed 10 - 4.

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

Note:
In the first case the maximum distance is between points (0, 1) and (4, 5). In the second case two of the points are the same, so the maximum distance is between one of them and the third point.

Example input:
3
0
1
2
3
4
5

Example output:
5.656854249

Example input:
3
10
12
-5
8
10
12

Example output:
15.5241747

Editorial:
Colour the Flag
Contest: Codeforces LATOKEN Round 1 (Div. 1 + Div. 2)
Difficulty rating: 800
Tags: brute force, implementation

Today we will be playing a red and white colouring game (no, this is not the Russian Civil War; these are just the colours of the Canadian flag).

You are given an $$$n \times m$$$ grid of "R", "W", and "." characters. "R" is red, "W" is white and "." is blank. The neighbours of a cell are those that share an edge with it (those that only share a corner do not count).

Your job is to colour the blank cells red or white so that every red cell only has white neighbours (and no red ones) and every white cell only has red neighbours (and no white ones). You are not allowed to recolour already coloured cells.

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

In each test case, the first line will contain $$$n$$$ ($$$1 \le n \le 50$$$) and $$$m$$$ ($$$1 \le m \le 50$$$), the height and width of the grid respectively.

The next $$$n$$$ lines will contain the grid. Each character of the grid is either 'R', 'W', or '.'.

Output format:
For each test case, output "YES" if there is a valid grid or "NO" if there is not.

If there is, output the grid on the next $$$n$$$ lines. If there are multiple answers, print any.

In the output, the "YES"s and "NO"s are case-insensitive, meaning that outputs such as "yEs" and "nO" are valid. However, the grid is case-sensitive.

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

Note:
The answer for the first example case is given in the example output, and it can be proven that no grid exists that satisfies the requirements of the second example case. In the third example all cells are initially coloured, and the colouring is valid.

Example input:
3
4 6
.R....
......
......
.W....
4 4
.R.W
....
....
....
5 1
R
W
R
W
R

Example output:
YES
WRWRWR
RWRWRW
WRWRWR
RWRWRW
NO
YES
R
W
R
W
R

Editorial:
Observe that there are only two valid grids, one where the top left cell is "R" and one where it's "W". We can just test those two grids and see if they conform with the requirements.
Time complexity: $$$\mathcal{O}(nm)$$$
Tiling with Hexagons
Contest: Codeforces Round 133 (Div. 2)
Difficulty rating: 1200
Tags: implementation, math

Several ages ago Berland was a kingdom. The King of Berland adored math. That's why, when he first visited one of his many palaces, he first of all paid attention to the floor in one hall. The floor was tiled with hexagonal tiles.

The hall also turned out hexagonal in its shape. The King walked along the perimeter of the hall and concluded that each of the six sides has a, b, c, a, b and c adjacent tiles, correspondingly.

To better visualize the situation, look at the picture showing a similar hexagon for a = 2, b = 3 and c = 4.

According to the legend, as the King of Berland obtained the values a, b and c, he almost immediately calculated the total number of tiles on the hall floor. Can you do the same?

Input format:
The first line contains three integers: a, b and c (2 ≤ a, b, c ≤ 1000).

Output format:
Print a single number — the total number of tiles on the hall floor.

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

Example input:
2 3 4

Example output:
18

Editorial:
Forming Teams
Contest: Codeforces Round 133 (Div. 2)
Difficulty rating: 1700
Tags: dfs and similar, implementation

One day n students come to the stadium. They want to play football, and for that they need to split into teams, the teams must have an equal number of people.

We know that this group of people has archenemies. Each student has at most two archenemies. Besides, if student A is an archenemy to student B, then student B is an archenemy to student A.

The students want to split so as no two archenemies were in one team. If splitting in the required manner is impossible, some students will have to sit on the bench.

Determine the minimum number of students you will have to send to the bench in order to form the two teams in the described manner and begin the game at last.

Input format:
The first line contains two integers n and m (2 ≤ n ≤ 100, 1 ≤ m ≤ 100) — the number of students and the number of pairs of archenemies correspondingly.

Next m lines describe enmity between students. Each enmity is described as two numbers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — the indexes of the students who are enemies to each other. Each enmity occurs in the list exactly once. It is guaranteed that each student has no more than two archenemies.

You can consider the students indexed in some manner with distinct integers from 1 to n.

Output format:
Print a single integer — the minimum number of students you will have to send to the bench in order to start the game.

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

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

Example output:
1

Example input:
6 2
1 4
3 4

Example output:
0

Editorial:
Hiring Staff
Contest: Codeforces Round 133 (Div. 2)
Difficulty rating: 1800
Tags: greedy

A new Berland businessman Vitaly is going to open a household appliances' store. All he's got to do now is to hire the staff.

The store will work seven days a week, but not around the clock. Every day at least k people must work in the store.

Berland has a law that determines the order of working days and non-working days. Namely, each employee must work for exactly n consecutive days, then rest for exactly m days, then work for n more days and rest for m more, and so on. Vitaly doesn't want to break the law. Fortunately, there is a loophole: the law comes into force on the day when the employee is hired. For example, if an employee is hired on day x, then he should work on days [x, x + 1, ..., x + n - 1], [x + m + n, x + m + n + 1, ..., x + m + 2n - 1], and so on. Day x can be chosen arbitrarily by Vitaly.

There is one more thing: the key to the store. Berland law prohibits making copies of keys, so there is only one key. Vitaly is planning to entrust the key to the store employees. At the same time on each day the key must be with an employee who works that day — otherwise on this day no one can get inside the store. During the day the key holder can give the key to another employee, if he also works that day. The key will handed to the first hired employee at his first working day.

Each employee has to be paid salary. Therefore, Vitaly wants to hire as few employees as possible provided that the store can operate normally on each day from 1 to infinity. In other words, on each day with index from 1 to infinity, the store must have at least k working employees, and one of the working employees should have the key to the store.

Help Vitaly and determine the minimum required number of employees, as well as days on which they should be hired.

Input format:
The first line contains three integers n, m and k (1 ≤ m ≤ n ≤ 1000, n ≠ 1, 1 ≤ k ≤ 1000).

Output format:
In the first line print a single integer z — the minimum required number of employees.

In the second line print z positive integers, separated by spaces: the i-th integer ai (1 ≤ ai ≤ 104) should represent the number of the day, on which Vitaly should hire the i-th employee.

If there are multiple answers, print any of them.

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

Example input:
4 3 2

Example output:
4
1 1 4 5

Example input:
3 3 1

Example output:
3
1 3 5

Editorial:
Spider's Web
Contest: Codeforces Round 133 (Div. 2)
Difficulty rating: 1700
Tags: binary search, sortings, two pointers

Paw the Spider is making a web. Web-making is a real art, Paw has been learning to do it his whole life. Let's consider the structure of the web.

There are n main threads going from the center of the web. All main threads are located in one plane and divide it into n equal infinite sectors. The sectors are indexed from 1 to n in the clockwise direction. Sectors i and i + 1 are adjacent for every i, 1 ≤ i < n. In addition, sectors 1 and n are also adjacent.

Some sectors have bridge threads. Each bridge connects the two main threads that make up this sector. The points at which the bridge is attached to the main threads will be called attachment points. Both attachment points of a bridge are at the same distance from the center of the web. At each attachment point exactly one bridge is attached. The bridges are adjacent if they are in the same sector, and there are no other bridges between them.

A cell of the web is a trapezoid, which is located in one of the sectors and is bounded by two main threads and two adjacent bridges. You can see that the sides of the cell may have the attachment points of bridges from adjacent sectors. If the number of attachment points on one side of the cell is not equal to the number of attachment points on the other side, it creates an imbalance of pulling forces on this cell and this may eventually destroy the entire web. We'll call such a cell unstable. The perfect web does not contain unstable cells.

Unstable cells are marked red in the figure. Stable cells are marked green.

Paw the Spider isn't a skillful webmaker yet, he is only learning to make perfect webs. Help Paw to determine the number of unstable cells in the web he has just spun.

Input format:
The first line contains integer n (3 ≤ n ≤ 1000) — the number of main threads.

The i-th of following n lines describe the bridges located in the i-th sector: first it contains integer ki (1 ≤ ki ≤ 105) equal to the number of bridges in the given sector. Then follow ki different integers pij (1 ≤ pij ≤ 105; 1 ≤ j ≤ ki). Number pij equals the distance from the attachment points of the j-th bridge of the i-th sector to the center of the web.

It is guaranteed that any two bridges between adjacent sectors are attached at a different distance from the center of the web. It is guaranteed that the total number of the bridges doesn't exceed 105.

Output format:
Print a single integer — the number of unstable cells in Paw the Spider's web.

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

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

Example output:
6

Editorial:
Martian Luck
Contest: Codeforces Round 133 (Div. 2)
Difficulty rating: 2000
Tags: math, number theory

You know that the Martians use a number system with base k. Digit b (0 ≤ b < k) is considered lucky, as the first contact between the Martians and the Earthlings occurred in year b (by Martian chronology).

A digital root d(x) of number x is a number that consists of a single digit, resulting after cascading summing of all digits of number x. Word "cascading" means that if the first summing gives us a number that consists of several digits, then we sum up all digits again, and again, until we get a one digit number.

For example, d(35047) = d((3 + 5 + 0 + 4)7) = d(157) = d((1 + 5)7) = d(67) = 67. In this sample the calculations are performed in the 7-base notation.

If a number's digital root equals b, the Martians also call this number lucky.

You have string s, which consists of n digits in the k-base notation system. Your task is to find, how many distinct substrings of the given string are lucky numbers. Leading zeroes are permitted in the numbers.

Note that substring s[i... j] of the string s = a1a2... an (1 ≤ i ≤ j ≤ n) is the string aiai + 1... aj. Two substrings s[i1... j1] and s[i2... j2] of the string s are different if either i1 ≠ i2 or j1 ≠ j2.

Input format:
The first line contains three integers k, b and n (2 ≤ k ≤ 109, 0 ≤ b < k, 1 ≤ n ≤ 105).

The second line contains string s as a sequence of n integers, representing digits in the k-base notation: the i-th integer equals ai (0 ≤ ai < k) — the i-th digit of string s. The numbers in the lines are space-separated.

Output format:
Print a single integer — the number of substrings that are lucky numbers.

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

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

Note:
In the first sample the following substrings have the sought digital root: s[1... 2] = "3 2", s[1... 3] = "3 2 0", s[3... 4] = "0 5", s[4... 4] = "5" and s[2... 6] = "2 0 5 6 1".

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

Example output:
5

Example input:
7 6 4
3 5 0 4

Example output:
1

Editorial:
Special Characters
Contest: Educational Codeforces Round 163 (Rated for Div. 2)
Difficulty rating: 800
Tags: brute force, constructive algorithms

You are given an integer $$$n$$$.

Your task is to build a string of uppercase Latin letters. There must be exactly $$$n$$$ special characters in this string. Let's call a character special if it is equal to exactly one of its neighbors.

For example, there are $$$6$$$ special characters in the AAABAACC string (at positions: $$$1$$$, $$$3$$$, $$$5$$$, $$$6$$$, $$$7$$$ and $$$8$$$).

Print any suitable string or report that there is no such string.

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

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

Output format:
For each test case, print the answer as follows:

- if there is no suitable string, print one line containing the string NO;
- otherwise, print two lines. The first line should contain the string YES; on the second line print a string of length at most $$$200$$$ — the answer itself (it can be shown that if some answers exist, then there is an answer of length at most $$$200$$$). If there are several solutions, print any of them.

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

Example input:
3
6
1
2

Example output:
YES
AAABAACC
NO
YES
MM

Editorial:
Let's look at the blocks of consecutive equal characters (such that it cannot be extended to the left or to the right):
• if its length is $$$1$$$, then this block has $$$0$$$ special characters;
• if its length is $$$2$$$, then this block has $$$2$$$ special characters;
• if its length is at least $$$3$$$, then this block has $$$2$$$ special characters (only the leftmost and the rightmost elements);
We can see that there is no way to obtain an odd number of special characters. So the answer is NO for all odd values of $$$n$$$. And we can easily build the string for all even values of $$$n$$$. The answer for an even $$$n$$$ may look like this: AABBAABB... with $$$\frac{n}{2}$$$ blocks of length $$$2$$$ alternating between two different letters.