2019-2020 ICPC, Asia Jakarta Regional Contest (Online Mirror, ICPC Rules, Teams Preferred)
11 problems from 2019-2020 ICPC, Asia Jakarta Regional Contest (Online Mirror, ICPC Rules, Teams Preferred) (contest 1252), difficulty 1000-3000. 4/11 solutions verified against sample I/O.
2019-2020 ICPC, Asia Jakarta Regional Contest (Online Mirror, ICPC Rules, Teams Preferred)
ICPC/IOI | 11 problems | 4/11 verified | Difficulty 1000-3000 | 31m
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Copying Homework | 1000 | 5,997 | 1m 50s | ✓ | |
| B | Cleaning Robots | 2300 | dp, trees | 585 | 1m 58s | ✓ |
| C | Even Path | 1600 | data-structures, implementation | 3,982 | 1m 50s | |
| D | Find String in a Grid | 3000 | data-structures, dp, strings | 412 | 1m 49s | |
| F | Regular Forestation | 2400 | hashing, trees | 1,069 | 4m 24s | |
| G | Performance Review | 2100 | data-structures | 1,553 | 2m 5s | ✓ |
| H | Twin Buildings | 1800 | greedy, implementation | 2,846 | 4m 48s | |
| I | Mission Possible | 3000 | 35 | 2m 2s | ||
| J | Tiling Terrace | 2300 | brute-force, dp | 783 | 6m 44s | ✓ |
| K | Addition Robot | 2100 | data-structures, math, matrices | 2,064 | 1m 52s | |
| L | Road Construction | 2300 | flows, graphs | 642 | 1m 38s |
CF 1252K - Addition Robot
The robot stores a binary instruction string over the alphabet {A, B}. When we process this string with an initial pair of values (A, B), each character acts like a small transformation step.
CF 1252L - Road Construction
We are given a set of cities where each city proposes exactly one possible road. City $i$ wants to connect to a specific other city $Ai$, so each proposal is an undirected edge $(i, Ai)$.
CF 1252I - Mission Possible
We are given a rectangular region and several circular sensors placed inside it. Each sensor detects any point that lies strictly inside its circle.
CF 1252C - Even Path
The grid in this problem is not given explicitly as an $N times N$ matrix. Instead, every cell value is determined by a simple additive structure: the value at position $(i, j)$ is $Ri + Cj$.
CF 1252D - Find String in a Grid
We are given a rectangular grid of uppercase letters and many query strings. For each query string, we need to count how many ways it can be traced inside the grid under a very specific movement rule: we start from some cell, first move only to the right any number of steps…
CF 1252J - Tiling Terrace
We are given a one-dimensional yard of length $N$, where each position is either usable soil or blocked by a rock. We want to place tiles on this line to maximize total “ghost repelling power”.
CF 1252H - Twin Buildings
We are given several rectangular plots of land, and we want to place two identical rectangular buildings of size $A times B$.
CF 1252F - Regular Forestation
We are given a tree with up to 4000 nodes, and we are allowed to pick a single node and remove it. Removing a node splits the tree into several connected components, each of which is itself a tree. The number of components equals the degree of the removed node.
CF 1252G - Performance Review
We are tracking whether a single employee, Randall, remains employed after a sequence of yearly “pruning” operations in a company where employees are ranked by a fixed performance value. The company always keeps exactly $N$ employees.
CF 1252B - Cleaning Robots
We are given a tree with $N$ junctions and $N-1$ roads connecting them. A tree means that every pair of junctions is connected by exactly one path.
CF 1252A - Copying Homework
We are given a permutation of integers from 1 to N, which represents Danang's completed homework. Darto wants to submit his own permutation, different enough from Danang's, but still using numbers 1 through N exactly once.