EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2)
Solutions for EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2) (contest 2002). 3/10 problems verified against sample I/O. Difficulty range: 800-3500.
EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2)
Type: Div. 1+2 | Problems: 10 | Verified: 3/10 | Rating range: 800-3500 | Time: 20m 9s
| Problem | Name | Rating | Tags | Solve Time | Verified |
|---|---|---|---|---|---|
| A | Distanced Coloring | 800 | constructive-algorithms, implementation, math | 1m 48s | ✓ |
| B | Removals Game | 1000 | constructive-algorithms, games | 3m | ✓ |
| C | Black Circles | 1200 | brute-force, geometry, greedy | 1m 22s | ✗ |
| D1 | DFS Checker (Easy Version) | 1900 | brute-force, data-structures, dfs-and-similar | 1m 30s | ✓ |
| D2 | DFS Checker (Hard Version) | 2300 | binary-search, data-structures, dfs-and-similar | 2m 23s | ✗ |
| E | Cosmic Rays | 2300 | brute-force, data-structures, dp | 2m 14s | ✗ |
| F1 | Court Blue (Easy Version) | 2600 | brute-force, dfs-and-similar, dp | 2m 57s | ✗ |
| F2 | Court Blue (Hard Version) | 2800 | brute-force, dp, math | 2m 14s | ✗ |
| G | Lattice Optimizing | 3400 | bitmasks, brute-force, hashing | 39s | ✗ |
| H | Counting 101 | 3500 | greedy | 2m 2s | ✗ |
CF 2002H - Counting 101
We are asked to count sequences of integers with a very particular merging property. For a given sequence of length n, each element between 1 and m, we are allowed to repeatedly take three consecutive elements ai, a{i+1}, a{i+2} and merge them into a single number defined as…
CF 2002F2 - Court Blue (Hard Version)
We are constructing a sequence of rounds where exactly one of two players gains a point in each round. After each round we maintain two counters, one for each player, and the process is only valid if at every prefix the greatest common divisor of the two counters never exceeds 1.
CF 2002F1 - Court Blue (Easy Version)
We are asked to plan a match between two performers, Lelle and Flamm, where each round produces a winner. The goal is to maximize the total score, which is computed as l WL + f WF, where WL and WF are the number of wins for Lelle and Flamm, respectively.
CF 2002G - Lattice Optimizing
The problem asks only for existence or nonexistence in three classes. For part (1), it suffices to exhibit a tetrahedron that tiles space by congruent copies. For part (2), we must decide whether a congruent tiling by equifacial tetrahedra exists.
CF 2002E - Cosmic Rays
This is a Type C problem: a precise numerical count of admissible fillings is requested. The solution produces a combinatorial formula $an = 2^{n-1}$ and rigorously justifies it via bijection arguments and induction.
CF 2002D2 - DFS Checker (Hard Version)
We are given a rooted tree where vertex 1 is the root. Alongside the tree, we maintain a permutation stored in an array indexed by positions, and we repeatedly swap two positions in this array.
CF 2002B - Removals Game
We have two players, Alice and Bob, each holding a permutation of the numbers from 1 to n. They will alternately remove elements from either end of their respective arrays. After n-1 turns, only one element remains in each array.
CF 2002D1 - DFS Checker (Easy Version)
We are given a perfect binary tree whose vertices are numbered in heap order. Vertex 1 is the root, and for every vertex i 1, its parent is i // 2. A permutation p of all vertices is maintained. After every query, two positions in the permutation are swapped.
CF 2002A - Distanced Coloring
We are given a rectangular grid with n rows and m columns. Each cell must be assigned a color, but colors are restricted by a distance rule: if two cells share the same color, then they must be sufficiently far apart in the Chebyshev sense, meaning the maximum of their row…
CF 2002C - Black Circles
This is a counting problem, so it falls under Type C. The goal is to determine the exact number of admissible fillings of the strip. The solution must provide a precise count and justify the enumeration rigorously.