ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
13 problems from ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred) (contest 1578), difficulty 1200-3500. 2/13 solutions verified against sample I/O.
ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
ICPC/IOI | 13 problems | 2/13 verified | Difficulty 1200-3500 | 56m 12s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Anti-Tetris | 2800 | constructive-algorithms, graphs, shortest-paths | 422 | 3m 52s | |
| B | Building Forest Trails | 2800 | data-structures, dsu | 475 | 4m 26s | ✓ |
| C | Cactus Lady and her Cing | 3500 | 13 | 6m 6s | ||
| D | Dragon Curve | 3200 | 55 | 2m 10s | ||
| E | Easy Scheduling | 1200 | implementation, math | 4,133 | 3m 21s | |
| F | Framing Pictures | 2900 | geometry | 187 | 7m 12s | |
| G | Game of Chance | 3500 | math, probabilities | 56 | 5m 52s | |
| H | Higher Order Functions | 1700 | implementation, strings | 2,169 | 1m 14s | ✓ |
| I | Interactive Rays | 3300 | geometry, interactive | 72 | 2m 13s | |
| J | Just Kingdom | 3100 | brute-force, data-structures, dfs-and-similar | 345 | 5m 32s | |
| K | Kingdom of Islands | 2800 | brute-force, graphs, implementation | 408 | 4m 15s | |
| L | Labyrinth | 2400 | binary-search, dsu, greedy | 1,435 | 3m 48s | |
| M | The Mind | 2700 | constructive-algorithms, interactive, probabilities | 515 | 6m 11s |
CF 1578M - The Mind
Each test gives us a hand of five distinct numbers between 1 and 100. Two players independently receive such hands, and each player only sees their own five numbers.
CF 1578L - Labyrinth
The labyrinth can be seen as a connected weighted graph where rooms are nodes and passages are undirected edges with capacities. Each room also has a one-time “growth value” that increases Lucy’s width if she chooses to eat that room’s candy.
CF 1578K - Kingdom of Islands
We are given a set of jarls, each belonging to exactly one island. The default rule of conflict is simple: jarls from different islands are in conflict, while jarls from the same island are peaceful.
CF 1578J - Just Kingdom
We are given a rooted hierarchy with a single root, the king, and up to $n$ lords forming a tree where each lord has exactly one parent. Each lord $i$ has a required amount of money $mi$.
CF 1578F - Framing Pictures
We are given a convex polygon in the plane, and this polygon represents the silhouette of an object. We imagine rotating the viewing direction uniformly at random, and for each orientation we project the polygon onto axes aligned with that view.
CF 1578G - Game of Chance
We are given a line of participants, each assigned a positive “luckiness” value. These participants enter a knockout tournament with a very rigid pairing structure.
CF 1578B - Building Forest Trails
We are given a circular arrangement of villages, labeled from 1 to n in clockwise order. Initially there are no connections between any pair of villages.
CF 1578A - Anti-Tetris
We are given a final board configuration of a grid-based stacking process where multiple small polyomino-like pieces were dropped one after another. Each piece is connected in four directions, has at most seven cells, and is identified by a letter.
CF 1578I - Interactive Rays
We are working in a plane where a circle is hidden from us. The circle is fully determined by its center coordinates and its radius, but we do not know them. Our only tool is to shoot a ray starting from the origin and passing through an integer point we choose.
CF 1578H - Higher Order Functions
We are given a single string that represents a type expression built from three constructs: a base unit type written as (), parentheses that group a type without changing its meaning, and a function constructor written as - that connects two types.
CF 1578E - Easy Scheduling
We are asked to schedule tasks that are arranged as a full binary tree of height $h$. A full binary tree of height $h$ has $2^h - 1$ nodes. Initially, only the root task is ready. At each discrete moment of time, up to $p$ processes can perform ready tasks simultaneously.
CF 1578C - Cactus Lady and her Cing
We are given a cactus graph, which is a connected undirected graph where each vertex lies on at most one simple cycle. That means every vertex is either part of a tree structure or part of a single cycle. No multi-edges or loops are allowed.
CF 1578D - Dragon Curve
Every unit square with integer corners is crossed by exactly one segment of one of four infinite dragon curves. For a query square with opposite corners $(x,y)$ and $(x+1,y+1)$, we must determine two things.