Codeforces Round 459 (Div. 1)

Solutions for Codeforces Round 459 (Div. 1) (contest 917). 2/5 problems verified against sample I/O. Difficulty range: 1700-3400.

5 items

Codeforces Round 459 (Div. 1)

Type: Div. 1 | Problems: 5 | Verified: 2/5 | Rating range: 1700-3400 | Time: 25m 47s

Problem	Name	Rating	Tags	Solve Time	Verified
A	The Monster	1800	dp, greedy, implementation	2m 41s	✓
B	MADMAX	1700	dfs-and-similar, dp, games	4m 34s	✗
C	Pollywog	2900	combinatorics, dp, matrices	6m 26s	✗
D	Stranger Trees	2600	dp, math, matrices	9m 19s	✗
E	Upside Down	3400	data-structures, string-suffix-structures, strings	2m 47s	✓

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

CF 917D - Stranger Trees

We are asked to examine variations of a given labeled tree with $n$ vertices, counting how many labeled trees share exactly $k$ edges with the given one for each $k$ from 0 to $n-1$. The input is the number of vertices followed by $n-1$ edges that define Will's tree.

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

CF 917E - Upside Down

The tree describes a network of junctions connected by directed tunnels, where each tunnel carries a lowercase letter. Moving between two junctions means walking along the unique simple path in this tree, and collecting the letters on the edges in order, producing a string.

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

CF 917C - Pollywog

We are asked to move a group of x pollywogs from the first x stones in a line to the last x stones. The stones are numbered 1 through n, and each pollywog occupies exactly one stone.

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

CF 917B - MADMAX

We are given a directed acyclic graph where each edge carries a lowercase letter. Two tokens start on possibly different vertices: one belongs to Max and one to Lucas.

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

CF 917A - The Monster

We are given a string consisting of three possible characters: '(', ')', and '?'. For every substring, we ask whether it can be turned into a non-empty correct bracket sequence by replacing each '?' independently with either '(' or ')'. Such a substring is called pretty.