Codeforces Round 812 (Div. 2)

Solutions for Codeforces Round 812 (Div. 2) (contest 1713). 1/6 problems verified against sample I/O. Difficulty range: 800-2900.

6 items

Codeforces Round 812 (Div. 2)

Type: Div. 2 | Problems: 6 | Verified: 1/6 | Rating range: 800-2900 | Time: 17m 31s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Traveling Salesman Problem	800	geometry, greedy, implementation	1m 44s	✓
B	Optimal Reduction	1000	constructive-algorithms, sortings	2m 28s	✗
C	Build Permutation	1200	constructive-algorithms, dp, math	6m 37s	✗
D	Tournament Countdown	1800	constructive-algorithms, greedy, interactive	1m 55s	✗
E	Cross Swapping	2400	2-sat, data-structures, dsu	2m 32s	✗
F	Lost Array	2900	bitmasks, combinatorics, constructive-algorithms	2m 15s	✗

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

CF 1713C - Build Permutation

We are asked to construct a permutation of the numbers from $0$ to $n-1$ such that for each index $i$, the sum of the value at that index and the index itself is a perfect square. In other words, for every $i$, $pi + i = k^2$ for some integer $k$.

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

CF 1713F - Lost Array

We are given a hidden array a of length n and a derived matrix b of size (n+1) × (n+1) defined using XOR. The matrix b starts with zeros in the first column and the first row is the array a. Every other cell in b is constructed as b[i][j] = b[i][j-1] XOR b[i-1][j].

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

CF 1713E - Cross Swapping

We are given a square matrix of integers, and we are allowed to perform a specific swap operation: for a chosen index k, we swap the k-th row with the k-th column, leaving the diagonal element at (k, k) unchanged.

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

CF 1713D - Tournament Countdown

We are dealing with a complete single-elimination tournament of size $2^n$. Players are indexed from 1 to $2^n$. Matches happened in a fixed bracket: adjacent pairs played first, then winners of neighboring matches played again, and so on until one champion remains.

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

CF 1713B - Optimal Reduction

We are given an array of positive integers. We can repeatedly choose a contiguous subarray and decrease all elements in that subarray by one. The goal is to bring all array elements to zero using as few operations as possible.

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

CF 1713A - Traveling Salesman Problem

We are working on a grid where movement is allowed in the four cardinal directions, and every move costs one step.