Codeforces Global Round 21

Solutions for Codeforces Global Round 21 (contest 1696). 3/8 problems verified against sample I/O. Difficulty range: 800-3500.

8 items

Codeforces Global Round 21

Type: Global | Problems: 8 | Verified: 3/8 | Rating range: 800-3500 | Time: 25m 20s

Problem	Name	Rating	Tags	Solve Time	Verified
A	NIT orz!	800	bitmasks, greedy	2m 3s	✓
B	NIT Destroys the Universe	900	greedy	2m 11s	✓
C	Fishingprince Plays With Array	1400	constructive-algorithms, greedy, implementation	8m 28s	✗
D	Permutation Graph	1900	binary-search, constructive-algorithms, data-structures	2m 42s	✗
E	Placing Jinas	2000	combinatorics, math	1m 59s	✓
F	Tree Recovery	2600	brute-force, constructive-algorithms, dfs-and-similar	2m 32s	✗
G	Fishingprince Plays With Array Again	3300	brute-force, data-structures, geometry	2m 55s	✗
H	Maximum Product?	3500	brute-force, combinatorics, dp	2m 30s	✗

Practice › Codeforces Solutions › Codeforces Global Round 21 ›

CF 1696H - Maximum Product?

We are given a collection of integers where each element is tied to its index, so even equal values are treated as distinct items. From this collection, every subset is considered independently.

Practice › Codeforces Solutions › Codeforces Global Round 21 ›

CF 1696C - Fishingprince Plays With Array

We are given two arrays and a fixed integer $m$. Starting from the first array, we may repeatedly split an element divisible by $m$ into $m$ equal pieces, or merge $m$ consecutive equal elements into one larger element.

Practice › Codeforces Solutions › Codeforces Global Round 21 ›

CF 1696G - Fishingprince Plays With Array Again

We are given an array whose values represent amounts that must be removed. An operation acts on one adjacent pair. If we spend $t$ seconds on edge $(i,i+1)$, we may subtract $(x t, y t)$ from the pair or $(y t, x t)$ from the pair.

Practice › Codeforces Solutions › Codeforces Global Round 21 ›

CF 1696F - Tree Recovery

We are asked to reconstruct a tree based on a set of distance equalities between triples of vertices. Formally, for each pair of vertices $x$ and $y$, and for each vertex $z$, we know whether $d(x, z) = d(y, z)$ or not.

Practice › Codeforces Solutions › Codeforces Global Round 21 ›

CF 1696D - Permutation Graph

We are given a permutation of integers from 1 to n and asked to construct a graph based on the relative minimum and maximum values in contiguous segments.

Practice › Codeforces Solutions › Codeforces Global Round 21 ›

CF 1696E - Placing Jinas

We are asked to control dolls on an infinite grid where each cell can be white or black. The color of each cell is defined by a non-increasing sequence $a0, a1, dots, an$, extended with zeros beyond $n$.

Practice › Codeforces Solutions › Codeforces Global Round 21 ›

CF 1696B - NIT Destroys the Universe

We are given an array representing the “universe,” where each element is a non-negative integer. The protagonist, NIT, can perform a specific operation on any contiguous subarray: compute the mex of that subarray and set every element in it to that mex.

Practice › Codeforces Solutions › Codeforces Global Round 21 ›

CF 1696A - NIT orz!

We are given an array of integers and a number $z$. We are allowed to repeatedly pick any element $ai$ and perform two bitwise operations: update $ai$ to $ai operatorname{or} z$ and simultaneously update $z$ to $ai operatorname{and} z$.