2019-2020 ICPC, Moscow Subregional

11 problems from 2019-2020 ICPC, Moscow Subregional (contest 104847), difficulty -. 11/11 solutions verified against sample I/O.

11 items

2019-2020 ICPC, Moscow Subregional

ICPC/IOI | 11 problems | 11/11 verified | Difficulty - | 10m 54s

#	Problem	Time	✓
A	Quantum Supremacy	47s	✓
B	Post-capitalism	1m 3s	✓
C	Huawei Frequencies Selection	1m 23s	✓
D	JCPC Registration System	48s	✓
E	Raiffeisenbank Logistics	50s	✓
F	Toll Road	47s	✓
G	Yandex Museum	1m 10s	✓
H	Rebellious Sequences	1m 9s	✓
I	Minimax Limit	52s	✓
J	You Are Given a Tree	1m 15s	✓
K	Dynamic Traffic with MegaFon	50s	✓

Practice › Codeforces Solutions › 2019-2020 ICPC, Moscow Subregional ›

CF 104847J - You Are Given a Tree

We are given a tree with vertices numbered from 1 to n. The edges are given in a very specific way: each new vertex i + 1 is connected to an earlier vertex pi.

Practice › Codeforces Solutions › 2019-2020 ICPC, Moscow Subregional ›

CF 104847K - Dynamic Traffic with MegaFon

We are given a sequence of integers that represent net traffic changes over time. Each value can be positive or negative, and we are allowed to discard any elements we want, preserving order among the remaining ones.

Practice › Codeforces Solutions › 2019-2020 ICPC, Moscow Subregional ›

CF 104847H - Rebellious Sequences

We are given a string that represents a correct bracket sequence, meaning it behaves like a well-formed parenthesis structure: as we scan from left to right, we never see more closing brackets than opening ones, and the total numbers of both types are equal.

Practice › Codeforces Solutions › 2019-2020 ICPC, Moscow Subregional ›

CF 104847I - Minimax Limit

We are given a function defined on the segment from 0 to n. Its values at integer points are fixed by an array a, where f(i) = a[i].

Practice › Codeforces Solutions › 2019-2020 ICPC, Moscow Subregional ›

CF 104847G - Yandex Museum

We are given up to one hundred thousand triangles drawn on a 2D plane. The canvas starts entirely red. Each triangle is applied one after another with a very specific paint rule: the boundary of the triangle is permanently painted black, while every point strictly inside the…

Practice › Codeforces Solutions › 2019-2020 ICPC, Moscow Subregional ›

CF 104847F - Toll Road

We are given a one-dimensional highway from position 0 to position L. Along this line there are special marked points, each placed at an integer coordinate, and each point is either an entrance or an exit.

Practice › Codeforces Solutions › 2019-2020 ICPC, Moscow Subregional ›

CF 104847E - Raiffeisenbank Logistics

We are given a directed system of locations, where each routing program behaves like a conditional edge: it only moves the drone from its starting location to its destination if the drone is currently at the correct start node. Otherwise it does nothing.

Practice › Codeforces Solutions › 2019-2020 ICPC, Moscow Subregional ›

CF 104847D - JCPC Registration System

We are given a calendar UI that can be manipulated through three independent controls: year, month, and day selection.

Practice › Codeforces Solutions › 2019-2020 ICPC, Moscow Subregional ›

CF 104847C - Huawei Frequencies Selection

We are given an array of length n that describes a sequence of maintenance bans. Each second i forbids exactly one frequency ai from being used. There are n + 1 possible frequencies, labeled from 0 up to n, where smaller labels are more desirable.

Practice › Codeforces Solutions › 2019-2020 ICPC, Moscow Subregional ›

CF 104847B - Post-capitalism

We are looking at a stochastic wealth process on $n$ people. Everyone starts with exactly one unit of money. After that, many additional unit transfers happen.

Practice › Codeforces Solutions › 2019-2020 ICPC, Moscow Subregional ›

CF 104847A - Quantum Supremacy

We are comparing two ways to exhaustively test all binary strings of length $n$. There are $2^n$ possible secrets. A classical machine tests exactly one candidate per $a$ seconds, so its total time is proportional to $a cdot 2^n$. A quantum machine behaves differently.