Codeforces Round 764 (Div. 3)

Solutions for Codeforces Round 764 (Div. 3) (contest 1624). 4/7 problems verified against sample I/O. Difficulty range: 800-2000.

7 items

Codeforces Round 764 (Div. 3)

Type: Div. 3 | Problems: 7 | Verified: 4/7 | Rating range: 800-2000 | Time: 14m 4s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Plus One on the Subset	800	math	5m 25s	✗
B	Make AP	900	implementation, math	1m 15s	✓
C	Division by Two and Permutation	1100	constructive-algorithms, flows, graph-matchings	1m 12s	✓
D	Palindromes Coloring	1400	binary-search, greedy, sortings	1m 13s	✓
E	Masha-forgetful	2000	brute-force, constructive-algorithms, dp	1m 47s	✗
F	Interacdive Problem	2000	binary-search, constructive-algorithms, interactive	1m 34s	✗
G	MinOr Tree	1900	bitmasks, dfs-and-similar, dsu	1m 38s	✓

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

CF 1624A - Plus One on the Subset

Now we can carefully trace exactly why the previous attempts failed. The problem is that the "chessboard XOR" must be applied not to the irregular input literally as read, but according to the grid structure, i.e.

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

CF 1624G - MinOr Tree

We are given a connected undirected graph where each edge has a positive integer weight. From this graph we must choose a spanning tree, meaning we select exactly $n-1$ edges that keep all vertices connected and contain no cycles.

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

CF 1624F - Interacdive Problem

We are interacting with a hidden integer $x$, where we are initially told a modulus-like parameter $n$. The only way to influence or observe the hidden state is by issuing commands that add a chosen value $c$ to $x$, after which we are told the value of $lfloor x / n rfloor$.

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

CF 1624E - Masha-forgetful

We are given a target digit string s and a collection of known digit strings, all of the same length. The goal is to reconstruct s as a sequence of contiguous segments, where each segment must exactly match a substring taken from one of the known strings.

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

CF 1624D - Palindromes Coloring

We are given a string of lowercase letters and an integer $k$, representing the number of colors available. The task is to color the letters so that, when we group the letters by color, each group forms a palindrome after any number of swaps within the same color.

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

CF 1624B - Make AP

We are given three fixed positions in a sequence: first value a, second value b, and third value c. We are allowed exactly one modification operation: choose one of these three positions and multiply it by some positive integer m of our choice.

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

CF 1624C - Division by Two and Permutation

We are given an array of positive integers of size $n$, and we want to know if we can turn it into a permutation of numbers from $1$ to $n$ by repeatedly dividing elements by two. Each division operation replaces an element $ai$ with $lfloor ai / 2 rfloor$.