Codeforces Round 556 (Div. 1)

Solutions for Codeforces Round 556 (Div. 1) (contest 1149). 3/5 problems verified against sample I/O. Difficulty range: 1200-3200.

5 items

Codeforces Round 556 (Div. 1)

Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1200-3200 | Time: 6m 20s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Prefix Sum Primes	1200	constructive-algorithms, greedy, math	1m 23s	✓
B	Three Religions	2200	dp, implementation, strings	1m 32s	✓
C	Tree Generator\u2122	2700	data-structures, implementation, trees	1m 57s	✗
D	Abandoning Roads	3000	brute-force, dp, graphs	54s	✓
E	Election Promises	3200	games, graphs	34s	✗

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

CF 1149D - Abandoning Roads

We are given a small island country with n settlements and m bidirectional roads connecting them. Each road has a travel time which is either a or b seconds. The roads are initially connected in such a way that every settlement is reachable from every other settlement.

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

CF 1149E - Election Promises

Working

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

CF 1149C - Tree Generator™

We are given a string of parentheses that encodes a rooted tree via an Euler tour traversal. Every opening bracket corresponds to walking down an edge in the rooted tree, and every closing bracket corresponds to walking back up that same edge.

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

CF 1149B - Three Religions

We are given a fixed base string, which we can think of as a long “universe sequence” of characters. Alongside it, there are three evolving strings, one per group.

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

CF 1149A - Prefix Sum Primes

We are given a bag of tiles, each labeled with either a 1 or a 2. Our task is to arrange all the tiles into a sequence so that when we calculate the prefix sums - that is, the sum of the first element, the sum of the first two elements, and so on - the number of sums that are…