Helvetic Coding Contest 2019 online mirror (teams allowed, unrated)
Solutions for Helvetic Coding Contest 2019 online mirror (teams allowed, unrated) (contest 1184). 11/14 problems verified against sample I/O. Difficulty range: 1200-3200.
Helvetic Coding Contest 2019 online mirror (teams allowed, unrated)
Type: Special | Problems: 14 | Verified: 11/14 | Rating range: 1200-3200 | Time: 56m 25s
| Problem | Name | Rating | Tags | Solve Time | Verified |
|---|---|---|---|---|---|
| A1 | Heidi Learns Hashing (Easy) | 1200 | brute-force, math, number-theory | 3m 46s | ✓ |
| A2 | Heidi Learns Hashing (Medium) | 2100 | brute-force, number-theory | 1m 26s | ✓ |
| A3 | Heidi Learns Hashing (Hard) | 3100 | fft, math, number-theory | 7m 45s | ✓ |
| B1 | The Doctor Meets Vader (Easy) | 1400 | binary-search, sortings | 5m 28s | ✓ |
| B2 | The Doctor Meets Vader (Medium) | 2200 | flows, graph-matchings, graphs | 2m 6s | ✓ |
| B3 | The Doctor Meets Vader (Hard) | 2700 | flows, shortest-paths | 5m 10s | ✗ |
| C1 | Heidi and the Turing Test (Easy) | 1600 | implementation | 2m 9s | ✓ |
| C2 | Heidi and the Turing Test (Medium) | 2200 | data-structures | 2m 8s | ✓ |
| C3 | Heidi and the Turing Test (Hard) | 3200 | - | 1m 4s | ✓ |
| D1 | Parallel Universes (Easy) | 1600 | implementation | 3m 16s | ✓ |
| D2 | Parallel Universes (Hard) | 3100 | math, matrices | 2m 28s | ✓ |
| E1 | Daleks' Invasion (easy) | 1900 | graphs, trees | 3m 19s | ✗ |
| E2 | Daleks' Invasion (medium) | 2100 | dfs-and-similar, graphs, shortest-paths | 10m 39s | ✓ |
| E3 | Daleks' Invasion (hard) | 2400 | data-structures, dsu, graphs | 5m 41s | ✗ |
CF 1184E2 - Daleks' Invasion (medium)
We are given a connected undirected graph where each edge represents a corridor with a unique energy cost. The Daleks always intend to build a minimum spanning tree, so among all possible spanning trees they will pick the one with minimum total cost, which is uniquely…
CF 1184E3 - Daleks' Invasion (hard)
We are given an undirected connected graph with weighted edges, where each edge represents a corridor between two locations and has an associated energy value.
CF 1184E1 - Daleks' Invasion (easy)
We are given a connected undirected graph where each edge represents a Time Corridor with an associated energy cost. The Daleks do not necessarily use all corridors.
CF 1184D2 - Parallel Universes (Hard)
We are simulating a probabilistic system that evolves a one-dimensional structure of length l, where a distinguished position called the Doctor’s current universe is fixed inside this structure.
CF 1184A3 - Heidi Learns Hashing (Hard)
We are given two strings of equal length and we want to force a collision under a polynomial rolling hash. The hash is defined by interpreting each string as coefficients of a polynomial in a base $r$, and then evaluating it modulo a prime $p$.
CF 1184C2 - Heidi and the Turing Test (Medium)
We are given a set of points on a 2D plane and a fixed radius in Manhattan distance. The task is to choose a center anywhere in the plane, not necessarily at an integer coordinate, and find the largest number of given points that lie within Manhattan distance at most r from…
CF 1184C1 - Heidi and the Turing Test (Easy)
We are given a small set of points on a grid, where almost all points lie exactly on the border of an axis-aligned square. Only one point is an exception and lies strictly inside the square. The task is to identify that single interior point. The square is not given explicitly.
CF 1184B1 - The Doctor Meets Vader (Easy)
Each spaceship has an attack power. Each empire base has a defense value and a gold amount. A spaceship can destroy every base whose defense is not greater than the spaceship's attack power.
CF 1184B3 - The Doctor Meets Vader (Hard)
We are working on a weighted selection problem over two interacting layers. First, there is a small fixed graph of planets, where distances are measured as the shortest number of wormholes between nodes. Then there is a large set of spaceships and bases placed on these planets.
CF 1184D1 - Parallel Universes (Easy)
We have a line of universes arranged sequentially, each numbered from 1 to $n$, with the Doctor starting at position $k$. The multiverse can change over time according to a series of operations.
CF 1184C3 - Heidi and the Turing Test (Hard)
We are given a set of noisy points in the plane that lie close to a small number of circles, or rings. Each ring has a center and a radius, and each sampled point deviates slightly from the exact circumference.
CF 1184A1 - Heidi Learns Hashing (Easy)
The problem gives us a function $H(x, y) = x^2 + 2xy + x + 1$, and a positive integer $r$. We need to determine whether there exists a pair of positive integers $(x, y)$ such that $H(x, y) = r$.
CF 1184B2 - The Doctor Meets Vader (Medium)
The galaxy is a small graph of planets connected by wormholes, where distance between planets is measured as the minimum number of edges in this graph. On top of this infrastructure, there are two kinds of actors: empire ships and rebel bases.
CF 1184A2 - Heidi Learns Hashing (Medium)
We are given a binary string y of length n. We want to count how many cyclic shift amounts k produce a situation where we can reconstruct some binary string x such that if we take x and XOR it with a circular right shift of itself by k, we obtain exactly y.