2020-2021 ACM-ICPC, Asia Seoul Regional Contest

12 problems from 2020-2021 ACM-ICPC, Asia Seoul Regional Contest (contest 102920), difficulty -. 10/12 solutions verified against sample I/O.

12 items

2020-2021 ACM-ICPC, Asia Seoul Regional Contest

ICPC/IOI | 12 problems | 10/12 verified | Difficulty - | 12m 4s

#	Problem	Time	✓
A	Autonomous Vehicle	1m 8s
B	Commemorative Dice	41s	✓
C	Dessert Caf\u00e9	57s	✓
D	Electric Vehicle	1m	✓
E	Imprecise Computer	59s	✓
F	Ink Mix	2m 47s
G	Mobile Robot	40s	✓
H	Needle	48s	✓
I	Stock Analysis	43s	✓
J	Switches	41s	✓
K	Tiling Polyomino	53s	✓
L	Two Buildings	47s	✓

Practice › Codeforces Solutions › 2020-2021 ACM-ICPC, Asia Seoul Regional Contest ›

CF 102920K - Tiling Polyomino

We are given a shape on an $n times n$ grid, described by cells marked as belonging to a polyomino. The shape is connected, has no holes, and every cell has at least two neighboring cells inside the shape. So locally, nothing behaves like a leaf or dead-end.

Practice › Codeforces Solutions › 2020-2021 ACM-ICPC, Asia Seoul Regional Contest ›

CF 102920L - Two Buildings

We are given a sequence of building heights arranged in a straight line, each position having a building of width 1.

Practice › Codeforces Solutions › 2020-2021 ACM-ICPC, Asia Seoul Regional Contest ›

CF 102920F - Ink Mix

Let $a1 ge a2 ge cdots ge am ge 1$ be a partition of $n$ into $m$ parts that is optimally balanced, meaning $ Let $t$ be the number of parts equal to $x$ and $m-t$ the number of parts equal to $x-1$. The partition has total sum $$n = tx + (m-t)(x-1) = mx - (m-t).

Practice › Codeforces Solutions › 2020-2021 ACM-ICPC, Asia Seoul Regional Contest ›

CF 102920J - Switches

We are given a system with the same number of switches and lights, and a binary connection matrix describing how switches influence lights.

Practice › Codeforces Solutions › 2020-2021 ACM-ICPC, Asia Seoul Regional Contest ›

CF 102920I - Stock Analysis

We are given a sequence of daily stock fluctuation values. Each value represents the change from one day to the next, so any contiguous segment represents the total change over a continuous time window. For each query, we restrict ourselves to a subarray interval $[S, E]$.

Practice › Codeforces Solutions › 2020-2021 ACM-ICPC, Asia Seoul Regional Contest ›

CF 102920H - Needle

The border between the two kingdoms is made of three horizontal lines, stacked one above another with equal vertical spacing. Each line has several “holes”, each located at an integer position along the horizontal axis.

Practice › Codeforces Solutions › 2020-2021 ACM-ICPC, Asia Seoul Regional Contest ›

CF 102920G - Mobile Robot

We are given a line with $n$ robots, each starting at some real coordinate. We must relocate them so that after movement they form a perfectly regular chain: robot $i+1$ must be exactly distance $d$ to the right of robot $i$.

Practice › Codeforces Solutions › 2020-2021 ACM-ICPC, Asia Seoul Regional Contest ›

CF 102920E - Imprecise Computer

We are given a sequence of integers of length $n$, and we are told to imagine it as a derived statistic from a peculiar tournament on the set ${1,2,dots,n}$. In this tournament, every pair of distinct numbers is compared twice.

Practice › Codeforces Solutions › 2020-2021 ACM-ICPC, Asia Seoul Regional Contest ›

CF 102920D - Electric Vehicle

We are given a complete graph whose vertices are villages placed on a 2D grid. The cost of traveling between two villages is not fixed in advance as an edge weight in the usual sense, but instead comes from energy consumption: moving between two points consumes energy equal to…

Practice › Codeforces Solutions › 2020-2021 ACM-ICPC, Asia Seoul Regional Contest ›

CF 102920A - Autonomous Vehicle

Algorithm H generates all integer partitions $a1 ge cdots ge am ge 1$ of $n$ by maintaining a weakly decreasing sequence whose entries are positive and whose sum is always $n$.

Practice › Codeforces Solutions › 2020-2021 ACM-ICPC, Asia Seoul Regional Contest ›

CF 102920C - Dessert Café

We are given a weighted tree where each node is a candidate location for a café, and a subset of nodes are marked as apartment complexes. The distance between any two nodes is the sum of edge weights along their unique path in the tree.

Practice › Codeforces Solutions › 2020-2021 ACM-ICPC, Asia Seoul Regional Contest ›

CF 102920B - Commemorative Dice

We are given two cubes, each with six faces. Every face contains a positive integer, and for each cube the six values sum to 21. When the cube is rolled, each face is equally likely to appear, so each cube defines a uniform probability distribution over its six face values.