Samara Farewell Contest 2020 (XXI Open Cup, Grand Prix of Samara)
14 problems from Samara Farewell Contest 2020 (XXI Open Cup, Grand Prix of Samara) (contest 102916), difficulty -. 12/14 solutions verified against sample I/O.
Samara Farewell Contest 2020 (XXI Open Cup, Grand Prix of Samara)
Special | 14 problems | 12/14 verified | Difficulty - | 14m 25s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Absenteeism | 53s | ✓ | |||
| B | Fakes and Shidget | 48s | ✓ | |||
| C | Cyclically Shifted Maze | 2m 38s | ||||
| D | Two Pirates - 2 | 44s | ✓ | |||
| E | Powerless Mage | 50s | ✓ | |||
| F | Exactly One Point | 38s | ✓ | |||
| G | Lexicographically Minimal Subsequence | 41s | ✓ | |||
| H | Video Reviews - 2 | 39s | ✓ | |||
| I | Chess Tournament | 42s | ✓ | |||
| J | Lost Island | 2m 32s | ||||
| K | Bloodseeker | 52s | ✓ | |||
| L | Not the Longest Increasing Subsequence | 46s | ✓ | |||
| M | Binary Search Tree | 53s | ✓ | |||
| N | Premove Checkmate | 49s | ✓ |
CF 102916J - Lost Island
Let $a1 ge a2 ge cdots ge am ge 1$ be a partition of $n$ into $m$ parts that is optimally balanced, meaning $ Let $t$ be the number of parts equal to $x$ and $m-t$ the number of parts equal to $x-1$. The partition has total sum $$n = tx + (m-t)(x-1) = mx - (m-t).
CF 102916N - Premove Checkmate
We are given a very specific chess endgame situation: white has only a king and a queen, while black has only a king. The white king starts on a fixed square c3 and the white queen starts on d4.
CF 102916M - Binary Search Tree
We are given an undirected tree with vertices labeled from 1 to n. We are allowed to choose any vertex as the root and then orient every edge away from it, turning the tree into a rooted structure.
CF 102916L - Not the Longest Increasing Subsequence
We are given a sequence of length $n$, where every value lies between $1$ and $k$. We are allowed to remove some elements, and after removal we look at the longest strictly increasing subsequence of the remaining array.
CF 102916K - Bloodseeker
We are given a character who survives over a timeline measured in seconds. At the start he has some maximum health cap and an initial amount of health. Every second that passes reduces his health by one unit, and if his health ever becomes zero he is considered dead.
CF 102916I - Chess Tournament
We are organizing a complete round-robin chess tournament among n players, meaning every pair of players must meet exactly once. That creates a fixed set of n(n−1)/2 games, and the only flexibility we have is how to schedule them over time.
CF 102916H - Video Reviews - 2
We are given a sequence of videobloggers in a fixed order. Each blogger has a threshold value a[i]. When we approach bloggers from left to right, a blogger will record a review automatically only if either they are explicitly convinced by the marketer, or the number of reviews…
CF 102916C - Cyclically Shifted Maze
Let $a1 ge a2 ge cdots ge am ge 1$ be a partition of $n$ into $m$ parts that is optimally balanced, meaning $ Let $t$ be the number of parts equal to $x$ and $m-t$ the number of parts equal to $x-1$. The partition has total sum $$n = tx + (m-t)(x-1) = mx - (m-t).
CF 102916G - Lexicographically Minimal Subsequence
We are given a single string and a number k. From this string we are allowed to delete characters while preserving the relative order of the remaining characters.
CF 102916F - Exactly One Point
We are given a collection of segments on a number line, and each segment spans between two even integers. The task is to place a set of points on the same line so that every segment contains exactly one chosen point, while also ensuring that every chosen point lies inside at…
CF 102916E - Powerless Mage
We are given a collection of spells, each spell consumes some combination of three types of mana: blue, purple, and orange. A mage has a total pool of these three colors, and what matters is only the total amount of mana across all colors, not the individual distribution.
CF 102916D - Two Pirates - 2
We are given a collection of treasures, each with a positive value. Two players take turns picking remaining items until none are left. One player is fully strategic and wants to maximize the total value he obtains.
CF 102916A - Absenteeism
We are given a day that spans a time segment from 0 to m. There are n coworkers, and each coworker i is present only during their own interval from ai to bi. Alex must choose a continuous working interval [x, y] inside the day.
CF 102916B - Fakes and Shidget
Each step of the process is identical in structure. Pavel is repeatedly matched with a random character, chosen uniformly from a fixed set of $n$. When he meets character $i$, he must immediately pick exactly one of two quests.