Codeforces Round 1048 (Div. 1)

8 problems from Codeforces Round 1048 (Div. 1) (contest 2138), difficulty 1100-3500. 0/8 solutions verified against sample I/O.

8 items

Codeforces Round 1048 (Div. 1)

Div. 1 | 8 problems | 0/8 verified | Difficulty 1100-3500 | 13m 56s

#	Problem	Rating	Tags	Accepted	Time
A	Cake Assignment	1100	bitmasks, constructive-algorithms, greedy	16,992	1m 40s
B	Antiamuny Wants to Learn Swap	1900	data-structures, greedy, two-pointers	5,325	1m 42s
C1	Maple and Tree Beauty (Easy Version)	1800	brute-force, dfs-and-similar, dp	5,423	1m 38s
C2	Maple and Tree Beauty (Hard Version)	2000	bitmasks, brute-force, dfs-and-similar	3,366	1m 32s
D	Antiamuny and Slider Movement	2600	brute-force, combinatorics, implementation	640	1m 56s
E1	Determinant Construction (Easy Version)	3100	brute-force, constructive-algorithms, math	239	2m 11s
E2	Determinant Construction (Hard Version)	3100	brute-force, constructive-algorithms, math	184	1m 32s
F	Ode to the Bridge Builder	3500	constructive-algorithms, geometry	82	1m 45s

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

CF 2138F - Ode to the Bridge Builder

We start with two fixed points in the plane, one at the origin and one at $(1,0)$, connected by a segment. The only allowed way to create new points is by repeatedly selecting an existing segment, treating its endpoints as two vertices of a triangle, and then placing a third…

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

CF 2138E2 - Determinant Construction (Hard Version)

We are asked to construct a square matrix with small integer entries, limited non-zero elements per row and column, and a determinant equal to a given target number.

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

CF 2138E1 - Determinant Construction (Easy Version)

The determinant can be written using the Leibniz formula: $$det(M)=sum{sigma} operatorname{sgn}(sigma)prodi M{i,sigma(i)}.$$ A brute force viewpoint is to think of each permutation as choosing one outgoing edge from every row and one incoming edge into every column.

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

CF 2138D - Antiamuny and Slider Movement

We are given a sorted line of unit-sized sliders placed on integer positions along a very long track. Each slider keeps a fixed identity, and the initial configuration is strictly increasing, meaning no two sliders start at the same position.

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

CF 2138C2 - Maple and Tree Beauty (Hard Version)

We are given a rooted tree with n vertices. Each vertex must be labeled either 0 or 1, with exactly k zeros and n - k ones. The "name" of a vertex is the string formed by concatenating the labels along the path from the root to that vertex.

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

CF 2138B - Antiamuny Wants to Learn Swap

We are given a permutation of integers from 1 to $n$, and we must answer multiple queries about whether certain subarrays are "perfect" according to a special sorting rule.

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

CF 2138A - Cake Assignment

We have two people, Chocola and Vanilla, who start with exactly the same number of cakes, which is $2^k$ each. The total number of cakes is $2^{k+1}$. The goal is to redistribute the cakes so that Chocola ends up with exactly $x$ cakes and Vanilla gets the rest.

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

CF 2138C1 - Maple and Tree Beauty (Easy Version)

We are given a rooted tree with n vertices, where the root is vertex 1. Each vertex is labeled either 0 or 1, but we do not know the exact labeling. All we know is that exactly k vertices have label 0, and the remaining n - k have label 1.