Codeforces Global Round 2

Solutions for Codeforces Global Round 2 (contest 1119). 6/8 problems verified against sample I/O. Difficulty range: 1100-3400.

8 items

Codeforces Global Round 2

Type: Global | Problems: 8 | Verified: 6/8 | Rating range: 1100-3400 | Time: 10m 34s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Ilya and a Colorful Walk	1100	greedy, implementation	1m 5s	✓
B	Alyona and a Narrow Fridge	1300	binary-search, flows, greedy	1m 54s	✓
C	Ramesses and Corner Inversion	1500	constructive-algorithms, greedy, implementation	1m 4s	✓
D	Frets On Fire	1800	binary-search, sortings	1m 37s	✓
E	Pavel and Triangles	1900	brute-force, dp, fft	1m 5s	✓
F	Niyaz and Small Degrees	3400	data-structures, dp, trees	48s	✗
G	Get Ready for the Battle	3100	constructive-algorithms, implementation	1m 21s	✗
H	Triple	3200	fft, math	1m 40s	✓

Practice › Codeforces Solutions › Codeforces Global Round 2 ›

CF 1119H - Triple

For every triple $(ai,bi,ci)$, we build an array that contains $ai$ exactly $x$ times, $bi$ exactly $y$ times, and $ci$ exactly $z$ times. From each of the $n$ arrays we choose one value. The XOR of all chosen values is some number $t$.

Practice › Codeforces Solutions › Codeforces Global Round 2 ›

CF 1119G - Get Ready for the Battle

We are given a situation where Evlampy has n identical soldiers and must fight an enemy army composed of m groups, each with a certain health hpi.

Practice › Codeforces Solutions › Codeforces Global Round 2 ›

CF 1119F - Niyaz and Small Degrees

We are given a weighted tree. For every degree limit $x$, we may delete any set of edges. Deleting an edge pays its weight. After all deletions, every vertex must have degree at most $x$. For each $x$, we need the minimum total deleted weight.

Practice › Codeforces Solutions › Codeforces Global Round 2 ›

CF 1119E - Pavel and Triangles

We are given many sticks whose lengths are powers of two. For each exponent i, there are ai sticks of length 2^i. Each stick can be used at most once, and we want to form as many non-degenerate triangles as possible, where each triangle uses exactly three sticks.

Practice › Codeforces Solutions › Codeforces Global Round 2 ›

CF 1119B - Alyona and a Narrow Fridge

The fridge has height h and exactly two columns. Shelves can be inserted at any heights, which means we are free to divide the fridge into horizontal compartments of arbitrary heights. Each bottle occupies one column and has height a[i].

Practice › Codeforces Solutions › Codeforces Global Round 2 ›

CF 1119A - Ilya and a Colorful Walk

We are given a street with n houses in a row, numbered from 1 to n, where each house has a color represented by an integer. Ilya wants to pick two houses of different colors and walk between them, measuring the distance simply as the difference in their indices (j - i) for i < j.

Practice › Codeforces Solutions › Codeforces Global Round 2 ›

CF 1119C - Ramesses and Corner Inversion

We are given two matrices, A and B, of size n × m filled with 0s and 1s. We can modify A by repeatedly selecting any submatrix of size at least 2 × 2 and flipping its four corner values.