1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Toy Cars
Contest: Codeforces Round 303 (Div. 2)
Difficulty rating: 900
Tags: implementation

Little Susie, thanks to her older brother, likes to play with cars. Today she decided to set up a tournament between them. The process of a tournament is described in the next paragraph.

There are n toy cars. Each pair collides. The result of a collision can be one of the following: no car turned over, one car turned over, both cars turned over. A car is good if it turned over in no collision. The results of the collisions are determined by an n × n matrix А: there is a number on the intersection of the і-th row and j-th column that describes the result of the collision of the і-th and the j-th car:

- - 1: if this pair of cars never collided.  - 1 occurs only on the main diagonal of the matrix.
- 0: if no car turned over during the collision.
- 1: if only the i-th car turned over during the collision.
- 2: if only the j-th car turned over during the collision.
- 3: if both cars turned over during the collision.

Susie wants to find all the good cars. She quickly determined which cars are good. Can you cope with the task?

Input format:
The first line contains integer n (1 ≤ n ≤ 100) — the number of cars.

Each of the next n lines contains n space-separated integers that determine matrix A.

It is guaranteed that on the main diagonal there are  - 1, and  - 1 doesn't appear anywhere else in the matrix.

It is guaranteed that the input is correct, that is, if Aij = 1, then Aji = 2, if Aij = 3, then Aji = 3, and if Aij = 0, then Aji = 0.

Output format:
Print the number of good cars and in the next line print their space-separated indices in the increasing order.

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

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

Example output:
2
1 3

Example input:
4
-1 3 3 3
3 -1 3 3
3 3 -1 3
3 3 3 -1

Example output:
0

Editorial:
Equidistant String
Contest: Codeforces Round 303 (Div. 2)
Difficulty rating: 1100
Tags: greedy

Little Susie loves strings. Today she calculates distances between them. As Susie is a small girl after all, her strings contain only digits zero and one. She uses the definition of Hamming distance:

We will define the distance between two strings s and t of the same length consisting of digits zero and one as the number of positions i, such that si isn't equal to ti.

As besides everything else Susie loves symmetry, she wants to find for two strings s and t of length n such string p of length n, that the distance from p to s was equal to the distance from p to t.

It's time for Susie to go to bed, help her find such string p or state that it is impossible.

Input format:
The first line contains string s of length n.

The second line contains string t of length n.

The length of string n is within range from 1 to 105. It is guaranteed that both strings contain only digits zero and one.

Output format:
Print a string of length n, consisting of digits zero and one, that meets the problem statement. If no such string exist, print on a single line "impossible" (without the quotes).

If there are multiple possible answers, print any of them.

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

Note:
In the first sample different answers are possible, namely — 0010, 0011, 0110, 0111, 1000, 1001, 1100, 1101.

Example input:
0001
1011

Example output:
0011

Example input:
000
111

Example output:
impossible

Editorial:
Woodcutters
Contest: Codeforces Round 303 (Div. 2)
Difficulty rating: 1500
Tags: dp, greedy

Little Susie listens to fairy tales before bed every day. Today's fairy tale was about wood cutters and the little girl immediately started imagining the choppers cutting wood. She imagined the situation that is described below.

There are n trees located along the road at points with coordinates x1, x2, ..., xn. Each tree has its height hi. Woodcutters can cut down a tree and fell it to the left or to the right. After that it occupies one of the segments [xi - hi, xi] or [xi;xi + hi]. The tree that is not cut down occupies a single point with coordinate xi. Woodcutters can fell a tree if the segment to be occupied by the fallen tree doesn't contain any occupied point. The woodcutters want to process as many trees as possible, so Susie wonders, what is the maximum number of trees to fell.

Input format:
The first line contains integer n (1 ≤ n ≤ 105) — the number of trees.

Next n lines contain pairs of integers xi, hi (1 ≤ xi, hi ≤ 109) — the coordinate and the height of the і-th tree.

The pairs are given in the order of ascending xi. No two trees are located at the point with the same coordinate.

Output format:
Print a single number — the maximum number of trees that you can cut down by the given rules.

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

Note:
In the first sample you can fell the trees like that:

- fell the 1-st tree to the left — now it occupies segment [ - 1;1]
- fell the 2-nd tree to the right — now it occupies segment [2;3]
- leave the 3-rd tree — it occupies point 5
- leave the 4-th tree — it occupies point 10
- fell the 5-th tree to the right — now it occupies segment [19;20]

In the second sample you can also fell 4-th tree to the right, after that it will occupy segment [10;19].

Example input:
5
1 2
2 1
5 10
10 9
19 1

Example output:
3

Example input:
5
1 2
2 1
5 10
10 9
20 1

Example output:
4

Editorial:
Queue
Contest: Codeforces Round 303 (Div. 2)
Difficulty rating: 1300
Tags: greedy, implementation, sortings

Little girl Susie went shopping with her mom and she wondered how to improve service quality.

There are n people in the queue. For each person we know time ti needed to serve him. A person will be disappointed if the time he waits is more than the time needed to serve him. The time a person waits is the total time when all the people who stand in the queue in front of him are served. Susie thought that if we swap some people in the queue, then we can decrease the number of people who are disappointed.

Help Susie find out what is the maximum number of not disappointed people can be achieved by swapping people in the queue.

Input format:
The first line contains integer n (1 ≤ n ≤ 105).

The next line contains n integers ti (1 ≤ ti ≤ 109), separated by spaces.

Output format:
Print a single number — the maximum number of not disappointed people in the queue.

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

Note:
Value 4 is achieved at such an arrangement, for example: 1, 2, 3, 5, 15. Thus, you can make everything feel not disappointed except for the person with time 5.

Example input:
5
15 2 1 5 3

Example output:
4

Editorial:
Paths and Trees
Contest: Codeforces Round 303 (Div. 2)
Difficulty rating: 2000
Tags: graphs, greedy, shortest paths

Little girl Susie accidentally found her elder brother's notebook. She has many things to do, more important than solving problems, but she found this problem too interesting, so she wanted to know its solution and decided to ask you about it. So, the problem statement is as follows.

Let's assume that we are given a connected weighted undirected graph G = (V, E) (here V is the set of vertices, E is the set of edges). The shortest-path tree from vertex u is such graph G1 = (V, E1) that is a tree with the set of edges E1 that is the subset of the set of edges of the initial graph E, and the lengths of the shortest paths from u to any vertex to G and to G1 are the same.

You are given a connected weighted undirected graph G and vertex u. Your task is to find the shortest-path tree of the given graph from vertex u, the total weight of whose edges is minimum possible.

Input format:
The first line contains two numbers, n and m (1 ≤ n ≤ 3·105, 0 ≤ m ≤ 3·105) — the number of vertices and edges of the graph, respectively.

Next m lines contain three integers each, representing an edge — ui, vi, wi — the numbers of vertices connected by an edge and the weight of the edge (ui ≠ vi, 1 ≤ wi ≤ 109). It is guaranteed that graph is connected and that there is no more than one edge between any pair of vertices.

The last line of the input contains integer u (1 ≤ u ≤ n) — the number of the start vertex.

Output format:
In the first line print the minimum total weight of the edges of the tree.

In the next line print the indices of the edges that are included in the tree, separated by spaces. The edges are numbered starting from 1 in the order they follow in the input. You may print the numbers of the edges in any order.

If there are multiple answers, print any of them.

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

Note:
In the first sample there are two possible shortest path trees:

- with edges 1 – 3 and 2 – 3 (the total weight is 3);
- with edges 1 – 2 and 2 – 3 (the total weight is 2);

And, for example, a tree with edges 1 – 2 and 1 – 3 won't be a shortest path tree for vertex 3, because the distance from vertex 3 to vertex 2 in this tree equals 3, and in the original graph it is 1.

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

Example output:
2
1 2

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

Example output:
4
2 3 4

Editorial:
Balls of Buma
Contest: 2019-2020 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 900

Balph is learning to play a game called Buma. In this game, he is given a row of colored balls. He has to choose the color of one new ball and the place to insert it (between two balls, or to the left of all the balls, or to the right of all the balls).

When the ball is inserted the following happens repeatedly: if some segment of balls of the same color became longer as a result of a previous action and its length became at least $$$3$$$, then all the balls of this segment are eliminated.

Consider, for example, a row of balls 'AAABBBWWBB'. Suppose Balph chooses a ball of color 'W' and the place to insert it after the sixth ball, i. e. to the left of the two 'W's. After Balph inserts this ball, the balls of color 'W' are eliminated, since this segment was made longer and has length $$$3$$$ now, so the row becomes 'AAABBBBB'. The balls of color 'B' are eliminated now, because the segment of balls of color 'B' became longer and has length $$$5$$$ now. Thus, the row becomes 'AAA'. However, none of the balls are eliminated now, because there is no elongated segment.

Help Balph count the number of possible ways to choose a color of a new ball and a place to insert it that leads to the elimination of all the balls.

Input format:
The only line contains a non-empty string of uppercase English letters of length at most $$$3 \cdot 10^5$$$. Each letter represents a ball with the corresponding color.

Output format:
Output the number of ways to choose a color and a position of a new ball in order to eliminate all the balls.

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

Example input:
BBWWBB

Example output:
3

Example input:
BWWB

Example output:
0

Editorial:
Elections
Contest: 2019-2020 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 1700
Tags: greedy

Byteburg Senate elections are coming. Usually "United Byteland", the ruling Byteland party, takes all the seats in the Senate to ensure stability and sustainable development. But this year there is one opposition candidate in one of the constituencies. Even one opposition member can disturb the stability in the Senate, so the head of the Party asks you to ensure that the opposition candidate will not be elected.

There are $$$n$$$ candidates, numbered from 1 to $$$n$$$. Candidate $$$n$$$ is the opposition candidate. There are $$$m$$$ polling stations in the constituency, numbered from 1 to $$$m$$$. You know the number of votes cast for each candidate at each polling station. The only thing you can do to prevent the election of the opposition candidate is to cancel the election results at some polling stations. The opposition candidate will be elected if the sum of the votes cast in their favor at all non-canceled stations will be strictly greater than the analogous sum for every other candidate.

Your task is to prevent the election of the opposition candidate by canceling the election results at the minimal possible number of polling stations. Notice that solution always exists, because if you cancel the elections at all polling stations, the number of votes for each candidate will be 0, and the opposition candidate will not be elected.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$2\le n\le 100$$$; $$$1\le m \le 100$$$) — the number of candidates and the number of polling stations. The next $$$m$$$ lines contain the election results at each polling station with $$$n$$$ numbers on each line. In the $$$i$$$-th line the $$$j$$$-th number is $$$a_{i,j}$$$ — the number of votes cast for the candidate $$$j$$$ at the station $$$i$$$ ($$$0\le a_{i,j} \le 1\,000$$$).

Output format:
In the first line output integer $$$k$$$ — the minimal number of the polling stations in which you need to cancel the election results. In the second line output $$$k$$$ integers — the indices of canceled polling stations, in any order. If there are multiple ways to cancel results at $$$k$$$ stations, output any one of them.

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

Note:
In the first example, the candidates from 1 to 5 received 14, 12, 13, 15, and 24 votes correspondingly. The opposition candidate has the most votes. However, if you cancel the election results at the first and the third polling stations, then only the result from the second polling station remains and the vote sums become 3, 7, 5, 6, and 7, without the opposition candidate being in the lead anymore.

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

Example output:
2
3 1

Example input:
2 1
1 1

Example output:
0

Editorial:
Game Relics
Contest: 2019-2020 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 3000
Tags: math, probabilities

Esports is a form of competitive sports using video games. Dota 2 is one of the most popular competitive video games in Esports. Recently, a new video game Dota 3 was released. In Dota 3 a player can buy some relics for their hero. Relics are counters that track hero's actions and statistics in a game.

Gloria likes to play Dota 3, so she wants to buy all $$$n$$$ available relics for her favorite hero.

Relics can be bought using an in-game currency called shards. Each relic has its own price — $$$c_i$$$ shards for the $$$i$$$-th relic. A player can buy a relic using one of the following options:

- Pay $$$c_i$$$ shards to buy the $$$i$$$-th relic;
- Pay $$$x$$$ shards and randomly get one of all $$$n$$$ relics. The probability of getting a relic is the same for all $$$n$$$ relics. If a duplicate relic is received, then the relic is recycled and $$$\frac{x}{2}$$$ shards are given back to the player.

Gloria wants to buy all $$$n$$$ relics. Help her minimize the expected number of shards she spends to buy all the relics.

Input format:
The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 100$$$; $$$1 \le x \le 10\,000$$$) — the number of relics and the cost to receive a random relic.

The second line consists of $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$x \le c_i \le 10\,000$$$; $$$\sum{c_i} \le 10\,000$$$) — the prices of $$$n$$$ relics.

Output format:
Print a single real number — the minimum expected number of shards that Gloria must spend to buy all the relics.

The absolute or relative error should not exceed $$$10^{-9}$$$.

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

Note:
In the first example, the optimal strategy is to randomly get one of the two relics paying $$$20$$$ shards. Then there are two scenarios.

The first one happens if Gloria receives the first relic. Then she keeps getting random relics until she obtains the second relic. The expected number of shards to spend in this scenario is $$$20 + 30 = 50$$$.

In the second scenario, Gloria initially gets the second relic. Then it is better to buy the first relic for $$$25$$$ shards, so the expected number of shards to spend in this scenario is $$$20 + 25 = 45$$$.

Thus, the expected number of shards to spend is $$$\frac{50 + 45}{2} = 47.5$$$.

Example input:
2 20
25 100

Example output:
47.50000000000000000

Example input:
4 30
60 50 60 80

Example output:
171.25000000000000000

Editorial:
Just Arrange the Icons
Contest: 2019-2020 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 1800
Tags: greedy, implementation, math

BerPhone X is almost ready for release with $$$n$$$ applications being preinstalled on the phone. A category of an application characterizes a genre or a theme of this application (like "game", "business", or "education"). The categories are given as integers between $$$1$$$ and $$$n$$$, inclusive; the $$$i$$$-th application has category $$$c_i$$$.

You can choose $$$m$$$ — the number of screens and $$$s$$$ — the size of each screen. You need to fit all $$$n$$$ icons of the applications (one icon representing one application) meeting the following requirements:

- On each screen, all the icons must belong to applications of the same category (but different screens can contain icons of applications of the same category);
- Each screen must be either completely filled with icons (the number of icons on the screen is equal to $$$s$$$) or almost filled with icons (the number of icons is equal to $$$s-1$$$).

Your task is to find the minimal possible number of screens $$$m$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) — the number of test cases in the input. Then $$$t$$$ test cases follow.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2\cdot10^6$$$) — the number of the icons. The second line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le n$$$), where $$$c_i$$$ is the category of the $$$i$$$-th application.

It is guaranteed that the sum of the values of $$$n$$$ for all test cases in the input does not exceed $$$2\cdot10^6$$$.

Output format:
Print $$$t$$$ integers — the answers to the given test cases in the order they follow in the input. The answer to a test case is an integer $$$m$$$ — the minimum number of screens on which all $$$n$$$ icons can be placed satisfying the given requirements.

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

Note:
In the first test case of the example, all the icons can be placed on three screens of size $$$4$$$: a screen with $$$4$$$ icons of the category $$$1$$$, a screen with $$$3$$$ icons of the category $$$1$$$, and a screen with $$$4$$$ icons of the category $$$5$$$.

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

Example output:
3
3
4

Editorial:
Key Storage
Contest: 2019-2020 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 2100
Tags: combinatorics, math

Karl is developing a key storage service. Each user has a positive integer key.

Karl knows that storing keys in plain text is bad practice. So, instead of storing a key, he decided to store a fingerprint of a key. However, using some existing fingerprint algorithm looked too boring to him, so he invented his own one.

Karl's fingerprint is calculated by the following process: divide the given integer by 2, then divide the result by 3, then divide the result by 4, and so on, until we get a result that equals zero (we are speaking about integer division each time). The fingerprint is defined as the multiset of the remainders of these divisions.

For example, this is how Karl's fingerprint algorithm is applied to the key 11: 11 divided by 2 has remainder 1 and result 5, then 5 divided by 3 has remainder 2 and result 1, and 1 divided by 4 has remainder 1 and result 0. Thus, the key 11 produces the sequence of remainders $$$[1, 2, 1]$$$ and has the fingerprint multiset $$$\{1, 1, 2\}$$$.

Ksenia wants to prove that Karl's fingerprint algorithm is not very good. For example, she found that both keys 178800 and 123456 produce the fingerprint of $$$\{0, 0, 0, 0, 2, 3, 3, 4\}$$$. Thus, users are at risk of fingerprint collision with some commonly used and easy to guess keys like 123456.

Ksenia wants to make her words more persuasive. She wants to calculate the number of other keys that have the same fingerprint as the keys in the given list of some commonly used keys. Your task is to help her.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 50\,000$$$) — the number of commonly used keys to examine. Each of the next $$$t$$$ lines contains one integer $$$k_i$$$ ($$$1 \le k_i \le 10^{18}$$$) — the key itself.

Output format:
For each of the keys print one integer — the number of other keys that have the same fingerprint.

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

Note:
The other key with the same fingerprint as 11 is 15. 15 produces a sequence of remainders $$$[1, 1, 2]$$$. So both numbers have the fingerprint multiset $$$\{1, 1, 2\}$$$.

Example input:
3
1
11
123456

Example output:
0
1
127

Editorial:
Lexicography
Contest: 2019-2020 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 1800
Tags: constructive algorithms, strings

Lucy likes letters. She studied the definition of the lexicographical order at school and plays with it.

At first, she tried to construct the lexicographically smallest word out of given letters. It was so easy! Then she tried to build multiple words and minimize one of them. This was much harder!

Formally, Lucy wants to make $$$n$$$ words of length $$$l$$$ each out of the given $$$n \cdot l$$$ letters, so that the $$$k$$$-th of them in the lexicographic order is lexicographically as small as possible.

Input format:
The first line contains three integers $$$n$$$, $$$l$$$, and $$$k$$$ ($$$1\le k \le n \le 1\,000$$$; $$$1 \le l \le 1\,000$$$) — the total number of words, the length of each word, and the index of the word Lucy wants to minimize.

The next line contains a string of $$$n \cdot l$$$ lowercase letters of the English alphabet.

Output format:
Output $$$n$$$ words of $$$l$$$ letters each, one per line, using the letters from the input. Words must be sorted in the lexicographic order, and the $$$k$$$-th of them must be lexicographically as small as possible. If there are multiple answers with the smallest $$$k$$$-th word, output any of them.

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

Example input:
3 2 2
abcdef

Example output:
af
bc
ed

Example input:
2 3 1
abcabc

Example output:
aab
bcc

Editorial:
Erasing Zeroes
Contest: Educational Codeforces Round 82 (Rated for Div. 2)
Difficulty rating: 800
Tags: implementation, strings

You are given a string $$$s$$$. Each character is either 0 or 1.

You want all 1's in the string to form a contiguous subsegment. For example, if the string is 0, 1, 00111 or 01111100, then all 1's form a contiguous subsegment, and if the string is 0101, 100001 or 11111111111101, then this condition is not met.

You may erase some (possibly none) 0's from the string. What is the minimum number of 0's that you have to erase?

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

Then $$$t$$$ lines follow, each representing a test case. Each line contains one string $$$s$$$ ($$$1 \le |s| \le 100$$$); each character of $$$s$$$ is either 0 or 1.

Output format:
Print $$$t$$$ integers, where the $$$i$$$-th integer is the answer to the $$$i$$$-th testcase (the minimum number of 0's that you have to erase from $$$s$$$).

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

Note:
In the first test case you have to delete the third and forth symbols from string 010011 (it turns into 0111).

Example input:
3
010011
0
1111000

Example output:
2
0
0

Editorial:
Let's find the first and the last position of $$$1$$$-characters (denote them as $$$l$$$ and $$$r$$$ respectively). Since the can't delete $$$1$$$-characters, all $$$1$$$-characters between $$$s_l$$$ and $$$s_r$$$ will remain. So, we have to delete all $$$0$$$-characters between $$$s_l$$$ and $$$s_r$$$.