1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
K-th Largest Value
Contest: Codeforces Global Round 13
Difficulty rating: 800
Tags: brute force, greedy, implementation

You are given an array $$$a$$$ consisting of $$$n$$$ integers. Initially all elements of $$$a$$$ are either $$$0$$$ or $$$1$$$. You need to process $$$q$$$ queries of two kinds:

- 1 x : Assign to $$$a_x$$$ the value $$$1 - a_x$$$.
- 2 k : Print the $$$k$$$-th largest value of the array.

As a reminder, $$$k$$$-th largest value of the array $$$b$$$ is defined as following:

- Sort the array in the non-increasing order, return $$$k$$$-th element from it.

For example, the second largest element in array $$$[0, 1, 0, 1]$$$ is $$$1$$$, as after sorting in non-increasing order it becomes $$$[1, 1, 0, 0]$$$, and the second element in this array is equal to $$$1$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^5$$$) — the length of the given array and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$) — elements of the initial array.

Each of the following $$$q$$$ lines contains two integers. The first integer is $$$t$$$ ($$$1 \le t \le 2$$$) — the type of query.

- If $$$t = 1$$$ the second integer is $$$x$$$ ($$$1 \le x \le n$$$) — the position of the modified number. You have to assign to $$$a_x$$$ the value $$$1 - a_x$$$.
- If $$$t = 2$$$ the second integer is $$$k$$$ ($$$1 \le k \le n$$$) — you need to print the $$$k$$$-th largest value of the array.

It's guaranteed that there will be at least one query of the second type (satisfying $$$t = 2$$$).

Output format:
For each query of the second type, print a single integer — the answer to the query.

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

Note:
Initially $$$a = [1, 1, 0, 1, 0]$$$.

The first operation is printing the third largest value, which is $$$1$$$.

The second operation is assigning $$$a_2$$$ the value $$$0$$$, $$$a$$$ becomes $$$[1, 0, 0, 1, 0]$$$.

The third operation is printing the third largest value, it is $$$0$$$.

The fourth operation is printing the first largest value, it is $$$1$$$.

The last operation is printing the fifth largest value, it is $$$0$$$.

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

Example output:
1
0
1
0

Editorial:
Let's define $$$cnt$$$ to represent the number of 1s in the array.
For the modifications, if $$$a_i$$$ is already $$$1$$$ now, then we let $$$cnt \gets cnt - 1$$$. Otherwise, let $$$cnt \gets cnt + 1$$$.
For the querys, just compare $$$cnt$$$ with $$$k$$$. If $$$cnt \ge k$$$, the answer will be $$$1$$$. Otherwise, the answer will be $$$0$$$.
The complexity : $$$O(n + q)$$$.
Red Versus Blue
Contest: Codeforces Round 782 (Div. 2)
Difficulty rating: 1000
Tags: constructive algorithms, greedy, implementation, math

Team Red and Team Blue competed in a competitive FPS. Their match was streamed around the world. They played a series of $$$n$$$ matches.

In the end, it turned out Team Red won $$$r$$$ times and Team Blue won $$$b$$$ times. Team Blue was less skilled than Team Red, so $$$b$$$ was strictly less than $$$r$$$.

You missed the stream since you overslept, but you think that the match must have been neck and neck since so many people watched it. So you imagine a string of length $$$n$$$ where the $$$i$$$-th character denotes who won the $$$i$$$-th match  — it is R if Team Red won or B if Team Blue won. You imagine the string was such that the maximum number of times a team won in a row was as small as possible. For example, in the series of matches RBBRRRB, Team Red won $$$3$$$ times in a row, which is the maximum.

You must find a string satisfying the above conditions. If there are multiple answers, print any.

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

Each test case has a single line containing three integers $$$n$$$, $$$r$$$, and $$$b$$$ ($$$3 \leq n \leq 100$$$; $$$1 \leq b < r \leq n$$$, $$$r+b=n$$$).

Output format:
For each test case, output a single line containing a string satisfying the given conditions. If there are multiple answers, print any.

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

Note:
The first test case of the first example gives the optimal answer for the example in the statement. The maximum number of times a team wins in a row in RBRBRBR is $$$1$$$. We cannot minimize it any further.

The answer for the second test case of the second example is RRBRBRBRBR. The maximum number of times a team wins in a row is $$$2$$$, given by RR at the beginning. We cannot minimize the answer any further.

Example input:
3
7 4 3
6 5 1
19 13 6

Example output:
RBRBRBR
RRRBRR
RRBRRBRRBRRBRRBRRBR

Example input:
6
3 2 1
10 6 4
11 6 5
10 9 1
10 8 2
11 9 2

Example output:
RBR
RRBRBRBRBR
RBRBRBRBRBR
RRRRRBRRRR
RRRBRRRBRR
RRRBRRRBRRR

Editorial:
We have $$$b$$$ B's which divide the string into $$$b + 1$$$ regions and we have to place the R's in these regions. By the strong form of the pigeonhole principle, at least one region must have at least $$$\lceil\frac{r}{b + 1}\rceil$$$ R's. This gives us a lower bound on the answer.
Now, we will construct a string whose answer is exactly equal to the lower bound.
We place the B's so that they are not adjacent. Then we equally distribute the R's in the $$$b + 1$$$ regions.
Let $$$p = \lfloor\frac{r}{b + 1}\rfloor$$$ and $$$q = r\bmod(b + 1)$$$.
We place $$$p$$$ R's in each region and an extra R in any $$$q$$$ regions. Hence, our answer for the construction is $$$\lceil\frac{r}{b + 1}\rceil$$$, which is equal to the lower bound.
Importantly, $$$r > b$$$, so none of the B's will be consecutive.
Time complexity: $$$\mathcal{O}(n)$$$.
Lame King
Contest: Nebius Welcome Round (Div. 1 + Div. 2)
Difficulty rating: 800
Tags: greedy, math

You are given a checkerboard of size $$$201 \times 201$$$, i. e. it has $$$201$$$ rows and $$$201$$$ columns. The rows of this checkerboard are numbered from $$$-100$$$ to $$$100$$$ from bottom to top. The columns of this checkerboard are numbered from $$$-100$$$ to $$$100$$$ from left to right. The notation $$$(r, c)$$$ denotes the cell located in the $$$r$$$-th row and the $$$c$$$-th column.

There is a king piece at position $$$(0, 0)$$$ and it wants to get to position $$$(a, b)$$$ as soon as possible. In this problem our king is lame. Each second, the king makes exactly one of the following five moves.

- Skip move. King's position remains unchanged.
- Go up. If the current position of the king is $$$(r, c)$$$ he goes to position $$$(r + 1, c)$$$.
- Go down. Position changes from $$$(r, c)$$$ to $$$(r - 1, c)$$$.
- Go right. Position changes from $$$(r, c)$$$ to $$$(r, c + 1)$$$.
- Go left. Position changes from $$$(r, c)$$$ to $$$(r, c - 1)$$$.

What is the minimum number of seconds the lame king needs to reach position $$$(a, b)$$$?

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then follow $$$t$$$ lines containing one test case description each.

Each test case consists of two integers $$$a$$$ and $$$b$$$ ($$$-100 \leq a, b \leq 100$$$) — the position of the cell that the king wants to reach. It is guaranteed that either $$$a \ne 0$$$ or $$$b \ne 0$$$.

Output format:
Print $$$t$$$ integers. The $$$i$$$-th of these integers should be equal to the minimum number of seconds the lame king needs to get to the position he wants to reach in the $$$i$$$-th test case. The king always starts at position $$$(0, 0)$$$.

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

Note:
One of the possible solutions for the first example is: go down, go right, go down, go right, go down, go left, go down.

One of the possible solutions for the second example is to alternate "go right" and "go up" moves $$$4$$$ times each.

One of the possible solutions for the third example is to alternate "go left" and "skip" moves starting with "go left". Thus, "go left" will be used $$$6$$$ times, and "skip" will be used $$$5$$$ times.

Example input:
5
-4 1
4 4
0 -6
-5 -4
7 -8

Example output:
7
8
11
9
15

Editorial:
Observation 1. Let $$$|a| = |b|$$$. The king can reach $$$(a, b)$$$ in $$$2 \cdot |a|$$$ moves by alternating moves along rows and moves along columns.
Observation 2. Let $$$|a| \ne |b|$$$, in particular $$$a > b \geq 0$$$ (without loss of generality due to the board symmetry). The king can reach $$$(a, b)$$$ in $$$2a - 1$$$ moves. He moves towards $$$a$$$ on turns $$$1, 3, 5, \ldots, 2a - 1$$$. The remaining $$$a - 1$$$ moves are enough to reach $$$b$$$. Finally, the remaining slots can be filled with "skip" moves.
Thus, the answer is $$$|a| + |b|$$$ if $$$|a| = |b|$$$ and $$$2 \cdot \max(|a|, |b|) - 1$$$ otherwise.
Nezzar and Colorful Balls
Contest: Codeforces Round 698 (Div. 2)
Difficulty rating: 800
Tags: brute force, greedy

Nezzar has $$$n$$$ balls, numbered with integers $$$1, 2, \ldots, n$$$. Numbers $$$a_1, a_2, \ldots, a_n$$$ are written on them, respectively. Numbers on those balls form a non-decreasing sequence, which means that $$$a_i \leq a_{i+1}$$$ for all $$$1 \leq i < n$$$.

Nezzar wants to color the balls using the minimum number of colors, such that the following holds.

- For any color, numbers on balls will form a strictly increasing sequence if he keeps balls with this chosen color and discards all other balls.

Note that a sequence with the length at most $$$1$$$ is considered as a strictly increasing sequence.

Please help Nezzar determine the minimum number of colors.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$). It is guaranteed that $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$.

Output format:
For each test case, output the minimum number of colors Nezzar can use.

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

Note:
Let's match each color with some numbers. Then:

In the first test case, one optimal color assignment is $$$[1,2,3,3,2,1]$$$.

In the second test case, one optimal color assignment is $$$[1,2,1,2,1]$$$.

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

Example output:
3
2
4
1
1

Editorial:
For positions which numbers are the same, they cannot be colored using same color.
Let us color the $$$i$$$-th occurrence of any number using color $$$i$$$.
We can see that:
• We cannot use fewer colors: if there are $$$k$$$ occurrence of any number, at least $$$k$$$ color is needed.
• The assignment of color is valid: Since the sequence was non-increasing, for any subsequence it is also non-increasing. As there are no duplicates in colored subsequence, the subsequence is strictly increasing as well.
Therefore, we only need to count the number of occurrence of every number and take the maximum of them.
Time complexity: $$$O(n)$$$ per test case
Nezzar and Lucky Number
Contest: Codeforces Round 698 (Div. 2)
Difficulty rating: 1100
Tags: brute force, dp, greedy, math

Nezzar's favorite digit among $$$1,\ldots,9$$$ is $$$d$$$. He calls a positive integer lucky if $$$d$$$ occurs at least once in its decimal representation.

Given $$$q$$$ integers $$$a_1,a_2,\ldots,a_q$$$, for each $$$1 \le i \le q$$$ Nezzar would like to know if $$$a_i$$$ can be equal to a sum of several (one or more) lucky numbers.

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

The first line of each test case contains two integers $$$q$$$ and $$$d$$$ ($$$1 \le q \le 10^4$$$, $$$1 \le d \le 9$$$).

The second line of each test case contains $$$q$$$ integers $$$a_1,a_2,\ldots,a_q$$$ ($$$1 \le a_i \le 10^9$$$).

Output format:
For each integer in each test case, print "YES" in a single line if $$$a_i$$$ can be equal to a sum of lucky numbers. Otherwise, print "NO".

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

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

Note:
In the first test case, $$$24 = 17 + 7$$$, $$$27$$$ itself is a lucky number, $$$25$$$ cannot be equal to a sum of lucky numbers.

Example input:
2
3 7
24 25 27
10 7
51 52 53 54 55 56 57 58 59 60

Example output:
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO

Editorial:
For any given $$$d$$$, We can observe the following:
• $$$10d$$$ to $$$10d + 9$$$ contains $$$d$$$ as one of its digit
• Let $$$k = 10d + 9$$$ be the upper bound of such range For every number $$$x > k$$$, we can keep reducing $$$x$$$ by $$$d$$$, $$$x$$$ will eventually fall into the range mentioned above, which contains $$$d$$$ as digit.
Therefore, for numbers $$$x > k$$$, they are always achievable. For $$$x \leq k - 10$$$, as $$$k <= 109$$$, we can run a standard knapsack dynamicprogramming solution, where $$$dp[x]$$$ indicates if $$$x$$$ is achievable. $$$dp[x]$$$ is achievable, if and only if one of the following is true:
• $$$x = 0$$$
• For some $$$y < x$$$, $$$dp[y]$$$ is true and $$$x - y$$$ contains $$$d$$$ as digit
Iterating for every $$$x$$$, all $$$dp[x]$$$ for $$$x < k$$$ can be computed with $$$O(k)$$$ per state (as we only need to consider $$$y < k$$$.
Besides dynamic programming solution, brute force solutions with enough optimization should also pass the test cases easily.
Time complexity: $$$O((10d)^2)$$$ per test case.
Nezzar and Symmetric Array
Contest: Codeforces Round 698 (Div. 2)
Difficulty rating: 1700
Tags: implementation, math, sortings

Long time ago there was a symmetric array $$$a_1,a_2,\ldots,a_{2n}$$$ consisting of $$$2n$$$ distinct integers. Array $$$a_1,a_2,\ldots,a_{2n}$$$ is called symmetric if for each integer $$$1 \le i \le 2n$$$, there exists an integer $$$1 \le j \le 2n$$$ such that $$$a_i = -a_j$$$.

For each integer $$$1 \le i \le 2n$$$, Nezzar wrote down an integer $$$d_i$$$ equal to the sum of absolute differences from $$$a_i$$$ to all integers in $$$a$$$, i. e. $$$d_i = \sum_{j = 1}^{2n} {|a_i - a_j|}$$$.

Now a million years has passed and Nezzar can barely remember the array $$$d$$$ and totally forget $$$a$$$. Nezzar wonders if there exists any symmetric array $$$a$$$ consisting of $$$2n$$$ distinct integers that generates the array $$$d$$$.

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

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

The second line of each test case contains $$$2n$$$ integers $$$d_1, d_2, \ldots, d_{2n}$$$ ($$$0 \le d_i \le 10^{12}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, print "YES" in a single line if there exists a possible array $$$a$$$. Otherwise, print "NO".

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

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

Note:
In the first test case, $$$a=[1,-3,-1,3]$$$ is one possible symmetric array that generates the array $$$d=[8,12,8,12]$$$.

In the second test case, it can be shown that there is no symmetric array consisting of distinct integers that can generate array $$$d$$$.

Example input:
6
2
8 12 8 12
2
7 7 9 11
2
7 11 7 11
1
1 1
4
40 56 48 40 80 56 80 48
6
240 154 210 162 174 154 186 240 174 186 162 210

Example output:
YES
NO
NO
NO
NO
YES

Editorial:
WLOG, we may assume that $$$0 < a_1 < a_2 < \ldots < a_n$$$, and $$$a_{i+n}=-a_i$$$ for each $$$1 \le i \le n$$$.
Let's sort array $$$d$$$ firstly. It can be observed that the array $$$d$$$ satisfied the following property:
• $$$d_{2i-1}=d_{2i}$$$ for each $$$1 \le i \le n$$$;
• $$$d_{2i} \neq d_{2i+2}$$$ for each $$$1 \le i < n$$$.
• $$$d_{2i}$$$ must be generated for index $$$i$$$ or $$$i+n$$$.
More importantly, we have the following relation: $$$$$$d_{2n}-d_{2n-2}=\sum_{i=1}^{n} (a_n-a_i)+\sum_{i=1}^n (a_n+a_i) - \sum_{i=1}^n|a_{n-1}-a_i| - \sum_{i=1}^n (a_{n-1}+a_i) = (2n-2)(a_n-a_{n-1})$$$$$$
And observe that $$$|a_i-a_n|+|a_i+a_n|=2a_n$$$ is a constant independent of index $$$1 \le i\le n$$$. Therefore, we may remove $$$a_n$$$ and $$$-a_n$$$ by subtracting some constant for $$$d_i$$$ for all $$$1 \le i \le 2(n-1)$$$, indicating that we will calculate $$$a_{i+1}-a_{i}$$$ for all $$$1 \le i < n$$$, which can be done in $$$O(n)$$$.
Lastly, we should determine if there exists an postivie integer $$$a_1$$$ which generates $$$d_1$$$, which can be done in $$$O(n)$$$.
Funky Numbers
Contest: Codeforces Round 121 (Div. 2)
Difficulty rating: 1300
Tags: binary search, brute force, implementation

As you very well know, this year's funkiest numbers are so called triangular numbers (that is, integers that are representable as $$\frac{k(k+1)}{2}$$, where k is some positive integer), and the coolest numbers are those that are representable as a sum of two triangular numbers.

A well-known hipster Andrew adores everything funky and cool but unfortunately, he isn't good at maths. Given number n, help him define whether this number can be represented by a sum of two triangular numbers (not necessarily different)!

Input format:
The first input line contains an integer n (1 ≤ n ≤ 109).

Output format:
Print "YES" (without the quotes), if n can be represented as a sum of two triangular numbers, otherwise print "NO" (without the quotes).

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

Note:
In the first sample number $$256 = \frac{2\cdot3}{2} + \frac{22\cdot23}{2}$$.

In the second sample number 512 can not be represented as a sum of two triangular numbers.

Example input:
256

Example output:
YES

Example input:
512

Example output:
NO

Editorial:
Walking in the Rain
Contest: Codeforces Round 121 (Div. 2)
Difficulty rating: 1100
Tags: brute force, implementation

In Berland the opposition is going to arrange mass walking on the boulevard. The boulevard consists of n tiles that are lain in a row and are numbered from 1 to n from right to left. The opposition should start walking on the tile number 1 and the finish on the tile number n. During the walk it is allowed to move from right to left between adjacent tiles in a row, and jump over a tile. More formally, if you are standing on the tile number i (i < n - 1), you can reach the tiles number i + 1 or the tile number i + 2 from it (if you stand on the tile number n - 1, you can only reach tile number n). We can assume that all the opposition movements occur instantaneously.

In order to thwart an opposition rally, the Berland bloody regime organized the rain. The tiles on the boulevard are of poor quality and they are rapidly destroyed in the rain. We know that the i-th tile is destroyed after ai days of rain (on day ai tile isn't destroyed yet, and on day ai + 1 it is already destroyed). Of course, no one is allowed to walk on the destroyed tiles! So the walk of the opposition is considered thwarted, if either the tile number 1 is broken, or the tile number n is broken, or it is impossible to reach the tile number n from the tile number 1 if we can walk on undestroyed tiles.

The opposition wants to gather more supporters for their walk. Therefore, the more time they have to pack, the better. Help the opposition to calculate how much time they still have and tell us for how many days the walk from the tile number 1 to the tile number n will be possible.

Input format:
The first line contains integer n (1 ≤ n ≤ 103) — the boulevard's length in tiles.

The second line contains n space-separated integers ai — the number of days after which the i-th tile gets destroyed (1 ≤ ai ≤ 103).

Output format:
Print a single number — the sought number of days.

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

Note:
In the first sample the second tile gets destroyed after day three, and the only path left is 1 → 3 → 4. After day five there is a two-tile gap between the first and the last tile, you can't jump over it.

In the second sample path 1 → 3 → 5 is available up to day five, inclusive. On day six the last tile is destroyed and the walk is thwarted.

Example input:
4
10 3 5 10

Example output:
5

Example input:
5
10 2 8 3 5

Example output:
5

Editorial:
Lights Out
Contest: Codeforces Round 168 (Div. 2)
Difficulty rating: 900
Tags: implementation

Lenny is playing a game on a 3 × 3 grid of lights. In the beginning of the game all lights are switched on. Pressing any of the lights will toggle it and all side-adjacent lights. The goal of the game is to switch all the lights off. We consider the toggling as follows: if the light was switched on then it will be switched off, if it was switched off then it will be switched on.

Lenny has spent some time playing with the grid and by now he has pressed each light a certain number of times. Given the number of times each light is pressed, you have to print the current state of each light.

Input format:
The input consists of three rows. Each row contains three integers each between 0 to 100 inclusive. The j-th number in the i-th row is the number of times the j-th light of the i-th row of the grid is pressed.

Output format:
Print three lines, each containing three characters. The j-th character of the i-th line is "1" if and only if the corresponding light is switched on, otherwise it's "0".

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

Example input:
1 0 0
0 0 0
0 0 1

Example output:
001
010
100

Example input:
1 0 1
8 8 8
2 0 3

Example output:
010
011
100

Editorial:
Convex Shape
Contest: Codeforces Round 168 (Div. 2)
Difficulty rating: 1700
Tags: constructive algorithms, implementation

Consider an n × m grid. Initially all the cells of the grid are colored white. Lenny has painted some of the cells (at least one) black. We call a painted grid convex if one can walk from any black cell to any another black cell using a path of side-adjacent black cells changing his direction at most once during the path. In the figure below, the left grid is convex while the right one is not convex, because there exist two cells which need more than one time to change direction in their path.

You're given a painted grid in the input. Tell Lenny if the grid is convex or not.

Input format:
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 50) — the size of the grid. Each of the next n lines contains m characters "B" or "W". Character "B" denotes a black cell of the grid and "W" denotes a white cell of the grid.

It's guaranteed that the grid has at least one black cell.

Output format:
On the only line of the output print "YES" if the grid is convex, otherwise print "NO". Do not print quotes.

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

Example input:
3 4
WWBW
BWWW
WWWB

Example output:
NO

Example input:
3 1
B
B
W

Example output:
YES

Editorial: