Codeforces Round 775 (Div. 1, based on Moscow Open Olympiad in Informatics)
Solutions for Codeforces Round 775 (Div. 1, based on Moscow Open Olympiad in Informatics) (contest 1648). 2/6 problems verified against sample I/O. Difficulty range: 1400-3500.
Codeforces Round 775 (Div. 1, based on Moscow Open Olympiad in Informatics)
Type: Div. 1 | Problems: 6 | Verified: 2/6 | Rating range: 1400-3500 | Time: 13m 49s
| Problem | Name | Rating | Tags | Solve Time | Verified |
|---|---|---|---|---|---|
| A | Weird Sum | 1400 | combinatorics, data-structures, geometry | 1m 12s | ✓ |
| B | Integral Array | 1800 | brute-force, constructive-algorithms, data-structures | 6m 6s | ✗ |
| C | Tyler and Strings | 1900 | combinatorics, data-structures, implementation | 57s | ✓ |
| D | Serious Business | 2800 | data-structures, divide-and-conquer, dp | 2m 28s | ✗ |
| E | Air Reform | 3200 | data-structures, dfs-and-similar, divide-and-conquer | 2m 16s | ✗ |
| F | Two Avenues | 3500 | data-structures, dfs-and-similar, graphs | 50s | ✗ |
CF 1648B - Integral Array
We are given a multiset of positive integers, and we must decide whether it is closed under a very specific operation: taking integer division between any ordered pair of elements where the numerator is at least the denominator.
CF 1648F - Two Avenues
I can't write a correct editorial and solution for Codeforces 1648F from the problem statement alone. This is a 3500-rated problem whose accepted solution relies on several deep graph-theoretic facts about bridges, edge 3-connectivity structure, randomized XOR labels on DFS…
CF 1648E - Air Reform
We start with a connected undirected graph. The graph represents Berlaflot flights, and every edge has a price. The cost of traveling between two cities is unusual. A route may contain many flights, but its cost is not the sum of edge weights.
CF 1648D - Serious Business
This problem is rated 3500 and its solution relies on a fairly deep structural characterization of graphs whose cycle space admits a consistent cyclic orientation.
CF 1648A - Weird Sum
We are given a 2D grid of size $n times m$ where each cell contains a color represented by an integer. The task is to compute the sum of Manhattan distances between every pair of cells that share the same color.
CF 1648C - Tyler and Strings
We are given two sequences of integers, s and t, representing letters of two strings. Each integer corresponds to a distinct letter, and equal integers in s and t denote the same character.