Codeforces Round 1080 (Div. 3)

8 problems from Codeforces Round 1080 (Div. 3) (contest 2195), difficulty 800-2400. 3/8 solutions verified against sample I/O.

8 items

Codeforces Round 1080 (Div. 3)

Div. 3 | 8 problems | 3/8 verified | Difficulty 800-2400 | 14m 21s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Sieve of Erato67henes	800	math, number-theory	35,395	1m 11s	✓
B	Heapify 1	900	implementation, sortings	24,817	1m 34s	✓
C	Dice Roll Sequence	1100	dp, greedy	20,501	1m 20s	✓
D	Absolute Cinema	1300	math	13,635	2m 12s
E	Idiot First Search	1500	dfs-and-similar, dp, trees	8,532	2m 4s
F	Parabola Independence	2000	dp, graphs, greedy	2,695	2m 4s
G	Idiot First Search and Queries	2300	binary-search, data-structures, dp	1,041	1m 47s
H	Codeforces Heuristic Contest 001	2400	brute-force, constructive-algorithms, geometry	461	2m 9s

Practice › Codeforces Solutions › Codeforces Round 1080 (Div. 3) ›

CF 2195H - Codeforces Heuristic Contest 001

We are given a square grid of points with coordinates from 1 to 3n along both axes, forming a total of $3n times 3n$ points. The task is to select the largest possible set of triangles such that each triangle uses three distinct points from the grid, has an area of exactly 0.

Practice › Codeforces Solutions › Codeforces Round 1080 (Div. 3) ›

CF 2195G - Idiot First Search and Queries

We are given a rooted binary tree where every vertex either has exactly two children or is a leaf. The root is vertex 0, and all other vertices are numbered from 1 to n. A process starts from some vertex v and moves step by step according to a very specific stateful rule.

Practice › Codeforces Solutions › Codeforces Round 1080 (Div. 3) ›

CF 2195F - Parabola Independence

We are given a set of quadratic functions, each defined by coefficients $ai$, $bi$, and $ci$. Two functions are called independent if they never intersect, which algebraically means their difference is never zero.

Practice › Codeforces Solutions › Codeforces Round 1080 (Div. 3) ›

CF 2195E - Idiot First Search

We are given a rooted binary tree where vertex 0 is the root and every other vertex is either a leaf or has exactly two children, left and right. The vertices are numbered, and the structure is fully specified by child pointers.

Practice › Codeforces Solutions › Codeforces Round 1080 (Div. 3) ›

CF 2195D - Absolute Cinema

We are given a hidden sequence of integers $a1, a2, dots, an$ and, instead of the sequence itself, we are provided with a function evaluated at each index: $f(x) = sum{i=1}^n ai cdot Given that $n$ can be as large as 300,000 and the total sum over all test cases is also…

Practice › Codeforces Solutions › Codeforces Round 1080 (Div. 3) ›

CF 2195B - Heapify 1

We are given a permutation of integers from 1 to n and can perform a specific type of swap: for any index i from 1 to n/2, we can swap the element at position i with the element at position 2i.

Practice › Codeforces Solutions › Codeforces Round 1080 (Div. 3) ›

CF 2195C - Dice Roll Sequence

We are given a sequence of numbers from 1 to 6, and we are allowed to change any element to any other value from 1 to 6. The goal is to transform the sequence so that every pair of neighboring elements behaves like valid transitions on a standard dice.

Practice › Codeforces Solutions › Codeforces Round 1080 (Div. 3) ›

CF 2195A - Sieve of Erato67henes

We are given several very small collections of integers, each collection containing at most five numbers, and we are asked whether we can pick some non-empty subset whose product is exactly 67. Each test case is independent.