Codeforces Round 936 (Div. 2)

6 problems from Codeforces Round 936 (Div. 2) (contest 1946), difficulty 800-2500. 3/6 solutions verified against sample I/O.

6 items

Codeforces Round 936 (Div. 2)

Div. 2 | 6 problems | 3/6 verified | Difficulty 800-2500 | 10m 45s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Median of an Array	800	greedy, implementation, sortings	28,569	1m 30s	✓
B	Maximum Sum	1100	dp, greedy, math	23,420	1m 14s	✓
C	Tree Cutting	1600	binary-search, dp, greedy	13,713	2m 50s	✓
D	Birthday Gift	1900	bitmasks, brute-force, constructive-algorithms	5,606	1m 45s
E	Girl Permutation	2200	combinatorics, dp, math	3,174	1m 48s
F	Nobody is needed	2500	2-sat, data-structures, dfs-and-similar	1,239	1m 38s

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

CF 1946F - Nobody is needed

We are given a permutation of integers from 1 to $n$ and a series of queries. Each query asks how many sequences of indices in a specified range $[l, r]$ can be formed such that the sequence is strictly increasing and each element divides the next one in the permutation.

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

CF 1946E - Girl Permutation

We are given a permutation of size $n$, which means it contains all integers from $1$ to $n$ exactly once, in some unknown order. Instead of seeing the permutation directly, we are told the positions of its prefix maximums and suffix maximums.

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

CF 1946D - Birthday Gift

We are given an array and we are allowed to cut it into contiguous segments that cover the entire array from left to right. Each segment is summarized into a single value, the XOR of its elements.

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

CF 1946A - Median of an Array

We are given an array of integers and asked to determine the minimum number of increment operations needed to increase the median of the array. An increment operation consists of picking any element and adding one to it.

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

CF 1946B - Maximum Sum

We start with an integer array. Each operation allows us to choose any contiguous subarray, including the empty subarray, compute its sum, and insert that sum as a new element anywhere in the array. The key observation is that inserting a value changes the total sum of the array.

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

CF 1946C - Tree Cutting

We are given a tree with $n$ vertices, which is a connected graph without cycles. The task is to remove exactly $k$ edges from this tree and determine the largest integer $x$ such that each resulting connected component has at least $x$ vertices.