Codeforces Round 707 (Div. 1, based on Moscow Open Olympiad in Informatics)
Solutions for Codeforces Round 707 (Div. 1, based on Moscow Open Olympiad in Informatics) (contest 1500). 1/6 problems verified against sample I/O. Difficulty range: 1800-3500.
Codeforces Round 707 (Div. 1, based on Moscow Open Olympiad in Informatics)
Type: Div. 1 | Problems: 6 | Verified: 1/6 | Rating range: 1800-3500 | Time: 26m 58s
| Problem | Name | Rating | Tags | Solve Time | Verified |
|---|---|---|---|---|---|
| A | Going Home | 1800 | brute-force, hashing, implementation | 19m 39s | ✗ |
| B | Two chandeliers | 2200 | binary-search, brute-force, chinese-remainder-theorem | 1m 3s | ✗ |
| C | Matrix Sorting | 2600 | bitmasks, brute-force, constructive-algorithms | 2m 46s | ✗ |
| D | Tiles for Bathroom | 2900 | data-structures, sortings, two-pointers | 1m 16s | ✓ |
| E | Subset Trick | 3300 | binary-search, data-structures | 56s | ✗ |
| F | Cupboards Jumps | 3500 | dp | 1m 18s | ✗ |
CF 1500A - Going Home
We are given an array of integers representing a gift from a friend to Nastya. She wants to find four distinct indices in the array such that the sum of the elements at the first two indices equals the sum of the elements at the other two indices.
CF 1500F - Cupboards Jumps
We are asked to reconstruct a sequence of cupboard heights based on partial information. Specifically, Krosh remembers the difference between the tallest and shortest cupboard for every consecutive triple.
CF 1500E - Subset Trick
The task revolves around reasoning about subset sums in a set of distinct positive integers. You are given an initial set $S$ and a series of operations that either add or remove elements.
CF 1500C - Matrix Sorting
We are given two matrices, $A$ and $B$, of size $n times m$. Each matrix consists of integers between $1$ and $n$. The task is to determine whether we can transform matrix $A$ into matrix $B$ using a sequence of stable column sorts.
CF 1500D - Tiles for Bathroom
We are given an $n times n$ grid representing a tile stand, where each cell contains a tile of a certain color. Kostya wants to know, for each possible subsquare size $k$, how many $k times k$ subsquares contain at most $q$ distinct colors.
CF 1500B - Two chandeliers
We have two cyclic sequences of colors. The first chandelier repeats an array a of length n, and the second chandelier repeats an array b of length m. On day d, the first chandelier shows position (d - 1) mod n, while the second shows position (d - 1) mod m.