XX Open Cup, Grand Prix of Korea

11 problems from XX Open Cup, Grand Prix of Korea (contest 102391), difficulty -. 7/11 solutions verified against sample I/O.

11 items

XX Open Cup, Grand Prix of Korea

Special | 11 problems | 7/11 verified | Difficulty - | 1h 18m

#	Problem	Time	✓
A	6789	22m 30s	✓
B	Bigger Sokoban 40k	2m 19s
C	Cleaning	10m 44s	✓
D	Container	8m 24s
E	Dead Cacti Society	8m 18s
F	Hilbert's Hotel	3m 42s	✓
G	Lexicographically Minimum Walk	2m 48s	✓
H	Maximizer	3m 40s	✓
I	Minimum Diameter Spanning Tree	6m 53s
J	Parklife	3m 13s	✓
K	Wind of Change	5m 37s	✓

Practice › Codeforces Solutions › XX Open Cup, Grand Prix of Korea ›

CF 102391E - Dead Cacti Society

We start with a connected weighted cactus. Each original vertex (v) has a healing value (RVv), and each original edge (e) has a length (Le) and a healing value (REe). For every cycle, exactly one edge must be removed. Removing an edge (e={u,v}) does not simply delete it.

Practice › Codeforces Solutions › XX Open Cup, Grand Prix of Korea ›

CF 102391I - Minimum Diameter Spanning Tree

We need to choose exactly (N-1) edges from a connected weighted undirected graph so that every vertex is reachable and the resulting graph is a tree. Among all such spanning trees, we want one whose longest weighted path is as short as possible.

Practice › Codeforces Solutions › XX Open Cup, Grand Prix of Korea ›

CF 102391B - Bigger Sokoban 40k

This is an output-only constructive problem. There is no input at all. Our program only has to print one Sokoban board satisfying the geometric constraints and having the stronger property that every valid solution requires at least 40,000 player moves.

Practice › Codeforces Solutions › XX Open Cup, Grand Prix of Korea ›

CF 102391C - Cleaning

Think of every grid cell as a vertex of a directed graph. Two cells sharing a side are candidates for an edge, but a cell refuses to move in the direction written on it.

Practice › Codeforces Solutions › XX Open Cup, Grand Prix of Korea ›

CF 102391F - Hilbert's Hotel

We have an infinite sequence of rooms numbered (0,1,2,ldots), and every room always contains exactly one guest. Guests belong to groups. Initially every room contains a guest from group (0). A type 1 operation creates a new group.

Practice › Codeforces Solutions › XX Open Cup, Grand Prix of Korea ›

CF 102391A - 6789

We have an N x M array whose entries are cards showing one of 6, 7, 8, or 9. A card may be rotated in place, but cards cannot move between cells. After choosing which cards to rotate, the resulting array must be unchanged by a 180-degree rotation.

Practice › Codeforces Solutions › XX Open Cup, Grand Prix of Korea ›

CF 102391K - Wind of Change

We have two weighted trees on the same set of vertices, with vertex labels (1) through (N). For two labels (i) and (j), their distance is not measured in either tree alone.

Practice › Codeforces Solutions › XX Open Cup, Grand Prix of Korea ›

CF 102391H - Maximizer

We start with two permutations (A) and (B), both containing every integer from (1) to (N) exactly once. We may rearrange (A), but only by swapping neighboring elements. The goal is not to construct one particular maximum arrangement.

Practice › Codeforces Solutions › XX Open Cup, Grand Prix of Korea ›

CF 102391D - Container

We have a binary array whose entries are container capacities, either 1 or 2. The goal is to transform the current array into a target array containing exactly the same number of each type. An allowed operation reverses either two consecutive entries or three consecutive entries.

Practice › Codeforces Solutions › XX Open Cup, Grand Prix of Korea ›

CF 102391J - Parklife

Each bridge can be represented by the half-open interval ([Si,Ei)). A bridge is visible from the small arc between consecutive points (i) and (i+1) exactly when that arc lies inside this interval. The input contains (N) weighted bridges.

Practice › Codeforces Solutions › XX Open Cup, Grand Prix of Korea ›

CF 102391G - Lexicographically Minimum Walk

We have a directed graph whose edges carry distinct integer colors. Starting from (S), we may traverse any outgoing edge, and we are allowed to revisit vertices and edges. The only requirement is that the walk eventually reaches (T).