1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Sasha and the Drawing
Contest: Codeforces Round 926 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, greedy, math

Even in kindergarten, Sasha liked a girl. Therefore, he wanted to give her a drawing and attract her attention.

As a drawing, he decided to draw a square grid of size $$$n \times n$$$, in which some cells are colored. But coloring the cells is difficult, so he wants to color as few cells as possible. But at the same time, he wants at least $$$k$$$ diagonals to have at least one colored cell. Note that the square grid of size $$$n \times n$$$ has a total of $$$4n - 2$$$ diagonals.

Help little Sasha to make the girl fall in love with him and tell him the minimum number of cells he needs to color.

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

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 10^8$$$, $$$1 \leq k \leq 4n - 2$$$) — the size of the square grid and the minimum number of diagonals in which there should be at least one colored cell.

Output format:
For each test case, output a single integer — the minimum number of cells that need to be colored.

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

Note:
In the pictures below, the colored cells are marked in black, and all diagonals are marked in purple.

In the first test case, you can color $$$2$$$ cells so that $$$4$$$ diagonals contain at least one colored cell:

In the third test case, you can color $$$6$$$ cells so that all $$$10$$$ diagonals contain at least one colored cell:

Example input:
7
3 4
3 3
3 10
3 9
4 7
7 11
2 3

Example output:
2
2
6
5
4
6
2

Editorial:
Sasha and the Casino
Contest: Codeforces Round 926 (Div. 2)
Difficulty rating: 1400
Tags: binary search, brute force, constructive algorithms, games, greedy, math

Sasha decided to give his girlfriend the best handbag, but unfortunately for Sasha, it is very expensive. Therefore, Sasha wants to earn it. After looking at earning tips on the internet, he decided to go to the casino.

Sasha knows that the casino operates under the following rules. If Sasha places a bet of $$$y$$$ coins (where $$$y$$$ is a positive integer), then in case of winning, he will receive $$$y \cdot k$$$ coins (i.e., his number of coins will increase by $$$y \cdot (k - 1)$$$). And in case of losing, he will lose the entire bet amount (i.e., his number of coins will decrease by $$$y$$$).

Note that the bet amount must always be a positive ($$$> 0$$$) integer and cannot exceed Sasha's current number of coins.

Sasha also knows that there is a promotion at the casino: he cannot lose more than $$$x$$$ times in a row.

Initially, Sasha has $$$a$$$ coins. He wonders whether he can place bets such that he is guaranteed to win any number of coins. In other words, is it true that for any integer $$$n$$$, Sasha can make bets so that for any outcome that does not contradict the rules described above, at some moment of time he will have at least $$$n$$$ coins.

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

The single line of each test case contains three integers $$$k, x$$$ and $$$a$$$ ($$$2 \leq k \leq 30$$$, $$$1 \leq x \leq 100$$$, $$$1 \leq a \leq 10^9$$$) — the number of times the bet is increased in case of a win, the maximum number of consecutive losses, and the initial number of coins Sasha has.

Output format:
For each test case, output "YES" (without quotes) if Sasha can achieve it and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, the strings "yEs", "yes" and "Yes" will be recognized as a positive answer).

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

Note:
In the first test case, Sasha can proceed as follows:

- If Sasha places a bet for the first time or if he won the previous bet, then he places $$$1$$$ coin.
- If Sasha lost the previous bet, then he places $$$2$$$ coins.

Note that Sasha cannot lose more than once in a row.

It can be proven that with this strategy, Sasha can obtain as many coins as he wants.

In the second test case, Sasha can only place $$$1$$$ coin for the first time. But in case of a loss, he will not be able to place any more bets, so he will not be able to guarantee having as many coins as he wants.

Example input:
9
2 1 7
2 1 1
2 3 15
3 3 6
4 4 5
5 4 7
4 88 1000000000
25 69 231
13 97 18806

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

Editorial:
Sasha and a Walk in the City
Contest: Codeforces Round 926 (Div. 2)
Difficulty rating: 1900
Tags: combinatorics, dp, math, trees

Sasha wants to take a walk with his girlfriend in the city. The city consists of $$$n$$$ intersections, numbered from $$$1$$$ to $$$n$$$. Some of them are connected by roads, and from any intersection, there is exactly one simple path$$$^{\dagger}$$$ to any other intersection. In other words, the intersections and the roads between them form a tree.

Some of the intersections are considered dangerous. Since it is unsafe to walk alone in the city, Sasha does not want to visit three or more dangerous intersections during the walk.

Sasha calls a set of intersections good if the following condition is satisfied:

- If in the city only the intersections contained in this set are dangerous, then any simple path in the city contains no more than two dangerous intersections.

However, Sasha does not know which intersections are dangerous, so he is interested in the number of different good sets of intersections in the city. Since this number can be very large, output it modulo $$$998\,244\,353$$$.

$$$^{\dagger}$$$A simple path is a path that passes through each intersection at most once.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \leq 3 \cdot 10^5$$$) — the number of intersections in the city.

The next $$$(n - 1)$$$ lines describe the roads. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \ne v_i$$$) — the numbers of the intersections connected by the $$$i$$$-th road.

It is guaranteed that these roads form a tree.

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

Output format:
For each test case, output a single integer — the number of good sets of intersections modulo $$$998\,244\,353$$$.

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

Note:
In the first test case, there are $$$2^3 = 8$$$ sets of intersections. All of them are good, except for the set $$$\{1, 2, 3\}$$$, because if intersections $$$1, 2$$$, and $$$3$$$ are dangerous, then the simple path $$$1 - 2 - 3$$$ contains $$$3$$$ dangerous intersections. Thus, there are $$$7$$$ good sets.

In the second test case, there are $$$2^4 = 16$$$ sets of intersections. Among them, the sets $$$\{1, 2, 3, 4\}$$$, $$$\{1, 2, 3\}$$$, $$$\{1, 3, 4\}$$$, $$$\{2, 3, 4\}$$$ are not good. Thus, there are a total of $$$12$$$ good sets. The city layout is shown below:

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

Example output:
7
12
16
11

Editorial:
Sasha and the Happy Tree Cutting
Contest: Codeforces Round 926 (Div. 2)
Difficulty rating: 2300
Tags: bitmasks, brute force, dfs and similar, dp, graphs, greedy, math, trees

Sasha was given a tree$$$^{\dagger}$$$ with $$$n$$$ vertices as a prize for winning yet another competition. However, upon returning home after celebrating his victory, he noticed that some parts of the tree were missing. Sasha remembers that he colored some of the edges of this tree. He is certain that for any of the $$$k$$$ pairs of vertices $$$(a_1, b_1), \ldots, (a_k, b_k)$$$, he colored at least one edge on the simple path$$$^{\ddagger}$$$ between vertices $$$a_i$$$ and $$$b_i$$$.

Sasha does not remember how many edges he exactly colored, so he asks you to tell him the minimum number of edges he could have colored to satisfy the above condition.

$$$^{\dagger}$$$A tree is an undirected connected graph without cycles.

$$$^{\ddagger}$$$A simple path is a path that passes through each vertex at most once.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the number of vertices in the tree.

The next $$$(n - 1)$$$ lines describe the edges of the tree. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \ne v_i$$$) — the numbers of the vertices connected by the $$$i$$$-th edge.

The next line contains a single integer $$$k$$$ ($$$1 \leq k \leq 20$$$) — the number of pairs of vertices between which Sasha colored at least one edge on a simple path.

The next $$$k$$$ lines describe pairs. The $$$j$$$-th line contains two integers $$$a_j$$$ and $$$b_j$$$ ($$$1 \leq a_j, b_j \leq n, a_j \neq b_j$$$) — the vertices in the $$$j$$$-th pair.

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

Output format:
For each test case, output a single integer — the minimum number of edges Sasha could have colored.

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

Note:
In the first test case, Sasha could have colored only one edge $$$(1, 2)$$$. Then, there would be at least one colored edge on the simple path between vertices $$$1$$$ and $$$3$$$, and vertices $$$4$$$ and $$$1$$$.

In the second test case, Sasha could have colored the edges $$$(1, 6)$$$ and $$$(1, 3)$$$.

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

Example output:
1
2
4

Editorial:
Selling Hamburgers
Contest: Kotlin Heroes 5: ICPC Round
Difficulty rating: 800
Tags: *special

There are $$$n$$$ customers in the cafeteria. Each of them wants to buy a hamburger. The $$$i$$$-th customer has $$$a_i$$$ coins, and they will buy a hamburger if it costs at most $$$a_i$$$ coins.

Suppose the cost of the hamburger is $$$m$$$. Then the number of coins the cafeteria earns is $$$m$$$ multiplied by the number of people who buy a hamburger if it costs $$$m$$$. Your task is to calculate the maximum number of coins the cafeteria can earn.

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

Each test case consists of two lines. The first line contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of customers.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$), where $$$a_i$$$ is the number of coins the $$$i$$$-th customer has.

Output format:
For each test case, print one integer — the maximum number of coins the cafeteria can earn.

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

Note:
Explanations for the test cases of the example:

1. the best price for the hamburger is $$$m = 1$$$, so $$$3$$$ hamburgers are bought, and the cafeteria earns $$$3$$$ coins;
2. the best price for the hamburger is $$$m = 4$$$, so $$$1$$$ hamburger is bought, and the cafeteria earns $$$4$$$ coins;
3. the best price for the hamburger is $$$m = 2$$$, so $$$3$$$ hamburgers are bought, and the cafeteria earns $$$6$$$ coins;
4. the best price for the hamburger is $$$m = 4$$$, so $$$5$$$ hamburgers are bought, and the cafeteria earns $$$20$$$ coins;
5. the best price for the hamburger is $$$m = 10^{12}$$$, so $$$1$$$ hamburger is bought, and the cafeteria earns $$$10^{12}$$$ coins;
6. the best price for the hamburger is $$$m = 10^{12} - 1$$$, so $$$2$$$ hamburgers are bought, and the cafeteria earns $$$2 \cdot 10^{12} - 2$$$ coins.

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

Example output:
3
4
6
20
1000000000000
1999999999998

Editorial:
The main idea is that $$$m$$$ should be equal to one of the values $$$a_i$$$ (because if it is different from all of the $$$a_i$$$, then we can increase it by $$$1$$$, and the answer becomes greater). So, we need to iterate on the value of $$$m$$$ from the array $$$a_i$$$, and for every such value, calculate the answer. The solution can be implemented in $$$O(n^2)$$$ or in $$$O(n \log n)$$$.
Note that the values in the input and the output may be large, so you have to use $$$64$$$-bit data types to solve this problem.
Polycarp and the Language of Gods
Contest: Kotlin Heroes 5: ICPC Round
Difficulty rating: 1400
Tags: *special, implementation, two pointers

Polycarp has just finished writing down the lecture on elvish languages. The language this week was "VwV" (pronounced as "uwu"). The writing system of this language consists of only two lowercase Latin letters: 'v' and 'w'.

Unfortunately, Polycarp has written all the lecture in cursive and without any spaces, so the notes look like a neverending sequence of squiggles. To be exact, Polycarp can't tell 'w' apart from 'vv' in his notes as both of them consist of the same two squiggles.

Luckily, his brother Monocarp has better writing habits, so Polycarp managed to take his notes and now wants to make his own notes more readable. To do that he can follow the notes of Monocarp and underline some letters in his own notes in such a way that there is no more ambiguity. If he underlines a 'v', then it can't be mistaken for a part of some 'w', and if the underlines a 'w', then it can't be mistaken for two adjacent letters 'v'.

What is the minimum number of letters Polycarp should underline to make his notes unambiguous?

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

Each of the next $$$t$$$ lines contains a non-empty string in VwV language, which consists only of lowercase Latin letters 'v' and 'w'. The length of the string does not exceed $$$100$$$.

Output format:
For each testcase print a single integer: the minimum number of letters Polycarp should underline so that there is no ambiguity in his notes.

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

Note:
In the first testcase it's enough to underline any of the two letters 'v'.

In the second testcase the letter 'v' is not ambiguous by itself already, so you don't have to underline anything.

In the third testcase you have to underline 'w', so that you don't mix it up with two letters 'v'.

In the fourth testcase you can underline 'w' to avoid all the ambiguity.

In the fifth testcase you can underline both letters 'w' and any of the two letters 'v' between them.

Example input:
5
vv
v
w
vwv
vwvvwv

Example output:
1
0
1
1
3

Editorial:
Underline every letter 'w', so that it can't be mistaken with 'vv'. The string splits into segments of letters 'v'. Out of each pair of consecutive letters 'v' at least one should be underlined. So for the minimum amount you can underline either all the odd positions of the segment or all the even ones. Thus, if the length of the segment is $$$len$$$, then $$$\lfloor \frac{len}{2} \rfloor$$$ underlined letters is enough.
Overall complexity: $$$O(n)$$$ per testcase.
Black Friday
Contest: Kotlin Heroes 5: ICPC Round
Difficulty rating: 1600
Tags: *special, implementation

There is a local shop in your area getting prepared for the great holiday of Black Friday. There are $$$n$$$ items with prices $$$p_1, p_2, \dots, p_n$$$ on the display. They are ordered by price, so $$$p_1 \le p_2 \le \dots \le p_n$$$.

The shop has a prechosen discount value $$$k$$$. The Black Friday discount is applied in the following way: for a single purchase of $$$x$$$ items, you get the cheapest $$$\lfloor \frac x k \rfloor$$$ items of them for free ($$$\lfloor \frac x k \rfloor$$$ is $$$x$$$ divided by $$$k$$$ rounded down to the nearest integer). You can include each item in your purchase no more than once.

For example, if there are items with prices $$$[1, 1, 2, 2, 2, 3, 4, 5, 6]$$$ in the shop, and you buy items with prices $$$[1, 2, 2, 4, 5]$$$, and $$$k = 2$$$, then you get the cheapest $$$\lfloor \frac 5 2 \rfloor = 2$$$ for free. They are items with prices $$$1$$$ and $$$2$$$.

So you, being the naive customer, don't care about how much money you spend. However, you want the total price of the items you get for free to be as large as possible.

What is the maximum total price of the items you can get for free on a single purchase?

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

Then the description of $$$t$$$ testcases follows.

The first line of each testcase contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 200$$$; $$$1 \le k \le n$$$) — the number of items in the shop and the discount value, respectively.

The second line of each testcase contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le 10^6$$$) — the prices of the items on the display of the shop. The items are ordered by their price, so $$$p_1 \le p_2 \le \dots \le p_n$$$.

Output format:
Print a single integer for each testcase: the maximum total price of the items you can get for free on a single purchase.

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

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

Example output:
7
4
6
7
1

Editorial:
Let's consider the most optimal set of items of some fixed size $$$x$$$. We want the cheapest items to be as expensive as possible, so it's easy to see that taking $$$x$$$ most expensive items overall works the best.
The other observation that makes it easier to code is that you only have to consider such $$$x$$$ that are multiples of $$$k$$$. If you take some $$$x$$$ that is not multiple of $$$k$$$, then you will only make $$$\lfloor \frac x k \rfloor$$$ cheapest items cheaper compared to the nearest multiple below it.
So the solution is to iterate over multiples of $$$k$$$ and choose the best answer of them.
Overall complexity: $$$O(n^2)$$$ per testcase.
Ilya and Bank Account
Contest: Codeforces Round 186 (Div. 2)
Difficulty rating: 900
Tags: implementation, number theory

Ilya is a very clever lion, he lives in an unusual city ZooVille. In this city all the animals have their rights and obligations. Moreover, they even have their own bank accounts. The state of a bank account is an integer. The state of a bank account can be a negative number. This means that the owner of the account owes the bank money.

Ilya the Lion has recently had a birthday, so he got a lot of gifts. One of them (the gift of the main ZooVille bank) is the opportunity to delete the last digit or the digit before last from the state of his bank account no more than once. For example, if the state of Ilya's bank account is -123, then Ilya can delete the last digit and get his account balance equal to -12, also he can remove its digit before last and get the account balance equal to -13. Of course, Ilya is permitted not to use the opportunity to delete a digit from the balance.

Ilya is not very good at math, and that's why he asks you to help him maximize his bank account. Find the maximum state of the bank account that can be obtained using the bank's gift.

Input format:
The single line contains integer n (10 ≤ |n| ≤ 109) — the state of Ilya's bank account.

Output format:
In a single line print an integer — the maximum state of the bank account that Ilya can get.

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

Note:
In the first test sample Ilya doesn't profit from using the present.

In the second test sample you can delete digit 1 and get the state of the account equal to 0.

Example input:
2230

Example output:
2230

Example input:
-10

Example output:
0

Editorial:
Ilya and Queries
Contest: Codeforces Round 186 (Div. 2)
Difficulty rating: 1100
Tags: dp, implementation

Ilya the Lion wants to help all his friends with passing exams. They need to solve the following problem to pass the IT exam.

You've got string s = s1s2... sn (n is the length of the string), consisting only of characters "." and "#" and m queries. Each query is described by a pair of integers li, ri (1 ≤ li < ri ≤ n). The answer to the query li, ri is the number of such integers i (li ≤ i < ri), that si = si + 1.

Ilya the Lion wants to help his friends but is there anyone to help him? Help Ilya, solve the problem.

Input format:
The first line contains string s of length n (2 ≤ n ≤ 105). It is guaranteed that the given string only consists of characters "." and "#".

The next line contains integer m (1 ≤ m ≤ 105) — the number of queries. Each of the next m lines contains the description of the corresponding query. The i-th line contains integers li, ri (1 ≤ li < ri ≤ n).

Output format:
Print m integers — the answers to the queries in the order in which they are given in the input.

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

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

Example output:
1
1
5
4

Example input:
#..###
5
1 3
5 6
1 5
3 6
3 4

Example output:
1
1
2
2
0

Editorial:
Ilya and Matrix
Contest: Codeforces Round 186 (Div. 2)
Difficulty rating: 1400
Tags: constructive algorithms, greedy, implementation, sortings

Ilya is a very good-natured lion. He likes maths. Of all mathematical objects, his favourite one is matrices. Now he's faced a complicated matrix problem he needs to solve.

He's got a square 2n × 2n-sized matrix and 4n integers. You need to arrange all these numbers in the matrix (put each number in a single individual cell) so that the beauty of the resulting matrix with numbers is maximum.

The beauty of a 2n × 2n-sized matrix is an integer, obtained by the following algorithm:

1. Find the maximum element in the matrix. Let's denote it as m.
2. If n = 0, then the beauty of the matrix equals m. Otherwise, a matrix can be split into 4 non-intersecting 2n - 1 × 2n - 1-sized submatrices, then the beauty of the matrix equals the sum of number m and other four beauties of the described submatrices.

As you can see, the algorithm is recursive.

Help Ilya, solve the problem and print the resulting maximum beauty of the matrix.

Input format:
The first line contains integer 4n (1 ≤ 4n ≤ 2·106). The next line contains 4n integers ai (1 ≤ ai ≤ 109) — the numbers you need to arrange in the 2n × 2n-sized matrix.

Output format:
On a single line print the maximum value of the beauty of the described matrix.

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: 1.0 s
Memory limit: 256.0 MB

Note:
Consider the second sample. You need to arrange the numbers in the matrix as follows:

Then the beauty of the matrix will equal: 4 + 1 + 2 + 3 + 4 = 14.

Example input:
1
13

Example output:
13

Example input:
4
1 2 3 4

Example output:
14

Editorial: