Codeforces Round 559 (Div. 1)

Solutions for Codeforces Round 559 (Div. 1) (contest 1158). 1/6 problems verified against sample I/O. Difficulty range: 1500-3500.

6 items

Codeforces Round 559 (Div. 1)

Type: Div. 1 | Problems: 6 | Verified: 1/6 | Rating range: 1500-3500 | Time: 10m 32s

Problem	Name	Rating	Tags	Solve Time	Verified
A	The Party and Sweets	1500	binary-search, constructive-algorithms, greedy	2m 36s	✗
B	The minimal unique substring	2200	constructive-algorithms, math, strings	1m 20s	✓
C	Permutation recovery	2100	constructive-algorithms, data-structures, dfs-and-similar	1m 37s	✗
D	Winding polygonal line	2600	constructive-algorithms, geometry, greedy	1m 39s	✗
E	Strange device	3400	binary-search, interactive, math	1m 49s	✗
F	Density of subarrays	3500	dp, math	1m 31s	✗

Practice › Codeforces Solutions › Codeforces Round 559 (Div. 1) ›

CF 1158F - Density of subarrays

We are given an array of positive integers, each bounded by a number $c$. The task is to examine all subsequences of this array and classify them by a number called their density.

Practice › Codeforces Solutions › Codeforces Round 559 (Div. 1) ›

CF 1158E - Strange device

We are asked to reconstruct an unknown tree with $n$ vertices by interacting with a device that allows a single type of query. Each vertex of the tree has a lamp, and the device lets us propose a set of distances $d1, d2, dots, dn$.

Practice › Codeforces Solutions › Codeforces Round 559 (Div. 1) ›

CF 1158C - Permutation recovery

We are asked to reconstruct a permutation of numbers from 1 to n given a partially known array called next. Each element next[i] represents the smallest index j greater than i such that p[j] p[i]. If no such j exists, next[i] is set to n+1. If next[i] is unreadable, it is -1.

Practice › Codeforces Solutions › Codeforces Round 559 (Div. 1) ›

CF 1158D - Winding polygonal line

We are given a set of $n$ distinct points on the plane, with the guarantee that no three points are collinear. We need to order these points into a polygonal line such that two conditions hold: it never intersects itself, and at each internal vertex, the turn direction matches…

Practice › Codeforces Solutions › Codeforces Round 559 (Div. 1) ›

CF 1158A - The Party and Sweets

We have a party with $n$ boys and $m$ girls. Each boy gives some number of sweets to every girl, forming an $n times m$ matrix of integers. For each boy, the minimum number of sweets he gives to any girl is specified as $bi$.

Practice › Codeforces Solutions › Codeforces Round 559 (Div. 1) ›

CF 1158B - The minimal unique substring

We are asked to construct a binary string of length n such that the shortest substring appearing exactly once has length k. A substring is a consecutive segment of the string, and it is unique if it occurs in exactly one position.