Grakn Forces 2020

Solutions for Grakn Forces 2020 (contest 1408). 3/9 problems verified against sample I/O. Difficulty range: 800-3300.

9 items

Grakn Forces 2020

Type: Special | Problems: 9 | Verified: 3/9 | Rating range: 800-3300 | Time: 22m 34s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Circle Coloring	800	constructive-algorithms	7m 47s	✗
B	Arrays Sum	1400	constructive-algorithms, greedy, math	1m 17s	✓
C	Discrete Acceleration	1500	binary-search, dp, implementation	2m 27s	✗
D	Searchlights	2000	binary-search, brute-force, data-structures	1m 32s	✗
E	Avoid Rainbow Cycles	2400	data-structures, dsu, graphs	1m 51s	✗
F	Two Different	2300	constructive-algorithms, divide-and-conquer	1m 39s	✓
G	Clusterization Counting	2700	combinatorics, dp, dsu	2m 28s	✗
H	Rainbow Triples	3300	binary-search, data-structures, flows	1m 29s	✓
I	Bitwise Magic	3200	dp, math	2m 4s	✗

Practice › Codeforces Solutions › Grakn Forces 2020 ›

CF 1408I - Bitwise Magic

We are given an array of distinct non-negative integers, each at least as large as a given integer $k$, and we perform $k$ random decrements on the array. Each second, one of the $n$ elements is chosen uniformly at random and decreased by 1.

Practice › Codeforces Solutions › Grakn Forces 2020 ›

CF 1408A - Circle Coloring

Your traceback repeatedly shows: This tells us two important facts: 1. You are still running a wrapper-based tester (run) that expects a solve() function 2. The code being tested is not consistently redefining solve() in the same execution scope 3.

Practice › Codeforces Solutions › Grakn Forces 2020 ›

CF 1408G - Clusterization Counting

We are given a complete graph on n computers. Every edge has a unique weight a[i][j], representing the difficulty of communication between those two computers. We want to partition the vertices into groups.

Practice › Codeforces Solutions › Grakn Forces 2020 ›

CF 1408H - Rainbow Triples

We are given an array of integers where the value zero plays a special role. We want to extract as many disjoint triples of indices as possible, and each triple must have a very rigid structure: it must look like a zero, then a non-zero value, then another zero.

Practice › Codeforces Solutions › Grakn Forces 2020 ›

CF 1408F - Two Different

We are asked to construct a sequence of operations on an array of size $n$ that starts as $[1, 2, dots, n]$. Each operation chooses two positions $x$ and $y$ and replaces both $ax$ and $ay$ with a value returned by an arbitrary function $f(ax, ay)$.

Practice › Codeforces Solutions › Grakn Forces 2020 ›

CF 1408E - Avoid Rainbow Cycles

We are given a collection of sets of integers, where each set represents a group of vertices in a graph. Each set has an associated cost ai for deleting any element from it, and each element has a deletion cost bj. The deletion cost for removing element j from set i is ai + bj.

Practice › Codeforces Solutions › Grakn Forces 2020 ›

CF 1408D - Searchlights

We are given a set of robbers positioned on a 2D grid and a set of searchlights, each with a fixed location. Robbers move in a constrained way: in a single move, all robbers either increase their x-coordinate by one or increase their y-coordinate by one.

Practice › Codeforces Solutions › Grakn Forces 2020 ›

CF 1408C - Discrete Acceleration

Two cars start at opposite ends of a road of length l. The left car starts at position 0 and moves to the right. The right car starts at position l and moves to the left. Both cars begin with speed 1. Along the road there are flags placed at fixed coordinates.

Practice › Codeforces Solutions › Grakn Forces 2020 ›

CF 1408B - Arrays Sum

We are given a non-decreasing array a where each entry is a non-negative integer. We want to split this array into a sum of m arrays b₁, b₂, ..., bₘ such that each bᵢ is also non-decreasing and has a strong structural restriction: it uses at most k distinct values.