2019 ICPC Asia-East Continent Final

13 problems from 2019 ICPC Asia-East Continent Final (contest 102471), difficulty -. 12/13 solutions verified against sample I/O.

13 items

2019 ICPC Asia-East Continent Final

ICPC/IOI | 13 problems | 12/13 verified | Difficulty - | 1h 21m

#	Problem	Time	✓
A	City	2m 38s	✓
B	Black and White	12m 11s	✓
C	Dirichlet $k$-th root	3m 40s	✓
D	Fire	8m 33s	✓
E	Flow	1m 20s	✓
F	Game	2m 23s
G	Happiness	11m 10s	✓
H	King	6m 30s	✓
I	Moon	5m 47s	✓
J	Permutation	7m 30s	✓
K	All Pair Maximum Flow	8m 50s	✓
L	Travel	4m 55s	✓
M	Value	6m 5s	✓

Practice › Codeforces Solutions › 2019 ICPC Asia-East Continent Final ›

CF 102471B - Black and White

We have an (ntimes m) chessboard whose cell ((i,j)) has value (+1) when (i+j) is even and (-1) otherwise. A valid path consists of exactly (n) north steps and (m) east steps, starting at the bottom-left corner and ending at the top-right corner.

Practice › Codeforces Solutions › 2019 ICPC Asia-East Continent Final ›

CF 102471L - Travel

We have a directed graph with up to 2000 vertices and 4000 directed edges. We must count ordered pairs of paths (P1, P2). A path may be empty and may repeat vertices, but repetition is only possible through a directed cycle.

Practice › Codeforces Solutions › 2019 ICPC Asia-East Continent Final ›

CF 102471M - Value

We choose some indices from 1 through n. Every chosen index i contributes ai to the score. There is one kind of interaction between chosen indices: if both i and j are chosen and j = i^k for some integer k 1, then bj is subtracted once.

Practice › Codeforces Solutions › 2019 ICPC Asia-East Continent Final ›

CF 102471K - All Pair Maximum Flow

The graph is drawn inside a convex polygon whose vertices are numbered cyclically. Every polygon side is present, and additional diagonals may be added, but the diagonals never cross except at common endpoints. Each edge has a nonnegative capacity.

Practice › Codeforces Solutions › 2019 ICPC Asia-East Continent Final ›

CF 102471J - Permutation

We have a permutation of the numbers from 1 to n, and an integer c. An operation looks at exactly c+1 consecutive positions. If the smallest value in that interval is at one endpoint, that endpoint is kept fixed and the other c values may be rearranged arbitrarily.

Practice › Codeforces Solutions › 2019 ICPC Asia-East Continent Final ›

CF 102471G - Happiness

Pang is one of n teams in a ten-problem ICPC contest. The other n - 1 teams have fixed final results. Pang knows a subset of the ten problems, and solving a known problem takes a fixed amount of time and incurs a fixed number of rejected submissions before acceptance.

Practice › Codeforces Solutions › 2019 ICPC Asia-East Continent Final ›

CF 102471C - Dirichlet $k$-th root

We work with arrays indexed by positive integers, but multiplication of arrays is not ordinary elementwise multiplication. For two functions (f) and (g), their Dirichlet convolution at (n) is [ (fg)(n)=sum{dmid n}f(d)g(n/d).

Practice › Codeforces Solutions › 2019 ICPC Asia-East Continent Final ›

CF 102471I - Moon

We have fixed points a 1 ,…,a n on the unit sphere. A new point a 0 is chosen uniformly from the sphere. We ask whether all n+1 points can fit inside one closed hemisphere.

Practice › Codeforces Solutions › 2019 ICPC Asia-East Continent Final ›

CF 102471H - King

We have a sequence (b1,b2,ldots,bn) of nonzero residues modulo a prime (p). A King sequence is a subsequence whose consecutive values are obtained by multiplying by one fixed nonzero residue (q).

Practice › Codeforces Solutions › 2019 ICPC Asia-East Continent Final ›

CF 102471D - Fire

Root the tree at vertex 1. Pang starts at the root and must eventually cast his magic exactly once at every vertex.

Practice › Codeforces Solutions › 2019 ICPC Asia-East Continent Final ›

CF 102471A - City

We have an n×m rectangular grid of unit squares. Its grid points have integer coordinates, so there are (n+1)(m+1) points in total.

Practice › Codeforces Solutions › 2019 ICPC Asia-East Continent Final ›

CF 102471F - Game

I can't produce a correct editorial for this problem because the prompt only contains the problem statement, not the key missing ingredient: the solution or enough information to derive it reliably.

Practice › Codeforces Solutions › 2019 ICPC Asia-East Continent Final ›

CF 102471E - Flow

The graph has a special shape: it is made from several independent routes going from the source vertex 1 to the sink vertex n. Every route contains the same number of edges, and routes do not share internal vertices. Capacities on edges can be moved around by unit operations.