COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Solutions for COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred) (contest 1575). 5/13 problems verified against sample I/O. Difficulty range: 1100-3000.
COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Type: ICPC/IOI | Problems: 13 | Verified: 5/13 | Rating range: 1100-3000 | Time: 35m 28s
| Problem | Name | Rating | Tags | Solve Time | Verified |
|---|---|---|---|---|---|
| A | Another Sorting Problem | 1100 | data-structures, sortings, strings | 12m 47s | ✗ |
| B | Building an Amusement Park | 2300 | binary-search, geometry | 5m 18s | ✗ |
| C | Cyclic Sum | 3000 | data-structures, fft, number-theory | 1m 49s | ✗ |
| D | Divisible by Twenty-Five | 1800 | brute-force, dfs-and-similar, dp | 2m 1s | ✓ |
| E | Eye-Pleasing City Park Tour | 2600 | data-structures, trees | 2m 8s | ✗ |
| F | Finding Expected Value | 2900 | math | 1m 16s | ✓ |
| G | GCD Festival | 2200 | math, number-theory | 2m 13s | ✗ |
| H | Holiday Wall Ornaments | 2200 | dp, strings | 37s | ✗ |
| I | Illusions of the Desert | 2300 | data-structures, trees | 43s | ✗ |
| J | Jeopardy of Dropped Balls | 1500 | binary-search, brute-force, dsu | 56s | ✓ |
| K | Knitting Batik | 2200 | implementation, math | 1m 46s | ✓ |
| L | Longest Array Deconstruction | 2100 | data-structures, divide-and-conquer, dp | 2m 34s | ✗ |
| M | Managing Telephone Poles | 2400 | data-structures, geometry | 1m 20s | ✓ |
CF 1575A - Another Sorting Problem
We have a collection of distinct book titles, all with the same length. The books are not sorted using ordinary lexicographic order. When comparing two titles, we scan from left to right until we find the first position where they differ.
CF 1575L - Longest Array Deconstruction
We start with an array. We may repeatedly delete arbitrary elements, and after each deletion the remaining elements close up together. For any resulting array, define its score as the number of positions where the value equals its current 1-based index.
CF 1575M - Managing Telephone Poles
The grid describes a city map where some cells contain telephone poles. Each cell corresponds to an integer coordinate point on a plane, and a value of 1 means a pole exists at that location.
CF 1575K - Knitting Batik
We are asked to count the number of ways to color a large rectangular cloth with size $n times m$ using $k$ colors, given that two fixed subrectangles of size $r times c$ must be identical in their color patterns.
CF 1575J - Jeopardy of Dropped Balls
We have an n × m grid. Every cell stores one of three directions. A value of 1 means a ball moves one cell to the right. A value of 2 means the ball moves one cell downward. A value of 3 means the ball moves one cell to the left.
CF 1575G - GCD Festival
We are given an array of integers a with length n. The goal is to compute a sum over all pairs (i, j) where i and j are indices of the array, and for each pair we multiply two quantities: the GCD of the array elements a[i] and a[j], and the GCD of their positions i and j.
CF 1575H - Holiday Wall Ornaments
We are given a binary string representing a wall, where each character is either 0 or 1. This string, a, is of length n. Mr. Chanek wants to place his nephew’s favorite pattern, another binary string b of length m, onto the wall.
CF 1575F - Finding Expected Value
We start with an array whose values lie in the range [0, k - 1]. As long as not all positions contain the same value, we repeatedly choose a random position and a random value, then overwrite that position.
CF 1575E - Eye-Pleasing City Park Tour
The city park is a tree where each attraction is a node and each rail is an edge. Every node has a happiness value, and every edge has a color, either black or white. Moving through the tree is always along simple paths, meaning you never revisit a node.
CF 1575B - Building an Amusement Park
We want to place a circular amusement park so that it touches the origin. If the park has radius $r$, then its center must lie exactly $r$ units from the origin, because the origin lies on the boundary of the park. Each bird habitat is a point in the plane.
CF 1575D - Divisible by Twenty-Five
We are given a very short string, at most length 8, that represents a partially unknown integer. Some positions contain fixed digits, some contain a wildcard underscore meaning “any digit is allowed here”, and some contain the character X meaning all X positions must share…
CF 1575C - Cyclic Sum
We are given an array a of length n and a repetition count m. From this, we form a cyclic sequence b by concatenating m copies of a. Conceptually, b is circular: after the last element, the first element follows.