Codeforces Round 666 (Div. 1)

Solutions for Codeforces Round 666 (Div. 1) (contest 1396). 1/5 problems verified against sample I/O. Difficulty range: 1600-3300.

5 items

Codeforces Round 666 (Div. 1)

Type: Div. 1 | Problems: 5 | Verified: 1/5 | Rating range: 1600-3300 | Time: 27m 33s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Multiples of Length	1600	constructive-algorithms, greedy, number-theory	7m 59s	✗
B	Stoned Game	1800	brute-force, constructive-algorithms, games	11m 46s	✓
C	Monster Invaders	2300	dp, greedy, implementation	2m 48s	✗
D	Rainbow Rectangles	3300	data-structures, sortings, two-pointers	2m 38s	✗
E	Distance Matching	3200	constructive-algorithms, dfs-and-similar, trees	2m 22s	✗

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

CF 1396B - Stoned Game

The traceback tells us exactly what happened: The code is trying to read an edge of a tree as two integers u v. But the actual input is: Let's trace it: First test case: Then the next line is which is an array of length 7.

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

CF 1396A - Multiples of Length

Thank you for clarifying. Now I can carefully trace the bug. The input is: Expected output: But your current code outputs: Your code probably does something like: But the expected outputs (3, 6, 1) do not match counting '1's directly: - "120" → output 3 (not 1) - "11011" →…

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

CF 1396E - Distance Matching

We are given a tree with an even number of nodes and an integer $k$. From this tree, we can construct a complete graph where each node represents a vertex from the tree and the weight of an edge between any two vertices is the distance between the corresponding nodes in the tree.

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

CF 1396D - Rainbow Rectangles

We are given a set of colored points on a very large grid. Each point has integer coordinates and one of $k$ colors. We want to count how many axis-aligned integer rectangles we can choose such that the rectangle contains at least one point of every color.

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

CF 1396C - Monster Invaders

We are asked to compute the minimum time for Ziota to clear all bosses in a sequence of game levels. Each level contains some number of normal monsters, each with 1 health point, and exactly one boss with 2 health points.