Codeforces Round 121 (Div. 1)

Solutions for Codeforces Round 121 (Div. 1) (contest 191). 5/5 problems verified against sample I/O. Difficulty range: 1500-2700.

5 items

Codeforces Round 121 (Div. 1)

Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1500-2700 | Time: 8m 55s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Dynasty Puzzles	1500	dp	1m 42s	✓
B	Demonstration	1700	greedy	1m 33s	✓
C	Fools and Roads	1900	data-structures, dfs-and-similar, trees	1m 55s	✓
D	Metro Scheme	2700	graphs, greedy	1m 59s	✓
E	Thwarting Demonstrations	2200	binary-search, data-structures, trees	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.