Codeforces Round 1076 (Div. 3)

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

8 items

Codeforces Round 1076 (Div. 3)

Div. 3 | 8 problems | 5/8 verified | Difficulty 800-2400 | 18m 26s

#	Problem	Rating	Tags	Accepted	Time	✓
A	DBMB and the Array	800	brute-force, math	42,618	1m 33s	✓
B	Reverse a Permutation	800	greedy	30,096	2m 10s
C	Replace and Sum	1000	data-structures, greedy	28,690	2m 52s	✓
D	Monster Game	1100	binary-search, sortings, two-pointers	21,545	1m 41s	✓
E	Product Queries	1300	dp, math, number-theory	15,179	2m 35s	✓
F	Pizza Delivery	1600	dp, greedy	8,441	2m 21s	✓
G	Paths in a Tree	2100	dfs-and-similar, interactive, sortings	2,236	3m 5s
H	Remove the Grail Tree	2400	dfs-and-similar, dp, graphs	1,043	2m 9s

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

CF 2193H - Remove the Grail Tree

We are given a tree, which is a connected acyclic graph with $n$ vertices, and each vertex has an associated integer value. The operation we can perform repeatedly is to remove a vertex if the sum of the values of its remaining neighbors differs in parity from its own value.

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

CF 2193G - Paths in a Tree

We are given a tree, which is an undirected, connected, acyclic graph of $n$ vertices. Two hidden vertices, $x$ and $y$, define a unique path because trees have exactly one simple path between any pair of vertices.

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

CF 2193F - Pizza Delivery

The courier starts at $(Ax, Ay)$, must visit every house, and finally reach $(Bx, By)$. The movement rules are unusual. He may move one unit to the right, one unit up, or one unit down. He can never decrease his $x$-coordinate.

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

CF 2193E - Product Queries

We are given an array whose values lie between 1 and n. An element may be reused any number of times, so the only thing that matters is which values are present in the array, not how many times they occur.

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

CF 2193D - Monster Game

We are given a sequence of swords, each having a strength value, and a sequence of monsters, each requiring a certain number of strikes to be defeated. Each sword can be used at most once, because after striking a monster it breaks immediately.

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

CF 2193C - Replace and Sum

We start with two arrays of the same length. For any position, we may directly overwrite a[i] with b[i]. We may also copy values from right to left by replacing a[i] with the current value of a[i+1]. Each query asks for the largest possible sum on a subarray a[l..

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

CF 2193B - Reverse a Permutation

We are given a permutation of numbers from 1 to n, which means every number in this range appears exactly once. We are allowed to choose a single continuous segment of this permutation and reverse it.

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

CF 2193A - DBMB and the Array

We are given an array of integers and a fixed increment value. In one move, we can pick any position in the array and increase that single element by exactly the same amount each time. We can repeat this operation as many times as we want on any indices.