CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)

Solutions for CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) (contest 1870). 2/8 problems verified against sample I/O. Difficulty range: 800-3500.

8 items

CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)

Type: Div. 1+2 | Problems: 8 | Verified: 2/8 | Rating range: 800-3500 | Time: 18m 56s

Problem	Name	Rating	Tags	Solve Time	Verified
A	MEXanized Array	800	constructive-algorithms, greedy, math	1m 45s	✗
B	Friendly Arrays	1200	bitmasks, greedy, math	1m 45s	✓
C	Colorful Table	1300	binary-search, data-structures, dp	2m 13s	✗
D	Prefix Purchase	1800	greedy, implementation, sortings	1m 45s	✗
E	Another MEX Problem	2300	bitmasks, brute-force, dp	5m 6s	✓
F	Lazy Numbers	2900	binary-search, math	2m 51s	✗
G	MEXanization	3300	data-structures	1m 42s	✗
H	Standard Graph Problem	3500	data-structures, graphs, greedy	1m 49s	✗

Practice › Codeforces Solutions › CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1870H - Standard Graph Problem

We are working with a weighted directed graph with n vertices and m edges. Each vertex can be “highlighted” or “normal,” starting with all vertices normal.

Practice › Codeforces Solutions › CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1870E - Another MEX Problem

We are given an array of integers, and we are allowed to carve it into several disjoint contiguous segments, leaving some elements unused if we want. For every chosen segment we compute its MEX, which is the smallest non-negative integer missing from that segment.

Practice › Codeforces Solutions › CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1870G - MEXanization

We are given an array, and we look at its prefixes one by one. For each prefix, we treat it as a multiset of integers and imagine repeatedly performing a very unusual operation: we pick any non-empty sub-multiset, remove it, compute its MEX, and insert that MEX back.

Practice › Codeforces Solutions › CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1870F - Lazy Numbers

We are asked to consider the numbers from 1 to $n$ expressed in base $k$. Once expressed in base $k$, we sort these representations lexicographically, like strings. After sorting, we number the elements from 1 to $n$.

Practice › Codeforces Solutions › CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1870D - Prefix Purchase

We are given a process that builds an array from left to right using prefix operations. Initially every position is zero.

Practice › Codeforces Solutions › CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1870C - Colorful Table

We are given an array a of length n with integers between 1 and k. From a, we define a square table b of size n × n where each cell (i, j) is the minimum of a[i] and a[j]. Each integer in b represents a "color".

Practice › Codeforces Solutions › CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1870A - MEXanized Array

We are building an array of length $n$ using non-negative integers, with each element capped at $x$. The array is not arbitrary: it must have a fixed MEX equal to $k$, and among all such valid arrays, we want the one with the largest possible sum of elements.

Practice › Codeforces Solutions › CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1870B - Friendly Arrays

We are given two arrays, a of length n and b of length m. We are allowed to repeatedly choose any element bj from b and update every element of a as ai = ai The key observations from the input constraints are that n and m can each be up to 200,000 but the sum across all test…