Codeforces Round 781 (Div. 2)

Solutions for Codeforces Round 781 (Div. 2) (contest 1665). 3/5 problems verified against sample I/O. Difficulty range: 800-2500.

5 items

Codeforces Round 781 (Div. 2)

Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 800-2500 | Time: 11m 29s

Problem	Name	Rating	Tags	Solve Time	Verified
A	GCD vs LCM	800	constructive-algorithms, math	1m 51s	✗
B	Array Cloning Technique	900	constructive-algorithms, greedy, sortings	1m 51s	✓
C	Tree Infection	1600	binary-search, greedy, sortings	4m 35s	✓
D	GCD Guess	2000	bitmasks, chinese-remainder-theorem, constructive-algorithms	1m 46s	✗
E	MinimizOR	2500	bitmasks, brute-force, data-structures	1m 26s	✓

Practice › Codeforces Solutions › Codeforces Round 781 (Div. 2) ›

CF 1665C - Tree Infection

We are asked to find the minimum time needed to infect all nodes of a rooted tree where infections spread in two ways each second. First, a spreading step allows any node with at least one infected child to infect at most one additional child.

Practice › Codeforces Solutions › Codeforces Round 781 (Div. 2) ›

CF 1665D - GCD Guess

We are asked to find a hidden positive integer $x$ between 1 and $10^9$. Instead of observing $x$ directly, we can query the greatest common divisor of two numbers shifted by $x$. Specifically, for any two positive integers $a$ and $b$, the interactor returns $gcd(x + a, x + b)$.

Practice › Codeforces Solutions › Codeforces Round 781 (Div. 2) ›

CF 1665E - MinimizOR

We are asked to process multiple subarray queries on an array of non-negative integers. For each subarray defined by indices $l$ and $r$, the task is to find the minimum value of the bitwise OR taken over all pairs of distinct elements in that subarray.

Practice › Codeforces Solutions › Codeforces Round 781 (Div. 2) ›

CF 1665A - GCD vs LCM

The problem asks us to split a given positive integer $n$ into four positive integers $a, b, c, d$ such that the sum $a + b + c + d = n$ holds, and at the same time the greatest common divisor of $a$ and $b$ equals the least common multiple of $c$ and $d$.

Practice › Codeforces Solutions › Codeforces Round 781 (Div. 2) ›

CF 1665B - Array Cloning Technique

We are given an array of integers, and we can perform two types of operations: cloning an entire array copy, or swapping elements between any two copies. Our goal is to produce at least one array where all elements are identical, using the minimal number of operations.