1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Maximum Control (medium)
Contest: Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)
Difficulty rating: 2200
Tags: data structures, dfs and similar, graphs, greedy, trees

The Resistance is trying to take control over as many planets of a particular solar system as possible. Princess Heidi is in charge of the fleet, and she must send ships to some planets in order to maximize the number of controlled planets.

The Galaxy contains N planets, connected by bidirectional hyperspace tunnels in such a way that there is a unique path between every pair of the planets.

A planet is controlled by the Resistance if there is a Resistance ship in its orbit, or if the planet lies on the shortest path between some two planets that have Resistance ships in their orbits.

Heidi has not yet made up her mind as to how many ships to use. Therefore, she is asking you to compute, for every K = 1, 2, 3, ..., N, the maximum number of planets that can be controlled with a fleet consisting of K ships.

Input format:
The first line of the input contains an integer N (1 ≤ N ≤ 105) – the number of planets in the galaxy.

The next N - 1 lines describe the hyperspace tunnels between the planets. Each of the N - 1 lines contains two space-separated integers u and v (1 ≤ u, v ≤ N) indicating that there is a bidirectional hyperspace tunnel between the planets u and v. It is guaranteed that every two planets are connected by a path of tunnels, and that each tunnel connects a different pair of planets.

Output format:
On a single line, print N space-separated integers. The K-th number should correspond to the maximum number of planets that can be controlled by the Resistance using a fleet of K ships.

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

Note:
Consider the first example. If K = 1, then Heidi can only send one ship to some planet and control it. However, for K ≥ 2, sending ships to planets 1 and 3 will allow the Resistance to control all planets.

Example input:
3
1 2
2 3

Example output:
1 3 3

Example input:
4
1 2
3 2
4 2

Example output:
1 3 4 4

Editorial:
Encryption (easy)
Contest: Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)
Difficulty rating: 1200
Tags: brute force

Rebel spy Heidi has just obtained the plans for the Death Star from the Empire and, now on her way to safety, she is trying to break the encryption of the plans (of course they are encrypted – the Empire may be evil, but it is not stupid!). The encryption has several levels of security, and here is how the first one looks.

Heidi is presented with a screen that shows her a sequence of integers A and a positive integer p. She knows that the encryption code is a single number S, which is defined as follows:

Define the score of X to be the sum of the elements of X modulo p.

Heidi is given a sequence A that consists of N integers, and also given an integer p. She needs to split A into 2 parts such that:

- Each part contains at least 1 element of A, and each part consists of contiguous elements of A.
- The two parts do not overlap.
- The total sum S of the scores of those two parts is maximized. This is the encryption code.

Output the sum S, which is the encryption code.

Input format:
The first line of the input contains two space-separated integer N and p (2 ≤ N ≤ 100 000, 2 ≤ p ≤ 10 000) – the number of elements in A, and the modulo for computing scores, respectively.

The second line contains N space-separated integers which are the elements of A. Each integer is from the interval [1, 1 000 000].

Output format:
Output the number S as described in the problem statement.

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

Note:
In the first example, the score is maximized if the input sequence is split into two parts as (3, 4), (7, 2). It gives the total score of $$(3+4\mod10)+(7+2\mod10)=16$$.

In the second example, the score is maximized if the first part consists of the first three elements, and the second part consists of the rest. Then, the score is $$( 1 6 + 3 + 2 4 \mod 1 2 ) + ( 1 3 + 9 + 8 + 7 + 5 + 1 2 \mod 1 2 ) = 7 + 6 = 1 3$$.

Example input:
4 10
3 4 7 2

Example output:
16

Example input:
10 12
16 3 24 13 9 8 7 5 12 12

Example output:
13

Editorial:
Encryption (medium)
Contest: Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)
Difficulty rating: 2000
Tags: dp

Heidi has now broken the first level of encryption of the Death Star plans, and is staring at the screen presenting her with the description of the next code she has to enter. It looks surprisingly similar to the first one – seems like the Empire engineers were quite lazy...

Heidi is once again given a sequence A, but now she is also given two integers k and p. She needs to find out what the encryption key S is.

Let X be a sequence of integers, and p a positive integer. We define the score of X to be the sum of the elements of X modulo p.

Heidi is given a sequence A that consists of N integers, and also given integers k and p. Her goal is to split A into k part such that:

- Each part contains at least 1 element of A, and each part consists of contiguous elements of A.
- No two parts overlap.
- The total sum S of the scores of those parts is maximized.

Output the sum S – the encryption code.

Input format:
The first line of the input contains three space-separated integer N, k and p (k ≤ N ≤ 20 000, 2 ≤ k ≤ 50, 2 ≤ p ≤ 100) – the number of elements in A, the number of parts A should be split into, and the modulo for computing scores, respectively.

The second line contains N space-separated integers that are the elements of A. Each integer is from the interval [1, 1 000 000].

Output format:
Output the number S as described in the problem statement.

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

Note:
In the first example, if the input sequence is split as (3, 4), (7), (2), the total score would be $$( 3 + 4 \mod 10 ) + ( 7 \mod 10 ) + ( 2 \mod 10 ) = 7 + 7 + 2 = 16$$. It is easy to see that this score is maximum.

In the second example, one possible way to obtain score 37 is to make the following split: (16, 3, 24), (13, 9), (8), (7), (5, 12, 12).

Example input:
4 3 10
3 4 7 2

Example output:
16

Example input:
10 5 12
16 3 24 13 9 8 7 5 12 12

Example output:
37

Editorial:
Encryption (hard)
Contest: Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)
Difficulty rating: 2500
Tags: data structures, dp

Heidi is now just one code away from breaking the encryption of the Death Star plans. The screen that should be presenting her with the description of the next code looks almost like the previous one, though who would have thought that the evil Empire engineers would fill this small screen with several million digits! It is just ridiculous to think that anyone would read them all...

Heidi is once again given a sequence A and two integers k and p. She needs to find out what the encryption key S is.

Let X be a sequence of integers, and p a positive integer. We define the score of X to be the sum of the elements of X modulo p.

Heidi is given a sequence A that consists of N integers, and also given integers k and p. Her goal is to split A into k parts such that:

- Each part contains at least 1 element of A, and each part consists of contiguous elements of A.
- No two parts overlap.
- The total sum S of the scores of those parts is minimized (not maximized!).

Output the sum S, which is the encryption code.

Input format:
The first line of the input contains three space-separated integers N, k and p (k ≤ N ≤ 500 000, 2 ≤ k ≤ 100, 2 ≤ p ≤ 100) – the number of elements in A, the number of parts A should be split into, and the modulo for computing scores, respectively.

The second line contains N space-separated integers that are the elements of A. Each integer is from the interval [1, 1 000 000].

Output format:
Output the number S as described in the problem statement.

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

Note:
In the first example, if the input sequence is split as (3), (4, 7), (2), the total score would be $$( 3 \bmod { 1 0 } ) + ( 4 + 7 \bmod { 1 0 } ) + ( 2 \bmod { 1 0 } ) = 3 + 1 + 2 = 6$$. It is easy to see that this score is the smallest possible.

In the second example, one possible way to obtain score 13 is to make the following split: (16, 3), (24), (13), (9, 8), (7, 5, 12, 12).

Example input:
4 3 10
3 4 7 2

Example output:
6

Example input:
10 5 12
16 3 24 13 9 8 7 5 12 12

Example output:
13

Editorial:
Hyperspace Jump (easy)
Contest: Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)
Difficulty rating: 1400
Tags: expression parsing, math

The Rebel fleet is on the run. It consists of m ships currently gathered around a single planet. Just a few seconds ago, the vastly more powerful Empire fleet has appeared in the same solar system, and the Rebels will need to escape into hyperspace. In order to spread the fleet, the captain of each ship has independently come up with the coordinate to which that ship will jump. In the obsolete navigation system used by the Rebels, this coordinate is given as the value of an arithmetic expression of the form $${ \frac { a + b } { c } }$$.

To plan the future of the resistance movement, Princess Heidi needs to know, for each ship, how many ships are going to end up at the same coordinate after the jump. You are her only hope!

Input format:
The first line of the input contains a single integer m (1 ≤ m ≤ 200 000) – the number of ships. The next m lines describe one jump coordinate each, given as an arithmetic expression. An expression has the form (a+b)/c. Namely, it consists of: an opening parenthesis (, a positive integer a of up to two decimal digits, a plus sign +, a positive integer b of up to two decimal digits, a closing parenthesis ), a slash /, and a positive integer c of up to two decimal digits.

Output format:
Print a single line consisting of m space-separated integers. The i-th integer should be equal to the number of ships whose coordinate is equal to that of the i-th ship (including the i-th ship itself).

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

Note:
In the sample testcase, the second and the third ship will both end up at the coordinate 3.

Note that this problem has only two versions – easy and hard.

Example input:
4
(99+98)/97
(26+4)/10
(12+33)/15
(5+1)/7

Example output:
1 2 2 1

Editorial:
Guard Duty (easy)
Contest: Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)
Difficulty rating: 1600
Tags: brute force, geometry, greedy, math

The Rebel fleet is afraid that the Empire might want to strike back again. Princess Heidi needs to know if it is possible to assign R Rebel spaceships to guard B bases so that every base has exactly one guardian and each spaceship has exactly one assigned base (in other words, the assignment is a perfect matching). Since she knows how reckless her pilots are, she wants to be sure that any two (straight) paths – from a base to its assigned spaceship – do not intersect in the galaxy plane (that is, in 2D), and so there is no risk of collision.

Input format:
The first line contains two space-separated integers R, B(1 ≤ R, B ≤ 10). For 1 ≤ i ≤ R, the i + 1-th line contains two space-separated integers xi and yi (|xi|, |yi| ≤ 10000) denoting the coordinates of the i-th Rebel spaceship. The following B lines have the same format, denoting the position of bases. It is guaranteed that no two points coincide and that no three points are on the same line.

Output format:
If it is possible to connect Rebel spaceships and bases so as satisfy the constraint, output Yes, otherwise output No (without quote).

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

Note:
For the first example, one possible way is to connect the Rebels and bases in order.

For the second example, there is no perfect matching between Rebels and bases.

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

Example output:
Yes

Example input:
2 1
1 0
2 2
3 1

Example output:
No

Editorial:
Guard Duty (medium)
Contest: Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)
Difficulty rating: 2200
Tags: binary search, dp, greedy, sortings

Princess Heidi decided to give orders to all her K Rebel ship commanders in person. Unfortunately, she is currently travelling through hyperspace, and will leave it only at N specific moments t1, t2, ..., tN. The meetings with commanders must therefore start and stop at those times. Namely, each commander will board her ship at some time ti and disembark at some later time tj. Of course, Heidi needs to meet with all commanders, and no two meetings can be held during the same time. Two commanders cannot even meet at the beginnings/endings of the hyperspace jumps, because too many ships in one position could give out their coordinates to the enemy.

Your task is to find minimum time that Princess Heidi has to spend on meetings, with her schedule satisfying the conditions above.

Input format:
The first line contains two integers K, N (2 ≤ 2K ≤ N ≤ 500000, K ≤ 5000). The second line contains N distinct integers t1, t2, ..., tN (1 ≤ ti ≤ 109) representing the times when Heidi leaves hyperspace.

Output format:
Output only one integer: the minimum time spent on meetings.

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

Note:
In the first example, there are five valid schedules: [1, 4], [6, 7] with total time 4, [1, 4], [6, 12] with total time 9, [1, 4], [7, 12] with total time 8, [1, 6], [7, 12] with total time 10, and [4, 6], [7, 12] with total time 7. So the answer is 4.

In the second example, there is only 1 valid schedule: [1, 2], [3, 4], [5, 6].

For the third example, one possible schedule with total time 6 is: [1, 3], [4, 5], [14, 15], [23, 25].

Example input:
2 5
1 4 6 7 12

Example output:
4

Example input:
3 6
6 3 4 2 5 1

Example output:
3

Editorial:
Guard Duty (hard)
Contest: Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)
Difficulty rating: 2700
Tags: geometry

Now that Heidi knows that she can assign Rebel spaceships to bases (recall the easy subtask), she is asking you: how exactly to do this? Now, given positions of N spaceships and N bases on a plane, your task is to connect spaceships and bases with line segments so that:

- The segments do not intersect.
- Such a connection forms a perfect matching.

Input format:
The first line contains an integer N (1 ≤ n ≤ 10000). For 1 ≤ i ≤ N, the i + 1-th line contains two integers xi and yi (|xi|, |yi| ≤ 10000) denoting the coordinates of the i-th spaceship. The following N lines have the same format, denoting the position of bases. It is guaranteed that no two points coincide and no three points are on the same line.

Output format:
The output should have N lines. The i-th line should contain an integer pi, the index of the base to which the i-th spaceship is connected. The sequence p1, ..., pN should form a permutation of 1, ..., N.

It is guaranteed that a solution exists. If there are multiple solutions, you can output any one of them.

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

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

Example output:
4
1
2
3

Editorial:
Lightsabers (easy)
Contest: Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)
Difficulty rating: 1500
Tags: implementation

There is unrest in the Galactic Senate. Several thousand solar systems have declared their intentions to leave the Republic. Master Heidi needs to select the Jedi Knights who will go on peacekeeping missions throughout the galaxy. It is well-known that the success of any peacekeeping mission depends on the colors of the lightsabers of the Jedi who will go on that mission.

Heidi has n Jedi Knights standing in front of her, each one with a lightsaber of one of m possible colors. She knows that for the mission to be the most effective, she needs to select some contiguous interval of knights such that there are exactly k1 knights with lightsabers of the first color, k2 knights with lightsabers of the second color, ..., km knights with lightsabers of the m-th color. Help her find out if this is possible.

Input format:
The first line of the input contains n (1 ≤ n ≤ 100) and m (1 ≤ m ≤ n). The second line contains n integers in the range {1, 2, ..., m} representing colors of the lightsabers of the subsequent Jedi Knights. The third line contains m integers k1, k2, ..., km (with $$1 \leq \sum_{i=1}^{m} k_i \leq n$$) – the desired counts of lightsabers of each color from 1 to m.

Output format:
Output YES if an interval with prescribed color counts exists, or output NO if there is none.

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

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

Example output:
YES

Editorial:
Lightsabers (medium)
Contest: Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)
Difficulty rating: 1800
Tags: binary search, two pointers

There is unrest in the Galactic Senate. Several thousand solar systems have declared their intentions to leave the Republic. Master Heidi needs to select the Jedi Knights who will go on peacekeeping missions throughout the galaxy. It is well-known that the success of any peacekeeping mission depends on the colors of the lightsabers of the Jedi who will go on that mission.

Heidi has n Jedi Knights standing in front of her, each one with a lightsaber of one of m possible colors. She knows that for the mission to be the most effective, she needs to select some contiguous interval of knights such that there are exactly k1 knights with lightsabers of the first color, k2 knights with lightsabers of the second color, ..., km knights with lightsabers of the m-th color.

However, since the last time, she has learned that it is not always possible to select such an interval. Therefore, she decided to ask some Jedi Knights to go on an indefinite unpaid vacation leave near certain pits on Tatooine, if you know what I mean. Help Heidi decide what is the minimum number of Jedi Knights that need to be let go before she is able to select the desired interval from the subsequence of remaining knights.

Input format:
The first line of the input contains n (1 ≤ n ≤ 2·105) and m (1 ≤ m ≤ n). The second line contains n integers in the range {1, 2, ..., m} representing colors of the lightsabers of the subsequent Jedi Knights. The third line contains m integers k1, k2, ..., km (with $$1 \leq \sum_{i=1}^{m} k_i \leq n$$) – the desired counts of Jedi Knights with lightsabers of each color from 1 to m.

Output format:
Output one number: the minimum number of Jedi Knights that need to be removed from the sequence so that, in what remains, there is an interval with the prescribed counts of lightsaber colors. If this is not possible, output  - 1.

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

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

Example output:
1

Editorial:
Lightsabers (hard)
Contest: Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)
Difficulty rating: 2600
Tags: fft

There used to be unrest in the Galactic Senate. Several thousand solar systems had declared their intentions to leave the Republic. But fear not! Master Heidi was able to successfully select the Jedi Knights that have restored peace in the galaxy. However, she knows that evil never sleeps and a time may come when she will need to pick another group of Jedi Knights. She wants to be sure she has enough options to do so.

There are n Jedi Knights, each of them with a lightsaber of one of m colors. Given a number k, compute the number of differently colored collections of k lightsabers that some k Jedi Knights might have. Jedi Knights with lightsabers of the same color are indistinguishable (it's not the person, it's the lightsaber color that matters!), and their order does not matter; that is, we consider two collections of Jedi Knights to be different if and only if their vectors of counts of lightsabers of each color (like what you were given in the easy and the medium versions) are different. We count all subsets, not only contiguous subsegments of the input sequence. Output the answer modulo 1009.

Input format:
The first line of the input contains n (1 ≤ n ≤ 2·105), m (1 ≤ m ≤ n) and k (1 ≤ k ≤ n). The second line contains n integers in the range {1, 2, ..., m} representing colors of the lightsabers of subsequent Jedi Knights.

Output format:
Output one number: the number of differently colored collections of k lightsabers modulo 1009.

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

Example input:
4 3 2
1 2 3 2

Example output:
4

Editorial:
Choose Two Numbers
Contest: Codeforces Round 580 (Div. 2)
Difficulty rating: 800
Tags: math, sortings

You are given an array $$$A$$$, consisting of $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$, and an array $$$B$$$, consisting of $$$m$$$ positive integers $$$b_1, b_2, \dots, b_m$$$.

Choose some element $$$a$$$ of $$$A$$$ and some element $$$b$$$ of $$$B$$$ such that $$$a+b$$$ doesn't belong to $$$A$$$ and doesn't belong to $$$B$$$.

For example, if $$$A = [2, 1, 7]$$$ and $$$B = [1, 3, 4]$$$, we can choose $$$1$$$ from $$$A$$$ and $$$4$$$ from $$$B$$$, as number $$$5 = 1 + 4$$$ doesn't belong to $$$A$$$ and doesn't belong to $$$B$$$. However, we can't choose $$$2$$$ from $$$A$$$ and $$$1$$$ from $$$B$$$, as $$$3 = 2 + 1$$$ belongs to $$$B$$$.

It can be shown that such a pair exists. If there are multiple answers, print any.

Choose and print any such two numbers.

Input format:
The first line contains one integer $$$n$$$ ($$$1\le n \le 100$$$) — the number of elements of $$$A$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 200$$$) — the elements of $$$A$$$.

The third line contains one integer $$$m$$$ ($$$1\le m \le 100$$$) — the number of elements of $$$B$$$.

The fourth line contains $$$m$$$ different integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le 200$$$) — the elements of $$$B$$$.

It can be shown that the answer always exists.

Output format:
Output two numbers $$$a$$$ and $$$b$$$ such that $$$a$$$ belongs to $$$A$$$, $$$b$$$ belongs to $$$B$$$, but $$$a+b$$$ doesn't belong to nor $$$A$$$ neither $$$B$$$.

If there are multiple answers, print any.

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

Note:
In the first example, we can choose $$$20$$$ from array $$$[20]$$$ and $$$20$$$ from array $$$[10, 20]$$$. Number $$$40 = 20 + 20$$$ doesn't belong to any of those arrays. However, it is possible to choose $$$10$$$ from the second array too.

In the second example, we can choose $$$3$$$ from array $$$[3, 2, 2]$$$ and $$$1$$$ from array $$$[1, 5, 7, 7, 9]$$$. Number $$$4 = 3 + 1$$$ doesn't belong to any of those arrays.

In the third example, we can choose $$$1$$$ from array $$$[1, 3, 5, 7]$$$ and $$$1$$$ from array $$$[7, 5, 3, 1]$$$. Number $$$2 = 1 + 1$$$ doesn't belong to any of those arrays.

Example input:
1
20
2
10 20

Example output:
20 20

Example input:
3
3 2 2
5
1 5 7 7 9

Example output:
3 1

Editorial:
Let $$$ a $$$ be the largest number in the array $$$ A $$$, $$$ b $$$ be the largest number in the array $$$ B $$$. Then the number $$$ a + b $$$ isn't present neither in the array $$$ A $$$ nor in the array $$$ B $$$. Indeed, $$$ a + b> a $$$, and $$$ a $$$ is the largest number in the array $$$ A $$$, so $$$ a + b $$$ is not included in $$$ A $$$. Similarly, $$$ a + b $$$ is not included in $$$ B $$$. Thus, you can select $$$ a $$$ from $$$ A $$$, $$$ b $$$ from $$$ B $$$.
The asymptotics is $$$ O (m \ log {m} + n \ log {n}) $$$ if you find the largest element by sorting (which many did), or $$$ O (m + n) $$$ if you find it linearly.