Codeforces Round 793 (Div. 2)

Solutions for Codeforces Round 793 (Div. 2) (contest 1682). 2/6 problems verified against sample I/O. Difficulty range: 800-2700.

6 items

Codeforces Round 793 (Div. 2)

Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 800-2700 | Time: 12m 7s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Palindromic Indices	800	greedy, strings	2m 10s	✗
B	AND Sorting	1100	bitmasks, constructive-algorithms, sortings	2m 16s	✗
C	LIS or Reverse LIS?	1400	constructive-algorithms, greedy, implementation	1m 42s	✓
D	Circular Spanning Tree	2000	constructive-algorithms, implementation, trees	1m 38s	✗
E	Unordered Swaps	2700	constructive-algorithms, dfs-and-similar, graphs	2m 13s	✗
F	MCMF?	2700	data-structures, flows, graphs	2m 8s	✓

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

CF 1682D - Circular Spanning Tree

We are asked to construct a tree on n nodes arranged in a circle. Each node has a requirement: its degree must be even or odd, depending on the corresponding character in a binary string s.

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

CF 1682F - MCMF?

We are given a sorted array a and an integer array b. Each query gives a segment [l, r], and we only care about it if the sum of b over this segment is zero. This condition guarantees that total “supply” and “demand” inside the segment balance perfectly.

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

CF 1682E - Unordered Swaps

We are given a permutation of integers from $1$ to $n$ and a set of $m$ swaps, which are guaranteed to be the minimum swaps required to sort the permutation. These swaps have been shuffled arbitrarily.

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

CF 1682B - AND Sorting

We are given a permutation of the integers from 0 to n−1, and we are allowed to rearrange it using a very unusual swap rule. A swap between two positions is only allowed when the bitwise AND of the two values currently stored at those positions equals a chosen value X.

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

CF 1682A - Palindromic Indices

We are given a string that is already a palindrome, meaning it reads the same from left to right and right to left. For each position in this string, we imagine removing exactly one character and then ask whether the remaining string is still a palindrome.

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

CF 1682C - LIS or Reverse LIS?

We are given several test cases. Each test case provides a multiset of numbers, and we are allowed to rearrange them in any order we want. After choosing an ordering, we look at two sequences: the chosen array itself, and its reverse.