Codeforces Round 888 (Div. 3)

Solutions for Codeforces Round 888 (Div. 3) (contest 1851). 1/7 problems verified against sample I/O. Difficulty range: 800-2000.

7 items

Codeforces Round 888 (Div. 3)

Type: Div. 3 | Problems: 7 | Verified: 1/7 | Rating range: 800-2000 | Time: 22m 9s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Escalator Conversations	800	brute-force, constructive-algorithms, math	1m 18s	✓
B	Parity Sort	800	greedy, sortings, two-pointers	6m 11s	✗
C	Tiles Comeback	1000	greedy	5m 49s	✗
D	Prefix Permutation Sums	1300	implementation, math	2m 33s	✗
E	Nastya and Potions	1500	dfs-and-similar, dp, graphs	1m 57s	✗
F	Lisa and the Martians	1800	bitmasks, greedy, math	2m 19s	✗
G	Vlad and the Mountains	2000	binary-search, data-structures, dsu	2m 2s	✗

Practice › Codeforces Solutions › Codeforces Round 888 (Div. 3) ›

CF 1851G - Vlad and the Mountains

The solution does answer the correct exercise: it attempts to extend Lemma B from integral $c$ to arbitrary real $c$ with $0le c<k$, and it proposes an explicit reciprocity formula. However, the proof does not justify the formula it claims.

Practice › Codeforces Solutions › Codeforces Round 888 (Div. 3) ›

CF 1851F - Lisa and the Martians

The problem can be understood as follows. Lisa receives a list of n non-negative integers, all strictly less than 2^k. She is then allowed to pick another integer x in the same range, and after that she considers all pairs of distinct numbers (ai, aj) from the list.

Practice › Codeforces Solutions › Codeforces Round 888 (Div. 3) ›

CF 1851B - Parity Sort

We are given an array of integers and can swap any two elements that share the same parity, meaning both are odd or both are even. The goal is to determine whether it is possible to sort the array in non-decreasing order using this operation any number of times.

Practice › Codeforces Solutions › Codeforces Round 888 (Div. 3) ›

CF 1851C - Tiles Comeback

We are given a row of $n$ tiles, each painted with some color. Vlad wants to walk along the tiles, starting from the first tile, making jumps of arbitrary length to the right, and ending exactly on the last tile.

Practice › Codeforces Solutions › Codeforces Round 888 (Div. 3) ›

CF 1851E - Nastya and Potions

We are given a collection of potion types where each type has a direct purchase price, but some potions can also be produced by mixing other potions according to fixed recipes. Each recipe consumes its ingredients completely, so once used, those input potions are gone.

Practice › Codeforces Solutions › Codeforces Round 888 (Div. 3) ›

CF 1851D - Prefix Permutation Sums

We are given an array derived from the prefix sums of a permutation of numbers from 1 to $n$. One of these prefix sums is missing. Our task is to determine whether the incomplete array could have come from a valid permutation.

Practice › Codeforces Solutions › Codeforces Round 888 (Div. 3) ›

CF 1851A - Escalator Conversations

We are given a fixed escalator structure and a set of people with known heights. Vlad also has a height. The escalator has equally spaced steps, and each step increases in height by a constant value.