1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Ohana Cleans Up
Contest: Codeforces Round 309 (Div. 2)
Difficulty rating: 1200
Tags: brute force, greedy, strings

Ohana Matsumae is trying to clean a room, which is divided up into an n by n grid of squares. Each square is initially either clean or dirty. Ohana can sweep her broom over columns of the grid. Her broom is very strange: if she sweeps over a clean square, it will become dirty, and if she sweeps over a dirty square, it will become clean. She wants to sweep some columns of the room to maximize the number of rows that are completely clean. It is not allowed to sweep over the part of the column, Ohana can only sweep the whole column.

Return the maximum number of rows that she can make completely clean.

Input format:
The first line of input will be a single integer n (1 ≤ n ≤ 100).

The next n lines will describe the state of the room. The i-th line will contain a binary string with n characters denoting the state of the i-th row of the room. The j-th character on this line is '1' if the j-th square in the i-th row is clean, and '0' if it is dirty.

Output format:
The output should be a single line containing an integer equal to a maximum possible number of rows that are completely clean.

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

Note:
In the first sample, Ohana can sweep the 1st and 3rd columns. This will make the 1st and 4th row be completely clean.

In the second sample, everything is already clean, so Ohana doesn't need to do anything.

Example input:
4
0101
1000
1111
0101

Example output:
2

Example input:
3
111
111
111

Example output:
3

Editorial:
For each row, there is only one set of columns we can toggle so it becomes all on. So, there are only n configurations of toggling columns to look at. Checking a configuration takes O(n2) time to count the number of rows that are all on. There are n configurations in all, so this takes O(n3) time total.
Login Verification
Contest: VK Cup 2018 - Квалификация 1
Difficulty rating: 1200
Tags: *special, strings

When registering in a social network, users are allowed to create their own convenient login to make it easier to share contacts, print it on business cards, etc.

Login is an arbitrary sequence of lower and uppercase latin letters, digits and underline symbols («_»). However, in order to decrease the number of frauds and user-inattention related issues, it is prohibited to register a login if it is similar with an already existing login. More precisely, two logins s and t are considered similar if we can transform s to t via a sequence of operations of the following types:

- transform lowercase letters to uppercase and vice versa;
- change letter «O» (uppercase latin letter) to digit «0» and vice versa;
- change digit «1» (one) to any letter among «l» (lowercase latin «L»), «I» (uppercase latin «i») and vice versa, or change one of these letters to other.

For example, logins «Codeforces» and «codef0rces» as well as «OO0OOO00O0OOO0O00OOO0OO_lol» and «OO0OOO0O00OOO0O00OO0OOO_1oI» are considered similar whereas «Codeforces» and «Code_forces» are not.

You're given a list of existing logins with no two similar amonst and a newly created user login. Check whether this new login is similar with any of the existing ones.

Input format:
The first line contains a non-empty string s consisting of lower and uppercase latin letters, digits and underline symbols («_») with length not exceeding 50  — the login itself.

The second line contains a single integer n (1 ≤ n ≤ 1 000) — the number of existing logins.

The next n lines describe the existing logins, following the same constraints as the user login (refer to the first line of the input). It's guaranteed that no two existing logins are similar.

Output format:
Print «Yes» (without quotes), if user can register via this login, i.e. none of the existing logins is similar with it.

Otherwise print «No» (without quotes).

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

Note:
In the second sample case the user wants to create a login consisting of three zeros. It's impossible due to collision with the third among the existing.

In the third sample case the new login is similar with the second one.

Example input:
1_wat
2
2_wat
wat_1

Example output:
Yes

Example input:
000
3
00
ooA
oOo

Example output:
No

Editorial:
At first let's format all existing logins. For each login we will do the following:
1. change all uppercase letters on lowercase letters;
2. change all letters o on the digit 0;
3. change all letters i and l on the digit 1.
If new login is equal to some of the formatted login, the user can not register new login. In the other case, he will be able to do this.
Two Regular Polygons
Contest: Educational Codeforces Round 83 (Rated for Div. 2)
Difficulty rating: 800
Tags: geometry, greedy, math, number theory

You are given two integers $$$n$$$ and $$$m$$$ ($$$m < n$$$). Consider a convex regular polygon of $$$n$$$ vertices. Recall that a regular polygon is a polygon that is equiangular (all angles are equal in measure) and equilateral (all sides have the same length).

Examples of convex regular polygons

Your task is to say if it is possible to build another convex regular polygon with $$$m$$$ vertices such that its center coincides with the center of the initial polygon and each of its vertices is some vertex of the initial polygon.

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

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

The next $$$t$$$ lines describe test cases. Each test case is given as two space-separated integers $$$n$$$ and $$$m$$$ ($$$3 \le m < n \le 100$$$) — the number of vertices in the initial polygon and the number of vertices in the polygon you want to build.

Output format:
For each test case, print the answer — "YES" (without quotes), if it is possible to build another convex regular polygon with $$$m$$$ vertices such that its center coincides with the center of the initial polygon and each of its vertices is some vertex of the initial polygon and "NO" otherwise.

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

Note:
The first test case of the example

It can be shown that the answer for the second test case of the example is "NO".

Example input:
2
6 3
7 3

Example output:
YES
NO

Editorial:
The answer is "YES" if and only if $$$n$$$ is divisible by $$$m$$$ because if you number all vertices of the initial polygon from $$$0$$$ to $$$n-1$$$ clockwise then you need to take every vertex divisible by $$$\frac{n}{m}$$$ (and this number obviously should be integer) and there is no other way to construct the other polygon.
Bogosort
Contest: Educational Codeforces Round 83 (Rated for Div. 2)
Difficulty rating: 1000
Tags: constructive algorithms, sortings

You are given an array $$$a_1, a_2, \dots , a_n$$$. Array is good if for each pair of indexes $$$i < j$$$ the condition $$$j - a_j \ne i - a_i$$$ holds. Can you shuffle this array so that it becomes good? To shuffle an array means to reorder its elements arbitrarily (leaving the initial order is also an option).

For example, if $$$a = [1, 1, 3, 5]$$$, then shuffled arrays $$$[1, 3, 5, 1]$$$, $$$[3, 5, 1, 1]$$$ and $$$[5, 3, 1, 1]$$$ are good, but shuffled arrays $$$[3, 1, 5, 1]$$$, $$$[1, 1, 3, 5]$$$ and $$$[1, 1, 5, 3]$$$ aren't.

It's guaranteed that it's always possible to shuffle an array to meet this condition.

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

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of array $$$a$$$.

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

Output format:
For each test case print the shuffled version of the array $$$a$$$ which is good.

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

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

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

Editorial:
Let's sort array $$$a$$$ in non-ascending order ($$$a_1 \ge a_2 \ge \dots \ge a_n$$$).
In this case for each pair of indexes $$$i < j$$$ the condition $$$j - a_j \ne i - a_i$$$ holds.
Adding Powers
Contest: Educational Codeforces Round 83 (Rated for Div. 2)
Difficulty rating: 1400
Tags: bitmasks, greedy, implementation, math, number theory, ternary search

Suppose you are performing the following algorithm. There is an array $$$v_1, v_2, \dots, v_n$$$ filled with zeroes at start. The following operation is applied to the array several times — at $$$i$$$-th step ($$$0$$$-indexed) you can:

- either choose position $$$pos$$$ ($$$1 \le pos \le n$$$) and increase $$$v_{pos}$$$ by $$$k^i$$$;
- or not choose any position and skip this step.

You can choose how the algorithm would behave on each step and when to stop it. The question is: can you make array $$$v$$$ equal to the given array $$$a$$$ ($$$v_j = a_j$$$ for each $$$j$$$) after some step?

Input format:
The first line contains one integer $$$T$$$ ($$$1 \le T \le 1000$$$) — the number of test cases. Next $$$2T$$$ lines contain test cases — two lines per test case.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 30$$$, $$$2 \le k \le 100$$$) — the size of arrays $$$v$$$ and $$$a$$$ and value $$$k$$$ used in the algorithm.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{16}$$$) — the array you'd like to achieve.

Output format:
For each test case print YES (case insensitive) if you can achieve the array $$$a$$$ after some step or NO (case insensitive) otherwise.

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

Note:
In the first test case, you can stop the algorithm before the $$$0$$$-th step, or don't choose any position several times and stop the algorithm.

In the second test case, you can add $$$k^0$$$ to $$$v_1$$$ and stop the algorithm.

In the third test case, you can't make two $$$1$$$ in the array $$$v$$$.

In the fifth test case, you can skip $$$9^0$$$ and $$$9^1$$$, then add $$$9^2$$$ and $$$9^3$$$ to $$$v_3$$$, skip $$$9^4$$$ and finally, add $$$9^5$$$ to $$$v_2$$$.

Example input:
5
4 100
0 0 0 0
1 2
1
3 4
1 4 1
3 2
0 1 3
3 9
0 59049 810

Example output:
YES
YES
NO
NO
YES

Editorial:
This is the solution that doesn't involve masks. Let's reverse the process and try to get all zeroes from the array $$$a$$$: since all $$$a_i \le 10^{16}$$$ we can start from maximum $$$k^s \le 10^{16}$$$.
The key idea: since $$$k^s > \sum_{x=0}^{s-1}{k^x}$$$ then there should be no more than one position $$$pos$$$ such that $$$a_{pos} \ge k^s$$$ and we should decrease it by $$$k^s$$$. Now we can decrease $$$s$$$ by $$$1$$$ and repeat the same process.
If at any step there are at least two $$$a_{pos} \ge k^s$$$ or as result, we won't get array filled with $$$0$$$ then there is no way to build the array $$$a$$$.
Count the Arrays
Contest: Educational Codeforces Round 83 (Rated for Div. 2)
Difficulty rating: 1700
Tags: combinatorics, math

Your task is to calculate the number of arrays such that:

- each array contains $$$n$$$ elements;
- each element is an integer from $$$1$$$ to $$$m$$$;
- for each array, there is exactly one pair of equal elements;
- for each array $$$a$$$, there exists an index $$$i$$$ such that the array is strictly ascending before the $$$i$$$-th element and strictly descending after it (formally, it means that $$$a_j < a_{j + 1}$$$, if $$$j < i$$$, and $$$a_j > a_{j + 1}$$$, if $$$j \ge i$$$).

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le m \le 2 \cdot 10^5$$$).

Output format:
Print one integer — the number of arrays that meet all of the aforementioned conditions, taken modulo $$$998244353$$$.

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

Note:
The arrays in the first example are:

- $$$[1, 2, 1]$$$;
- $$$[1, 3, 1]$$$;
- $$$[1, 4, 1]$$$;
- $$$[2, 3, 2]$$$;
- $$$[2, 4, 2]$$$;
- $$$[3, 4, 3]$$$.

Example input:
3 4

Example output:
6

Example input:
3 5

Example output:
10

Editorial:
First of all, there will be exactly $$$n - 1$$$ distinct elements in our array. Let's choose them, there are $$${m}\choose{n-1}$$$ ways to do that.
After that, there should be exactly one element that appears twice. There are $$$n - 1$$$ elements to choose from, but are all of them eligible? If we duplicate the maximum element, there will be no way to meet the fourth condition. So we should multiply the current answer by $$$n - 2$$$, not $$$n - 1$$$.
And finally, some elements will appear earlier than the maximum in our array, and some — later. The duplicated element will appear on both sides, but all other elements should appear either to the left or to the right, so there are $$$2^{n - 3}$$$ ways to choose their positions.
Thus the answer is $$${{m}\choose{n - 1}} (n - 2)2^{n - 3}$$$. Note that you have to precompute all factorials and use their inverse elements to calculate $$${m}\choose{n-1}$$$.
Note that there is a tricky case when $$$n = 2$$$: some binpow implementations go into infinite loop trying to compute $$$2^{-1}$$$, so you may have to handle it specifically.
Array Shrinking
Contest: Educational Codeforces Round 83 (Rated for Div. 2)
Difficulty rating: 2100
Tags: dp, greedy

You are given an array $$$a_1, a_2, \dots, a_n$$$. You can perform the following operation any number of times:

- Choose a pair of two neighboring equal elements $$$a_i = a_{i + 1}$$$ (if there is at least one such pair).
- Replace them by one element with value $$$a_i + 1$$$.

After each such operation, the length of the array will decrease by one (and elements are renumerated accordingly). What is the minimum possible length of the array $$$a$$$ you can get?

Input format:
The first line contains the single integer $$$n$$$ ($$$1 \le n \le 500$$$) — the initial length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 1000$$$) — the initial array $$$a$$$.

Output format:
Print the only integer — the minimum possible length you can get after performing the operation described above any number of times.

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

Note:
In the first test, this is one of the optimal sequences of operations: $$$4$$$ $$$3$$$ $$$2$$$ $$$2$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$3$$$ $$$3$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$4$$$ $$$3$$$ $$$\rightarrow$$$ $$$5$$$ $$$3$$$.

In the second test, this is one of the optimal sequences of operations: $$$3$$$ $$$3$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$3$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$3$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$\rightarrow$$$ $$$5$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$\rightarrow$$$ $$$5$$$ $$$5$$$ $$$4$$$ $$$\rightarrow$$$ $$$6$$$ $$$4$$$.

In the third and fourth tests, you can't perform the operation at all.

Example input:
5
4 3 2 2 3

Example output:
2

Example input:
7
3 3 4 4 4 3 3

Example output:
2

Editorial:
Let's look at the answer: by construction, each element in the final answer was the result of replace series of elements on the corresponding segment. So all we need to find is the minimal (by size) partition of the array $$$a$$$ on segments where each segment can be transformed in one element by series of replaces.
We can calculate it using standard prefix dynamic programming, or $$$dp2[len]$$$ is the size of such minimal partition of a prefix of length $$$len$$$. The transitions are standard: let's check all segments $$$[len, nxt)$$$ and if it can be replaced by one element let's relax $$$dp2[nxt]$$$.
Now we need to check for all segments of $$$a$$$ — can it be replaced by one element. Let's calculate another $$$dp[l][r]$$$ using the following fact: if there is a way to replace all segment as one element so the segment either has the length $$$1$$$ or it can be divided into two parts where the prefix can be replaced by one element, the suffix also can be replaced by one element and these elements are equal. It's exactly the transitions we need to check to calculate $$$dp[l][r]$$$.
The resulting complexity is $$$O(n^3)$$$.
Points and Segments (easy)
Contest: Codeforces Round 245 (Div. 2)
Difficulty rating: 1600
Tags: constructive algorithms, sortings

Iahub isn't well prepared on geometry problems, but he heard that this year there will be a lot of geometry problems on the IOI selection camp. Scared, Iahub locked himself in the basement and started thinking of new problems of this kind. One of them is the following.

Iahub wants to draw n distinct points and m segments on the OX axis. He can draw each point with either red or blue. The drawing is good if and only if the following requirement is met: for each segment [li, ri] consider all the red points belong to it (ri points), and all the blue points belong to it (bi points); each segment i should satisfy the inequality |ri - bi| ≤ 1.

Iahub thinks that point x belongs to segment [l, r], if inequality l ≤ x ≤ r holds.

Iahub gives to you all coordinates of points and segments. Please, help him to find any good drawing.

Input format:
The first line of input contains two integers: n (1 ≤ n ≤ 100) and m (1 ≤ m ≤ 100). The next line contains n space-separated integers x1, x2, ..., xn (0 ≤ xi ≤ 100) — the coordinates of the points. The following m lines contain the descriptions of the m segments. Each line contains two integers li and ri (0 ≤ li ≤ ri ≤ 100) — the borders of the i-th segment.

It's guaranteed that all the points are distinct.

Output format:
If there is no good drawing for a given test, output a single integer -1. Otherwise output n integers, each integer must be 0 or 1. The i-th number denotes the color of the i-th point (0 is red, and 1 is blue).

If there are multiple good drawings you can output any of them.

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

Example input:
3 3
3 7 14
1 5
6 10
11 15

Example output:
0 0 0

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

Example output:
1 0 1

Editorial:
Balls Game
Contest: Codeforces Round 245 (Div. 2)
Difficulty rating: 1400
Tags: brute force, two pointers

Iahub is training for the IOI. What is a better way to train than playing a Zuma-like game?

There are n balls put in a row. Each ball is colored in one of k colors. Initially the row doesn't contain three or more contiguous balls with the same color. Iahub has a single ball of color x. He can insert his ball at any position in the row (probably, between two other balls). If at any moment there are three or more contiguous balls of the same color in the row, they are destroyed immediately. This rule is applied multiple times, until there are no more sets of 3 or more contiguous balls of the same color.

For example, if Iahub has the row of balls [black, black, white, white, black, black] and a white ball, he can insert the ball between two white balls. Thus three white balls are destroyed, and then four black balls become contiguous, so all four balls are destroyed. The row will not contain any ball in the end, so Iahub can destroy all 6 balls.

Iahub wants to destroy as many balls as possible. You are given the description of the row of balls, and the color of Iahub's ball. Help Iahub train for the IOI by telling him the maximum number of balls from the row he can destroy.

Input format:
The first line of input contains three integers: n (1 ≤ n ≤ 100), k (1 ≤ k ≤ 100) and x (1 ≤ x ≤ k). The next line contains n space-separated integers c1, c2, ..., cn (1 ≤ ci ≤ k). Number ci means that the i-th ball in the row has color ci.

It is guaranteed that the initial row of balls will never contain three or more contiguous balls of the same color.

Output format:
Print a single integer — the maximum number of balls Iahub can destroy.

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

Example input:
6 2 2
1 1 2 2 1 1

Example output:
6

Example input:
1 1 1
1

Example output:
0

Editorial:
Shifting Stacks
Contest: Codeforces Round 703 (Div. 2)
Difficulty rating: 900
Tags: greedy, implementation

You have $$$n$$$ stacks of blocks. The $$$i$$$-th stack contains $$$h_i$$$ blocks and it's height is the number of blocks in it. In one move you can take a block from the $$$i$$$-th stack (if there is at least one block) and put it to the $$$i + 1$$$-th stack. Can you make the sequence of heights strictly increasing?

Note that the number of stacks always remains $$$n$$$: stacks don't disappear when they have $$$0$$$ blocks.

Input format:
First line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 100)$$$. The second line of each test case contains $$$n$$$ integers $$$h_i$$$ $$$(0 \leq h_i \leq 10^9)$$$ — starting heights of the stacks.

It's guaranteed that the sum of all $$$n$$$ does not exceed $$$10^4$$$.

Output format:
For each test case output YES if you can make the sequence of heights strictly increasing and NO otherwise.

You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer).

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

Note:
In the first test case there is no need to make any moves, the sequence of heights is already increasing.

In the second test case we need to move one block from the first stack to the second. Then the heights become $$$0$$$ $$$1$$$.

In the third test case we could move one block from the first stack to the second and then from the second to the third, which would make the heights $$$3$$$ $$$4$$$ $$$5$$$.

In the fourth test case we can't make a move, but the sequence is not increasing, so the answer is NO.

In the fifth test case we can only make one move (from the second to the third stack), which would make the heights $$$0$$$ $$$0$$$ $$$1$$$. Both $$$0$$$ $$$1$$$ $$$0$$$ and $$$0$$$ $$$0$$$ $$$1$$$ are not increasing sequences, so the answer is NO.

Example input:
6
2
1 2
2
1 0
3
4 4 4
2
0 0
3
0 1 0
4
1000000000 1000000000 1000000000 1000000000

Example output:
YES
YES
YES
NO
NO
YES

Editorial:
Eastern Exhibition
Contest: Codeforces Round 703 (Div. 2)
Difficulty rating: 1500
Tags: binary search, geometry, shortest paths, sortings

You and your friends live in $$$n$$$ houses. Each house is located on a 2D plane, in a point with integer coordinates. There might be different houses located in the same point. The mayor of the city is asking you for places for the building of the Eastern exhibition. You have to find the number of places (points with integer coordinates), so that the summary distance from all the houses to the exhibition is minimal. The exhibition can be built in the same point as some house. The distance between two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is $$$|x_1 - x_2| + |y_1 - y_2|$$$, where $$$|x|$$$ is the absolute value of $$$x$$$.

Input format:
First line contains a single integer $$$t$$$ $$$(1 \leq t \leq 1000)$$$ — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 1000)$$$. Next $$$n$$$ lines describe the positions of the houses $$$(x_i, y_i)$$$ $$$(0 \leq x_i, y_i \leq 10^9)$$$.

It's guaranteed that the sum of all $$$n$$$ does not exceed $$$1000$$$.

Output format:
For each test case output a single integer - the number of different positions for the exhibition. The exhibition can be built in the same point as some house.

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

Note:
Here are the images for the example test cases. Blue dots stand for the houses, green — possible positions for the exhibition.

First test case.

Second test case.

Third test case.

Fourth test case.

Fifth test case.

Sixth test case. Here both houses are located at $$$(0, 0)$$$.

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

Example output:
1
4
4
4
3
1

Editorial: