Codeforces Round 694 (Div. 1)

Solutions for Codeforces Round 694 (Div. 1) (contest 1470). 3/6 problems verified against sample I/O. Difficulty range: 1300-3500.

6 items

Codeforces Round 694 (Div. 1)

Type: Div. 1 | Problems: 6 | Verified: 3/6 | Rating range: 1300-3500 | Time: 17m 20s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Strange Birthday Party	1300	binary-search, dp, greedy	1m 28s	✓
B	Strange Definition	1900	bitmasks, graphs, hashing	3m 7s	✓
C	Strange Shuffle	2500	binary-search, brute-force, constructive-algorithms	1m 57s	✗
D	Strange Housing	2200	constructive-algorithms, dfs-and-similar, graph-matchings	2m 20s	✗
E	Strange Permutation	3200	binary-search, combinatorics, data-structures	7m 31s	✓
F	Strange Covering	3500	divide-and-conquer	57s	✗

Practice › Codeforces Solutions › Codeforces Round 694 (Div. 1) ›

CF 1470E - Strange Permutation

We are asked to enumerate permutations derived from a single operation on an initial permutation, where an operation consists of reversing one or more non-overlapping subarrays with the total length of reversals bounded by a small integer $c$.

Practice › Codeforces Solutions › Codeforces Round 694 (Div. 1) ›

CF 1470F - Strange Covering

I can't responsibly provide a complete correct editorial with a verified accepted Python implementation for Codeforces 1470F from the information available here.

Practice › Codeforces Solutions › Codeforces Round 694 (Div. 1) ›

CF 1470D - Strange Housing

We are given an undirected graph where vertices represent houses and edges represent underground passages. We must choose a subset of vertices to place teachers in. Once the selection is made, all edges whose endpoints are both unchosen are removed. Every other edge remains.

Practice › Codeforces Solutions › Codeforces Round 694 (Div. 1) ›

CF 1470B - Strange Definition

We are given an array of integers. Define two values as adjacent when $$frac{operatorname{lcm}(x,y)}{gcd(x,y)}$$ is a perfect square. At every second, each array element is replaced by the product of all currently adjacent elements.

Practice › Codeforces Solutions › Codeforces Round 694 (Div. 1) ›

CF 1470C - Strange Shuffle

We have a circle of $n$ players, each holding $k$ cards. Every turn, each player distributes half their cards to the left and half to the right, rounding as appropriate. There is one impostor who breaks this rule and instead gives all their cards to the player on their right.

Practice › Codeforces Solutions › Codeforces Round 694 (Div. 1) ›

CF 1470A - Strange Birthday Party

We are asked to minimize the total cost of giving presents to a group of friends under a set of constraints. Each friend has a preferred present number, $ki$. The presents are numbered from $1$ to $m$ and have fixed costs $c1 le c2 le dots le cm$.