Codeforces Round 892 (Div. 2)

Solutions for Codeforces Round 892 (Div. 2) (contest 1859). 3/6 problems verified against sample I/O. Difficulty range: 800-3200.

6 items

Codeforces Round 892 (Div. 2)

Type: Div. 2 | Problems: 6 | Verified: 3/6 | Rating range: 800-3200 | Time: 14m 44s

Problem	Name	Rating	Tags	Solve Time	Verified
A	United We Stand	800	constructive-algorithms, math, number-theory	1m 58s	✗
B	Olya and Game with Arrays	1000	constructive-algorithms, greedy, math	2m 2s	✗
C	Another Permutation Problem	1200	brute-force, dp, greedy	2m 48s	✓
D	Andrey and Escape from Capygrad	1800	binary-search, data-structures, dp	3m 15s	✗
E	Maximum Monogonosity	2500	brute-force, dp, math	3m 19s	✓
F	Teleportation in Byteland	3200	data-structures, dfs-and-similar, divide-and-conquer	1m 22s	✓

Practice › Codeforces Solutions › Codeforces Round 892 (Div. 2) ›

CF 1859E - Maximum Monogonosity

We are given two arrays of length $n$, $a$ and $b$. For any contiguous subarray, or segment, defined by its start $l$ and end $r$, we can compute a "cost" using the formula $ The problem is subtle because segment costs depend on both ends of the segment and both arrays.

Practice › Codeforces Solutions › Codeforces Round 892 (Div. 2) ›

CF 1859D - Andrey and Escape from Capygrad

We are asked to model escape paths in a one-dimensional world where Andrey can use portals repeatedly. Each portal is a segment [li, ri] from which Andrey can enter and teleport to another contained segment [ai, bi].

Practice › Codeforces Solutions › Codeforces Round 892 (Div. 2) ›

CF 1859F - Teleportation in Byteland

We are given a tree with n cities connected by roads. Each road has a hardness value wi. The travel time along a road depends on the driver’s skill c and is calculated as ceil(wi / c).

Practice › Codeforces Solutions › Codeforces Round 892 (Div. 2) ›

CF 1859C - Another Permutation Problem

We are given a permutation of the numbers from 1 to n. For a permutation p, define $$text{cost}(p)=sum{i=1}^{n} pi cdot i-max{i=1}^{n}(picdot i).$$ The task is to find the largest possible value of this expression among all permutations of length n.

Practice › Codeforces Solutions › Codeforces Round 892 (Div. 2) ›

CF 1859B - Olya and Game with Arrays

We are given multiple arrays, each containing at least two positive integers. We are allowed to move at most one number from each array to some other array. After these moves, the “beauty” of the collection is defined as the sum of the smallest element in each array.

Practice › Codeforces Solutions › Codeforces Round 892 (Div. 2) ›

CF 1859A - United We Stand

We are given an array of integers, and our goal is to split it into two non-empty arrays, b and c, such that no element in c divides any element in b. Each element must go into exactly one array. If this is impossible, we return -1.