Hello 2018

Solutions for Hello 2018 (contest 913). 4/8 problems verified against sample I/O. Difficulty range: 900-3400.

8 items

Hello 2018

Type: Special | Problems: 8 | Verified: 4/8 | Rating range: 900-3400 | Time: 47m 3s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Modular Exponentiation	900	implementation, math	6m 16s	✓
B	Christmas Spruce	1200	implementation, trees	2m 58s	✓
C	Party Lemonade	1600	bitmasks, dp, greedy	6m 30s	✓
D	Too Easy Problems	1800	binary-search, brute-force, data-structures	6m 50s	✗
E	Logical Expression	2400	bitmasks, dp, shortest-paths	3m 25s	✗
F	Strongly Connected Tournament	2800	dp, graphs, math	6m 14s	✗
G	Power Substring	3200	math, number-theory	5m	✗
H	Don't Exceed	3400	math, probabilities	9m 50s	✓

Practice › Codeforces Solutions › Hello 2018 ›

Practice › Codeforces Solutions › Hello 2018 ›

CF 913F - Strongly Connected Tournament

We are asked to compute the expected total number of games in a recursively defined chess tournament. There are n players, each with a known probability of beating any lower-numbered player.

Practice › Codeforces Solutions › Hello 2018 ›

CF 913G - Power Substring

Each query gives a positive integer $a$, and we need to construct another integer $k$. The constraint is not about optimizing $k$, but about shaping the number $2k$.

Practice › Codeforces Solutions › Hello 2018 ›

CF 913E - Logical Expression

We are working with Boolean functions of exactly three variables, x, y, and z. A Boolean function on three variables has only eight possible input assignments. The input gives the value of the function on each of those eight assignments as a binary string of length eight.

Practice › Codeforces Solutions › Hello 2018 ›

CF 913D - Too Easy Problems

We are given a set of exam problems, each with a solving time and a “strictness limit” that controls whether it contributes to our score. We can pick any subset of problems to solve as long as the total time does not exceed the exam duration.

Practice › Codeforces Solutions › Hello 2018 ›

CF 913C - Party Lemonade

We are asked to buy at least L liters of lemonade at minimum cost. The store offers n types of bottles, where the i-th type has a volume of 2^(i-1) liters and a cost of c[i] roubles, and we can buy an unlimited number of each type.

Practice › Codeforces Solutions › Hello 2018 ›

CF 913A - Modular Exponentiation

The problem asks us to compute the remainder when an integer m is divided by $2^n$, where n and m are positive integers. In other words, we are given the size of a power-of-two modulus and a dividend, and we must find what is left after dividing the dividend by that modulus.

Practice › Codeforces Solutions › Hello 2018 ›

CF 913B - Christmas Spruce

We are given a rooted tree with vertices numbered from 1 to n. Vertex 1 is always the root. For every other vertex, the input tells us its parent, which completely defines the tree structure. A vertex is considered a leaf if it has no children and is not the root.