Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!)

Solutions for Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) (contest 1774). 2/9 problems verified against sample I/O. Difficulty range: 800-3500.

9 items

Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!)

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

Problem	Name	Rating	Tags	Solve Time	Verified
A	Add Plus Minus Sign	800	constructive-algorithms, math	1m 20s	✓
B	Coloring	1500	constructive-algorithms, greedy, math	2m 17s	✗
C	Ice and Fire	1300	constructive-algorithms, dp, greedy	5m 3s	✗
D	Same Count One	1600	brute-force, constructive-algorithms, greedy	2m 9s	✓
E	Two Chess Pieces	1900	dfs-and-similar, dp, greedy	2m 20s	✗
F1	Magician and Pigs (Easy Version)	2400	brute-force, data-structures, implementation	3m 35s	✗
F2	Magician and Pigs (Hard Version)	2700	binary-search, brute-force, data-structures	1m 45s	✗
G	Segment Covering	3200	brute-force, combinatorics, constructive-algorithms	1m 19s	✗
H	Maximum Permutation	3500	constructive-algorithms	1m 39s	✗

Practice › Codeforces Solutions › Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1774H - Maximum Permutation

We are given a deck of cards numbered from 1 to $n$, and we are asked to construct a permutation of these numbers such that a certain value is maximized. The value of a permutation is defined as the minimum sum of any contiguous subarray of length $k$.

Practice › Codeforces Solutions › Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1774F1 - Magician and Pigs (Easy Version)

We are given a sequence of operations that act on a set of pigs. Each pig has a Health Point value. The operations can either create a new pig with a certain health, reduce the health of all existing pigs by a fixed amount, or repeat all previous operations.

Practice › Codeforces Solutions › Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1774F2 - Magician and Pigs (Hard Version)

We are given a sequence of operations a magician performs. The magician has pigs, each with a certain Health Point (HP). The operations can create pigs, reduce the HP of all pigs, or repeat all previous operations.

Practice › Codeforces Solutions › Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1774G - Segment Covering

We are given a collection of intervals on a huge number line and many queries, each asking about a fixed target interval $[l, r]$.

Practice › Codeforces Solutions › Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1774C - Ice and Fire

We have a tournament with players numbered from 1 to $n$, where each player has a "temperature" equal to their number. Battles happen in environments labeled 0 or 1. In environment 0, the lower-temperature player wins, and in environment 1, the higher-temperature player wins.

Practice › Codeforces Solutions › Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1774E - Two Chess Pieces

We have a rooted tree with root at node 1. Two chess pieces start at the root. Piece A must visit every node from a given set A, piece B must visit every node from another set B. The order is arbitrary. After all required visits are completed, both pieces must return to the root.

Practice › Codeforces Solutions › Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1774D - Same Count One

We have n binary rows, each of length m. A single operation chooses two rows and one column, then swaps the values in that column between those two rows. Because the swap happens inside the same column, the total number of 1s in the whole matrix never changes.

Practice › Codeforces Solutions › Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1774B - Coloring

This is a Type B (prove inequality) problem, not Type C. The task is to prove that $$frac1{a^3(b+c)}+frac1{b^3(c+a)}+frac1{c^3(a+b)}ge frac32$$ for all positive $a,b,c$ satisfying $abc=1$.

Practice › Codeforces Solutions › Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1774A - Add Plus Minus Sign

We are given a binary string, a sequence of 0 and 1, and we want to insert either + or - between each pair of consecutive digits so that the absolute value of the resulting arithmetic expression is minimized.