Codeforces Round 733 (Div. 1 + Div. 2, based on VK Cup 2021 - Elimination (Engine))
Solutions for Codeforces Round 733 (Div. 1 + Div. 2, based on VK Cup 2021 - Elimination (Engine)) (contest 1530). 1/8 problems verified against sample I/O. Difficulty range: 800-3400.
Codeforces Round 733 (Div. 1 + Div. 2, based on VK Cup 2021 - Elimination (Engine))
Type: Div. 1+2 | Problems: 8 | Verified: 1/8 | Rating range: 800-3400 | Time: 15m 8s
| Problem | Name | Rating | Tags | Solve Time | Verified |
|---|---|---|---|---|---|
| A | Binary Decimal | 800 | greedy, math | 2m 4s | ✓ |
| B | Putting Plates | 800 | constructive-algorithms, implementation | 3m 16s | ✗ |
| C | Pursuit | 1200 | binary-search, brute-force, greedy | 45s | ✗ |
| D | Secret Santa | 1600 | constructive-algorithms, flows, graphs | 2m 38s | ✗ |
| E | Minimax | 2100 | constructive-algorithms, greedy, strings | 2m 33s | ✗ |
| F | Bingo | 2600 | bitmasks, combinatorics, dp | 2m 2s | ✗ |
| G | What a Reversal | 3300 | constructive-algorithms | 49s | ✗ |
| H | Turing's Award | 3400 | data-structures, dp | 1m 1s | ✗ |
CF 1530F - Bingo
We are asked to compute the probability that a square table of events is "winning." Each cell of an $n times n$ table contains an event that may happen with a given probability. Rows, columns, the main diagonal, and the antidiagonal are considered lines.
CF 1530H - Turing's Award
We are given a permutation of numbers from 1 to n. A token starts at position 0 on an infinite integer line. Over time, each value of the permutation is written on
CF 1530E - Minimax
The solution is attempting to justify formula (25) via polynomial interpolation of the product polynomial values.
CF 1530G - What a Reversal
We are given two binary strings, a and b, of the same length n and an integer k. Our goal is to transform a into b by repeatedly reversing substrings of a that contain exactly k ones. Each reversal can involve any number of zeros.
CF 1530D - Secret Santa
We are asked to construct a permutation-like assignment for a group of people. Each person must give a gift to exactly one other person, and no one is allowed to give a gift to themselves.
CF 1530B - Putting Plates
We are asked to maximize the number of plates on a rectangular table, represented as an $h times w$ grid. Plates can only be placed along the perimeter, which includes the first row, last row, first column, and last column.
CF 1530A - Binary Decimal
The problem asks us to break a positive integer $n$ into a sum of numbers whose decimal digits are only 0 or 1. These numbers are called binary decimals, like 1, 10, 11, 101, 1000. The goal is to determine the smallest number of such binary decimals that sum up to $n$.
CF 1530C - Pursuit
We have a contest with multiple stages, each stage giving between 0 and 100 points. You and Ilya have already completed n stages, and we know the scores for both of you.