Codeforces Round 121 (Div. 1)

5 problems from Codeforces Round 121 (Div. 1) (contest 191), difficulty 1500-2700. 5/5 solutions verified against sample I/O.

5 items

Codeforces Round 121 (Div. 1)

Div. 1 | 5 problems | 5/5 verified | Difficulty 1500-2700 | 8m 55s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Dynasty Puzzles	1500	dp	4,553	1m 42s	✓
B	Demonstration	1700	greedy	1,101	1m 33s	✓
C	Fools and Roads	1900	data-structures, dfs-and-similar, trees	9,215	1m 55s	✓
D	Metro Scheme	2700	graphs, greedy	392	1m 59s	✓
E	Thwarting Demonstrations	2200	binary-search, data-structures, trees	959	1m 46s	✓

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

CF 191A - Dynasty Puzzles

We are given a list of abbreviated king names in chronological order. Each name is a lowercase string. We may choose some of these names to form a dynasty, while preserving their original order. A valid dynasty must satisfy two conditions.

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

CF 191B - Demonstration

We are asked to determine the earliest square where the opposition can hold a demonstration given the interference of the city administration. There are n squares arranged by increasing distance from the city center, with square 1 being the most central.

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

CF 191C - Fools and Roads

The input describes a tree of cities. Since there is exactly one simple path between every pair of cities, the road network forms a connected acyclic graph. Then we are given several pairs of cities.

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

CF 191D - Metro Scheme

We are given an undirected connected graph describing a subway system. Every edge is a tunnel, every vertex is a station. The graph is guaranteed to be a vertex cactus, meaning each vertex belongs to at most one simple cycle. The subway is composed of lines of two possible types.

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

CF 191E - Thwarting Demonstrations

We have an array of soldier reliabilities. Every contiguous subarray represents one possible police group. The general always chooses the strongest unused group first, meaning all subarray sums are sorted in descending order and picked one by one.