Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)
Solutions for Helvetic Coding Contest 2024 online mirror (teams allowed, unrated) (contest 1970). 6/21 problems verified against sample I/O. Difficulty range: 1000-3100.
Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)
Type: Special | Problems: 21 | Verified: 6/21 | Rating range: 1000-3100 | Time: 47m 10s
| Problem | Name | Rating | Tags | Solve Time | Verified |
|---|---|---|---|---|---|
| A1 | Balanced Shuffle (Easy) | 1000 | implementation, sortings | 2m 8s | ✓ |
| A2 | Balanced Unshuffle (Medium) | 2400 | brute-force, constructive-algorithms, trees | 2m 43s | ✗ |
| A3 | Balanced Unshuffle (Hard) | 2400 | constructive-algorithms, trees | 2m 8s | ✗ |
| B1 | Exact Neighbours (Easy) | 1900 | constructive-algorithms | 1m 52s | ✗ |
| B2 | Exact Neighbours (Medium) | 2100 | constructive-algorithms | 2m 32s | ✗ |
| B3 | Exact Neighbours (Hard) | 2300 | constructive-algorithms | 2m 1s | ✗ |
| C1 | Game on Tree (Easy) | 1400 | games | 1m 18s | ✓ |
| C2 | Game on Tree (Medium) | 1700 | dfs-and-similar, dp, games | 2m | ✓ |
| C3 | Game on Tree (Hard) | 1900 | dfs-and-similar, dp, games | 1m 59s | ✓ |
| D1 | Arithmancy (Easy) | 2100 | brute-force, constructive-algorithms, interactive | 2m 4s | ✗ |
| D2 | Arithmancy (Medium) | 2600 | constructive-algorithms, interactive, probabilities | 1m 57s | ✗ |
| D3 | Arithmancy (Hard) | 3100 | interactive | 2m 23s | ✗ |
| E1 | Trails (Easy) | 1800 | dp | 1m 38s | ✓ |
| E2 | Trails (Medium) | 2000 | dp, matrices | 1m 39s | ✓ |
| E3 | Trails (Hard) | 2200 | dp, matrices | 2m 16s | ✗ |
| F1 | Playing Quidditch (Easy) | 2300 | implementation | 2m 30s | ✗ |
| F2 | Playing Quidditch (Medium) | 2300 | implementation | 2m 35s | ✗ |
| F3 | Playing Quidditch (Hard) | 2300 | implementation | 5m 28s | ✗ |
| G1 | Min-Fund Prison (Easy) | 1900 | dfs-and-similar, trees | 1m 43s | ✗ |
| G2 | Min-Fund Prison (Medium) | 2200 | brute-force, dfs-and-similar, dp | 2m 12s | ✗ |
| G3 | Min-Fund Prison (Hard) | 2400 | bitmasks, dfs-and-similar, dp | 2m 4s | ✗ |
CF 1970F3 - Playing Quidditch (Hard)
We are simulating a very small event-driven game played on a grid. The grid contains players from two teams, fixed goals for each team, and up to three types of balls: the Quaffle (used for scoring), the Bludger (which eliminates players on contact), and the Golden Snitch…
CF 1970G3 - Min-Fund Prison (Hard)
We are given an undirected graph representing a prison, where vertices are cells and edges are existing corridors.
CF 1970G2 - Min-Fund Prison (Medium)
We are asked to partition a prison into two complexes in a way that minimizes total funding. Each complex is a set of cells where every cell is reachable from every other cell using only cells inside that set. The cost of a complex is the square of its size.
CF 1970G1 - Min-Fund Prison (Easy)
The input describes a collection of cells connected by corridors forming a tree. Each cell is a node, and each corridor is an undirected edge. Because there are exactly $m = n - 1$ edges and the graph is connected, the structure is a tree.
CF 1970F2 - Playing Quidditch (Medium)
The game is a simplified simulation of Quidditch on a 2D grid. Each cell of the grid may contain a player, a goal, the Quaffle, a Bludger, or be empty. Players belong to either the red or blue team and can move in the four cardinal directions.
CF 1970F1 - Playing Quidditch (Easy)
We are asked to simulate a simplified Quidditch game on a rectangular grid. The field contains players from two teams, goals for both teams, and exactly one Quaffle. Each player can move in one of four directions, catch the Quaffle if it is on their cell, and throw it.
CF 1970E3 - Trails (Hard)
We are asked to count the number of possible sequences of trails Harry can take over n days starting from cabin 1. Each day consists of two moves: first from his current cabin to the lake, then from the lake to any cabin.
CF 1970E2 - Trails (Medium)
The problem describes a scenario where Harry Potter moves between a set of cabins and a central lake along trails. Each cabin has a number of short and long trails connecting it to the lake.
CF 1970D3 - Arithmancy (Hard)
We are tasked with designing n distinct strings of characters X and O, called magic words. Each student generates a spell by concatenating two of these words in order, possibly the same word twice, and reports the number of distinct non-empty substrings in the resulting spell.
CF 1970E1 - Trails (Easy)
We are asked to count the number of valid hiking itineraries for Harry Potter in the Alps over n days. There are m cabins, each connected to the central meeting point by a number of short and long trails.
CF 1970D2 - Arithmancy (Medium)
We are asked to play the role of Professor Vector. We need to construct a set of distinct magic words made of 'X' and 'O' and then, given a number called the power of a spell, figure out which two words (and in which order) were concatenated to create that power.
CF 1970D1 - Arithmancy (Easy)
We are asked to play the role of Professor Vector in an interactive problem. Our task is twofold. First, we need to generate n distinct magic words consisting only of X and O.
CF 1970C3 - Game on Tree (Hard)
We are given a tree of n nodes, and multiple rounds of a two-player game. In each round, a stone starts on one node. Players alternate moves, moving the stone to an unactivated neighbor and marking that neighbor as activated. The player who cannot move loses.
CF 1970C2 - Game on Tree (Medium)
We are given a tree where every node is initially unused. A single stone is placed on a chosen starting node. From that moment, players alternate moves, starting with Ron. A move consists of sliding the stone along an edge to a neighboring node that has never been visited before.
CF 1970C1 - Game on Tree (Easy)
The structure we are given is not an arbitrary tree in the usual sense, but a very restricted one: it has exactly two leaves. That means every node has degree at most two, except possibly some internal nodes, and the whole graph is essentially a single chain.
CF 1970B3 - Exact Neighbours (Hard)
We are asked to place n wizard houses on an n × n grid such that two conditions are met. First, no two houses can occupy the same column; this ensures that each wizard has an unobstructed view north and south.
CF 1970B2 - Exact Neighbours (Medium)
We are asked to place $n$ wizard houses on an $n times n$ grid such that each wizard can reach another wizard’s house at a prescribed Manhattan distance $ai$, and no two houses share the same column.
CF 1970B1 - Exact Neighbours (Easy)
We are asked to place n wizard houses on an n x n grid such that each house occupies a unique row and column, and each wizard has a target distance ai that they want to travel to another house during the weekend.
CF 1970A2 - Balanced Unshuffle (Medium)
The task is to invert the so-called balanced shuffle operation on a balanced parentheses string. You are given a string s of parentheses that is guaranteed to be balanced.
CF 1970A1 - Balanced Shuffle (Easy)
We are given a string composed solely of opening and closing parentheses. The string is guaranteed to be a balanced parentheses sequence, which means the total number of "(" matches the number of ")" and every prefix of the string has at least as many "(" as ")".
CF 1970A3 - Balanced Unshuffle (Hard)
We are given a single valid parentheses sequence, meaning it contains the same number of opening and closing brackets and never drops below zero balance in any prefix.