Codeforces Round 958 (Div. 2)

Solutions for Codeforces Round 958 (Div. 2) (contest 1988). 3/6 problems verified against sample I/O. Difficulty range: 900-3000.

6 items

Codeforces Round 958 (Div. 2)

Type: Div. 2 | Problems: 6 | Verified: 3/6 | Rating range: 900-3000 | Time: 16m 7s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Split the Multiset	900	brute-force, greedy, implementation	1m 20s	✓
B	Make Majority	900	greedy, implementation	5m 10s	✗
C	Increasing Sequence with Fixed OR	1300	bitmasks, constructive-algorithms, greedy	1m 37s	✗
D	The Omnipotent Monster Killer	2000	brute-force, dfs-and-similar, dp	3m 29s	✓
E	Range Minimum Sum	2300	binary-search, brute-force, data-structures	1m 47s	✗
F	Heartbeat	3000	combinatorics, dp, fft	2m 44s	✓

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

CF 1988F - Heartbeat

We are asked to sum over all permutations of numbers from 1 to $n$, a cost function that depends on three characteristics of each permutation: the number of prefix maximums, the number of suffix maximums, and the number of ascents.

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

CF 1988B - Make Majority

We are given a binary sequence that can change shape over time. The only allowed move is to take any contiguous segment and compress it into a single value equal to the majority of that segment, where ties are resolved in favor of zero.

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

CF 1988D - The Omnipotent Monster Killer

We are given a tree with n vertices, where each vertex holds a monster with a certain attack power. You, the monster killer, face the monsters for effectively an infinite number of rounds.

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

CF 1988E - Range Minimum Sum

We are working with a permutation of numbers from 1 to n, placed on a line. For any arrangement of numbers, we define a value based on all contiguous subarrays: each subarray contributes its minimum element, and we sum these contributions over every possible subarray.

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

CF 1988C - Increasing Sequence with Fixed OR

We are given a number $n$, and we want to build the longest possible strictly increasing sequence of positive integers, where every element is at most $n$. The key constraint is that every adjacent pair must combine under bitwise OR to exactly $n$.

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

CF 1988A - Split the Multiset

We start with a multiset that contains a single number n. The only way to change this multiset is to repeatedly pick one existing number u, delete it, and replace it with at most k positive integers whose sum is exactly u.