1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Cookies
Contest: Codeforces Beta Round 94 (Div. 2 Only)
Difficulty rating: 900
Tags: implementation

Olga came to visit the twins Anna and Maria and saw that they have many cookies. The cookies are distributed into bags. As there are many cookies, Olga decided that it's no big deal if she steals a bag. However, she doesn't want the sisters to quarrel because of nothing when they divide the cookies. That's why Olga wants to steal a bag with cookies so that the number of cookies in the remaining bags was even, that is, so that Anna and Maria could evenly divide it into two (even 0 remaining cookies will do, just as any other even number). How many ways there are to steal exactly one cookie bag so that the total number of cookies in the remaining bags was even?

Input format:
The first line contains the only integer n (1 ≤ n ≤ 100) — the number of cookie bags Anna and Maria have. The second line contains n integers ai (1 ≤ ai ≤ 100) — the number of cookies in the i-th bag.

Output format:
Print in the only line the only number — the sought number of ways. If there are no such ways print 0.

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

Note:
In the first sample Olga should take the only bag so that the twins ended up with the even number of cookies.

In the second sample Olga can take any of five bags with two cookies or any of three bags with four cookies — 5 + 3 = 8 ways in total.

In the third sample, no matter which bag with two cookies Olga chooses, the twins are left with 2 * 9 + 99 = 117 cookies. Thus, Olga has only one option: to take the bag with 99 cookies.

Example input:
1
1

Example output:
1

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

Example output:
8

Editorial:
Students and Shoelaces
Contest: Codeforces Beta Round 94 (Div. 2 Only)
Difficulty rating: 1200
Tags: brute force, dfs and similar, graphs, implementation

Anna and Maria are in charge of the math club for junior students. When the club gathers together, the students behave badly. They've brought lots of shoe laces to the club and got tied with each other. Specifically, each string ties together two students. Besides, if two students are tied, then the lace connects the first student with the second one as well as the second student with the first one.

To restore order, Anna and Maria do the following. First, for each student Anna finds out what other students he is tied to. If a student is tied to exactly one other student, Anna reprimands him. Then Maria gathers in a single group all the students who have been just reprimanded. She kicks them out from the club. This group of students immediately leaves the club. These students takes with them the laces that used to tie them. Then again for every student Anna finds out how many other students he is tied to and so on. And they do so until Anna can reprimand at least one student.

Determine how many groups of students will be kicked out of the club.

Input format:
The first line contains two integers n and m — the initial number of students and laces ($$1 \leq n \leq 100, 0 \leq m \leq \frac{n(n-1)}{2}$$). The students are numbered from 1 to n, and the laces are numbered from 1 to m. Next m lines each contain two integers a and b — the numbers of students tied by the i-th lace (1 ≤ a, b ≤ n, a ≠ b). It is guaranteed that no two students are tied with more than one lace. No lace ties a student to himself.

Output format:
Print the single number — the number of groups of students that will be kicked out from the club.

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

Note:
In the first sample Anna and Maria won't kick out any group of students — in the initial position every student is tied to two other students and Anna won't be able to reprimand anyone.

In the second sample four students are tied in a chain and two more are running by themselves. First Anna and Maria kick out the two students from both ends of the chain (1 and 4), then — two other students from the chain (2 and 3). At that the students who are running by themselves will stay in the club.

In the third sample Anna and Maria will momentarily kick out all students except for the fourth one and the process stops at that point. The correct answer is one.

Example input:
3 3
1 2
2 3
3 1

Example output:
0

Example input:
6 3
1 2
2 3
3 4

Example output:
2

Editorial:
Yet Another Dividing into Teams
Contest: Codeforces Round 595 (Div. 3)
Difficulty rating: 800
Tags: math

You are a coach of a group consisting of $$$n$$$ students. The $$$i$$$-th student has programming skill $$$a_i$$$. All students have distinct programming skills. You want to divide them into teams in such a way that:

- No two students $$$i$$$ and $$$j$$$ such that $$$|a_i - a_j| = 1$$$ belong to the same team (i.e. skills of each pair of students in the same team have the difference strictly greater than $$$1$$$);
- the number of teams is the minimum possible.

You have to answer $$$q$$$ independent queries.

Input format:
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 100$$$) — the number of queries. Then $$$q$$$ queries follow.

The first line of the query contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of students in the query. The second line of the query contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$, all $$$a_i$$$ are distinct), where $$$a_i$$$ is the programming skill of the $$$i$$$-th student.

Output format:
For each query, print the answer on it — the minimum number of teams you can form if no two students $$$i$$$ and $$$j$$$ such that $$$|a_i - a_j| = 1$$$ may belong to the same team (i.e. skills of each pair of students in the same team has the difference strictly greater than $$$1$$$)

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

Note:
In the first query of the example, there are $$$n=4$$$ students with the skills $$$a=[2, 10, 1, 20]$$$. There is only one restriction here: the $$$1$$$-st and the $$$3$$$-th students can't be in the same team (because of $$$|a_1 - a_3|=|2-1|=1$$$). It is possible to divide them into $$$2$$$ teams: for example, students $$$1$$$, $$$2$$$ and $$$4$$$ are in the first team and the student $$$3$$$ in the second team.

In the second query of the example, there are $$$n=2$$$ students with the skills $$$a=[3, 6]$$$. It is possible to compose just a single team containing both students.

Example input:
4
4
2 10 1 20
2
3 6
5
2 3 4 99 100
1
42

Example output:
2
1
2
1

Editorial:
The answer is always $$$1$$$ or $$$2$$$. Why it is so? Because if there is no such pair $$$i, j$$$ among all students that $$$|a_i - a_j| = 1$$$ then we can take all students into one team. Otherwise, we can divide them into two teams by their programming skill parity.
Books Exchange (easy version)
Contest: Codeforces Round 595 (Div. 3)
Difficulty rating: 1000
Tags: dsu, math

The only difference between easy and hard versions is constraints.

There are $$$n$$$ kids, each of them is reading a unique book. At the end of any day, the $$$i$$$-th kid will give his book to the $$$p_i$$$-th kid (in case of $$$i = p_i$$$ the kid will give his book to himself). It is guaranteed that all values of $$$p_i$$$ are distinct integers from $$$1$$$ to $$$n$$$ (i.e. $$$p$$$ is a permutation). The sequence $$$p$$$ doesn't change from day to day, it is fixed.

For example, if $$$n=6$$$ and $$$p=[4, 6, 1, 3, 5, 2]$$$ then at the end of the first day the book of the $$$1$$$-st kid will belong to the $$$4$$$-th kid, the $$$2$$$-nd kid will belong to the $$$6$$$-th kid and so on. At the end of the second day the book of the $$$1$$$-st kid will belong to the $$$3$$$-th kid, the $$$2$$$-nd kid will belong to the $$$2$$$-th kid and so on.

Your task is to determine the number of the day the book of the $$$i$$$-th child is returned back to him for the first time for every $$$i$$$ from $$$1$$$ to $$$n$$$.

Consider the following example: $$$p = [5, 1, 2, 4, 3]$$$. The book of the $$$1$$$-st kid will be passed to the following kids:

- after the $$$1$$$-st day it will belong to the $$$5$$$-th kid,
- after the $$$2$$$-nd day it will belong to the $$$3$$$-rd kid,
- after the $$$3$$$-rd day it will belong to the $$$2$$$-nd kid,
- after the $$$4$$$-th day it will belong to the $$$1$$$-st kid.

So after the fourth day, the book of the first kid will return to its owner. The book of the fourth kid will return to him for the first time after exactly one day.

You have to answer $$$q$$$ independent queries.

Input format:
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 200$$$) — the number of queries. Then $$$q$$$ queries follow.

The first line of the query contains one integer $$$n$$$ ($$$1 \le n \le 200$$$) — the number of kids in the query. The second line of the query contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$, all $$$p_i$$$ are distinct, i.e. $$$p$$$ is a permutation), where $$$p_i$$$ is the kid which will get the book of the $$$i$$$-th kid.

Output format:
For each query, print the answer on it: $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, where $$$a_i$$$ is the number of the day the book of the $$$i$$$-th child is returned back to him for the first time in this query.

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

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

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

Editorial:
In this problem you just need to implement what is written in the problem statement. For the kid $$$i$$$ the following pseudocode will calculate the answer (indices of the array $$$p$$$ and its values are $$$0$$$-indexed):
Good Numbers (easy version)
Contest: Codeforces Round 595 (Div. 3)
Difficulty rating: 1300
Tags: brute force, greedy, implementation

The only difference between easy and hard versions is the maximum value of $$$n$$$.

You are given a positive integer number $$$n$$$. You really love good numbers so you want to find the smallest good number greater than or equal to $$$n$$$.

The positive integer is called good if it can be represented as a sum of distinct powers of $$$3$$$ (i.e. no duplicates of powers of $$$3$$$ are allowed).

For example:

- $$$30$$$ is a good number: $$$30 = 3^3 + 3^1$$$,
- $$$1$$$ is a good number: $$$1 = 3^0$$$,
- $$$12$$$ is a good number: $$$12 = 3^2 + 3^1$$$,
- but $$$2$$$ is not a good number: you can't represent it as a sum of distinct powers of $$$3$$$ ($$$2 = 3^0 + 3^0$$$),
- $$$19$$$ is not a good number: you can't represent it as a sum of distinct powers of $$$3$$$ (for example, the representations $$$19 = 3^2 + 3^2 + 3^0 = 3^2 + 3^1 + 3^1 + 3^1 + 3^0$$$ are invalid),
- $$$20$$$ is also not a good number: you can't represent it as a sum of distinct powers of $$$3$$$ (for example, the representation $$$20 = 3^2 + 3^2 + 3^0 + 3^0$$$ is invalid).

Note, that there exist other representations of $$$19$$$ and $$$20$$$ as sums of powers of $$$3$$$ but none of them consists of distinct powers of $$$3$$$.

For the given positive integer $$$n$$$ find such smallest $$$m$$$ ($$$n \le m$$$) that $$$m$$$ is a good number.

You have to answer $$$q$$$ independent queries.

Input format:
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 500$$$) — the number of queries. Then $$$q$$$ queries follow.

The only line of the query contains one integer $$$n$$$ ($$$1 \le n \le 10^4$$$).

Output format:
For each query, print such smallest integer $$$m$$$ (where $$$n \le m$$$) that $$$m$$$ is a good number.

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

Example input:
7
1
2
6
13
14
3620
10000

Example output:
1
3
9
13
27
6561
19683

Editorial:
As you can see from the example, the maximum answer doesn't exceed $$$2 \cdot 10^4$$$. So we can run some precalculation before all queries, which will find all good numbers less than $$$2 \cdot 10^4$$$. The number is good if it has no $$$2$$$ in the ternary numeral system. When you read the next query, you can increase $$$n$$$ until you find some precalculated good number. Time complexity is $$$O(nq + n \log n)$$$.
You also can implement the solution which doesn't use any precalculations and just increase $$$n$$$ each time in each query and checks if the number is good inside this loop. Then time complexity will be $$$O(n q \log n)$$$.
Good Numbers (hard version)
Contest: Codeforces Round 595 (Div. 3)
Difficulty rating: 1500
Tags: binary search, greedy, math, meet-in-the-middle

The only difference between easy and hard versions is the maximum value of $$$n$$$.

You are given a positive integer number $$$n$$$. You really love good numbers so you want to find the smallest good number greater than or equal to $$$n$$$.

The positive integer is called good if it can be represented as a sum of distinct powers of $$$3$$$ (i.e. no duplicates of powers of $$$3$$$ are allowed).

For example:

- $$$30$$$ is a good number: $$$30 = 3^3 + 3^1$$$,
- $$$1$$$ is a good number: $$$1 = 3^0$$$,
- $$$12$$$ is a good number: $$$12 = 3^2 + 3^1$$$,
- but $$$2$$$ is not a good number: you can't represent it as a sum of distinct powers of $$$3$$$ ($$$2 = 3^0 + 3^0$$$),
- $$$19$$$ is not a good number: you can't represent it as a sum of distinct powers of $$$3$$$ (for example, the representations $$$19 = 3^2 + 3^2 + 3^0 = 3^2 + 3^1 + 3^1 + 3^1 + 3^0$$$ are invalid),
- $$$20$$$ is also not a good number: you can't represent it as a sum of distinct powers of $$$3$$$ (for example, the representation $$$20 = 3^2 + 3^2 + 3^0 + 3^0$$$ is invalid).

Note, that there exist other representations of $$$19$$$ and $$$20$$$ as sums of powers of $$$3$$$ but none of them consists of distinct powers of $$$3$$$.

For the given positive integer $$$n$$$ find such smallest $$$m$$$ ($$$n \le m$$$) that $$$m$$$ is a good number.

You have to answer $$$q$$$ independent queries.

Input format:
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 500$$$) — the number of queries. Then $$$q$$$ queries follow.

The only line of the query contains one integer $$$n$$$ ($$$1 \le n \le 10^{18}$$$).

Output format:
For each query, print such smallest integer $$$m$$$ (where $$$n \le m$$$) that $$$m$$$ is a good number.

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

Example input:
8
1
2
6
13
14
3620
10000
1000000000000000000

Example output:
1
3
9
13
27
6561
19683
1350851717672992089

Editorial:
Let's see the representation of $$$n$$$ in the ternary numeral system. If it has no twos, then the answer is $$$n$$$. Otherwise, let $$$pos_2$$$ be the maximum position of $$$2$$$ in the ternary representation. Then we obviously need to replace it with $$$0$$$ and add some power of three to the right from it. Let $$$pos_0$$$ be the leftmost position of $$$0$$$ to the right from $$$pos_2$$$. We can add $$$3^{pos_0}$$$ and replace all digits from the position $$$pos_0 - 1$$$ to the position $$$0$$$ with $$$0$$$. Then the resulting number will be good because we replaced all twos with zeros and the minimum because, in fact, we added only one power of three and this power is the minimum one we could add.
Time complexity is $$$O(\log n)$$$ per query.
Too Many Segments (easy version)
Contest: Codeforces Round 595 (Div. 3)
Difficulty rating: 1800
Tags: greedy

The only difference between easy and hard versions is constraints.

You are given $$$n$$$ segments on the coordinate axis $$$OX$$$. Segments can intersect, lie inside each other and even coincide. The $$$i$$$-th segment is $$$[l_i; r_i]$$$ ($$$l_i \le r_i$$$) and it covers all integer points $$$j$$$ such that $$$l_i \le j \le r_i$$$.

The integer point is called bad if it is covered by strictly more than $$$k$$$ segments.

Your task is to remove the minimum number of segments so that there are no bad points at all.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 200$$$) — the number of segments and the maximum number of segments by which each integer point can be covered.

The next $$$n$$$ lines contain segments. The $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 200$$$) — the endpoints of the $$$i$$$-th segment.

Output format:
In the first line print one integer $$$m$$$ ($$$0 \le m \le n$$$) — the minimum number of segments you need to remove so that there are no bad points.

In the second line print $$$m$$$ distinct integers $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i \le n$$$) — indices of segments you remove in any order. If there are multiple answers, you can print any of them.

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

Example input:
7 2
11 11
9 11
7 8
8 9
7 8
9 11
7 9

Example output:
3
1 4 7

Example input:
5 1
29 30
30 30
29 29
28 30
30 30

Example output:
3
1 2 4

Editorial:
In this problem, the following greedy solution works: let's find the leftmost point covered by more than $$$k$$$ segments. We should fix it somehow. How to do it? Let's find some segment that was not removed already, it covers this point and its rightmost end is maximum possible, and remove this segment.
You can implement it in any time you want, even in $$$O(n^3)$$$ naively.
Chores
Contest: Educational Codeforces Round 30
Difficulty rating: 800
Tags: implementation

Luba has to do n chores today. i-th chore takes ai units of time to complete. It is guaranteed that for every $$i \in [2..n]$$ the condition ai ≥ ai - 1 is met, so the sequence is sorted.

Also Luba can work really hard on some chores. She can choose not more than k any chores and do each of them in x units of time instead of ai ($${ x < \operatorname* { m i n } _ { i = 1 } ^ { n } a _ { i } }$$).

Luba is very responsible, so she has to do all n chores, and now she wants to know the minimum time she needs to do everything. Luba cannot do two chores simultaneously.

Input format:
The first line contains three integers n, k, x (1 ≤ k ≤ n ≤ 100, 1 ≤ x ≤ 99) — the number of chores Luba has to do, the number of chores she can do in x units of time, and the number x itself.

The second line contains n integer numbers ai (2 ≤ ai ≤ 100) — the time Luba has to spend to do i-th chore.

It is guaranteed that $${ x < \operatorname* { m i n } _ { i = 1 } ^ { n } a _ { i } }$$, and for each $$i \in [2..n]$$ ai ≥ ai - 1.

Output format:
Print one number — minimum time Luba needs to do all n chores.

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

Note:
In the first example the best option would be to do the third and the fourth chore, spending x = 2 time on each instead of a3 and a4, respectively. Then the answer is 3 + 6 + 2 + 2 = 13.

In the second example Luba can choose any two chores to spend x time on them instead of ai. So the answer is 100·3 + 2·1 = 302.

Example input:
4 2 2
3 6 7 10

Example output:
13

Example input:
5 2 1
100 100 100 100 100

Example output:
302

Editorial:
Since $${ x < \operatorname* { m i n } _ { i = 1 } ^ { n } a _ { i } }$$, it is better to do exactly k chores in time x. And since we need to minimize total time we need to spend, it's better to speed up the "longest" chores. So the answer is $${ k \cdot x + \sum _ { i = 1 } ^ { n - k } a _ { i } }$$.
Balanced Substring
Contest: Educational Codeforces Round 30
Difficulty rating: 1500
Tags: dp, implementation

You are given a string s consisting only of characters 0 and 1. A substring [l, r] of s is a string slsl + 1sl + 2... sr, and its length equals to r - l + 1. A substring is called balanced if the number of zeroes (0) equals to the number of ones in this substring.

You have to determine the length of the longest balanced substring of s.

Input format:
The first line contains n (1 ≤ n ≤ 100000) — the number of characters in s.

The second line contains a string s consisting of exactly n characters. Only characters 0 and 1 can appear in s.

Output format:
If there is no non-empty balanced substring in s, print 0. Otherwise, print the length of the longest balanced substring.

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

Note:
In the first example you can choose the substring [3, 6]. It is balanced, and its length is 4. Choosing the substring [2, 5] is also possible.

In the second example it's impossible to find a non-empty balanced substring.

Example input:
8
11010111

Example output:
4

Example input:
3
111

Example output:
0

Editorial:
Let cnt0(i) be the number of zeroes and cnt1(i) — the number of ones on prefix of length i; also let balance(i) = cnt0(i) - cnt1(i) (i ≥ 0). The interesting property of balance is that the substring [x, y] is balanced iff balance(y) = balance(x - 1). That leads to a solution: for each value of balance maintain the minimum i where this balance is obtained (let it be called minIndex), and for each index i in the string update answer with i - minIndex(balance(i)).
Strange Game On Matrix
Contest: Educational Codeforces Round 30
Difficulty rating: 1600
Tags: greedy, two pointers

Ivan is playing a strange game.

He has a matrix a with n rows and m columns. Each element of the matrix is equal to either 0 or 1. Rows and columns are 1-indexed. Ivan can replace any number of ones in this matrix with zeroes. After that, his score in the game will be calculated as follows:

1. Initially Ivan's score is 0;
2. In each column, Ivan will find the topmost 1 (that is, if the current column is j, then he will find minimum i such that ai, j = 1). If there are no 1's in the column, this column is skipped;
3. Ivan will look at the next min(k, n - i + 1) elements in this column (starting from the element he found) and count the number of 1's among these elements. This number will be added to his score.

Of course, Ivan wants to maximize his score in this strange game. Also he doesn't want to change many elements, so he will replace the minimum possible number of ones with zeroes. Help him to determine the maximum possible score he can get and the minimum possible number of replacements required to achieve that score.

Input format:
The first line contains three integer numbers n, m and k (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100).

Then n lines follow, i-th of them contains m integer numbers — the elements of i-th row of matrix a. Each number is either 0 or 1.

Output format:
Print two numbers: the maximum possible score Ivan can get and the minimum number of replacements required to get this score.

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

Note:
In the first example Ivan will replace the element a1, 2.

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

Example output:
4 1

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

Example output:
2 0

Editorial:
Let's notice that this task can be solved independently for each column, total result will be the sum of results for columns.
The ones you should remove will always be the top ones in column. It makes no profit to erase some one while there are still ones on top of it, score won't become higher.
Go from the top of the column to the bottom and recalculate the score after removing every one. Take the first position of the maximal score and update global answer with it.
Overall complexity: O(n3). O(n2) can be achieved with partial sums.