Codeforces Round 783 (Div. 1)

Solutions for Codeforces Round 783 (Div. 1) (contest 1667). 2/6 problems verified against sample I/O. Difficulty range: 1300-3500.

6 items

Codeforces Round 783 (Div. 1)

Type: Div. 1 | Problems: 6 | Verified: 2/6 | Rating range: 1300-3500 | Time: 18m 33s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Make it Increasing	1300	brute-force, greedy, math	2m 9s	✗
B	Optimal Partition	2100	data-structures, dp	1m 40s	✗
C	Half Queen Cover	2400	constructive-algorithms, math	8m 27s	✓
D	Edge Elimination	2900	constructive-algorithms, dfs-and-similar, dp	2m 2s	✗
E	Centroid Probabilities	3000	combinatorics, dp, fft	1m 55s	✓
F	Yin Yang	3500	implementation	2m 20s	✗

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

CF 1667C - Half Queen Cover

The task is to place the minimum number of half-queens on an $n times n$ chessboard such that every square is either occupied or attacked. A half-queen attacks all cells in its row, its column, and the diagonal going from top-left to bottom-right that passes through its position.

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

CF 1667F - Yin Yang

We are given a grid where some cells are already fixed as black or white, and the rest are empty. The goal is to assign a color to every empty cell so that, after filling, all black cells form a single connected region using 4-directional movement, and all white cells also…

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

CF 1667E - Centroid Probabilities

We are asked to count, for each vertex in a special class of labeled trees, how many trees have that vertex as a centroid. The trees have $n$ vertices labeled $1$ through $n$, with the restriction that each vertex $i ge 2$ is connected to exactly one vertex with a smaller index.

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

CF 1667D - Edge Elimination

We are given a tree, which is a connected graph with no cycles, and we are asked to remove all its edges following a very particular rule: an edge can be removed only if it is adjacent to an even number of remaining edges. Two edges are adjacent if they share exactly one vertex.

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

CF 1667A - Make it Increasing

We are asked to construct an array $b$ from an array $a$ such that each element of $b$ is obtained from zero by either adding or subtracting a multiple of the corresponding element in $a$.

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

CF 1667B - Optimal Partition

We are asked to partition an array of integers into contiguous subarrays in order to maximize a custom score. Each subarray contributes to the total sum based on its sum: if the sum is positive, its contribution is the length of the subarray; if zero, it contributes nothing…