The 2020 ICPC Asia Yinchuan Regional Programming Contest

13 problems from The 2020 ICPC Asia Yinchuan Regional Programming Contest (contest 104022), difficulty -. 12/13 solutions verified against sample I/O.

13 items

The 2020 ICPC Asia Yinchuan Regional Programming Contest

ICPC/IOI | 13 problems | 12/13 verified | Difficulty - | 12m 16s

#	Problem	Time	✓
A	Best Player	2m 4s
B	The Great Wall	49s	✓
C	Lucky Sequence	1m 5s	✓
D	Farm	49s	✓
E	Isomerism	40s	✓
F	Maximize the Ratio	51s	✓
G	Photograph	48s	✓
H	Absolute Space	50s	✓
I	The Answer!	47s	✓
J	Let's Play Jigsaw Puzzles!	51s	✓
K	Browser Games	44s	✓
L	Sheep Village	1m 15s	✓
M	Tower of the Sorcerer	43s	✓

Practice › Codeforces Solutions › The 2020 ICPC Asia Yinchuan Regional Programming Contest ›

CF 104022L - Sheep Village

We are given a connected undirected graph with n cities and m roads. Each road has a traversal cost, and the graph is almost a tree: there are at most n edges beyond a spanning tree, and every edge participates in at most one simple cycle.

Practice › Codeforces Solutions › The 2020 ICPC Asia Yinchuan Regional Programming Contest ›

CF 104022M - Tower of the Sorcerer

We are given a sequence of monsters, each described by a pair of values: its attack strength and its health. We control a warrior who starts with some initial strength and effectively unlimited health, so survival is not about dying, but about minimizing how much damage the…

Practice › Codeforces Solutions › The 2020 ICPC Asia Yinchuan Regional Programming Contest ›

CF 104022K - Browser Games

We are given a stream of URLs, one per day, and after each day we must decide how many “confirmation prefixes” the server must maintain. A confirmation prefix is a non-empty string. A URL is considered valid (i.e.

Practice › Codeforces Solutions › The 2020 ICPC Asia Yinchuan Regional Programming Contest ›

CF 104022H - Absolute Space

We are asked to construct a finite set of points in three-dimensional space such that each point has exactly $n$ other points at Euclidean distance exactly 1.

Practice › Codeforces Solutions › The 2020 ICPC Asia Yinchuan Regional Programming Contest ›

CF 104022J - Let's Play Jigsaw Puzzles!

We are given a complete set of square jigsaw pieces arranged in an unknown m by m grid. Each piece is identified by a unique number from 1 to m², and for each piece we are given four pointers indicating which other piece lies directly to its north, south, west, and east.

Practice › Codeforces Solutions › The 2020 ICPC Asia Yinchuan Regional Programming Contest ›

CF 104022I - The Answer!

We are given two indices $x$ and $y$, an integer base $a$, and a modulus $m$. From these values we construct two Fibonacci-indexed exponents and build two numbers: $$u = a^{Fx} - 1,quad v = a^{Fy} - 1$$ where $Fn$ is the Fibonacci sequence.

Practice › Codeforces Solutions › The 2020 ICPC Asia Yinchuan Regional Programming Contest ›

CF 104022G - Photograph

We are given a fixed set of students, each with a unique index from 1 to n and an associated height. A photo is always taken in a strict ordering by student index, not by arrival order.

Practice › Codeforces Solutions › The 2020 ICPC Asia Yinchuan Regional Programming Contest ›

CF 104022F - Maximize the Ratio

We are given several test cases, each containing a set of planar points. From these points we are allowed to select some subset and connect them with straight segments so that the segments form the boundary of a convex polygon.

Practice › Codeforces Solutions › The 2020 ICPC Asia Yinchuan Regional Programming Contest ›

CF 104022A - Best Player

Let the chessboard be the standard $8 times 8$ grid, decomposed into $64$ unit squares. A domino covering is a perfect tiling by $1 times 2$ or $2 times 1$ rectangles aligned with the grid. Each domino occupies exactly two adjacent squares.

Practice › Codeforces Solutions › The 2020 ICPC Asia Yinchuan Regional Programming Contest ›

CF 104022E - Isomerism

We are given four substituents attached to a fixed ethylene-like structure. Think of a double bond between two carbons, where each carbon has two attachments: the left carbon has R1 and R2, and the right carbon has R3 and R4.

Practice › Codeforces Solutions › The 2020 ICPC Asia Yinchuan Regional Programming Contest ›

CF 104022D - Farm

We are given a collection of candidate roads between farms. Each road connects two farms and has an associated cost.

Practice › Codeforces Solutions › The 2020 ICPC Asia Yinchuan Regional Programming Contest ›

CF 104022C - Lucky Sequence

We are given a sequence of length $n$. Each position holds a non-negative integer, but the allowed range of values is extremely small: the upper bound is a fixed constant derived from an expression involving $sqrt{5}$, which evaluates to a value between 1 and 2.

Practice › Codeforces Solutions › The 2020 ICPC Asia Yinchuan Regional Programming Contest ›

CF 104022B - The Great Wall

We are given a sequence of tower heights arranged from west to east. The task is to split this sequence into exactly $k$ contiguous groups, where each group must contain at least one tower.