1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Game with Powers
Contest: Codeforces Round 188 (Div. 1)
Difficulty rating: 2300
Tags: dp, games

Vasya and Petya wrote down all integers from 1 to n to play the "powers" game (n can be quite large; however, Vasya and Petya are not confused by this fact).

Players choose numbers in turn (Vasya chooses first). If some number x is chosen at the current turn, it is forbidden to choose x or all of its other positive integer powers (that is, x2, x3, ...) at the next turns. For instance, if the number 9 is chosen at the first turn, one cannot choose 9 or 81 later, while it is still allowed to choose 3 or 27. The one who cannot make a move loses.

Who wins if both Vasya and Petya play optimally?

Input format:
Input contains single integer n (1 ≤ n ≤ 109).

Output format:
Print the name of the winner — "Vasya" or "Petya" (without quotes).

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

Note:
In the first sample Vasya will choose 1 and win immediately.

In the second sample no matter which number Vasya chooses during his first turn, Petya can choose the remaining number and win.

Example input:
1

Example output:
Vasya

Example input:
2

Example output:
Petya

Editorial:
Card Exchange
Contest: Codeforces Round 941 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, games, greedy

You have a hand of $$$n$$$ cards, where each card has a number written on it, and a fixed integer $$$k$$$. You can perform the following operation any number of times:

- Choose any $$$k$$$ cards from your hand that all have the same number.
- Exchange these cards for $$$k-1$$$ cards, each of which can have any number you choose (including the number written on the cards you just exchanged).

Here is one possible sequence of operations for the first example case, which has $$$k=3$$$:

What is the minimum number of cards you can have in your hand at the end of this process?

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100$$$, $$$2 \le k \le 100$$$) — the number of cards you have, and the number of cards you exchange during each operation, respectively.

The next line of each test case contains $$$n$$$ integers $$$c_1, c_2, \ldots c_n$$$ ($$$1 \le c_i \le 100$$$) — the numbers written on your cards.

Output format:
For each test case, output a single integer — the minimum number of cards you can have left in your hand after any number of operations.

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

Note:
The first example case corresponds to the picture above. The sequence of operations displayed there is optimal, so the answer is $$$2$$$.

In the second example case, no operations can be performed, so the answer is $$$1$$$.

In the fourth example case, you can repeatedly select $$$4$$$ cards numbered with $$$1$$$ and replace them with $$$3$$$ cards numbered with $$$1$$$, until there are $$$3$$$ cards left.

Example input:
7
5 3
4 1 1 4 4
1 10
7
7 2
4 2 1 100 5 2 3
10 4
1 1 1 1 1 1 1 1 1 1
5 2
3 8 1 48 7
6 2
10 20 30 10 20 40
6 3
10 20 30 10 20 40

Example output:
2
1
1
3
5
1
6

Editorial:
If you don't initially have at least $$$k$$$ copies of any number, you can't perform any operations, so the answer is $$$n$$$.
Otherwise, we can show that we can always get down to $$$k-1$$$ cards, with the following algorithm:
1. Choose any card that you have $$$k$$$ copies of, and remove those $$$k$$$ copies
2. If you have no more cards, take any $$$k-1$$$ cards and end the process.
3. Otherwise, let $$$x$$$ be the number on any card you have. Take $$$k-1$$$ copies of $$$x$$$. Now, you have at least $$$k$$$ copies of $$$x$$$, so return to step $$$1$$$.
Since the total number of cards decreases at each step, this process will always terminate, so you will always end up with $$$k-1$$$ cards.
Also, since the total number of cards decreases by exactly $$$1$$$ at each step, and you can't do any operations if you have less than $$$k$$$ cards, it is impossible to do better than $$$k-1$$$, so our solution of $$$k-1$$$ is optimal.
Complexity: $$$O(n)$$$ or $$$O(n \log n)$$$ depending on implementation.
Not Wool Sequences
Contest: Codeforces Round 148 (Div. 1)
Difficulty rating: 1300
Tags: constructive algorithms, math

A sequence of non-negative integers a1, a2, ..., an of length n is called a wool sequence if and only if there exists two integers l and r (1 ≤ l ≤ r ≤ n) such that $$a_{l} \oplus a_{l+1} \oplus \cdots \oplus a_{r} = 0$$. In other words each wool sequence contains a subsequence of consecutive elements with xor equal to 0.

The expression $$x \oplus y$$ means applying the operation of a bitwise xor to numbers x and y. The given operation exists in all modern programming languages, for example, in languages C++ and Java it is marked as "^", in Pascal — as "xor".

In this problem you are asked to compute the number of sequences made of n integers from 0 to 2m - 1 that are not a wool sequence. You should print this number modulo 1000000009 (109 + 9).

Input format:
The only line of input contains two space-separated integers n and m (1 ≤ n, m ≤ 105).

Output format:
Print the required number of sequences modulo 1000000009 (109 + 9) on the only line of output.

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

Note:
Sequences of length 3 made of integers 0, 1, 2 and 3 that are not a wool sequence are (1, 3, 1), (1, 2, 1), (2, 1, 2), (2, 3, 2), (3, 1, 3) and (3, 2, 3).

Example input:
3 2

Example output:
6

Editorial:
Boring Partition
Contest: Codeforces Round 148 (Div. 1)
Difficulty rating: 1800
Tags: constructive algorithms

This problem is the most boring one you've ever seen.

Given a sequence of integers a1, a2, ..., an and a non-negative integer h, our goal is to partition the sequence into two subsequences (not necessarily consist of continuous elements). Each element of the original sequence should be contained in exactly one of the result subsequences. Note, that one of the result subsequences can be empty.

Let's define function f(ai, aj) on pairs of distinct elements (that is i ≠ j) in the original sequence. If ai and aj are in the same subsequence in the current partition then f(ai, aj) = ai + aj otherwise f(ai, aj) = ai + aj + h.

Consider all possible values of the function f for some partition. We'll call the goodness of this partiotion the difference between the maximum value of function f and the minimum value of function f.

Your task is to find a partition of the given sequence a that have the minimal possible goodness among all possible partitions.

Input format:
The first line of input contains integers n and h (2 ≤ n ≤ 105, 0 ≤ h ≤ 108). In the second line there is a list of n space-separated integers representing a1, a2, ..., an (0 ≤ ai ≤ 108).

Output format:
The first line of output should contain the required minimum goodness.

The second line describes the optimal partition. You should print n whitespace-separated integers in the second line. The i-th integer is 1 if ai is in the first subsequence otherwise it should be 2.

If there are several possible correct answers you are allowed to print any of them.

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

Note:
In the first sample the values of f are as follows: f(1, 2) = 1 + 2 + 2 = 5, f(1, 3) = 1 + 3 + 2 = 6 and f(2, 3) = 2 + 3 = 5. So the difference between maximum and minimum values of f is 1.

In the second sample the value of h is large, so it's better for one of the sub-sequences to be empty.

Example input:
3 2
1 2 3

Example output:
1
1 2 2

Example input:
5 10
0 1 0 2 1

Example output:
3
2 2 2 2 2

Editorial:
World Eater Brothers
Contest: Codeforces Round 148 (Div. 1)
Difficulty rating: 2100
Tags: dfs and similar, dp, greedy, trees

You must have heard of the two brothers dreaming of ruling the world. With all their previous plans failed, this time they decided to cooperate with each other in order to rule the world.

As you know there are n countries in the world. These countries are connected by n - 1 directed roads. If you don't consider direction of the roads there is a unique path between every pair of countries in the world, passing through each road at most once.

Each of the brothers wants to establish his reign in some country, then it's possible for him to control the countries that can be reached from his country using directed roads.

The brothers can rule the world if there exists at most two countries for brothers to choose (and establish their reign in these countries) so that any other country is under control of at least one of them. In order to make this possible they want to change the direction of minimum number of roads. Your task is to calculate this minimum number of roads.

Input format:
The first line of input contains an integer n (1 ≤ n ≤ 3000). Each of the next n - 1 lines contains two space-separated integers ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi) saying there is a road from country ai to country bi.

Consider that countries are numbered from 1 to n. It's guaranteed that if you don't consider direction of the roads there is a unique path between every pair of countries in the world, passing through each road at most once.

Output format:
In the only line of output print the minimum number of roads that their direction should be changed so that the brothers will be able to rule the world.

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

Example input:
4
2 1
3 1
4 1

Example output:
1

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

Example output:
0

Editorial:
Tape Programming
Contest: Codeforces Round 148 (Div. 1)
Difficulty rating: 2900
Tags: data structures, implementation

There is a programming language in which every program is a non-empty sequence of "<" and ">" signs and digits. Let's explain how the interpreter of this programming language works. A program is interpreted using movement of instruction pointer (IP) which consists of two parts.

- Current character pointer (CP);
- Direction pointer (DP) which can point left or right;

Initially CP points to the leftmost character of the sequence and DP points to the right.

We repeat the following steps until the first moment that CP points to somewhere outside the sequence.

- If CP is pointing to a digit the interpreter prints that digit then CP moves one step according to the direction of DP. After that the value of the printed digit in the sequence decreases by one. If the printed digit was 0 then it cannot be decreased therefore it's erased from the sequence and the length of the sequence decreases by one.
- If CP is pointing to "<" or ">" then the direction of DP changes to "left" or "right" correspondingly. Then CP moves one step according to DP. If the new character that CP is pointing to is "<" or ">" then the previous character will be erased from the sequence.

If at any moment the CP goes outside of the sequence the execution is terminated.

It's obvious the every program in this language terminates after some steps.

We have a sequence s1, s2, ..., sn of "<", ">" and digits. You should answer q queries. Each query gives you l and r and asks how many of each digit will be printed if we run the sequence sl, sl + 1, ..., sr as an independent program in this language.

Input format:
The first line of input contains two integers n and q (1 ≤ n, q ≤ 105) — represents the length of the sequence s and the number of queries.

The second line contains s, a sequence of "<", ">" and digits (0..9) written from left to right. Note, that the characters of s are not separated with spaces.

The next q lines each contains two integers li and ri (1 ≤ li ≤ ri ≤ n) — the i-th query.

Output format:
For each query print 10 space separated integers: x0, x1, ..., x9 where xi equals the number of times the interpreter prints i while running the corresponding program. Print answers to the queries in the order they are given in input.

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

Example input:
7 4
1>3>22<
1 3
4 7
7 7
1 7

Example output:
0 1 0 1 0 0 0 0 0 0
2 2 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
2 3 2 1 0 0 0 0 0 0

Editorial:
Meeting Her
Contest: Codeforces Round 148 (Div. 1)
Difficulty rating: 2600
Tags: dp, graphs, shortest paths

Urpal lives in a big city. He has planned to meet his lover tonight.

The city has n junctions numbered from 1 to n. The junctions are connected by m directed streets, all the roads have equal length. Urpal lives in junction a and the date is planned in a restaurant in junction b. He wants to use public transportation to get to junction b. There are k bus transportation companies. At the beginning of every second, a bus from the i-th company chooses a random shortest path between junction si and junction ti and passes through it. There might be no path from si to ti. In that case no bus will leave from si to ti. If a bus passes through a junction where Urpal stands, he can get on the bus. He can also get off the bus at any junction along the path.

Now Urpal wants to know if it's possible to go to the date using public transportation in a finite amount of time (the time of travel is the sum of length of the traveled roads) and what is the minimum number of buses he should take in the worst case.

At any moment Urpal knows only his own position and the place where the date will be. When he gets on the bus he knows only the index of the company of this bus. Of course Urpal knows the city map and the the pairs (si, ti) for each company.

Note that Urpal doesn't know buses velocity.

Input format:
The first line of the input contains four integers n, m, a, b (2 ≤ n ≤ 100; 0 ≤ m ≤ n·(n - 1); 1 ≤ a, b ≤ n; a ≠ b).

The next m lines contain two integers each ui and vi (1 ≤ ui, vi ≤ n; ui ≠ vi) describing a directed road from junction ui to junction vi. All roads in the input will be distinct.

The next line contains an integer k (0 ≤ k ≤ 100). There will be k lines after this, each containing two integers si and ti (1 ≤ si, ti ≤ n; si ≠ ti) saying there is a bus route starting at si and ending at ti. Please note that there might be no path from si to ti, this case is described in the problem statement.

Output format:
In the only line of output print the minimum number of buses Urpal should get on on his way in the worst case. If it's not possible to reach the destination in the worst case print -1.

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

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

Example output:
2

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

Example output:
-1

Editorial:
Likes
Contest: Codeforces Round 857 (Div. 2)
Difficulty rating: 800
Tags: greedy, implementation

Nikita recently held a very controversial round, after which his contribution changed very quickly.

The announcement hung on the main page for $$$n$$$ seconds. In the $$$i$$$th second $$$|a_i|$$$th person either liked or removed the like (Nikita was lucky in this task and there are no dislikes). If $$$a_i > 0$$$, then the $$$a_i$$$th person put a like. If $$$a_i < 0$$$, then the person $$$-a_i$$$ removed the like. Each person put and removed the like no more than once. A person could not remove a like if he had not put it before.

Since Nikita's contribution became very bad after the round, he wanted to analyze how his contribution changed while the announcement was on the main page. He turned to the creator of the platform with a request to give him the sequence $$$a_1, a_2, \ldots, a_n$$$. But due to the imperfection of the platform, the sequence $$$a$$$ was shuffled.

You are given a shuffled sequence of $$$a$$$ that describes user activity. You need to tell for each moment from $$$1$$$ to $$$n$$$ what the maximum and minimum number of likes could be on the post at that moment.

Input format:
The first line of input data contains one number $$$t$$$ ($$$1 \leqslant t \leqslant 1000$$$) — the number of test cases.

In the first line of test case, one number is given $$$n$$$ ($$$1 \leqslant n \leqslant 100$$$) — the number of seconds during which Nikita's announcement hung on the main page.

The next line contains $$$n$$$ numbers $$$b_1, b_2, b_3, \ldots, b_n$$$ ($$$1 \leqslant |b_i| \leqslant n$$$) — mixed array $$$a$$$. It is guaranteed that there exists such a permutation of $$$b$$$ that it is a correct sequence of events described in the condition.

It is guaranteed that the sum of $$$n$$$ for all input test cases does not exceed $$$10^4$$$.

Output format:
For each test case, output two lines, each of which contains $$$n$$$ numbers.

In the first line, for each test case, output the maximum number of likes that Nikita could have at the announcement at the $$$i$$$th second.

In the second line, for each test case, output the minimum number of likes that Nikita could have at the announcement at the $$$i$$$th second.

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

Note:
In the first test case, the maximum values are reached with the following permutation: $$$1, 2, -2$$$. And the minimum values for such: $$$2, -2, 1$$$.

In the third test case, all maximal values are reached with the following permutation: $$$4, 2, 3, 1, -1, -2$$$. And the minimum values for the next permutation: $$$2, -2, 1, -1, 3, 4$$$.

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

Example output:
1 2 1 
1 0 1 
1 0 
1 0 
1 2 3 4 3 2 
1 0 1 0 1 2 
1 2 3 4 3 
1 0 1 2 3 
1 2 3 4 5 4 3 
1 0 1 0 1 2 3

Editorial:
Exams
Contest: Codeforces Round 122 (Div. 2)
Difficulty rating: 900
Tags: implementation, math

One day the Codeforces round author sat exams. He had n exams and he needed to get an integer from 2 to 5 for each exam. He will have to re-sit each failed exam, i.e. the exam that gets mark 2.

The author would need to spend too much time and effort to make the sum of his marks strictly more than k. That could have spoilt the Codeforces round. On the other hand, if the sum of his marks is strictly less than k, the author's mum won't be pleased at all.

The Codeforces authors are very smart and they always get the mark they choose themselves. Also, the Codeforces authors just hate re-sitting exams.

Help the author and find the minimum number of exams he will have to re-sit if he passes the exams in the way that makes the sum of marks for all n exams equal exactly k.

Input format:
The single input line contains space-separated integers n and k (1 ≤ n ≤ 50, 1 ≤ k ≤ 250) — the number of exams and the required sum of marks.

It is guaranteed that there exists a way to pass n exams in the way that makes the sum of marks equal exactly k.

Output format:
Print the single number — the minimum number of exams that the author will get a 2 for, considering that the sum of marks for all exams must equal k.

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

Note:
In the first sample the author has to get a 2 for all his exams.

In the second sample he should get a 3 for two exams and a 2 for two more.

In the third sample he should get a 3 for one exam.

Example input:
4 8

Example output:
4

Example input:
4 10

Example output:
2

Editorial:
Square
Contest: Codeforces Round 122 (Div. 2)
Difficulty rating: 1200
Tags: math

There is a square painted on a piece of paper, the square's side equals n meters. John Doe draws crosses on the square's perimeter. John paints the first cross in the lower left corner of the square. Then John moves along the square's perimeter in the clockwise direction (first upwards, then to the right, then downwards, then to the left and so on). Every time he walks (n + 1) meters, he draws a cross (see picture for clarifications).

John Doe stops only when the lower left corner of the square has two crosses. How many crosses will John draw?

The figure shows the order in which John draws crosses for a square with side 4. The lower left square has two crosses. Overall John paints 17 crosses.

Input format:
The first line contains integer t (1 ≤ t ≤ 104) — the number of test cases.

The second line contains t space-separated integers ni (1 ≤ ni ≤ 109) — the sides of the square for each test sample.

Output format:
For each test sample print on a single line the answer to it, that is, the number of crosses John will draw as he will move along the square of the corresponding size. Print the answers to the samples in the order in which the samples are given in the input.

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

Example input:
3
4 8 100

Example output:
17
33
401

Editorial:
Meximization
Contest: Codeforces Round 708 (Div. 2)
Difficulty rating: 800
Tags: brute force, data structures, greedy, sortings

You are given an integer $$$n$$$ and an array $$$a_1, a_2, \ldots, a_n$$$. You should reorder the elements of the array $$$a$$$ in such way that the sum of $$$\textbf{MEX}$$$ on prefixes ($$$i$$$-th prefix is $$$a_1, a_2, \ldots, a_i$$$) is maximized.

Formally, you should find an array $$$b_1, b_2, \ldots, b_n$$$, such that the sets of elements of arrays $$$a$$$ and $$$b$$$ are equal (it is equivalent to array $$$b$$$ can be found as an array $$$a$$$ with some reordering of its elements) and $$$\sum\limits_{i=1}^{n} \textbf{MEX}(b_1, b_2, \ldots, b_i)$$$ is maximized.

$$$\textbf{MEX}$$$ of a set of nonnegative integers is the minimal nonnegative integer such that it is not in the set.

For example, $$$\textbf{MEX}(\{1, 2, 3\}) = 0$$$, $$$\textbf{MEX}(\{0, 1, 2, 4, 5\}) = 3$$$.

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

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$$$ $$$(0 \le a_i \le 100)$$$.

Output format:
For each test case print an array $$$b_1, b_2, \ldots, b_n$$$  — the optimal reordering of $$$a_1, a_2, \ldots, a_n$$$, so the sum of $$$\textbf{MEX}$$$ on its prefixes is maximized.

If there exist multiple optimal answers you can find any.

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

Note:
In the first test case in the answer $$$\textbf{MEX}$$$ for prefixes will be:

1. $$$\textbf{MEX}(\{0\}) = 1$$$
2. $$$\textbf{MEX}(\{0, 1\}) = 2$$$
3. $$$\textbf{MEX}(\{0, 1, 2\}) = 3$$$
4. $$$\textbf{MEX}(\{0, 1, 2, 3\}) = 4$$$
5. $$$\textbf{MEX}(\{0, 1, 2, 3, 4\}) = 5$$$
6. $$$\textbf{MEX}(\{0, 1, 2, 3, 4, 7\}) = 5$$$
7. $$$\textbf{MEX}(\{0, 1, 2, 3, 4, 7, 3\}) = 5$$$

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

Example output:
0 1 2 3 4 7 3 
2 6 8 9 2 
0

Editorial:
To maximize the sum of $$$\textbf{MEX}$$$ on prefixes we will use a greedy algorithm. Firstly we put all unique elements in increasing order to get maximal $$$\textbf{MEX}$$$ on each prefix. It is easy to see that replacing any two elements after that makes both $$$\textbf{MEX}$$$ and sum of $$$\textbf{MEX}$$$ less.
In the end we put all elements that are not used in any order because $$$\textbf{MEX}$$$ will not change and will still be maximal.