1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Pasha and Pipe
Contest: Codeforces Round 293 (Div. 2)
Difficulty rating: 2300
Tags: binary search, brute force, combinatorics, dp, implementation

On a certain meeting of a ruling party "A" minister Pavel suggested to improve the sewer system and to create a new pipe in the city.

The city is an n × m rectangular squared field. Each square of the field is either empty (then the pipe can go in it), or occupied (the pipe cannot go in such square). Empty squares are denoted by character '.', occupied squares are denoted by character '#'.

The pipe must meet the following criteria:

- the pipe is a polyline of width 1,
- the pipe goes in empty squares,
- the pipe starts from the edge of the field, but not from a corner square,
- the pipe ends at the edge of the field but not in a corner square,
- the pipe has at most 2 turns (90 degrees),
- the border squares of the field must share exactly two squares with the pipe,
- if the pipe looks like a single segment, then the end points of the pipe must lie on distinct edges of the field,
- for each non-border square of the pipe there are exacly two side-adjacent squares that also belong to the pipe,
- for each border square of the pipe there is exactly one side-adjacent cell that also belongs to the pipe.

Here are some samples of allowed piping routes:

Here are some samples of forbidden piping routes:

In these samples the pipes are represented by characters ' * '.

You were asked to write a program that calculates the number of distinct ways to make exactly one pipe in the city.

The two ways to make a pipe are considered distinct if they are distinct in at least one square.

Input format:
The first line of the input contains two integers n, m (2 ≤ n, m ≤ 2000) — the height and width of Berland map.

Each of the next n lines contains m characters — the map of the city.

If the square of the map is marked by character '.', then the square is empty and the pipe can through it.

If the square of the map is marked by character '#', then the square is full and the pipe can't through it.

Output format:
In the first line of the output print a single integer — the number of distinct ways to create a pipe.

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

Note:
In the first sample there are 3 ways to make a pipe (the squares of the pipe are marked by characters ' * '):

Example input:
3 3
...
..#
...

Example output:
3

Example input:
4 2
..
..
..
..

Example output:
2

Editorial:
Splits
Contest: Tinkoff Internship Warmup Round 2018 and Codeforces Round 475 (Div. 2)
Difficulty rating: 800
Tags: math

Let's define a split of $$$n$$$ as a nonincreasing sequence of positive integers, the sum of which is $$$n$$$.

For example, the following sequences are splits of $$$8$$$: $$$[4, 4]$$$, $$$[3, 3, 2]$$$, $$$[2, 2, 1, 1, 1, 1]$$$, $$$[5, 2, 1]$$$.

The following sequences aren't splits of $$$8$$$: $$$[1, 7]$$$, $$$[5, 4]$$$, $$$[11, -3]$$$, $$$[1, 1, 4, 1, 1]$$$.

The weight of a split is the number of elements in the split that are equal to the first element. For example, the weight of the split $$$[1, 1, 1, 1, 1]$$$ is $$$5$$$, the weight of the split $$$[5, 5, 3, 3, 3]$$$ is $$$2$$$ and the weight of the split $$$[9]$$$ equals $$$1$$$.

For a given $$$n$$$, find out the number of different weights of its splits.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 10^9$$$).

Output format:
Output one integer — the answer to the problem.

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

Note:
In the first sample, there are following possible weights of splits of $$$7$$$:

Weight 1: [$$$\textbf 7$$$]

Weight 2: [$$$\textbf 3$$$, $$$\textbf 3$$$, 1]

Weight 3: [$$$\textbf 2$$$, $$$\textbf 2$$$, $$$\textbf 2$$$, 1]

Weight 7: [$$$\textbf 1$$$, $$$\textbf 1$$$, $$$\textbf 1$$$, $$$\textbf 1$$$, $$$\textbf 1$$$, $$$\textbf 1$$$, $$$\textbf 1$$$]

Example input:
7

Example output:
4

Example input:
8

Example output:
5

Editorial:
There are 2 cases:
If weight of the split equals $$$n$$$, then the split consist of ones. Here we have only 1 option.
Else maximum number in the split is more then 1. Then we can replace all maximum numbers with twos and the rest we split into ones and weight will be the same. So, here we have $$$\frac{n}{2}$$$ options.
Answer for this problem is $$$\frac{n}{2}$$$ + 1.
Messages
Contest: Tinkoff Internship Warmup Round 2018 and Codeforces Round 475 (Div. 2)
Difficulty rating: 1300
Tags: math

There are n incoming messages for Vasya. The i-th message is going to be received after ti minutes. Each message has a cost, which equals to A initially. After being received, the cost of a message decreases by B each minute (it can become negative). Vasya can read any message after receiving it at any moment of time. After reading the message, Vasya's bank account receives the current cost of this message. Initially, Vasya's bank account is at 0.

Also, each minute Vasya's bank account receives C·k, where k is the amount of received but unread messages.

Vasya's messages are very important to him, and because of that he wants to have all messages read after T minutes.

Determine the maximum amount of money Vasya's bank account can hold after T minutes.

Input format:
The first line contains five integers n, A, B, C and T (1 ≤ n, A, B, C, T ≤ 1000).

The second string contains n integers ti (1 ≤ ti ≤ T).

Output format:
Output one integer  — the answer to the problem.

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

Note:
In the first sample the messages must be read immediately after receiving, Vasya receives A points for each message, n·A = 20 in total.

In the second sample the messages can be read at any integer moment.

In the third sample messages must be read at the moment T. This way Vasya has 1, 2, 3, 4 and 0 unread messages at the corresponding minutes, he gets 40 points for them. When reading messages, he receives (5 - 4·3) + (5 - 3·3) + (5 - 2·3) + (5 - 1·3) + 5 =  - 5 points. This is 35 in total.

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

Example output:
20

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

Example output:
15

Editorial:
Adding C·k to account is equivalent to adding C to prices of all come, but not read messages. Then after every minute to every unread messages adds C - B. If C - B is positive, then answer is maximum when we read all messages at the time T. Otherwise we should read every message at the time it comes.
Three Piles of Candies
Contest: Codeforces Round 575 (Div. 3)
Difficulty rating: 800
Tags: brute force, constructive algorithms, math

Alice and Bob have received three big piles of candies as a gift. Now they want to divide these candies as fair as possible. To do this, Alice takes one pile of candies, then Bob takes one of the other two piles. The last pile is split between Alice and Bob as they want: for example, it is possible that Alice takes the whole pile, and Bob gets nothing from it.

After taking the candies from the piles, if Alice has more candies than Bob, she discards some candies so that the number of candies she has is equal to the number of candies Bob has. Of course, Bob does the same if he has more candies.

Alice and Bob want to have as many candies as possible, and they plan the process of dividing candies accordingly. Please calculate the maximum number of candies Alice can have after this division process (of course, Bob will have the same number of candies).

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

Let's see the following example: $$$[1, 3, 4]$$$. Then Alice can choose the third pile, Bob can take the second pile, and then the only candy from the first pile goes to Bob — then Alice has $$$4$$$ candies, and Bob has $$$4$$$ candies.

Another example is $$$[1, 10, 100]$$$. Then Alice can choose the second pile, Bob can choose the first pile, and candies from the third pile can be divided in such a way that Bob takes $$$54$$$ candies, and Alice takes $$$46$$$ candies. Now Bob has $$$55$$$ candies, and Alice has $$$56$$$ candies, so she has to discard one candy — and after that, she has $$$55$$$ candies too.

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

The only line of the query contains three integers $$$a, b$$$ and $$$c$$$ ($$$1 \le a, b, c \le 10^{16}$$$) — the number of candies in the first, second and third piles correspondingly.

Output format:
Print $$$q$$$ lines. The $$$i$$$-th line should contain the answer for the $$$i$$$-th query — the maximum number of candies Alice can have after the division, if both Alice and Bob act optimally (of course, Bob will have the same number of candies).

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

Example input:
4
1 3 4
1 10 100
10000000000000000 10000000000000000 10000000000000000
23 34 45

Example output:
4
55
15000000000000000
51

Editorial:
The answer is always $$$\lfloor\frac{a + b + c}{2}\rfloor$$$. Let's understand why it is so. Let $$$a \le b \le c$$$. Then let Bob take the pile with $$$a$$$ candies and Alice take the pile with $$$b$$$ candies. Then because of $$$b \le a + c$$$ we can see that Bob's pile always can reach size of Alice's pile (and remaining candies can be divided between them fairly except one candy if $$$a + b + c$$$ is odd).
RGB Substring (easy version)
Contest: Codeforces Round 575 (Div. 3)
Difficulty rating: 1500
Tags: implementation

The only difference between easy and hard versions is the size of the input.

You are given a string $$$s$$$ consisting of $$$n$$$ characters, each character is 'R', 'G' or 'B'.

You are also given an integer $$$k$$$. Your task is to change the minimum number of characters in the initial string $$$s$$$ so that after the changes there will be a string of length $$$k$$$ that is a substring of $$$s$$$, and is also a substring of the infinite string "RGBRGBRGB ...".

A string $$$a$$$ is a substring of string $$$b$$$ if there exists a positive integer $$$i$$$ such that $$$a_1 = b_i$$$, $$$a_2 = b_{i + 1}$$$, $$$a_3 = b_{i + 2}$$$, ..., $$$a_{|a|} = b_{i + |a| - 1}$$$. For example, strings "GBRG", "B", "BR" are substrings of the infinite string "RGBRGBRGB ..." while "GR", "RGR" and "GGG" are not.

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

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

The first line of the query contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2000$$$) — the length of the string $$$s$$$ and the length of the substring.

The second line of the query contains a string $$$s$$$ consisting of $$$n$$$ characters 'R', 'G' and 'B'.

It is guaranteed that the sum of $$$n$$$ over all queries does not exceed $$$2000$$$ ($$$\sum n \le 2000$$$).

Output format:
For each query print one integer — the minimum number of characters you need to change in the initial string $$$s$$$ so that after changing there will be a substring of length $$$k$$$ in $$$s$$$ that is also a substring of the infinite string "RGBRGBRGB ...".

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

Note:
In the first example, you can change the first character to 'R' and obtain the substring "RG", or change the second character to 'R' and obtain "BR", or change the third, fourth or fifth character to 'B' and obtain "GB".

In the second example, the substring is "BRG".

Example input:
3
5 2
BGGGG
5 3
RBRGR
5 5
BBBRR

Example output:
1
0
3

Editorial:
You can just implement what is written in the problem statement and solve this problem this way.
Let's iterate over all starting positions of the substring $$$i$$$ from $$$0$$$ to $$$n-k+1$$$ and over all possible offsets of the string $$$t$$$ = "RGB" $$$offset$$$ from $$$0$$$ to $$$2$$$ inclusive. Then let's iterate over all position of the current substring $$$pos$$$ from $$$0$$$ to $$$k-1$$$ and carry the variable $$$cur$$$ which denotes the answer for the current starting position and the current offset. And if $$$s_{i + pos} \ne t_{(offset + pos) \% 3}$$$ then let's increase $$$cur$$$ by $$$1$$$. After iterating over all positions $$$pos$$$ let's update the answer with the value of $$$cur$$$.
K-th Path
Contest: Codeforces Round 575 (Div. 3)
Difficulty rating: 2200
Tags: brute force, constructive algorithms, shortest paths, sortings

You are given a connected undirected weighted graph consisting of $$$n$$$ vertices and $$$m$$$ edges.

You need to print the $$$k$$$-th smallest shortest path in this graph (paths from the vertex to itself are not counted, paths from $$$i$$$ to $$$j$$$ and from $$$j$$$ to $$$i$$$ are counted as one).

More formally, if $$$d$$$ is the matrix of shortest paths, where $$$d_{i, j}$$$ is the length of the shortest path between vertices $$$i$$$ and $$$j$$$ ($$$1 \le i < j \le n$$$), then you need to print the $$$k$$$-th element in the sorted array consisting of all $$$d_{i, j}$$$, where $$$1 \le i < j \le n$$$.

Input format:
The first line of the input contains three integers $$$n, m$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$n - 1 \le m \le \min\Big(\frac{n(n-1)}{2}, 2 \cdot 10^5\Big)$$$, $$$1 \le k \le \min\Big(\frac{n(n-1)}{2}, 400\Big)$$$ — the number of vertices in the graph, the number of edges in the graph and the value of $$$k$$$, correspondingly.

Then $$$m$$$ lines follow, each containing three integers $$$x$$$, $$$y$$$ and $$$w$$$ ($$$1 \le x, y \le n$$$, $$$1 \le w \le 10^9$$$, $$$x \ne y$$$) denoting an edge between vertices $$$x$$$ and $$$y$$$ of weight $$$w$$$.

It is guaranteed that the given graph is connected (there is a path between any pair of vertices), there are no self-loops (edges connecting the vertex with itself) and multiple edges (for each pair of vertices $$$x$$$ and $$$y$$$, there is at most one edge between this pair of vertices in the graph).

Output format:
Print one integer — the length of the $$$k$$$-th smallest shortest path in the given graph (paths from the vertex to itself are not counted, paths from $$$i$$$ to $$$j$$$ and from $$$j$$$ to $$$i$$$ are counted as one).

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

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

Example output:
3

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

Example output:
9

Editorial:
The main observation is that you don't need more than $$$min(k, m)$$$ smallest by weight edges (among all edges with the maximum weights you can choose any). Maybe there will be a proof later, but now I ask other participant to write it.
So you sort the initial edges and after that you can construct a graph consisting of no more than $$$2min(k, m)$$$ vertices and no more than $$$min(m, k)$$$ edges. You just can build the new graph consisting only on these vertices and edges and run Floyd-Warshall algorithm to find the matrix of shortest paths. Then sort all shorted distances and print the $$$k$$$-th element of this sorted array.
Time complexity: $$$O(m \log m + k^3)$$$.
I know that there are other approaches that can solve this problem with greater $$$k$$$, but to make this problem easily this solution is enough.
Suits
Contest: Codeforces Round 608 (Div. 2)
Difficulty rating: 800
Tags: brute force, greedy, math

A new delivery of clothing has arrived today to the clothing store. This delivery consists of $$$a$$$ ties, $$$b$$$ scarves, $$$c$$$ vests and $$$d$$$ jackets.

The store does not sell single clothing items — instead, it sells suits of two types:

- a suit of the first type consists of one tie and one jacket;
- a suit of the second type consists of one scarf, one vest and one jacket.

Each suit of the first type costs $$$e$$$ coins, and each suit of the second type costs $$$f$$$ coins.

Calculate the maximum possible cost of a set of suits that can be composed from the delivered clothing items. Note that one item cannot be used in more than one suit (though some items may be left unused).

Input format:
The first line contains one integer $$$a$$$ $$$(1 \le a \le 100\,000)$$$ — the number of ties.

The second line contains one integer $$$b$$$ $$$(1 \le b \le 100\,000)$$$ — the number of scarves.

The third line contains one integer $$$c$$$ $$$(1 \le c \le 100\,000)$$$ — the number of vests.

The fourth line contains one integer $$$d$$$ $$$(1 \le d \le 100\,000)$$$ — the number of jackets.

The fifth line contains one integer $$$e$$$ $$$(1 \le e \le 1\,000)$$$ — the cost of one suit of the first type.

The sixth line contains one integer $$$f$$$ $$$(1 \le f \le 1\,000)$$$ — the cost of one suit of the second type.

Output format:
Print one integer — the maximum total cost of some set of suits that can be composed from the delivered items.

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

Note:
It is possible to compose three suits of the second type in the first example, and their total cost will be $$$6$$$. Since all jackets will be used, it's impossible to add anything to this set.

The best course of action in the second example is to compose nine suits of the first type and eleven suits of the second type. The total cost is $$$9 \cdot 4 + 11 \cdot 6 = 102$$$.

Example input:
4
5
6
3
1
2

Example output:
6

Example input:
12
11
13
20
4
6

Example output:
102

Editorial:
There are two ways to approach this problem. The first way is to iterate on the number of suits of one type that we will compose and calculate the number of suits of the second type we can compose from the remaining items.
The second way is to use the fact that if $$$e > f$$$, then we have to make as many suits of the first type as possible (and the opposite is true if $$$f > e$$$). So we firstly make the maximum possible number of more expensive suits, and use the remaining items to compose cheaper suits.
Kyoya and Colored Balls
Contest: Codeforces Round 309 (Div. 1)
Difficulty rating: 1500
Tags: combinatorics, dp, math

Kyoya Ootori has a bag with n colored balls that are colored with k different colors. The colors are labeled from 1 to k. Balls of the same color are indistinguishable. He draws balls from the bag one by one until the bag is empty. He noticed that he drew the last ball of color i before drawing the last ball of color i + 1 for all i from 1 to k - 1. Now he wonders how many different ways this can happen.

Input format:
The first line of input will have one integer k (1 ≤ k ≤ 1000) the number of colors.

Then, k lines will follow. The i-th line will contain ci, the number of balls of the i-th color (1 ≤ ci ≤ 1000).

The total number of balls doesn't exceed 1000.

Output format:
A single integer, the number of ways that Kyoya can draw the balls from the bag as described in the statement, modulo 1 000 000 007.

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

Note:
In the first sample, we have 2 balls of color 1, 2 balls of color 2, and 1 ball of color 3. The three ways for Kyoya are:

Example input:
3
2
2
1

Example output:
3

Example input:
4
1
2
3
4

Example output:
1680

Editorial:
Let fi be the number of ways to solve the problem using only the first i colors. We want to compute fn.
Initially, we have f1 = 1, since we only have a single color. Now, to go from fi to fi + 1, we note that we need to put a ball of color i + 1 at the very end, but the other balls of color i + 1 can go anywhere in the sequence. Thus, we can just multiply by the correct binomial coefficient. Thus, $$f_{i+1} = f_i \cdot \binom{c_1 + \ldots + c_{i+1} - 1}{c_{i+1} - 1}$$. So, we just need to precompute binomial coefficients, and then evaluate the product.
The Child and Homework
Contest: Codeforces Round 250 (Div. 2)
Difficulty rating: 1300
Tags: implementation

Once upon a time a child got a test consisting of multiple-choice questions as homework. A multiple-choice question consists of four choices: A, B, C and D. Each choice has a description, and the child should find out the only one that is correct.

Fortunately the child knows how to solve such complicated test. The child will follow the algorithm:

- If there is some choice whose description at least twice shorter than all other descriptions, or at least twice longer than all other descriptions, then the child thinks the choice is great.
- If there is exactly one great choice then the child chooses it. Otherwise the child chooses C (the child think it is the luckiest choice).

You are given a multiple-choice questions, can you predict child's choose?

Input format:
The first line starts with "A." (without quotes), then followed the description of choice A. The next three lines contains the descriptions of the other choices in the same format. They are given in order: B, C, D. Please note, that the description goes after prefix "X.", so the prefix mustn't be counted in description's length.

Each description is non-empty and consists of at most 100 characters. Each character can be either uppercase English letter or lowercase English letter, or "_".

Output format:
Print a single line with the child's choice: "A", "B", "C" or "D" (without quotes).

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

Note:
In the first sample, the first choice has length 39, the second one has length 35, the third one has length 37, and the last one has length 15. The choice D (length 15) is twice shorter than all other choices', so it is great choice. There is no other great choices so the child will choose D.

In the second sample, no choice is great, so the child will choose the luckiest choice C.

In the third sample, the choice B (length 2) is twice longer than all other choices', so it is great choice. There is no other great choices so the child will choose B.

Example input:
A.VFleaKing_is_the_author_of_this_problem
B.Picks_is_the_author_of_this_problem
C.Picking_is_the_author_of_this_problem
D.Ftiasch_is_cute

Example output:
D

Example input:
A.ab
B.abcde
C.ab
D.abc

Example output:
C

Editorial:
The Child and Set
Contest: Codeforces Round 250 (Div. 2)
Difficulty rating: 1500
Tags: bitmasks, greedy, implementation, sortings

At the children's day, the child came to Picks's house, and messed his house up. Picks was angry at him. A lot of important things were lost, in particular the favorite set of Picks.

Fortunately, Picks remembers something about his set S:

- its elements were distinct integers from 1 to limit;
- the value of $$\sum_{x \in S} lowbit(x)$$ was equal to sum; here lowbit(x) equals 2k where k is the position of the first one in the binary representation of x. For example, lowbit(100102) = 102, lowbit(100012) = 12, lowbit(100002) = 100002 (binary representation).

Can you help Picks and find any set S, that satisfies all the above conditions?

Input format:
The first line contains two integers: sum, limit (1 ≤ sum, limit ≤ 105).

Output format:
In the first line print an integer n (1 ≤ n ≤ 105), denoting the size of S. Then print the elements of set S in any order. If there are multiple answers, print any of them.

If it's impossible to find a suitable set, print -1.

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

Note:
In sample test 1: lowbit(4) = 4, lowbit(5) = 1, 4 + 1 = 5.

In sample test 2: lowbit(1) = 1, lowbit(2) = 2, lowbit(3) = 1, 1 + 2 + 1 = 4.

Example input:
5 5

Example output:
2
4 5

Example input:
4 3

Example output:
3
2 3 1

Editorial: