Codeforces Round 259 (Div. 1)

5 problems from Codeforces Round 259 (Div. 1) (contest 453), difficulty 1600-3100. 4/5 solutions verified against sample I/O.

5 items

Codeforces Round 259 (Div. 1)

Div. 1 | 5 problems | 4/5 verified | Difficulty 1600-3100 | 8m 34s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Little Pony and Expected Maximum	1600	probabilities	12,433	1m 46s	✓
B	Little Pony and Harmony Chest	2000	bitmasks, brute-force, dp	5,399	1m 19s	✓
C	Little Pony and Summer Sun Celebration	2200	constructive-algorithms, dfs-and-similar, graphs	1,742	2m 13s
D	Little Pony and Elements of Harmony	3000	dp, matrices	577	2m 30s	✓
E	Little Pony and Lord Tirek	3100	data-structures	911	46s	✓

Practice › Codeforces Solutions › Codeforces Round 259 (Div. 1) ›

CF 453A - Little Pony and Expected Maximum

We roll a fair die with faces numbered from 1 to m, exactly n times. Every roll is independent, and each face appears with probability 1 / m. Among those n rolls, we look only at the largest value that appeared. The task is to compute the expected value of that maximum.

Practice › Codeforces Solutions › Codeforces Round 259 (Div. 1) ›

CF 453B - Little Pony and Harmony Chest

We are given a sequence of integers a1, a2, ..., an with values between 1 and 30, and we need to construct another sequence b1, b2, ..., bn of positive integers such that every pair in b is coprime.

Practice › Codeforces Solutions › Codeforces Round 259 (Div. 1) ›

CF 453C - Little Pony and Summer Sun Celebration

We are given an undirected graph and, for every vertex, the parity of how many times that vertex must appear in a walk. A walk is represented by a sequence of vertices. Consecutive vertices in the sequence must be connected by an edge.

Practice › Codeforces Solutions › Codeforces Round 259 (Div. 1) ›

CF 453D - Little Pony and Elements of Harmony

We have a vector of energies indexed by all bitmasks of length m. Since n = 2^m, every vertex can be identified with an m-bit number. One transformation step is linear.

Practice › Codeforces Solutions › Codeforces Round 259 (Div. 1) ›

CF 453E - Little Pony and Lord Tirek

We have a lineup of ponies, each with three attributes: their current mana, their maximum mana, and their mana regeneration rate per unit time. Over time, Lord Tirek performs several operations called Absorb Mana, each targeting a consecutive segment of ponies.