Codeforces Round 1009 (Div. 3)

7 problems from Codeforces Round 1009 (Div. 3) (contest 2074), difficulty 800-2100. 4/7 solutions verified against sample I/O.

7 items

Codeforces Round 1009 (Div. 3)

Div. 3 | 7 problems | 4/7 verified | Difficulty 800-2100 | 10m 28s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Draw a Square	800	geometry, implementation	44,308	1m 25s	✓
B	The Third Side	800	geometry, greedy, math	34,751	1m 31s	✓
C	XOR and Triangle	1100	bitmasks, brute-force, geometry	21,968	1m 33s
D	Counting Points	1400	brute-force, data-structures, geometry	12,057	1m 14s	✓
E	Empty Triangle	1600	geometry, interactive, probabilities	6,654	1m 25s
F	Counting Necessary Nodes	2000	bitmasks, divide-and-conquer, greedy	2,474	1m 24s	✓
G	Game With Triangles: Season 2	2100	dp, geometry	2,163	1m 56s

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

CF 2074G - Game With Triangles: Season 2

We are given a regular polygon with $n$ vertices, each vertex labeled with a positive integer. The goal is to draw non-overlapping triangles inside the polygon to maximize the sum of products of the numbers at their vertices.

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

CF 2074F - Counting Necessary Nodes

We are given a fixed infinite quadtree structure where every node represents an axis-aligned square whose side length is a power of two, and whose coordinates are aligned to that same scale.

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

CF 2074E - Empty Triangle

We are given a hidden set of points on a plane, and we know there are no duplicates and no three points are collinear. The challenge is that we do not know their coordinates.

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

CF 2074D - Counting Points

We are given several circles drawn on a 2D integer grid. Every circle is centered somewhere on the x-axis, so each center has coordinates of the form $(xi, 0)$, and each circle has a radius $ri$.

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

CF 2074C - XOR and Triangle

We are asked to find, for a given integer x ≥ 2, another integer y such that three numbers x, y, and x XOR y can form a non-degenerate triangle, where a non-degenerate triangle is defined by the triangle inequality. The number y must be strictly less than x.

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

CF 2074B - The Third Side

We start with an array of positive integers. While more than one number remains, we choose two values, replace them with a new positive integer $x$, and require that the three lengths form a non-degenerate triangle.

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

CF 2074A - Draw a Square

We are given four fixed points in the plane. Their coordinates are always aligned with the axes: one lies on the negative x-axis at $(-l, 0)$, one on the positive x-axis at $(r, 0)$, one on the negative y-axis at $(0, -d)$, and one on the positive y-axis at $(0, u)$.