Codeforces Round 854 by cybercats (Div. 1 + Div. 2)

Solutions for Codeforces Round 854 by cybercats (Div. 1 + Div. 2) (contest 1799). 2/9 problems verified against sample I/O. Difficulty range: 800-3200.

9 items

Codeforces Round 854 by cybercats (Div. 1 + Div. 2)

Type: Div. 1+2 | Problems: 9 | Verified: 2/9 | Rating range: 800-3200 | Time: 21m 23s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Recent Actions	800	data-structures, greedy, implementation	2m 16s	✗
B	Equalize by Divide	1200	brute-force, constructive-algorithms, greedy	2m 59s	✗
C	Double Lexicographically Minimum	1700	greedy, strings	3m 36s	✗
D1	Hot Start Up (easy version)	1900	dp	3m 6s	✓
D2	Hot Start Up (hard version)	2100	data-structures, dp	1m 58s	✓
E	City Union	2300	constructive-algorithms, dfs-and-similar, dsu	1m 52s	✗
F	Halve or Subtract	2700	binary-search, brute-force, dp	2m 16s	✗
G	Count Voting	2600	combinatorics, dp, math	2m 23s	✗
H	Tree Cutting	3200	bitmasks, dfs-and-similar, dp	57s	✗

Practice › Codeforces Solutions › Codeforces Round 854 by cybercats (Div. 1 + Div. 2) ›

CF 1799G - Count Voting

We have a group of $n$ people, each belonging to a specific team, and each person wants to receive a certain number of votes. The rules restrict voting so that no one can vote for themselves and no one can vote for someone on their own team.

Practice › Codeforces Solutions › Codeforces Round 854 by cybercats (Div. 1 + Div. 2) ›

CF 1799F - Halve or Subtract

We are given an array of positive integers and two types of optional operations that can be applied to elements, with global limits and per-element limits.

Practice › Codeforces Solutions › Codeforces Round 854 by cybercats (Div. 1 + Div. 2) ›

CF 1799H - Tree Cutting

I can't reliably write a correct, complete editorial for Codeforces 1799H from the problem statement alone. This is a 3200-rated problem with a highly nontrivial tree DP over subsets, and the solution involves delicate state design and transition conditions.

Practice › Codeforces Solutions › Codeforces Round 854 by cybercats (Div. 1 + Div. 2) ›

CF 1799E - City Union

We are given a rectangular grid of size $n times m$, where each cell is either filled or empty. A "city" is defined as a connected component of filled cells, where connectivity is through sides (no diagonals). Initially, there are exactly two cities on the grid.

Practice › Codeforces Solutions › Codeforces Round 854 by cybercats (Div. 1 + Div. 2) ›

CF 1799D1 - Hot Start Up (easy version)

We are given a fixed execution order of programs, and we must execute them sequentially on a machine with two independent CPUs. Each program has two possible execution costs: a normal cost and a reduced cost.

Practice › Codeforces Solutions › Codeforces Round 854 by cybercats (Div. 1 + Div. 2) ›

CF 1799D2 - Hot Start Up (hard version)

We are given a sequence of programs that must be executed in order, using two CPUs. Each program has two run times: a cold time, which applies if the CPU last ran a different program, and a hot time, which applies if the CPU last ran the same program.

Practice › Codeforces Solutions › Codeforces Round 854 by cybercats (Div. 1 + Div. 2) ›

CF 1799C - Double Lexicographically Minimum

We are given a string consisting of lowercase letters, and the task is to reorder its characters into a new string t such that when we consider t and its reverse, the lexicographically larger of the two-denoted tmax-is as small as possible in lexicographic order.

Practice › Codeforces Solutions › Codeforces Round 854 by cybercats (Div. 1 + Div. 2) ›

CF 1799B - Equalize by Divide

We are given an array of positive integers. We can repeatedly pick two distinct indices $i$ and $j$, and set the element at index $i$ to the ceiling of its division by the element at index $j$.

Practice › Codeforces Solutions › Codeforces Round 854 by cybercats (Div. 1 + Div. 2) ›

CF 1799A - Recent Actions

We are asked to track the "Recent Actions" field of posts on a site like Codeforces. Initially, the field contains the first $n$ posts, numbered $1$ through $n$, from top to bottom. New posts with numbers $n+1$ and higher can appear through actions.