Codeforces Round 259 (Div. 1)

Solutions for Codeforces Round 259 (Div. 1) (contest 453). 4/5 problems verified against sample I/O. Difficulty range: 1600-3100.

5 items

Codeforces Round 259 (Div. 1)

Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1600-3100 | Time: 8m 34s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Little Pony and Expected Maximum	1600	probabilities	1m 46s	✓
B	Little Pony and Harmony Chest	2000	bitmasks, brute-force, dp	1m 19s	✓
C	Little Pony and Summer Sun Celebration	2200	constructive-algorithms, dfs-and-similar, graphs	2m 13s	✗
D	Little Pony and Elements of Harmony	3000	dp, matrices	2m 30s	✓
E	Little Pony and Lord Tirek	3100	data-structures	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.