COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Solutions for COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred) (contest 1866). 6/13 problems verified against sample I/O. Difficulty range: 800-3100.
COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Type: ICPC/IOI | Problems: 13 | Verified: 6/13 | Rating range: 800-3100 | Time: 26m 2s
| Problem | Name | Rating | Tags | Solve Time | Verified |
|---|---|---|---|---|---|
| A | Ambitious Kid | 800 | math | 3m 12s | ✓ |
| B | Battling with Numbers | 1400 | combinatorics, math, number-theory | 1m 23s | ✓ |
| C | Completely Searching for Inversions | 1900 | dfs-and-similar, dp, graphs | 1m 35s | ✗ |
| D | Digital Wallet | 2300 | dp, greedy | 1m 17s | ✓ |
| E | Elevators of Tamem | 2700 | dp | 1m 44s | ✗ |
| F | Freak Joker Process | 3100 | binary-search, data-structures, sortings | 1m 31s | ✓ |
| G | Grouped Carriages | 2100 | binary-search, data-structures, dp | 3m 10s | ✓ |
| H | Happy Sets | 2100 | combinatorics | 1m 52s | ✗ |
| I | Imagination Castle | 2300 | dp, games, two-pointers | 1m 42s | ✓ |
| J | Jackets and Packets | 2800 | dp | 1m 57s | ✗ |
| K | Keen Tree Calculation | 2500 | binary-search, data-structures, dp | 1m 46s | ✗ |
| L | Lihmuf Balling | 2400 | binary-search, brute-force, math | 2m 35s | ✗ |
| M | Mighty Rock Tower | 2400 | brute-force, combinatorics, dp | 2m 18s | ✗ |
CF 1866M - Mighty Rock Tower
We are asked to compute the expected number of moves to build a tower of height N using identical small rocks, where each placement may trigger a cascading fall of the top rocks. Every time a rock is placed at height x, the topmost rock has a probability Px/100 of falling.
CF 1866K - Keen Tree Calculation
We are given a weighted tree, so there is exactly one simple path between any two vertices and every edge contributes a distance equal to its weight. The diameter of this tree is the maximum distance between any pair of vertices under these edge weights.
CF 1866J - Jackets and Packets
We start with a single stack of $N$ jackets. Each jacket has a color, and the order is fixed from top to bottom. There is a second empty stack.
CF 1866G - Grouped Carriages
Each carriage initially contains some number of passengers. A passenger starting in carriage i may move left or right, but cannot cross more than Di doors.
CF 1866I - Imagination Castle
We are given a grid with $N$ rows and $M$ columns. A game piece starts at the top-left cell $(1,1)$. From any cell, the piece can move either to the right within the same row or downward within the same column, but never left or up.
CF 1866H - Happy Sets
We are given a collection of $N$ sets, each set is formed from integers in the range $1$ to $K$. The sets are unordered internally, but the array of sets is ordered. After we construct these $N$ sets, we are allowed to permute them in any order.
CF 1866F - Freak Joker Process
We are maintaining a group of players, each described by two evolving attributes: an offensive value and a defensive value. Over time, both attributes can change independently through updates.
CF 1866E - Elevators of Tamem
We are managing three elevators inside a tall building. Each elevator sits on a floor and can move up or down, paying a cost proportional to how far it travels.
CF 1866A - Ambitious Kid
We are given a list of integers, and we can modify any element by repeatedly incrementing or decrementing it by one. Each such unit change costs one operation.
CF 1866D - Digital Wallet
We are given several rows of numbers, each row representing a sequence of rewards spread across time positions from 1 to M. We will perform exactly M − K + 1 actions, and each action is tied to a sliding window of K consecutive positions that moves from left to right.
CF 1866C - Completely Searching for Inversions
We are given a directed acyclic graph where each vertex has an ordered list of outgoing edges. Each edge carries a label, either 0 or 1, and points to another vertex.
CF 1866B - Battling with Numbers
We are given two integers, but instead of being written in decimal form, they are described by their prime factorizations. One number, call it $X$, is fully determined by a list of primes and their exponents. The other number $Y$ is described the same way.