Pinely Round 1 (Div. 1 + Div. 2)

Solutions for Pinely Round 1 (Div. 1 + Div. 2) (contest 1761). 2/8 problems verified against sample I/O. Difficulty range: 800-3500.

8 items

Pinely Round 1 (Div. 1 + Div. 2)

Type: Div. 1+2 | Problems: 8 | Verified: 2/8 | Rating range: 800-3500 | Time: 49m 53s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Two Permutations	800	brute-force, constructive-algorithms	3m 26s	✓
B	Elimination of a Ring	1000	constructive-algorithms, greedy, implementation	5m 59s	✓
C	Set Construction	1400	constructive-algorithms, dfs-and-similar, graphs	6m 36s	✗
D	Carry Bit	2100	combinatorics, math	3m 53s	✗
E	Make It Connected	2400	binary-search, brute-force, constructive-algorithms	11m 43s	✗
F1	Anti-median (Easy Version)	3100	dp, math	6m 8s	✗
F2	Anti-median (Hard Version)	3500	combinatorics, dp, math	6m 25s	✗
G	Centroid Guess	3500	interactive, probabilities, trees	5m 43s	✗

Practice › Codeforces Solutions › Pinely Round 1 (Div. 1 + Div. 2) ›

CF 1761G - Centroid Guess

We are given a hidden tree with n nodes, and we do not know its structure. Our goal is to identify its centroid, which is the unique node such that removing it leaves all connected components with at most n/2 nodes each.

Practice › Codeforces Solutions › Pinely Round 1 (Div. 1 + Div. 2) ›

CF 1761E - Make It Connected

We are given an undirected graph and a special operation. Choosing a vertex flips all of its incident edges: every neighbor becomes a non-neighbor, and every non-neighbor becomes a neighbor.

Practice › Codeforces Solutions › Pinely Round 1 (Div. 1 + Div. 2) ›

CF 1761F2 - Anti-median (Hard Version)

We are asked to count permutations of length $n$ that avoid a certain "bad" pattern in every odd-length subarray. A permutation is a rearrangement of numbers $1$ through $n$, and some entries may already be fixed while others are unknown.

Practice › Codeforces Solutions › Pinely Round 1 (Div. 1 + Div. 2) ›

CF 1761F1 - Anti-median (Easy Version)

We are asked to construct permutations of integers from 1 to (n) with a specific property: no subarray of odd length greater than or equal to three can have its middle element equal to the median of that subarray.

Practice › Codeforces Solutions › Pinely Round 1 (Div. 1 + Div. 2) ›

CF 1761D - Carry Bit

We are asked to count how many pairs of non-negative integers $a$ and $b$, each less than $2^n$, produce exactly $k$ carry bits when summed in binary.

Practice › Codeforces Solutions › Pinely Round 1 (Div. 1 + Div. 2) ›

CF 1761C - Set Construction

We are given a binary $n times n$ matrix, and our task is to construct $n$ distinct non-empty sets of integers between $1$ and $n$.

Practice › Codeforces Solutions › Pinely Round 1 (Div. 1 + Div. 2) ›

CF 1761B - Elimination of a Ring

We are given a cyclic sequence, which means the first and last positions are also adjacent. Initially, no two adjacent elements are equal. At any moment, Muxii may choose one element and erase it. After that erasure, the ring checks whether equal values have become adjacent.

Practice › Codeforces Solutions › Pinely Round 1 (Div. 1 + Div. 2) ›

CF 1761A - Two Permutations

We are not asked to construct the permutations. We only need to decide whether two permutations of length n can exist such that they share exactly a positions at the beginning and exactly b positions at the end. Think about two permutations p and q.