Codeforces Round 1058 (Div. 1)

7 problems from Codeforces Round 1058 (Div. 1) (contest 2159), difficulty 1700-3500. 1/7 solutions verified against sample I/O.

7 items

Codeforces Round 1058 (Div. 1)

Div. 1 | 7 problems | 1/7 verified | Difficulty 1700-3500 | 14m 14s

#	Problem	Rating	Tags	Accepted	Time	✓
A	MAD Interactive Problem	1700	constructive-algorithms, implementation, interactive	8,128	2m 27s
B	Rectangles	2100	brute-force, data-structures, dp	2,308	1m 48s	✓
C	Twin Polynomials	2300	combinatorics, graph-matchings, math	1,687	1m 54s
D1	Inverse Minimum Partition (Easy Version)	2500	binary-search, brute-force, dp	1,019	2m 20s
D2	Inverse Minimum Partition (Hard Version)	3200	dp, greedy, math	394	1m 43s
E	Super-Short-Polynomial-San	3500	math, meet-in-the-middle	199	2m 18s
F	Grand Finale: Snakes	3500	binary-search, interactive, ternary-search	134	1m 44s

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

CF 2159F - Grand Finale: Snakes

We are given a permutation grid of size $n times n$, where every number from $1$ to $n^2$ appears exactly once. Instead of directly using this grid, we interact with a hidden process that defines, for each snake length $l$ and time $T$, a value $f(l,T)$.

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

CF 2159E - Super-Short-Polynomial-San

We are given a quadratic polynomial in one variable, and we repeatedly raise it to a power that changes per query.

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

CF 2159D1 - Inverse Minimum Partition (Easy Version)

We are asked to partition a sequence of positive integers into contiguous subarrays such that each subarray has a cost defined by the ratio of its last element to its minimum element, rounded up. Formally, for a subarray $b$, the cost is $lceil bk / min(b1, dots, bk) rceil$.

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

CF 2159D2 - Inverse Minimum Partition (Hard Version)

We are asked to work with sequences of positive integers. For any contiguous subsequence $b$ of a sequence $a$, there is a notion of cost: it is the ceiling of the last element of $b$ divided by the minimum of all elements in $b$.

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

CF 2159A - MAD Interactive Problem

We are tasked with reconstructing a hidden sequence of length $2n$ in which each number from $1$ to $n$ appears exactly twice. The only tool we have is the MAD query.

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

CF 2159C - Twin Polynomials

We are given a polynomial $f(x)$ of degree $n$ where some coefficients are known and others are undetermined (represented by $-1$).

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

CF 2159B - Rectangles

We are given a grid filled with zeros and ones. For every cell in this grid, we want to know the smallest possible “valid rectangle” that covers it, where validity is defined in a very specific way: the rectangle must have ones at all four corners, not necessarily inside.