Mail.Ru Cup 2018 Round 1

8 problems from Mail.Ru Cup 2018 Round 1 (contest 1054), difficulty 800-3500. 3/8 solutions verified against sample I/O.

8 items

Mail.Ru Cup 2018 Round 1

Special | 8 problems | 3/8 verified | Difficulty 800-3500 | 37m 21s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Elevator or Stairs?	800	implementation	9,591	2m 27s	✓
B	Appending Mex	1000	implementation	7,068	2m 32s	✓
C	Candies Distribution	1500	constructive-algorithms, implementation	4,483	9m 3s
D	Changing Array	1900	greedy, implementation	2,415	3m 46s	✓
E	Chips Puzzle	2400	constructive-algorithms, implementation, math	514	4m 54s
F	Electric Scheme	2700	flows, graph-matchings	387	3m 50s
G	New Road Network	3300	constructive-algorithms, greedy, math	451	3m 39s
H	Epic Convolution	3500	chinese-remainder-theorem, fft, math	212	7m 10s

Practice › Codeforces Solutions › Mail.Ru Cup 2018 Round 1 ›

CF 1054H - Epic Convolution

We are given two sequences, one indexed by $i$ and one indexed by $j$, and we are asked to combine every pair $(i, j)$ into a single weighted contribution. The weight is not linear or even separable in the usual sense: each pair contributes $$ai cdot bj cdot c^{i^2 j^3}.

Practice › Codeforces Solutions › Mail.Ru Cup 2018 Round 1 ›

CF 1054G - New Road Network

We are asked to construct a tree on $n$ labeled vertices, representing citizens, using exactly $n-1$ edges so that the graph is connected and acyclic.

Practice › Codeforces Solutions › Mail.Ru Cup 2018 Round 1 ›

CF 1054F - Electric Scheme

We are given a set of points in the plane, each point being an “event location” where a horizontal wire and a vertical wire must cross. Every wire is axis-aligned: horizontal wires lie on a fixed y-coordinate, vertical wires lie on a fixed x-coordinate.

Practice › Codeforces Solutions › Mail.Ru Cup 2018 Round 1 ›

CF 1054C - Candies Distribution

We are given a line of children, and we need to reconstruct any valid assignment of candy counts to them. Each child has already reported two numbers: how many children to their left have strictly more candies than them, and how many children to their right have strictly more…

Practice › Codeforces Solutions › Mail.Ru Cup 2018 Round 1 ›

CF 1054E - Chips Puzzle

We are given a grid where each cell contains a short string made of characters 0 and 1. Think of each cell as a small stack of chips written in a row, where we can see the order of chips from left to right.

Practice › Codeforces Solutions › Mail.Ru Cup 2018 Round 1 ›

CF 1054D - Changing Array

We are given an array of integers where each value is represented using exactly $k$ bits. Alongside the array, we are allowed a very specific transformation: for any position, we can flip all bits of the number, turning it into its bitwise complement within the $k$-bit space.

Practice › Codeforces Solutions › Mail.Ru Cup 2018 Round 1 ›

CF 1054B - Appending Mex

We are given a sequence that is claimed to be constructed step by step starting from an empty array. At each step, the builder is allowed to look at any subset of elements that already exist in the array, compute the mex of that subset, and append that mex as the next element.

Practice › Codeforces Solutions › Mail.Ru Cup 2018 Round 1 ›

CF 1054A - Elevator or Stairs?

Masha starts on a floor $x$ and wants to reach floor $y$. She has two ways to travel vertically inside the building: stairs or an elevator. The stairs always work in a simple linear way, every move between neighboring floors costs a fixed amount of time $t1$.