Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2)
8 problems from Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2) (contest 1553), difficulty 800-3400. 5/8 solutions verified against sample I/O.
Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2)
Div. 1+2 | 8 problems | 5/8 verified | Difficulty 800-3400 | 35m 39s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Digits Sum | 800 | math, number-theory | 34,257 | 4m 41s | ✓ |
| C | Penalty | 1200 | bitmasks, brute-force, dp | 19,800 | 2m 51s | ✓ |
| D | Backspace | 1500 | dp, greedy, strings | 15,084 | 6m 1s | |
| E | Permutation Shift | 2100 | brute-force, combinatorics, constructive-algorithms | 3,773 | 4m 48s | ✓ |
| F | Pairwise Modulo | 2300 | data-structures, math | 2,518 | 4m 38s | |
| G | Common Divisor Graph | 2700 | brute-force, constructive-algorithms, dsu | 1,213 | 3m 40s | ✓ |
| H | XOR and Distance | 2900 | bitmasks, divide-and-conquer, trees | 841 | 2m 49s | ✓ |
| I | Stairs | 3400 | combinatorics, divide-and-conquer, dp | 313 | 6m 11s |
CF 1553G - Common Divisor Graph
We are given a fixed set of nodes, each labeled by a distinct integer. Two nodes are connected if their labels share any prime factor. This means the graph is determined entirely by the prime factorizations of the given numbers. For each query, we are given two starting nodes.
CF 1553F - Pairwise Modulo
We are given a sequence of distinct positive integers. After reading the first k elements, we define a score pk that aggregates the remainder produced by dividing every ordered pair (ai, aj) among the first k elements.
CF 1553D - Backspace
We are simulating a typing process where we scan a source string s from left to right. At each position, we either append the current character to an evolving text buffer or press backspace, which deletes the most recently added character if it exists.
CF 1553E - Permutation Shift
We start from the identity permutation, which is simply the numbers from 1 to n in order. Someone first rotates this array cyclically to the right by an unknown shift k, and then performs at most m arbitrary swaps of elements.
CF 1553I - Stairs
We are given an array a of length n. It is not a permutation itself but a derived “stability profile” of an unknown permutation of 1..n. For each position i in that hidden permutation, we look at all subarrays that contain i.
CF 1553A - Digits Sum
We are given several independent queries. Each query provides a positive integer $n$, and we must count how many integers $x$ in the range from 1 to $n$ have a special property. For a number $x$, we compare the sum of its digits before and after adding one.
CF 1553H - XOR and Distance
We have a set of distinct integers $a1,dots,an$, each lying in the range $[0,2^k)$. For every mask $x$, we XOR every array element with $x$, producing the set $${a1oplus x,dots,anoplus x}.$$ Among all pairs in that transformed set, we want the smallest absolute difference.
CF 1553C - Penalty
We are simulating a penalty shootout between two football teams, each taking alternating kicks up to five each, for a total of ten kicks. Each kick either succeeds (scores a goal), fails, or is unknown.