1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Heidi and Library (easy)
Contest: Helvetic Coding Contest 2017 online mirror (teams allowed, unrated)
Difficulty rating: 1800
Tags: greedy

Your search for Heidi is over – you finally found her at a library, dressed up as a human. In fact, she has spent so much time there that she now runs the place! Her job is to buy books and keep them at the library so that people can borrow and read them. There are n different books, numbered 1 through n.

We will look at the library's operation during n consecutive days. Heidi knows in advance that on the i-th day (1 ≤ i ≤ n) precisely one person will come to the library, request to borrow the book ai, read it in a few hours, and return the book later on the same day.

Heidi desperately wants to please all her guests, so she will make sure to always have the book ai available in the library on the i-th day. During the night before the i-th day, she has the option of going to the bookstore (which operates at nights to avoid competition with the library) and buying any book for the price of 1 CHF. Of course, if she already has a book at the library, she does not need to buy it again. Initially, the library contains no books.

There is a problem, though. The capacity of the library is k – this means that at any time, there can be at most k books at the library. If buying a new book would cause Heidi to have more than k books, she must first get rid of some book that she already has, in order to make room for the new book. If she later needs a book that she got rid of, she will need to buy that book again.

You are given k and the sequence of requests for books a1, a2, ..., an. What is the minimum cost (in CHF) of buying new books to satisfy all the requests?

Input format:
The first line of input will contain two integers n and k (1 ≤ n, k ≤ 80). The second line will contain n integers a1, a2, ..., an (1 ≤ ai ≤ n) – the sequence of book requests.

Output format:
On a single line print the minimum cost of buying books at the store so as to satisfy all requests.

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

Note:
In the first test case, Heidi is able to keep all books forever. Therefore, she only needs to buy the book 1 before the first day and the book 2 before the second day.

In the second test case, she can only keep one book at a time. Therefore she will need to buy new books on the first, second and fourth day.

In the third test case, before buying book 3 on the third day, she must decide which of the books 1 and 2 she should get rid of. Of course, she should keep the book 1, which will be requested on the fourth day.

Example input:
4 80
1 2 2 1

Example output:
2

Example input:
4 1
1 2 2 1

Example output:
3

Editorial:
Heidi and Library (medium)
Contest: Helvetic Coding Contest 2017 online mirror (teams allowed, unrated)
Difficulty rating: 1800
Tags: data structures, greedy

Whereas humans nowadays read fewer and fewer books on paper, book readership among marmots has surged. Heidi has expanded the library and is now serving longer request sequences.

Input format:
Same as the easy version, but the limits have changed: 1 ≤ n, k ≤ 400 000.

Output format:
Same as the easy version.

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

Example input:
4 100
1 2 2 1

Example output:
2

Example input:
4 1
1 2 2 1

Example output:
3

Editorial:
Heidi and Library (hard)
Contest: Helvetic Coding Contest 2017 online mirror (teams allowed, unrated)
Difficulty rating: 2600
Tags: flows

The good times at Heidi's library are over. Marmots finally got their internet connections and stopped coming to the library altogether. Not only that, but the bookstore has begun charging extortionate prices for some books. Namely, whereas in the previous versions each book could be bought for 1 CHF, now the price of book i is ci CHF.

Input format:
The first line of input will contain two integers n and k ($${ 1 \leq n, k \leq 8 0 }$$). The second line will contain n integers a1, a2, ..., an (1 ≤ ai ≤ n) – the sequence of book requests. The third line contains n integers c1, c2, ..., cn (0 ≤ ci ≤ 106) – the costs of the books.

Output format:
On a single line print the minimum cost of buying books at the store so as to satisfy all requests.

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

Note:
The first three sample cases are repeated, but the fourth one is new.

In the fourth test case, when buying book 3, Heidi should discard either book 1 or 2. Even though book 2 will be requested later than book 1, she should keep it, because it is so expensive to buy again.

Example input:
4 80
1 2 2 1
1 1 1 1

Example output:
2

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

Example output:
3

Editorial:
Marmots (easy)
Contest: Helvetic Coding Contest 2017 online mirror (teams allowed, unrated)
Difficulty rating: 2100
Tags: math

Heidi is a statistician to the core, and she likes to study the evolution of marmot populations in each of V (1 ≤ V ≤ 100) villages! So it comes that every spring, when Heidi sees the first snowdrops sprout in the meadows around her barn, she impatiently dons her snowshoes and sets out to the Alps, to welcome her friends the marmots to a new season of thrilling adventures.

Arriving in a village, Heidi asks each and every marmot she comes across for the number of inhabitants of that village. This year, the marmots decide to play an April Fools' joke on Heidi. Instead of consistently providing the exact number of inhabitants P (10 ≤ P ≤ 1000) of the village, they respond with a random non-negative integer k, drawn from one of two types of probability distributions:

- Poisson (d'avril) distribution: the probability of getting an answer k is $$\frac{p^k e^{-p}}{k!}$$ for k = 0, 1, 2, 3, ...,
- Uniform distribution: the probability of getting an answer k is $$\frac{1}{2P+1}$$ for k = 0, 1, 2, ..., 2P.

Heidi collects exactly 250 answers per village. Every village follows either the Poisson or the uniform distribution. Heidi cannot tell marmots apart, so she may query some marmots several times, and each time the marmot will answer with a new number drawn from the village's distribution.

Can you help Heidi to find out whether a village follows a Poisson or a uniform distribution?

Input format:
The first line of input will contain the number of villages V (1 ≤ V ≤ 100). The following V lines each describe one village. The description of each village consists of 250 space-separated integers k, drawn from one of the above distributions.

Output format:
Output one line per village, in the same order as provided in the input. The village's line shall state poisson if the village's distribution is of the Poisson type, and uniform if the answer came from a uniform distribution.

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

Note:
The full example input is visually represented below, along with the probability distribution function it was drawn from (the y-axis is labeled by its values multiplied by 250).

Example input:
2
92 100 99 109 93 105 103 106 101 99 ... (input is truncated)
28 180 147 53 84 80 180 85 8 16 ... (input is truncated)

Example output:
poisson
uniform

Editorial:
Marmots (medium)
Contest: Helvetic Coding Contest 2017 online mirror (teams allowed, unrated)
Difficulty rating: 2200
Tags: math

Good job! Now that Heidi is able to distinguish between Poisson and uniform distributions, she is in a good position to actually estimate the populations.

Can you help Heidi estimate each village's population?

Input format:
Same as the easy version.

Output format:
Output one line per village, in the same order as provided in the input, containing your (integer) population estimate.

Your answer is considered correct if it is an integer that falls into the interval $$\left[0.95 \cdot P\right], \left[1.05 \cdot P\right]$$, where P is the real population of the village, used to create the distribution (either Poisson or uniform) from which the marmots drew their answers.

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

Editorial:
Marmots (hard)
Contest: Helvetic Coding Contest 2017 online mirror (teams allowed, unrated)
Difficulty rating: 2800
Tags: math, probabilities

Your task is the exact same as for the easy version. But this time, the marmots subtract the village's population P from their random number before responding to Heidi's request.

Also, there are now villages with as few as a single inhabitant, meaning that $${ 1 \leq P \leq 1000 }$$.

Can you help Heidi find out whether a village follows a Poisson or a uniform distribution?

Input format:
Same as for the easy and medium versions. But remember that now 1 ≤ P ≤ 1000 and that the marmots may provide positive as well as negative integers.

Output format:
Output one line per village, in the same order as provided in the input. The village's line shall state poisson if the village's distribution is of the Poisson type, and uniform if the answers came from a uniform distribution.

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

Editorial:
Fake News (easy)
Contest: Helvetic Coding Contest 2017 online mirror (teams allowed, unrated)
Difficulty rating: 800
Tags: implementation, strings

As it's the first of April, Heidi is suspecting that the news she reads today are fake, and she does not want to look silly in front of all the contestants. She knows that a newspiece is fake if it contains heidi as a subsequence. Help Heidi assess whether the given piece is true, but please be discreet about it...

Input format:
The first and only line of input contains a single nonempty string s of length at most 1000 composed of lowercase letters (a-z).

Output format:
Output YES if the string s contains heidi as a subsequence and NO otherwise.

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

Note:
A string s contains another string p as a subsequence if it is possible to delete some characters from s and obtain p.

Example input:
abcheaibcdi

Example output:
YES

Example input:
hiedi

Example output:
NO

Editorial:
Fake News (medium)
Contest: Helvetic Coding Contest 2017 online mirror (teams allowed, unrated)
Difficulty rating: 2200
Tags: constructive algorithms, strings

Thanks to your help, Heidi is confident that no one can fool her. She has now decided to post some fake news on the HC2 Facebook page. However, she wants to be able to communicate to the HC2 committee that the post is fake, using some secret phrase hidden in the post as a subsequence. To make this method foolproof, she wants the phrase to appear n times in the post. She is asking you to design a post (string) s and a hidden phrase p such that p appears in s as a subsequence exactly n times.

Input format:
The first and only line of input contains a single integer n (1 ≤ n ≤ 1 000 000).

Output format:
The output should contain two nonempty strings s and p separated by a single space. Each string should be composed of letters (a-z and A-Z: both lowercase and uppercase are allowed) and have length at most 200. The number of occurrences of p in s as a subsequence should be exactly n. If there are many possible solutions, output any of them. It is guaranteed that at least one solution exists.

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

Note:
An occurrence of p as a subsequence in s should be thought of as a set of positions in s such that the letters at these positions, in order, form p. The number of occurences is thus the number of such sets. For example, ab appears 6 times as a subsequence in aaabb, for the following sets of positions: {1, 4}, {1, 5}, {2, 4}, {2, 5}, {3, 4}, {3, 5} (that is, we should choose one of the a's and one of the b's).

Example input:
2

Example output:
hHheidi Hei

Example input:
4

Example output:
bbbba ba

Editorial:
Fake News (hard)
Contest: Helvetic Coding Contest 2017 online mirror (teams allowed, unrated)
Difficulty rating: 2300
Tags: string suffix structures

Now that you have proposed a fake post for the HC2 Facebook page, Heidi wants to measure the quality of the post before actually posting it. She recently came across a (possibly fake) article about the impact of fractal structure on multimedia messages and she is now trying to measure the self-similarity of the message, which is defined as

$$\sum_{p} \operatorname{cnt}(s,p)^2,$$

where the sum is over all nonempty strings p and $$\operatorname{cnt}(s,p)$$ is the number of occurences of p in s as a substring. (Note that the sum is infinite, but it only has a finite number of nonzero summands.)

Heidi refuses to do anything else until she knows how to calculate this self-similarity. Could you please help her? (If you would like to instead convince Heidi that a finite string cannot be a fractal anyway – do not bother, we have already tried.)

Input format:
The input starts with a line indicating the number of test cases T (1 ≤ T ≤ 10). After that, T test cases follow, each of which consists of one line containing a string s (1 ≤ |s| ≤ 100 000) composed of lowercase letters (a-z).

Output format:
Output T lines, every line containing one number – the answer to the corresponding test case.

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

Note:
A string s contains another string p as a substring if p is a contiguous subsequence of s. For example, ab is a substring of cab but not of acb.

Example input:
4
aa
abcd
ccc
abcc

Example output:
5
10
14
12

Editorial:
Send the Fool Further! (easy)
Contest: Helvetic Coding Contest 2017 online mirror (teams allowed, unrated)
Difficulty rating: 1400
Tags: dfs and similar, graphs, trees

Heidi's friend Jenny is asking Heidi to deliver an important letter to one of their common friends. Since Jenny is Irish, Heidi thinks that this might be a prank. More precisely, she suspects that the message she is asked to deliver states: "Send the fool further!", and upon reading it the recipient will ask Heidi to deliver the same message to yet another friend (that the recipient has in common with Heidi), and so on.

Heidi believes that her friends want to avoid awkward situations, so she will not be made to visit the same person (including Jenny) twice. She also knows how much it costs to travel between any two of her friends who know each other. She wants to know: what is the maximal amount of money she will waste on travel if it really is a prank?

Heidi's n friends are labeled 0 through n - 1, and their network of connections forms a tree. In other words, every two of her friends a, b know each other, possibly indirectly (there is a sequence of friends starting from a and ending on b and such that each two consecutive friends in the sequence know each other directly), and there are exactly n - 1 pairs of friends who know each other directly.

Jenny is given the number 0.

Input format:
The first line of the input contains the number of friends n (3 ≤ n ≤ 100). The next n - 1 lines each contain three space-separated integers u, v and c (0 ≤ u, v ≤ n - 1, 1 ≤ c ≤ 104), meaning that u and v are friends (know each other directly) and the cost for travelling between u and v is c.

It is guaranteed that the social network of the input forms a tree.

Output format:
Output a single integer – the maximum sum of costs.

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

Note:
In the second example, the worst-case scenario goes like this: Jenny sends Heidi to the friend labeled by number 2 (incurring a cost of 100), then friend 2 sends her to friend 1 (costing Heidi 3), and finally friend 1 relays her to friend 4 (incurring an additional cost of 2).

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

Example output:
5

Example input:
6
1 2 3
0 2 100
1 4 2
0 3 7
3 5 10

Example output:
105

Editorial:
Send the Fool Further! (medium)
Contest: Helvetic Coding Contest 2017 online mirror (teams allowed, unrated)
Difficulty rating: 2100
Tags: dp, trees

Thank you for helping Heidi! It is now the second of April, but she has been summoned by Jenny again. The pranks do not seem to end...

In the meantime, Heidi has decided that she does not trust her friends anymore. Not too much, anyway. Her relative lack of trust is manifested as follows: whereas previously she would not be made to visit the same person twice, now she can only be sure that she will not be made to visit the same person more than k times. (In the case of Jenny, this includes her first visit in the beginning. The situation from the easy version corresponds to setting k = 1.)

This is not as bad as it looks, since a single ticket for a route between two friends allows Heidi to travel between this pair of friends the whole day (in both directions). In other words, once she pays for travel between a pair of friends, all further travels between that pair are free.

How much money will Heidi waste now, in a worst-case scenario?

Input format:
The first line contains two space-separated integers – the number of friends n ($$3 \leq n \leq 10^5$$) and the parameter k (1 ≤ k ≤ 105). The next n - 1 lines each contain three space-separated integers u, v and c (0 ≤ u, v ≤ n - 1, 1 ≤ c ≤ 104) meaning that u and v are friends and the cost for traveling between u and v is c.

It is again guaranteed that the social network of the input forms a tree.

Output format:
Again, output a single integer – the maximum sum of costs of tickets.

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

Note:
In the first example, the worst-case scenario for Heidi is to visit the friends in the following order: 0, 1, 5, 1, 3, 1, 0, 2, 6, 2, 7, 2, 8. Observe that no friend is visited more than 3 times.

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

Example output:
15

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

Example output:
17

Editorial:
Send the Fool Further! (hard)
Contest: Helvetic Coding Contest 2017 online mirror (teams allowed, unrated)
Difficulty rating: 2400
Tags: dfs and similar, dp, math, trees

Heidi is terrified by your estimate and she found it unrealistic that her friends would collaborate to drive her into debt. She expects that, actually, each person will just pick a random friend to send Heidi to. (This randomness assumption implies, however, that she can now visit the same friend an arbitrary number of times...) Moreover, if a person only has one friend in common with Heidi (i.e., if that person is in a leaf of the tree), then that person will not send Heidi back (so that Heidi's travel will end at some point).

Heidi also found unrealistic the assumption that she can make all the travels in one day. Therefore now she assumes that every time she travels a route between two friends, she needs to buy a new ticket. She wants to know: how much should she expect to spend on the trips?

For what it's worth, Heidi knows that Jenny has at least two friends.

Input format:
The first line contains the number of friends n (3 ≤ n ≤ 105). The next n - 1 lines each contain three space-separated integers u, v and c (0 ≤ u, v ≤ n - 1, 1 ≤ c ≤ 104) meaning that u and v are friends and the cost for traveling between u and v is c (paid every time!).

It is again guaranteed that the social network of the input forms a tree.

Output format:
Assume that the expected cost of the trips is written as an irreducible fraction a / b (that is, a and b are coprime). Then Heidi, the weird cow that she is, asks you to output $${ a \cdot b ^ { - 1 } { \bmod { ( 1 0 ^ { 9 } + 7 ) } } }$$. (Output a single integer between 0 and 109 + 6.)

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

Note:
In the first example, with probability 1 / 2 Heidi will go to 1 from 0, and with probability 1 / 2 she will go to 2. In the first case the cost would be 10, and in the second it would be 20. After reaching 1 or 2 she will stop, as 1 and 2 are leaves of the social tree. Hence, the expected cost she has to pay is 10·1 / 2 + 20·1 / 2 = 15.

In the third example, the expected cost is 81 / 5. You should output 400000019.

In her travels, Heidi has learned an intriguing fact about the structure of her social network. She tells you the following: The mysterious determinant that you might be wondering about is such that it does not cause strange errors in your reasonable solution... Did we mention that Heidi is a weird cow?

Example input:
3
0 1 10
0 2 20

Example output:
15

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

Example output:
13

Editorial:
April Fools' Problem (easy)
Contest: Helvetic Coding Contest 2017 online mirror (teams allowed, unrated)
Difficulty rating: 1200
Tags: greedy, sortings

The marmots have prepared a very easy problem for this year's HC2 – this one. It involves numbers n, k and a sequence of n positive integers a1, a2, ..., an. They also came up with a beautiful and riveting story for the problem statement. It explains what the input means, what the program should output, and it also reads like a good criminal.

However I, Heidi, will have none of that. As my joke for today, I am removing the story from the statement and replacing it with these two unhelpful paragraphs. Now solve the problem, fools!

Input format:
The first line of the input contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 2200). The second line contains n space-separated integers a1, ..., an (1 ≤ ai ≤ 104).

Output format:
Output one number.

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

Example input:
8 5
1 1 1 1 1 1 1 1

Example output:
5

Example input:
10 3
16 8 2 4 512 256 32 128 64 1

Example output:
7

Editorial:
April Fools' Problem (medium)
Contest: Helvetic Coding Contest 2017 online mirror (teams allowed, unrated)
Difficulty rating: 2400
Tags: binary search, flows, graphs

The marmots need to prepare k problems for HC2 over n days. Each problem, once prepared, also has to be printed.

The preparation of a problem on day i (at most one per day) costs ai CHF, and the printing of a problem on day i (also at most one per day) costs bi CHF. Of course, a problem cannot be printed before it has been prepared (but doing both on the same day is fine).

What is the minimum cost of preparation and printing?

Input format:
The first line of input contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 2200). The second line contains n space-separated integers a1, ..., an ($$1 \leq a_i \leq 10^9$$) — the preparation costs. The third line contains n space-separated integers b1, ..., bn ($$1 \leq b_i \leq 10^9$$) — the printing costs.

Output format:
Output the minimum cost of preparation and printing k problems — that is, the minimum possible sum ai1 + ai2 + ... + aik + bj1 + bj2 + ... + bjk, where 1 ≤ i1 < i2 < ... < ik ≤ n, 1 ≤ j1 < j2 < ... < jk ≤ n and i1 ≤ j1, i2 ≤ j2, ..., ik ≤ jk.

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

Note:
In the sample testcase, one optimum solution is to prepare the first problem on day 1 and print it on day 1, prepare the second problem on day 2 and print it on day 4, prepare the third problem on day 3 and print it on day 5, and prepare the fourth problem on day 6 and print it on day 8.

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

Example output:
32

Editorial:
April Fools' Problem (hard)
Contest: Helvetic Coding Contest 2017 online mirror (teams allowed, unrated)
Difficulty rating: 2900
Tags: binary search, data structures, flows

The plans for HC2 are rather far-fetched: we are just over 500 000 days away from HC2 3387, for example, and accordingly we are planning to have a couple hundred thousand problems in that edition (we hope that programming contests will become wildly more popular). The marmots need to get to work, and they could use a good plan...

Input format:
Same as the medium version, but the limits have changed: 1 ≤ k ≤ n ≤ 500 000.

Output format:
Same as the medium version.

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

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

Example output:
32

Editorial: