Codeforces Global Round 31 (Div. 1 + Div. 2)

10 problems from Codeforces Global Round 31 (Div. 1 + Div. 2) (contest 2180), difficulty 800-3500. 3/10 solutions verified against sample I/O.

10 items

Codeforces Global Round 31 (Div. 1 + Div. 2)

Div. 1+2 | 10 problems | 3/10 verified | Difficulty 800-3500 | 24m 11s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Carnival Wheel	800	brute-force, number-theory	25,862	1m 34s	✓
B	Ashmal	800	greedy, strings	24,564	1m 29s	✓
C	XOR-factorization	1900	bitmasks, constructive-algorithms, dp	6,458	2m 9s
D	Insolvable Disks	1900	data-structures, dp, greedy	4,251	2m 9s
E	No Effect XOR	2300	bitmasks, divide-and-conquer, dp	1,737	4m 36s
F1	Control Car (Easy Version)	2800	combinatorics, dp, probabilities	405	5m 10s
F2	Control Car (Hard Version)	3200	combinatorics, dp, matrices	223	1m 46s
G	Balance	3500	bitmasks, combinatorics, implementation	134	1m 50s
H1	Bug Is Feature (Unconditional Version)	3400	games	120	1m 47s
H2	Bug Is Feature (Conditional Version)	3500	games	105	1m 41s	✓

Practice › Codeforces Solutions › Codeforces Global Round 31 (Div. 1 + Div. 2) ›

CF 2180H2 - Bug Is Feature (Conditional Version)

Each game starts from three numbers forming an arithmetic progression, so the state can always be described as $(a, a+d, a+2d)$ with $d 0$. The players repeatedly pick one coordinate and increase it, but the triple must remain an arithmetic progression after every move.

Practice › Codeforces Solutions › Codeforces Global Round 31 (Div. 1 + Div. 2) ›

CF 2180H1 - Bug Is Feature (Unconditional Version)

Working

Practice › Codeforces Solutions › Codeforces Global Round 31 (Div. 1 + Div. 2) ›

CF 2180F1 - Control Car (Easy Version)

The grid in this problem is best thought of as a lattice of junction points, not cells. Every intersection point on the grid is assigned one of four directions. From each such point, we draw a unit segment in its chosen direction.

Practice › Codeforces Solutions › Codeforces Global Round 31 (Div. 1 + Div. 2) ›

CF 2180G - Balance

We maintain a sequence that starts empty and evolves through three kinds of operations. One operation deletes the middle element of the current sequence, where the middle is defined as the ceiling of half the current length.

Practice › Codeforces Solutions › Codeforces Global Round 31 (Div. 1 + Div. 2) ›

CF 2180E - No Effect XOR

We have frogs on every integer position inside a contiguous segment $[l,r]$. After choosing a positive integer $x$, every frog moves from position $i$ to position $i oplus x$. XOR with a fixed value is a permutation of all non-negative integers.

Practice › Codeforces Solutions › Codeforces Global Round 31 (Div. 1 + Div. 2) ›

CF 2180F2 - Control Car (Hard Version)

We are asked to count the number of ways to assign directions to the corners of an $n times m$ grid so that a simulated car starting at the top-left cell eventually stops inside the grid.

Practice › Codeforces Solutions › Codeforces Global Round 31 (Div. 1 + Div. 2) ›

CF 2180D - Insolvable Disks

We are given a set of points on a line, each point representing the center of a disk we must draw. Every disk has a positive radius, and no two disks can overlap, though touching at the edges is allowed.

Practice › Codeforces Solutions › Codeforces Global Round 31 (Div. 1 + Div. 2) ›

CF 2180C - XOR-factorization

We are asked to take an integer $n$ and split it into exactly $k$ non-negative integers whose bitwise XOR equals $n$. Among all such splits, we want one that maximizes the sum of the numbers. Each number in the split must be between 0 and $n$ inclusive.

Practice › Codeforces Solutions › Codeforces Global Round 31 (Div. 1 + Div. 2) ›

CF 2180A - Carnival Wheel

We are given a circular prize wheel with l numbered sections from 0 to l-1. The wheel pointer starts at a section a. Each spin moves the pointer forward by exactly b positions modulo l.

Practice › Codeforces Solutions › Codeforces Global Round 31 (Div. 1 + Div. 2) ›

CF 2180B - Ashmal

We are given a sequence of strings, and we must insert them one by one into an initially empty string. Each new string can be placed either at the left end or the right end of the current result. After all insertions, we obtain a single final string.