Codeforces Round 873 (Div. 1)

Solutions for Codeforces Round 873 (Div. 1) (contest 1827). 1/7 problems verified against sample I/O. Difficulty range: 1100-3500.

7 items

Codeforces Round 873 (Div. 1)

Type: Div. 1 | Problems: 7 | Verified: 1/7 | Rating range: 1100-3500 | Time: 13m 2s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Counting Orders	1100	combinatorics, math, sortings	1m 30s	✓
B1	Range Sorting (Easy Version)	2000	binary-search, dp, dsu	2m 22s	✗
B2	Range Sorting (Hard Version)	2400	binary-search, data-structures, dp	1m 35s	✗
C	Palindrome Partition	2600	binary-search, brute-force, data-structures	1m 28s	✗
D	Two Centroids	2800	data-structures, dfs-and-similar, greedy	1m 33s	✗
E	Bus Routes	3400	binary-search, constructive-algorithms, dfs-and-similar	3m 8s	✗
F	Copium Permutation	3500	constructive-algorithms, data-structures, greedy	1m 26s	✗

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

CF 1827E - Bus Routes

The original logic did the following: 1. Read all intervals and sorted them by left endpoint. 2. Merged overlapping intervals into merged blocks. 3. Marked all positions covered by merged blocks as used. 4. Counted "free positions" (free = used.

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

CF 1827F - Copium Permutation

We are given a permutation of length $n$. We are allowed to take the suffix starting at position $k+1$ and freely rearrange it, while keeping the prefix $a1 ldots ak$ fixed in place.

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

CF 1827D - Two Centroids

We are asked to process a dynamic tree that grows one node at a time. Initially, the tree has a single node labeled 1. Each query adds a new node and connects it to an existing node, forming a tree incrementally.

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

CF 1827C - Palindrome Partition

We are given a string consisting of lowercase Latin letters, and we are asked to count its “beautiful” substrings. A substring is beautiful if it is an even palindrome or can be partitioned into smaller even palindromes.

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

CF 1827B1 - Range Sorting (Easy Version)

We are asked to compute a “beauty” metric for all subarrays of a given array of distinct integers. The beauty of a subarray is the minimum total time needed to sort it using range-sort operations.

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

CF 1827B2 - Range Sorting (Hard Version)

We are given an array of distinct integers and asked to compute, for every contiguous subarray, the minimum total time required to sort it using range-sort operations.

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

CF 1827A - Counting Orders

We are given two arrays, a and b, each of length n. The elements in a are all distinct, while b may contain repeated numbers. The task is to count the number of ways we can reorder the elements of a so that after reordering, for every index i, the condition a[i] b[i] holds.