Codeforces Round 873 (Div. 2)

Solutions for Codeforces Round 873 (Div. 2) (contest 1828). 1/7 problems verified against sample I/O. Difficulty range: 800-2800.

7 items

Codeforces Round 873 (Div. 2)

Type: Div. 2 | Problems: 7 | Verified: 1/7 | Rating range: 800-2800 | Time: 11m 24s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Divisible Array	800	constructive-algorithms, math	1m 30s	✗
B	Permutation Swap	900	math, number-theory	1m 20s	✓
C	Counting Orders	1100	binary-search, combinatorics, sortings	2m 16s	✗
D1	Range Sorting (Easy Version)	2000	binary-search, brute-force, data-structures	1m 38s	✗
D2	Range Sorting (Hard Version)	2400	binary-search, data-structures, dp	1m 24s	✗
E	Palindrome Partition	2600	data-structures, dp, hashing	2m 5s	✗
F	Two Centroids	2800	dfs-and-similar	1m 11s	✗

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

CF 1828E - Palindrome Partition

The solution correctly generalizes the serial test from pairs to $k$-tuples by grouping the sequence into disjoint blocks of length $k$, ensuring independence under the null hypothesis.

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

CF 1828F - Two Centroids

We are given a tree that grows incrementally: it starts with vertex 1, and each subsequent vertex is attached to some existing vertex in the tree. For each insertion, we are asked how many extra vertices we must add to make the tree have exactly two centroids.

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

CF 1828D1 - Range Sorting (Easy Version)

We are asked to compute a cumulative measure of "beauty" over all subarrays of a given array of distinct integers.

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

CF 1828D2 - Range Sorting (Hard Version)

We are asked to compute a "beauty" measure for every subarray of a given array of distinct integers. The array can be large, up to 300,000 elements, and the total across all test cases is bounded by the same number.

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

CF 1828C - Counting Orders

The solution correctly generalizes the serial test from pairs to $k$-tuples by grouping the sequence into disjoint blocks of length $k$, ensuring independence under the null hypothesis.

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

CF 1828A - Divisible Array

We are asked to construct an array for each test case, where the array length is fixed to a given integer $n$. Each position $i$ in the array must contain a value that is a multiple of $i$, and every value must stay within a small fixed range up to 1000.

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

CF 1828B - Permutation Swap

We are given a permutation of integers from 1 to n in some arbitrary order. Our task is to sort the permutation into ascending order by repeatedly swapping pairs of elements that are exactly k positions apart, for some fixed k.