1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Infinite Fence
Contest: Educational Codeforces Round 77 (Rated for Div. 2)
Difficulty rating: 1700
Tags: greedy, math, number theory

You are a rebel leader and you are planning to start a revolution in your country. But the evil Government found out about your plans and set your punishment in the form of correctional labor.

You must paint a fence which consists of $$$10^{100}$$$ planks in two colors in the following way (suppose planks are numbered from left to right from $$$0$$$):

- if the index of the plank is divisible by $$$r$$$ (such planks have indices $$$0$$$, $$$r$$$, $$$2r$$$ and so on) then you must paint it red;
- if the index of the plank is divisible by $$$b$$$ (such planks have indices $$$0$$$, $$$b$$$, $$$2b$$$ and so on) then you must paint it blue;
- if the index is divisible both by $$$r$$$ and $$$b$$$ you can choose the color to paint the plank;
- otherwise, you don't need to paint the plank at all (and it is forbidden to spent paint on it).

Furthermore, the Government added one additional restriction to make your punishment worse. Let's list all painted planks of the fence in ascending order: if there are $$$k$$$ consecutive planks with the same color in this list, then the Government will state that you failed the labor and execute you immediately. If you don't paint the fence according to the four aforementioned conditions, you will also be executed.

The question is: will you be able to accomplish the labor (the time is not important) or the execution is unavoidable and you need to escape at all costs.

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

The next $$$T$$$ lines contain descriptions of test cases — one per line. Each test case contains three integers $$$r$$$, $$$b$$$, $$$k$$$ ($$$1 \le r, b \le 10^9$$$, $$$2 \le k \le 10^9$$$) — the corresponding coefficients.

Output format:
Print $$$T$$$ words — one per line. For each test case print REBEL (case insensitive) if the execution is unavoidable or OBEY (case insensitive) otherwise.

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

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

Example output:
OBEY
REBEL
OBEY
OBEY

Editorial:
At first, suppose that $$$r \le b$$$ (if not — swap them). Let's look at the case, where $$$gcd(r, b) = 1$$$. We can be sure that there will be a situation where the $$$pos$$$-th plank is painted in blue and $$$pos + 1$$$ plank is painted in red. It's true because it's equivalent to the solution of equation $$$r \cdot x - b \cdot y = 1$$$.
And all we need to check that interval $$$(pos, pos + b)$$$ contains less than $$$k$$$ red planks. Or, in formulas, $$$(k - 1) \cdot r + 1 \ge b$$$.
The situation with $$$gcd(r, b) > 1$$$ is almost the same if we look only at positions, which are divisible by $$$gcd(r, b)$$$ — in other words we can just divide $$$r$$$ on $$$gcd$$$ and $$$b$$$ on $$$gcd$$$ and check the same condition.
Sereja and Mugs
Contest: Codeforces Round 243 (Div. 2)
Difficulty rating: 800
Tags: implementation

Sereja showed an interesting game to his friends. The game goes like that. Initially, there is a table with an empty cup and n water mugs on it. Then all players take turns to move. During a move, a player takes a non-empty mug of water and pours all water from it into the cup. If the cup overfills, then we assume that this player lost.

As soon as Sereja's friends heard of the game, they wanted to play it. Sereja, on the other hand, wanted to find out whether his friends can play the game in such a way that there are no losers. You are given the volumes of all mugs and the cup. Also, you know that Sereja has (n - 1) friends. Determine if Sereja's friends can play the game so that nobody loses.

Input format:
The first line contains integers n and s (2 ≤ n ≤ 100; 1 ≤ s ≤ 1000) — the number of mugs and the volume of the cup. The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 10). Number ai means the volume of the i-th mug.

Output format:
In a single line, print "YES" (without the quotes) if his friends can play in the described manner, and "NO" (without the quotes) otherwise.

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

Example input:
3 4
1 1 1

Example output:
YES

Example input:
3 4
3 1 3

Example output:
YES

Editorial:
Sereja and Mirroring
Contest: Codeforces Round 243 (Div. 2)
Difficulty rating: 1300
Tags: implementation

Let's assume that we are given a matrix b of size x × y, let's determine the operation of mirroring matrix b. The mirroring of matrix b is a 2x × y matrix c which has the following properties:

- the upper half of matrix c (rows with numbers from 1 to x) exactly matches b;
- the lower half of matrix c (rows with numbers from x + 1 to 2x) is symmetric to the upper one; the symmetry line is the line that separates two halves (the line that goes in the middle, between rows x and x + 1).

Sereja has an n × m matrix a. He wants to find such matrix b, that it can be transformed into matrix a, if we'll perform on it several (possibly zero) mirrorings. What minimum number of rows can such matrix contain?

Input format:
The first line contains two integers, n and m (1 ≤ n, m ≤ 100). Each of the next n lines contains m integers — the elements of matrix a. The i-th line contains integers ai1, ai2, ..., aim (0 ≤ aij ≤ 1) — the i-th row of the matrix a.

Output format:
In the single line, print the answer to the problem — the minimum number of rows of matrix b.

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

Note:
In the first test sample the answer is a 2 × 3 matrix b:

If we perform a mirroring operation with this matrix, we get the matrix a that is given in the input:

Example input:
4 3
0 0 1
1 1 0
1 1 0
0 0 1

Example output:
2

Example input:
3 3
0 0 0
0 0 0
0 0 0

Example output:
3

Editorial:
Longest Palindrome
Contest: Codeforces Round 620 (Div. 2)
Difficulty rating: 1100
Tags: brute force, constructive algorithms, greedy, implementation, strings

Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse. For example, strings "pop", "noon", "x", and "kkkkkk" are palindromes, while strings "moon", "tv", and "abab" are not. An empty string is also a palindrome.

Gildong loves this concept so much, so he wants to play with it. He has $$$n$$$ distinct strings of equal length $$$m$$$. He wants to discard some of the strings (possibly none or all) and reorder the remaining strings so that the concatenation becomes a palindrome. He also wants the palindrome to be as long as possible. Please help him find one.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 100$$$, $$$1 \le m \le 50$$$) — the number of strings and the length of each string.

Next $$$n$$$ lines contain a string of length $$$m$$$ each, consisting of lowercase Latin letters only. All strings are distinct.

Output format:
In the first line, print the length of the longest palindrome string you made.

In the second line, print that palindrome. If there are multiple answers, print any one of them. If the palindrome is empty, print an empty line or don't print this line at all.

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

Note:
In the first example, "battab" is also a valid answer.

In the second example, there can be 4 different valid answers including the sample output. We are not going to provide any hints for what the others are.

In the third example, the empty string is the only valid palindrome string.

Example input:
3 3
tab
one
bat

Example output:
6
tabbat

Example input:
4 2
oo
ox
xo
xx

Example output:
6
oxxxxo

Editorial:
Let's define $$$rev(S)$$$ as the reversed string of a string $$$S$$$. There are two cases when we choose $$$K$$$ strings to make a palindrome string $$$S_1 + S_2 + \cdots + S_K$$$:
• If $$$K$$$ is even, for every integer $$$X$$$ ($$$1 \le X \le \cfrac{K}{2}$$$), $$$S_X = rev(S_{K-X+1})$$$.
• if $$$K$$$ is odd, $$$S_{\frac{K+1}{2}}$$$ must be palindrome. Also for every integer $$$X$$$ ($$$1 \le X \le \cfrac{K-1}{2}$$$), $$$S_X = rev(S_{K-X+1})$$$.
In either case we want to find as many pairs of strings as possible such that one is the reverse of the other. It is also clear that if $$$T$$$ is a palindrome string then $$$rev(T) = T$$$. We cannot make a pair of T and rev(T) because all strings in the input are distinct.
Therefore, for each string we need to find if there is another string that is its reverse. If there exists one, put them on the left / right end respectively. If there are one or more strings that are palindrome themselves, pick any one of them and put it in the middle.
Time complexity: $$$O(n^2m)$$$ if we implement it naively. $$$O(nmlogn)$$$ is possible if we use a data structure that provides $$$O(logn)$$$ search such as std::set in C++.
Chain Reaction
Contest: Codeforces Round 336 (Div. 1)
Difficulty rating: 1600
Tags: binary search, dp

There are n beacons located at distinct positions on a number line. The i-th beacon has position ai and power level bi. When the i-th beacon is activated, it destroys all beacons to its left (direction of decreasing coordinates) within distance bi inclusive. The beacon itself is not destroyed however. Saitama will activate the beacons one at a time from right to left. If a beacon is destroyed, it cannot be activated.

Saitama wants Genos to add a beacon strictly to the right of all the existing beacons, with any position and any power level, such that the least possible number of beacons are destroyed. Note that Genos's placement of the beacon means it will be the first beacon activated. Help Genos by finding the minimum number of beacons that could be destroyed.

Input format:
The first line of input contains a single integer n (1 ≤ n ≤ 100 000) — the initial number of beacons.

The i-th of next n lines contains two integers ai and bi (0 ≤ ai ≤ 1 000 000, 1 ≤ bi ≤ 1 000 000) — the position and power level of the i-th beacon respectively. No two beacons will have the same position, so ai ≠ aj if i ≠ j.

Output format:
Print a single integer — the minimum number of beacons that could be destroyed if exactly one beacon is added.

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

Note:
For the first sample case, the minimum number of beacons destroyed is 1. One way to achieve this is to place a beacon at position 9 with power level 2.

For the second sample case, the minimum number of beacons destroyed is 3. One way to achieve this is to place a beacon at position 1337 with power level 42.

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

Example output:
1

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

Example output:
3

Editorial:
We can solve this problem using dynamic programming. Let dp[x] be the minimum number of objects destroyed in the range [0, x] given that position x is unaffected by an explosion. We can compute dp[x] using the following recurrence:
Now, if we can place an object to the right of all objects with any power level, we can destroy some suffix of the (sorted list of) objects. The answer is thus the minimum number of objects destroyed given that we destroy some suffix of the objects first. This can be easily evaluated as
Time Complexity - O(max(ai)), Memory Complexity - O(max(ai))
Zuma
Contest: Codeforces Round 336 (Div. 1)
Difficulty rating: 1900
Tags: dp

Genos recently installed the game Zuma on his phone. In Zuma there exists a line of n gemstones, the i-th of which has color ci. The goal of the game is to destroy all the gemstones in the line as quickly as possible.

In one second, Genos is able to choose exactly one continuous substring of colored gemstones that is a palindrome and remove it from the line. After the substring is removed, the remaining gemstones shift to form a solid line again. What is the minimum number of seconds needed to destroy the entire line?

Let us remind, that the string (or substring) is called palindrome, if it reads same backwards or forward. In our case this means the color of the first gemstone is equal to the color of the last one, the color of the second gemstone is equal to the color of the next to last and so on.

Input format:
The first line of input contains a single integer n (1 ≤ n ≤ 500) — the number of gemstones.

The second line contains n space-separated integers, the i-th of which is ci (1 ≤ ci ≤ n) — the color of the i-th gemstone in a line.

Output format:
Print a single integer — the minimum number of seconds needed to destroy the entire line.

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

Note:
In the first sample, Genos can destroy the entire line in one second.

In the second sample, Genos can only destroy one gemstone at a time, so destroying three gemstones takes three seconds.

In the third sample, to achieve the optimal time of two seconds, destroy palindrome 4 4 first and then destroy palindrome 1 2 3 2 1.

Example input:
3
1 2 1

Example output:
1

Example input:
3
1 2 3

Example output:
3

Editorial:
We use dp on contiguous ranges to calculate the answer. Let D[i][j] denote the number of seconds it takes to collapse some range [i, j]. Let us work out a transition for this definition. Consider the left-most marble. This marble will either be destroyed individually or as part of a non-singular range. In the first case, we destroy the left-most marble and reduce to the subproblem [i + 1, j]. In the second case, notice that the left-most marble will match up with some marble to its right. We can iterate through every marble with the same color as the left-most (let k be the index of this matching marble) and reduce to two subproblems [i + 1, k - 1] and [k + 1, j]. We must also make a special case for when the first two elements in a range are equal and consider the subproblem [i + 2, j].
Here is a formalization of the dp:
Why is this dp correct? Notice that the recursive version of our dp will come across the optimal solution in its search. Moreover, every path in the recursive search tree corresponds to some valid sequence of deletions. Since our dp only searches across valid deletions and will at some point come across the optimal sequence of deletions, the answer it produces will be optimal.
Time Complexity - O(n3), Space Complexity - O(n2)
Timofey and a tree
Contest: Codeforces Round 395 (Div. 1)
Difficulty rating: 1600
Tags: dfs and similar, dp, dsu, graphs, implementation, trees

Each New Year Timofey and his friends cut down a tree of n vertices and bring it home. After that they paint all the n its vertices, so that the i-th vertex gets color ci.

Now it's time for Timofey birthday, and his mother asked him to remove the tree. Timofey removes the tree in the following way: he takes some vertex in hands, while all the other vertices move down so that the tree becomes rooted at the chosen vertex. After that Timofey brings the tree to a trash can.

Timofey doesn't like it when many colors are mixing together. A subtree annoys him if there are vertices of different color in it. Timofey wants to find a vertex which he should take in hands so that there are no subtrees that annoy him. He doesn't consider the whole tree as a subtree since he can't see the color of the root vertex.

A subtree of some vertex is a subgraph containing that vertex and all its descendants.

Your task is to determine if there is a vertex, taking which in hands Timofey wouldn't be annoyed.

Input format:
The first line contains single integer n (2 ≤ n ≤ 105) — the number of vertices in the tree.

Each of the next n - 1 lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v), denoting there is an edge between vertices u and v. It is guaranteed that the given graph is a tree.

The next line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 105), denoting the colors of the vertices.

Output format:
Print "NO" in a single line, if Timofey can't take the tree in such a way that it doesn't annoy him.

Otherwise print "YES" in the first line. In the second line print the index of the vertex which Timofey should take in hands. If there are multiple answers, print any of them.

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

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

Example output:
YES
2

Example input:
3
1 2
2 3
1 2 3

Example output:
YES
2

Editorial:
Take any edge which vertices are colored in different colors. If such edge doesn't exist you can print any vertex, because all the tree is colored in the same color. Otherwise, try to make a root from each of these vertices. Check if is possible with simple dfs. If it succeedes for one of them, print "YES" and this vertex. If it fails for both vertices, the answer is "NO". Indeed, if both of them cannot be the root, they lay in the same subtree and they are colored differently. So the condition isn't fulfilled. The asymptotics of this solution is O(n + m).
Author's solution: http://pastebin.com/M58NY7C1
Timofey and rectangles
Contest: Codeforces Round 395 (Div. 1)
Difficulty rating: 2100
Tags: constructive algorithms, geometry

One of Timofey's birthday presents is a colourbook in a shape of an infinite plane. On the plane n rectangles with sides parallel to coordinate axes are situated. All sides of the rectangles have odd length. Rectangles cannot intersect, but they can touch each other.

Help Timofey to color his rectangles in 4 different colors in such a way that every two rectangles touching each other by side would have different color, or determine that it is impossible.

Two rectangles intersect if their intersection has positive area. Two rectangles touch by sides if there is a pair of sides such that their intersection has non-zero length

The picture corresponds to the first example

Input format:
The first line contains single integer n (1 ≤ n ≤ 5·105) — the number of rectangles.

n lines follow. The i-th of these lines contains four integers x1, y1, x2 and y2 ( - 109 ≤ x1 < x2 ≤ 109,  - 109 ≤ y1 < y2 ≤ 109), that means that points (x1, y1) and (x2, y2) are the coordinates of two opposite corners of the i-th rectangle.

It is guaranteed, that all sides of the rectangles have odd lengths and rectangles don't intersect each other.

Output format:
Print "NO" in the only line if it is impossible to color the rectangles in 4 different colors in such a way that every two rectangles touching each other by side would have different color.

Otherwise, print "YES" in the first line. Then print n lines, in the i-th of them print single integer ci (1 ≤ ci ≤ 4) — the color of i-th rectangle.

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

Example input:
8
0 0 5 3
2 -1 5 0
-3 -4 2 -1
-1 -1 2 0
-3 0 0 5
5 2 10 3
7 -3 10 2
4 -2 7 -1

Example output:
YES
1
2
2
3
2
2
4
1

Editorial:
Let's consider vertical touchings graph, where vertex is rectangle. For each vertex we keep x coordinate of bottom-right angle. While moving to next rectangle it changes by odd number. In this graph doesn't exist cycle of odd length (sum of odd number of odd numbers can't be zero). Similar to this you can see about horizontal touchings. Let's consider two touching rectagles. Sides lengths are odd, so $$2 * ( x \mod 2 ) + ( y \mod 2)$$ give different colors for adjacent rectangles, where x is x coordinate of bottom-left angle and y is y coordinate of bottom-left angle.
Author's solution: http://pastebin.com/ntEV9bGt
Timofey and remoduling
Contest: Codeforces Round 395 (Div. 1)
Difficulty rating: 2600
Tags: brute force, implementation, math, number theory

Little Timofey likes integers a lot. Unfortunately, he is very young and can't work with very big integers, so he does all the operations modulo his favorite prime m. Also, Timofey likes to look for arithmetical progressions everywhere.

One of his birthday presents was a sequence of distinct integers a1, a2, ..., an. Timofey wants to know whether he can rearrange the elements of the sequence so that is will be an arithmetical progression modulo m, or not.

Arithmetical progression modulo m of length n with first element x and difference d is sequence of integers x, x + d, x + 2d, ..., x + (n - 1)·d, each taken modulo m.

Input format:
The first line contains two integers m and n (2 ≤ m ≤ 109 + 7, 1 ≤ n ≤ 105, m is prime) — Timofey's favorite prime module and the length of the sequence.

The second line contains n distinct integers a1, a2, ..., an (0 ≤ ai < m) — the elements of the sequence.

Output format:
Print -1 if it is not possible to rearrange the elements of the sequence so that is will be an arithmetical progression modulo m.

Otherwise, print two integers — the first element of the obtained progression x (0 ≤ x < m) and its difference d (0 ≤ d < m).

If there are multiple answers, print any of them.

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

Example input:
17 5
0 2 4 13 15

Example output:
13 2

Example input:
17 5
0 2 4 13 14

Example output:
-1

Editorial:
First, let's think about the case when 2n < m.
In this editorial we say that an outcoming sequence is s, s + d, s + 2d, ..., s + (n - 1)d
Assume x is the difference of some two elements a and b of A ($$x = b - a \mod m$$). Let's say that a was on i-th place in the sequence and b was on i + k-th place. Then $$x = k \cdot d \mod m$$.
On the other hand, we have that n is less then $$\frac{m}{2}$$, so x must be difference of exactly n - k + 1 pairs of elements of A. We can count this value in $$O(n \log n)$$ time using binary search or in O(n) time using a hashtable. Then we know the value of k. After that we calculate the value $$x \div k \mod m$$ (m is prime so we can use Fermat's little theorem) and then we know the difference of the sequence. Then we just take any element y of A and look on values y, y + d, y + 2d, ..., and also on y - d, y - 2d, .... If we can get all of the numbers in A in this way, then we know the first element of the sequence. Otherwise, the answer is NO.
If 2n > m, we just solve the problem for the complement of A in $$z_{m}$$, and then add to the first element value (m - n)d. If we had a correct sequence in A, then we must have a correct sequence in its complement with the same difference (as long as m is coprime with the difference, the complement is just set of numbers s + nd, s + (n + 1)d, ..., s + (m - 1)d).
Author's solution: http://pastebin.com/jTdcUpFM