1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
The Bits
Contest: Codeforces Round 502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2)
Difficulty rating: 1200
Tags: implementation, math

Rudolf is on his way to the castle. Before getting into the castle, the security staff asked him a question:

Given two binary numbers $$$a$$$ and $$$b$$$ of length $$$n$$$. How many different ways of swapping two digits in $$$a$$$ (only in $$$a$$$, not $$$b$$$) so that bitwise OR of these two numbers will be changed? In other words, let $$$c$$$ be the bitwise OR of $$$a$$$ and $$$b$$$, you need to find the number of ways of swapping two bits in $$$a$$$ so that bitwise OR will not be equal to $$$c$$$.

Note that binary numbers can contain leading zeros so that length of each number is exactly $$$n$$$.

Bitwise OR is a binary operation. A result is a binary number which contains a one in each digit if there is a one in at least one of the two numbers. For example, $$$01010_2$$$ OR $$$10011_2$$$ = $$$11011_2$$$.

Well, to your surprise, you are not Rudolf, and you don't need to help him$$$\ldots$$$ You are the security staff! Please find the number of ways of swapping two bits in $$$a$$$ so that bitwise OR will be changed.

Input format:
The first line contains one integer $$$n$$$ ($$$2\leq n\leq 10^5$$$) — the number of bits in each number.

The second line contains a binary number $$$a$$$ of length $$$n$$$.

The third line contains a binary number $$$b$$$ of length $$$n$$$.

Output format:
Print the number of ways to swap two bits in $$$a$$$ so that bitwise OR will be changed.

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

Note:
In the first sample, you can swap bits that have indexes $$$(1, 4)$$$, $$$(2, 3)$$$, $$$(3, 4)$$$, and $$$(3, 5)$$$.

In the second example, you can swap bits that have indexes $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(2, 4)$$$, $$$(3, 4)$$$, $$$(3, 5)$$$, and $$$(3, 6)$$$.

Example input:
5
01011
11001

Example output:
4

Example input:
6
011000
010011

Example output:
6

Editorial:
Let $$$t_{xy}$$$ be the number of indexes $$$i$$$ such that $$$a_i=x$$$ and $$$b_i=y$$$.
The answer is $$$t_{00}\cdot t_{10} + t_{00}\cdot t_{11} + t_{01}\cdot t_{10}$$$.
Nauuo and Votes
Contest: Codeforces Round 564 (Div. 2)
Difficulty rating: 800
Tags: greedy

Nauuo is a girl who loves writing comments.

One day, she posted a comment on Codeforces, wondering whether she would get upvotes or downvotes.

It's known that there were $$$x$$$ persons who would upvote, $$$y$$$ persons who would downvote, and there were also another $$$z$$$ persons who would vote, but you don't know whether they would upvote or downvote. Note that each of the $$$x+y+z$$$ people would vote exactly one time.

There are three different results: if there are more people upvote than downvote, the result will be "+"; if there are more people downvote than upvote, the result will be "-"; otherwise the result will be "0".

Because of the $$$z$$$ unknown persons, the result may be uncertain (i.e. there are more than one possible results). More formally, the result is uncertain if and only if there exist two different situations of how the $$$z$$$ persons vote, that the results are different in the two situations.

Tell Nauuo the result or report that the result is uncertain.

Input format:
The only line contains three integers $$$x$$$, $$$y$$$, $$$z$$$ ($$$0\le x,y,z\le100$$$), corresponding to the number of persons who would upvote, downvote or unknown.

Output format:
If there is only one possible result, print the result : "+", "-" or "0".

Otherwise, print "?" to report that the result is uncertain.

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

Note:
In the first example, Nauuo would definitely get three upvotes and seven downvotes, so the only possible result is "-".

In the second example, no matter the person unknown downvotes or upvotes, Nauuo would get more upvotes than downvotes. So the only possible result is "+".

In the third example, Nauuo would definitely get one upvote and one downvote, so the only possible result is "0".

In the fourth example, if the only one person upvoted, the result would be "+", otherwise, the result would be "-". There are two possible results, so the result is uncertain.

Example input:
3 7 0

Example output:
-

Example input:
2 0 1

Example output:
+

Editorial:
Consider the two edge cases: all the $$$z$$$ persons upvote / all the $$$z$$$ persons downvote. If the results are the same in these two cases, it is the answer. Otherwise, the result is uncertain.
Nauuo and Chess
Contest: Codeforces Round 564 (Div. 2)
Difficulty rating: 1100
Tags: constructive algorithms, greedy

Nauuo is a girl who loves playing chess.

One day she invented a game by herself which needs $$$n$$$ chess pieces to play on a $$$m\times m$$$ chessboard. The rows and columns are numbered from $$$1$$$ to $$$m$$$. We denote a cell on the intersection of the $$$r$$$-th row and $$$c$$$-th column as $$$(r,c)$$$.

The game's goal is to place $$$n$$$ chess pieces numbered from $$$1$$$ to $$$n$$$ on the chessboard, the $$$i$$$-th piece lies on $$$(r_i,\,c_i)$$$, while the following rule is satisfied: for all pairs of pieces $$$i$$$ and $$$j$$$, $$$|r_i-r_j|+|c_i-c_j|\ge|i-j|$$$. Here $$$|x|$$$ means the absolute value of $$$x$$$.

However, Nauuo discovered that sometimes she couldn't find a solution because the chessboard was too small.

She wants to find the smallest chessboard on which she can put $$$n$$$ pieces according to the rules.

She also wonders how to place the pieces on such a chessboard. Can you help her?

Input format:
The only line contains a single integer $$$n$$$ ($$$1\le n\le 1000$$$) — the number of chess pieces for the game.

Output format:
The first line contains a single integer — the minimum value of $$$m$$$, where $$$m$$$ is the length of sides of the suitable chessboard.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$r_i$$$ and $$$c_i$$$ ($$$1\le r_i,c_i\le m$$$) — the coordinates of the $$$i$$$-th chess piece.

If there are multiple answers, print any.

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

Note:
In the first example, you can't place the two pieces on a $$$1\times1$$$ chessboard without breaking the rule. But you can place two pieces on a $$$2\times2$$$ chessboard like this:

In the second example, you can't place four pieces on a $$$2\times2$$$ chessboard without breaking the rule. For example, if you place the pieces like this:

then $$$|r_1-r_3|+|c_1-c_3|=|1-2|+|1-1|=1$$$, $$$|1-3|=2$$$, $$$1<2$$$; and $$$|r_1-r_4|+|c_1-c_4|=|1-2|+|1-2|=2$$$, $$$|1-4|=3$$$, $$$2<3$$$. It doesn't satisfy the rule.

However, on a $$$3\times3$$$ chessboard, you can place four pieces like this:

Example input:
2

Example output:
2
1 1
1 2

Example input:
4

Example output:
3
1 1
1 3
3 1
3 3

Editorial:
1. $$$m\ge\left\lfloor\frac n 2\right\rfloor+1$$$
Consider the chess pieces $$$1$$$ and $$$n$$$.
$$$\because\begin{cases}|r_1-r_n|+|c_1-c_n|\ge n-1\\|r_1-r_n|\le m-1\\|c_1-c_n|\le m-1\end{cases}$$$
$$$\therefore m-1+m-1\ge n-1$$$
$$$\therefore m\ge\frac{n+1}2$$$
$$$\because m\text{ is an integer}$$$
$$$\therefore m\ge\left\lfloor\frac n 2\right\rfloor+1$$$
2. $$$m$$$ can be $$$\left\lfloor\frac n 2\right\rfloor+1$$$
If we put the $$$i$$$-th piece on $$$(r_i,c_i)$$$ satisfying $$$r_i+c_i=i+1$$$, it is a feasible plan, because $$$|r_i-r_j|+|c_i-c_j|\ge|r_i+c_i-r_j-c_j|$$$.
Joysticks
Contest: Codeforces Round 345 (Div. 2)
Difficulty rating: 1100
Tags: dp, greedy, implementation, math

Friends are going to play console. They have two joysticks and only one charger for them. Initially first joystick is charged at a1 percent and second one is charged at a2 percent. You can connect charger to a joystick only at the beginning of each minute. In one minute joystick either discharges by 2 percent (if not connected to a charger) or charges by 1 percent (if connected to a charger).

Game continues while both joysticks have a positive charge. Hence, if at the beginning of minute some joystick is charged by 1 percent, it has to be connected to a charger, otherwise the game stops. If some joystick completely discharges (its charge turns to 0), the game also stops.

Determine the maximum number of minutes that game can last. It is prohibited to pause the game, i. e. at each moment both joysticks should be enabled. It is allowed for joystick to be charged by more than 100 percent.

Input format:
The first line of the input contains two positive integers a1 and a2 (1 ≤ a1, a2 ≤ 100), the initial charge level of first and second joystick respectively.

Output format:
Output the only integer, the maximum number of minutes that the game can last. Game continues until some joystick is discharged.

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

Note:
In the first sample game lasts for 6 minute by using the following algorithm:

- at the beginning of the first minute connect first joystick to the charger, by the end of this minute first joystick is at 4%, second is at 3%;
- continue the game without changing charger, by the end of the second minute the first joystick is at 5%, second is at 1%;
- at the beginning of the third minute connect second joystick to the charger, after this minute the first joystick is at 3%, the second one is at 2%;
- continue the game without changing charger, by the end of the fourth minute first joystick is at 1%, second one is at 3%;
- at the beginning of the fifth minute connect first joystick to the charger, after this minute the first joystick is at 2%, the second one is at 1%;
- at the beginning of the sixth minute connect second joystick to the charger, after this minute the first joystick is at 0%, the second one is at 2%.

After that the first joystick is completely discharged and the game is stopped.

Example input:
3 5

Example output:
6

Example input:
4 4

Example output:
5

Editorial:
Beautiful Paintings
Contest: Codeforces Round 345 (Div. 2)
Difficulty rating: 1200
Tags: greedy, sortings

There are n pictures delivered for the new exhibition. The i-th painting has beauty ai. We know that a visitor becomes happy every time he passes from a painting to a more beautiful one.

We are allowed to arranged pictures in any order. What is the maximum possible number of times the visitor may become happy while passing all pictures from first to last? In other words, we are allowed to rearrange elements of a in any order. What is the maximum possible number of indices i (1 ≤ i ≤ n - 1), such that ai + 1 > ai.

Input format:
The first line of the input contains integer n (1 ≤ n ≤ 1000) — the number of painting.

The second line contains the sequence a1, a2, ..., an (1 ≤ ai ≤ 1000), where ai means the beauty of the i-th painting.

Output format:
Print one integer — the maximum possible number of neighbouring pairs, such that ai + 1 > ai, after the optimal rearrangement.

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

Note:
In the first sample, the optimal order is: 10, 20, 30, 40, 50.

In the second sample, the optimal order is: 100, 200, 100, 200.

Example input:
5
20 30 10 50 40

Example output:
4

Example input:
4
200 100 100 200

Example output:
2

Editorial:
Desorting
Contest: Codeforces Round 887 (Div. 2)
Difficulty rating: 800
Tags: brute force, greedy, math

Call an array $$$a$$$ of length $$$n$$$ sorted if $$$a_1 \leq a_2 \leq \ldots \leq a_{n-1} \leq a_n$$$.

Ntarsis has an array $$$a$$$ of length $$$n$$$.

He is allowed to perform one type of operation on it (zero or more times):

- Choose an index $$$i$$$ ($$$1 \leq i \leq n-1$$$).
- Add $$$1$$$ to $$$a_1, a_2, \ldots, a_i$$$.
- Subtract $$$1$$$ from $$$a_{i+1}, a_{i+2}, \ldots, a_n$$$.

The values of $$$a$$$ can be negative after an operation.

Determine the minimum operations needed to make $$$a$$$ not sorted.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 500$$$) — the length of the array $$$a$$$.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the values of array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$500$$$.

Output format:
Output the minimum number of operations needed to make the array not sorted.

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

Note:
In the first case, we can perform $$$1$$$ operation to make the array not sorted:

- Pick $$$i = 1$$$. The array $$$a$$$ then becomes $$$[2, 0]$$$, which is not sorted.

In the second case, we can perform $$$2$$$ operations to make the array not sorted:

- Pick $$$i = 3$$$. The array $$$a$$$ then becomes $$$[2, 9, 11, 12]$$$.
- Pick $$$i = 3$$$. The array $$$a$$$ then becomes $$$[3, 10, 12, 11]$$$, which is not sorted.

It can be proven that $$$1$$$ and $$$2$$$ operations are the minimal numbers of operations in the first and second test cases, respectively.

In the third case, the array is already not sorted, so we perform $$$0$$$ operations.

Example input:
4
2
1 1
4
1 8 10 13
3
1 3 2
3
1 9 14

Example output:
1
2
0
3

Editorial:
Fibonaccharsis
Contest: Codeforces Round 887 (Div. 2)
Difficulty rating: 1200
Tags: binary search, brute force, math

Ntarsis has received two integers $$$n$$$ and $$$k$$$ for his birthday. He wonders how many fibonacci-like sequences of length $$$k$$$ can be formed with $$$n$$$ as the $$$k$$$-th element of the sequence.

A sequence of non-decreasing non-negative integers is considered fibonacci-like if $$$f_i = f_{i-1} + f_{i-2}$$$ for all $$$i > 2$$$, where $$$f_i$$$ denotes the $$$i$$$-th element in the sequence. Note that $$$f_1$$$ and $$$f_2$$$ can be arbitrary.

For example, sequences such as $$$[4,5,9,14]$$$ and $$$[0,1,1]$$$ are considered fibonacci-like sequences, while $$$[0,0,0,1,1]$$$, $$$[1, 2, 1, 3]$$$, and $$$[-1,-1,-2]$$$ are not: the first two do not always satisfy $$$f_i = f_{i-1} + f_{i-2}$$$, the latter does not satisfy that the elements are non-negative.

Impress Ntarsis by helping him with this task.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$), the number of test cases. The description of each test case is as follows.

Each test case contains two integers, $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$3 \leq k \leq 10^9$$$).

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

Output format:
For each test case output an integer, the number of fibonacci-like sequences of length $$$k$$$ such that the $$$k$$$-th element in the sequence is $$$n$$$. That is, output the number of sequences $$$f$$$ of length $$$k$$$ so $$$f$$$ is a fibonacci-like sequence and $$$f_k = n$$$. It can be shown this number is finite.

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

Note:
There are $$$4$$$ valid fibonacci-like sequences for $$$n = 22$$$, $$$k = 4$$$:

- $$$[6,8,14,22]$$$,
- $$$[4,9,13,22]$$$,
- $$$[2,10,12,22]$$$,
- $$$[0,11,11,22]$$$.

For $$$n = 3$$$, $$$k = 9$$$, it can be shown that there are no fibonacci-like sequences satisfying the given conditions.

For $$$n = 55$$$, $$$k = 11$$$, $$$[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]$$$ is the only fibonacci-like sequence.

Example input:
8
22 4
3 9
55 11
42069 6
69420 4
69 1434
1 3
1 4

Example output:
4
0
1
1052
11571
0
1
0

Editorial:
Shuffle Party
Contest: Codeforces Round 930 (Div. 2)
Difficulty rating: 800
Tags: implementation, math

You are given an array $$$a_1, a_2, \ldots, a_n$$$. Initially, $$$a_i=i$$$ for each $$$1 \le i \le n$$$.

The operation $$$\texttt{swap}(k)$$$ for an integer $$$k \ge 2$$$ is defined as follows:

- Let $$$d$$$ be the largest divisor$$$^\dagger$$$ of $$$k$$$ which is not equal to $$$k$$$ itself. Then swap the elements $$$a_d$$$ and $$$a_k$$$.

Suppose you perform $$$\texttt{swap}(i)$$$ for each $$$i=2,3,\ldots, n$$$ in this exact order. Find the position of $$$1$$$ in the resulting array. In other words, find such $$$j$$$ that $$$a_j = 1$$$ after performing these operations.

$$$^\dagger$$$ An integer $$$x$$$ is a divisor of $$$y$$$ if there exists an integer $$$z$$$ such that $$$y = x \cdot z$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The only line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^9$$$) — the length of the array $$$a$$$.

Output format:
For each test case, output the position of $$$1$$$ in the resulting array.

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

Note:
In the first test case, the array is $$$[1]$$$ and there are no operations performed.

In the second test case, $$$a$$$ changes as follows:

- Initially, $$$a$$$ is $$$[1,2,3,4]$$$.
- After performing $$$\texttt{swap}(2)$$$, $$$a$$$ changes to $$$[\underline{2},\underline{1},3,4]$$$ (the elements being swapped are underlined).
- After performing $$$\texttt{swap}(3)$$$, $$$a$$$ changes to $$$[\underline{3},1,\underline{2},4]$$$.
- After performing $$$\texttt{swap}(4)$$$, $$$a$$$ changes to $$$[3,\underline{4},2,\underline{1}]$$$.

Finally, the element $$$1$$$ lies on index $$$4$$$ (that is, $$$a_4 = 1$$$). Thus, the answer is $$$4$$$.

Example input:
4
1
4
5
120240229

Example output:
1
4
4
67108864

Editorial:
On $$$n=1$$$, the answer is trivially $$$1$$$.
On $$$n=2$$$, index $$$1$$$ and $$$2$$$ are swapped. The answer is therefore $$$2$$$.
For $$$n>2$$$, let us assume the element $$$1$$$ is on index $$$a$$$ and it will be swapped with index $$$k$$$. Then, $$$a$$$ must be $$$k/2$$$. We will prove this by contradiction. Let us assume that there is no divisor greater than $$$a$$$, and $$$a$$$ is lesser than $$$k/2$$$. But then, as $$$a$$$ is a multiple of $$$2$$$ in the base condition, $$$k$$$ must be a multiple of $$$2$$$, and $$$k/2$$$ is a divisor of $$$k$$$. This contradicts the assumption. By induction we can see that $$$a$$$ is always a multiple of $$$2$$$, and this proof will always hold. The element $$$1$$$ will move only when $$$k/2=a$$$.
Therefore, we can find the largest value of $$$v$$$ such that $$$2^v \le n$$$. The answer turns out to be $$$2^v$$$.
Magical Boxes
Contest: Codeforces Round 165 (Div. 1)
Difficulty rating: 1600
Tags: greedy, math

Emuskald is a well-known illusionist. One of his trademark tricks involves a set of magical boxes. The essence of the trick is in packing the boxes inside other boxes.

From the top view each magical box looks like a square with side length equal to 2k (k is an integer, k ≥ 0) units. A magical box v can be put inside a magical box u, if side length of v is strictly less than the side length of u. In particular, Emuskald can put 4 boxes of side length 2k - 1 into one box of side length 2k, or as in the following figure:

Emuskald is about to go on tour performing around the world, and needs to pack his magical boxes for the trip. He has decided that the best way to pack them would be inside another magical box, but magical boxes are quite expensive to make. Help him find the smallest magical box that can fit all his boxes.

Input format:
The first line of input contains an integer n (1 ≤ n ≤ 105), the number of different sizes of boxes Emuskald has. Each of following n lines contains two integers ki and ai (0 ≤ ki ≤ 109, 1 ≤ ai ≤ 109), which means that Emuskald has ai boxes with side length 2ki. It is guaranteed that all of ki are distinct.

Output format:
Output a single integer p, such that the smallest magical box that can contain all of Emuskald’s boxes has side length 2p.

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

Note:
Picture explanation. If we have 3 boxes with side length 2 and 5 boxes with side length 1, then we can put all these boxes inside a box with side length 4, for example, as shown in the picture.

In the second test case, we can put all four small boxes into a box with side length 2.

Example input:
2
0 3
1 5

Example output:
3

Example input:
1
0 4

Example output:
1

Editorial:
Greenhouse Effect
Contest: Codeforces Round 165 (Div. 1)
Difficulty rating: 1700
Tags: dp

Emuskald is an avid horticulturist and owns the world's longest greenhouse — it is effectively infinite in length.

Over the years Emuskald has cultivated n plants in his greenhouse, of m different plant species numbered from 1 to m. His greenhouse is very narrow and can be viewed as an infinite line, with each plant occupying a single point on that line.

Emuskald has discovered that each species thrives at a different temperature, so he wants to arrange m - 1 borders that would divide the greenhouse into m sections numbered from 1 to m from left to right with each section housing a single species. He is free to place the borders, but in the end all of the i-th species plants must reside in i-th section from the left.

Of course, it is not always possible to place the borders in such way, so Emuskald needs to replant some of his plants. He can remove each plant from its position and place it anywhere in the greenhouse (at any real coordinate) with no plant already in it. Since replanting is a lot of stress for the plants, help Emuskald find the minimum number of plants he has to replant to be able to place the borders.

Input format:
The first line of input contains two space-separated integers n and m (1 ≤ n, m ≤ 5000, n ≥ m), the number of plants and the number of different species. Each of the following n lines contain two space-separated numbers: one integer number si (1 ≤ si ≤ m), and one real number xi (0 ≤ xi ≤ 109), the species and position of the i-th plant. Each xi will contain no more than 6 digits after the decimal point.

It is guaranteed that all xi are different; there is at least one plant of each species; the plants are given in order "from left to the right", that is in the ascending order of their xi coordinates (xi < xi + 1, 1 ≤ i < n).

Output format:
Output a single integer — the minimum number of plants to be replanted.

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

Note:
In the first test case, Emuskald can replant the first plant to the right of the last plant, so the answer is 1.

In the second test case, the species are already in the correct order, so no replanting is needed.

Example input:
3 2
2 1
1 2.0
1 3.100

Example output:
1

Example input:
3 3
1 5.0
2 5.5
3 6.0

Example output:
0

Editorial: