Hello 2024

Solutions for Hello 2024 (contest 1919). 3/9 problems verified against sample I/O. Difficulty range: 800-3500.

9 items

Hello 2024

Type: Special | Problems: 9 | Verified: 3/9 | Rating range: 800-3500 | Time: 19m 25s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Wallet Exchange	800	games, math	2m 5s	✓
B	Plus-Minus Split	800	greedy	1m 58s	✓
C	Grouping Increases	1400	data-structures, dp, greedy	2m 56s	✓
D	01 Tree	2100	constructive-algorithms, data-structures, dsu	46s	✗
E	Counting Prefixes	2600	combinatorics, constructive-algorithms, dp	2m 42s	✗
F1	Wine Factory (Easy Version)	2300	data-structures, greedy	4m 55s	✗
F2	Wine Factory (Hard Version)	2800	data-structures, dp, flows	43s	✗
G	Tree LGM	3500	constructive-algorithms, divide-and-conquer, games	1m 6s	✗
H	Tree Diameter	2000	interactive, trees	2m 14s	✗

Practice › Codeforces Solutions › Hello 2024 ›

CF 1919F1 - Wine Factory (Easy Version)

Because every valve capacity is fixed at $10^{18}$, the valves never become a bottleneck. Any water that remains in tower $i$ after the wizard acts can always move completely into tower $i+1$. This changes the nature of the process dramatically.

Practice › Codeforces Solutions › Hello 2024 ›

CF 1919H - Tree Diameter

We are asked to reconstruct an unknown tree with $n$ vertices and $n-1$ edges by interacting with a grader that allows two types of queries. The first query lets us assign arbitrary positive weights to the edges and returns the resulting diameter of the weighted tree.

Practice › Codeforces Solutions › Hello 2024 ›

CF 1919E - Counting Prefixes

We are asked to reverse-engineer a hidden array of size $n$ that contains only $1$ and $-1$. Instead of being given the array itself, we are given the sorted list of prefix sums of the array. The prefix sum at position $i$ is the sum of the first $i$ elements of the array.

Practice › Codeforces Solutions › Hello 2024 ›

CF 1919G - Tree LGM

We are asked to reconstruct a tree from a matrix of game outcomes. Each entry s[i][j] indicates whether the first player can force a win when the tree is rooted at vertex i and the coin starts at vertex j. A vertex can only move the coin to its children.

Practice › Codeforces Solutions › Hello 2024 ›

CF 1919F2 - Wine Factory (Hard Version)

We are tasked with simulating a sequence of water towers, each containing an initial amount of water. In front of each tower stands a wizard who can convert a limited number of liters into wine.

Practice › Codeforces Solutions › Hello 2024 ›

CF 1919C - Grouping Increases

We are given an array and we must split it into two subsequences, call them $s$ and $t$, covering every element exactly once while preserving relative order inside each subsequence.

Practice › Codeforces Solutions › Hello 2024 ›

CF 1919D - 01 Tree

We are given the distances from the root to the leaves of a binary tree, listed in DFS leaf order. Every internal vertex has exactly two children. One outgoing edge has weight 0 and the other has weight 1.

Practice › Codeforces Solutions › Hello 2024 ›

CF 1919A - Wallet Exchange

Alice and Bob each start with a wallet containing some number of coins. On every turn, the current player may either keep the wallets as they are or swap the two wallets. After that choice, they must remove exactly one coin from the wallet they currently hold.

Practice › Codeforces Solutions › Hello 2024 ›

CF 1919B - Plus-Minus Split

The string consists only of '+' and '-'. We can interpret each character as a number: '+' becomes +1, and '-' becomes -1. We are allowed to split this sequence into any number of contiguous non-empty pieces.