Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)
8 problems from Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2) (contest 1208), difficulty 900-3500. 7/8 solutions verified against sample I/O.
Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)
Div. 1+2 | 8 problems | 7/8 verified | Difficulty 900-3500 | 30m 32s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | XORinacci | 900 | math | 18,014 | 1m 28s | ✓ |
| B | Uniqueness | 1500 | binary-search, brute-force, implementation | 11,661 | 3m 49s | ✓ |
| C | Magic Grid | 1800 | constructive-algorithms | 6,362 | 6m 28s | |
| D | Restore Permutation | 1900 | binary-search, data-structures, greedy | 5,459 | 5m 28s | ✓ |
| E | Let Them Slide | 2200 | data-structures, implementation | 2,183 | 2m 18s | ✓ |
| F | Bits And Pieces | 2600 | bitmasks, dfs-and-similar, dp | 3,300 | 2m 39s | ✓ |
| G | Polygons | 2800 | greedy, math, number-theory | 928 | 6m 55s | ✓ |
| H | Red Blue Tree | 3500 | data-structures, implementation, trees | 189 | 1m 27s | ✓ |
CF 1208G - Polygons
We are asked to build several regular polygons that all lie on the same circle, and we want to reuse the circle’s boundary points as much as possible. Each polygon is determined only by how many vertices it has.
CF 1208F - Bits And Pieces
We are given a sequence of integers and asked to choose three indices $i < j < k$. For each such triple, we take the value of the first element OR the bitwise AND of the other two elements. The goal is to maximize this expression over all valid triples.
CF 1208C - Magic Grid
We are asked to fill an $n times n$ table with all integers from $0$ to $n^2 - 1$ exactly once, so every number is used in a permutation of the grid cells.
CF 1208D - Restore Permutation
We are given a hidden permutation of numbers from 1 to n. Instead of seeing the permutation directly, we are given a derived value for each position. For position i, the value s[i] is the sum of all elements that appear before i and are smaller than the element placed at i.
CF 1208B - Uniqueness
We are given a sequence of numbers and we are allowed to remove one continuous block from it, or remove nothing at all. After this single deletion, the remaining elements must all be different from each other.
CF 1208H - Red Blue Tree
The tree defines a bottom-up majority-like rule where only leaves carry fixed information and every internal node derives its state from its children.
CF 1208E - Let Them Slide
We are given a table with n rows and w columns. Each row contains an array that can be slid left or right within its row, but it must remain fully inside the table and occupy consecutive columns. The arrays can have different lengths, and some elements can be negative.
CF 1208A - XORinacci
We are asked to compute a sequence similar to Fibonacci numbers, but instead of summing the previous two terms, each term is obtained by applying the bitwise XOR operation to the two previous terms.