The 2022 ICPC Asia Hangzhou Regional Programming Contest

13 problems from The 2022 ICPC Asia Hangzhou Regional Programming Contest (contest 104090), difficulty -. 10/13 solutions verified against sample I/O.

13 items

The 2022 ICPC Asia Hangzhou Regional Programming Contest

ICPC/IOI | 13 problems | 10/13 verified | Difficulty - | 13m 30s

#	Problem	Time	✓
A	Modulo Ruins the Legend	52s	✓
B	Useful Algorithm	53s	✓
C	No Bug No Game	53s	✓
D	Money Game	56s	✓
E	Oscar is All You Need	53s	✓
F	Da Mi Lao Shi Ai Kan De	2m 13s
G	Subgraph Isomorphism	57s	✓
H	RPG Pro League	1m 6s	✓
I	Guess Cycle Length	45s	✓
J	Painting	39s
K	Master of Both	2m 3s
L	Levenshtein Distance	43s	✓
M	Please Save Pigeland	37s	✓

Practice › Codeforces Solutions › The 2022 ICPC Asia Hangzhou Regional Programming Contest ›

CF 104090K - Master of Both

In a ZDD, each level corresponds to a variable, and a node labeled $k$ represents a decision on $xk$, where the low edge excludes the variable and the high edge includes it in the represented family of sets.

Practice › Codeforces Solutions › The 2022 ICPC Asia Hangzhou Regional Programming Contest ›

CF 104090M - Please Save Pigeland

We are given a weighted tree of up to 5×10^5 cities. A subset of k cities are infected. We must choose one city r as a hospital location and also choose a fixed integer parameter d for a special transport system.

Practice › Codeforces Solutions › The 2022 ICPC Asia Hangzhou Regional Programming Contest ›

CF 104090L - Levenshtein Distance

We are given a pattern string S and a text string T. From T, we consider every contiguous substring. For each such substring X, we compute its Levenshtein distance to S, meaning the minimum number of insertions, deletions, or substitutions needed to transform one string into…

Practice › Codeforces Solutions › The 2022 ICPC Asia Hangzhou Regional Programming Contest ›

CF 104090J - Painting

Working

Practice › Codeforces Solutions › The 2022 ICPC Asia Hangzhou Regional Programming Contest ›

CF 104090I - Guess Cycle Length

We are interacting with a hidden directed structure that is actually a single cycle of unknown length. There are n vertices arranged in a loop, but we do not know n and we do not know the labeling order.

Practice › Codeforces Solutions › The 2022 ICPC Asia Hangzhou Regional Programming Contest ›

CF 104090F - Da Mi Lao Shi Ai Kan De

Practice › Codeforces Solutions › The 2022 ICPC Asia Hangzhou Regional Programming Contest ›

CF 104090H - RPG Pro League

We are given a pool of players. Each player has a price and a set of roles they are capable of performing. A player can be used in at most one team and, within that team, occupies exactly one role from their allowed set.

Practice › Codeforces Solutions › The 2022 ICPC Asia Hangzhou Regional Programming Contest ›

CF 104090G - Subgraph Isomorphism

We are given a connected undirected simple graph $G$. From this graph, consider all connected subgraphs that use all $n$ vertices and contain exactly $n-1$ edges.

Practice › Codeforces Solutions › The 2022 ICPC Asia Hangzhou Regional Programming Contest ›

CF 104090D - Money Game

We are given a circular system of players, each holding a real-valued amount of money. The players are arranged in a fixed cycle, and during one round every player simultaneously transfers half of their current money to their clockwise neighbor, with the last player sending…

Practice › Codeforces Solutions › The 2022 ICPC Asia Hangzhou Regional Programming Contest ›

CF 104090E - Oscar is All You Need

We are given a permutation of size $n$, and we are allowed to repeatedly rearrange it using a very specific block operation. Each operation selects two cut points that split the array into three consecutive non-empty segments.

Practice › Codeforces Solutions › The 2022 ICPC Asia Hangzhou Regional Programming Contest ›

CF 104090C - No Bug No Game

We are given a collection of items, each item having two pieces of information: a mandatory “size” value $pi$, and a list of possible bonus values $w{i,1}, w{i,2}, dots, w{i,pi}$. The player chooses an ordering of all items.

Practice › Codeforces Solutions › The 2022 ICPC Asia Hangzhou Regional Programming Contest ›

CF 104090A - Modulo Ruins the Legend

We are given an array of integers, and we are allowed to modify it using a very structured operation: choose two non-negative integers s and d, then add an arithmetic progression to the array so that position k (1-indexed) increases by s + (k-1)d.

Practice › Codeforces Solutions › The 2022 ICPC Asia Hangzhou Regional Programming Contest ›

CF 104090B - Useful Algorithm

We are given a small bit-width $m le 16$, so every value $ci$ is an $m$-bit binary number. The core operation is binary addition with full carry propagation exactly as in standard bitwise addition: each bit produces a sum bit and a carry to the next position.