Codeforces Round 1030 (Div. 2)

7 problems from Codeforces Round 1030 (Div. 2) (contest 2118), difficulty 800-3100. 1/7 solutions verified against sample I/O.

7 items

Codeforces Round 1030 (Div. 2)

Div. 2 | 7 problems | 1/7 verified | Difficulty 800-3100 | 12m 28s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Equal Subsequences	800	constructive-algorithms, greedy	29,112	1m 27s
B	Make It Permutation	1200	constructive-algorithms	20,032	1m 33s
C	Make It Beautiful	1300	bitmasks, data-structures, greedy	18,463	1m 58s
D1	Red Light, Green Light (Easy version)	1700	brute-force, dfs-and-similar, dp	8,453	1m 58s	✓
D2	Red Light, Green Light (Hard version)	2200	binary-search, brute-force, data-structures	2,497	1m 37s
E	Grid Coloring	2400	constructive-algorithms, geometry, greedy	1,425	1m 59s
F	Shifts and Swaps	3100	data-structures, graphs, hashing	283	1m 56s

Practice › Codeforces Solutions › Codeforces Round 1030 (Div. 2) ›

CF 2118F - Shifts and Swaps

We are asked whether one array of integers, a, can be transformed into another array, b, using two types of operations. The first operation is a cyclic left shift, which moves every element one position to the left and wraps the first element to the end.

Practice › Codeforces Solutions › Codeforces Round 1030 (Div. 2) ›

CF 2118E - Grid Coloring

We have an odd-sized rectangular grid. Cells are colored one at a time. Whenever a new cell is colored, we look only at the cells that were already colored before this step. Among those cells, every cell that is farthest from the newly colored one receives one penalty.

Practice › Codeforces Solutions › Codeforces Round 1030 (Div. 2) ›

CF 2118D1 - Red Light, Green Light (Easy version)

We have a one-dimensional strip of length up to $10^{15}$, along which certain cells contain traffic lights. Each light has a fixed period $k$ and a delay $di < k$, and it turns red at times $l cdot k + di$ for integer $l ge 0$. All other times, the light is green.

Practice › Codeforces Solutions › Codeforces Round 1030 (Div. 2) ›

CF 2118D2 - Red Light, Green Light (Hard version)

We are asked to simulate motion along a one-dimensional strip of length up to $10^{15}$, where certain cells contain traffic lights with periodic red signals. Each traffic light has a fixed period $k$ and a delay $di$, meaning it shows red at times $t$ where $t mod k = di$.

Practice › Codeforces Solutions › Codeforces Round 1030 (Div. 2) ›

CF 2118C - Make It Beautiful

We are given an array of integers. Each integer has a "beauty" defined as the number of 1s in its binary representation. For example, 5 in binary is 101, which has two 1s, so its beauty is 2. The total beauty of the array is the sum of the beauties of all its elements.

Practice › Codeforces Solutions › Codeforces Round 1030 (Div. 2) ›

CF 2118B - Make It Permutation

We start with an $n times n$ matrix where every row is identical and equal to the sequence $1,2,3,dots,n$. So initially every column is constant, and no column is a permutation at all.

Practice › Codeforces Solutions › Codeforces Round 1030 (Div. 2) ›

CF 2118A - Equal Subsequences

We are asked to construct a binary string of length $n$, containing exactly $k$ ones, with an additional structural constraint involving subsequences of length three.