Codeforces Round 630 (Div. 2)

5 problems from Codeforces Round 630 (Div. 2) (contest 1332), difficulty 1400-3100. 3/5 solutions verified against sample I/O.

5 items

Codeforces Round 630 (Div. 2)

Div. 2 | 5 problems | 3/5 verified | Difficulty 1400-3100 | 13m 43s

#	Problem	Rating	Tags	Accepted	Time	✓
B	Composite Coloring	1400	brute-force, constructive-algorithms, greedy	18,950	1m 55s
C	K-Complete Word	1500	dfs-and-similar, dsu, greedy	20,851	2m 56s	✓
E	Height All the Same	2100	combinatorics, constructive-algorithms, math	4,311	2m 29s	✓
F	Independent Set	2500	dfs-and-similar, dp, trees	1,128	1m 58s	✓
G	No Monotone Triples	3100	data-structures	363	4m 25s

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

CF 1332G - No Monotone Triples

We are given an array of numbers and many queries over subsegments. For each query interval $[L, R]$, we must pick a subsequence of indices inside this interval, in increasing order, with length at least 3, such that the chosen values contain no triple of indices $i < j < k$…

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

CF 1332E - Height All the Same

We are given a rectangular grid with $n times m$ cells, and each cell starts with some integer height $a{i,j}$. The game allows two types of moves that increase heights: either we add one cube to two adjacent cells at the same time, or we add two cubes to a single cell.

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

CF 1332F - Independent Set

We are given a tree with $n$ vertices. For every nonempty subset of edges $E'$, we build the edge-induced subgraph consisting of those edges and every endpoint that appears in at least one selected edge. For that subgraph we count its independent sets.

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

CF 1332C - K-Complete Word

We are given a string s of length n and an integer k such that n is divisible by k. A string is considered k-complete if it is both a palindrome and periodic with period k. Being a palindrome means the string reads the same forwards and backwards.

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

CF 1332B - Composite Coloring

The reviewer is correct. The displayed sequences are not addition chains, because the quantities $2^g,2^h,2^k,2^m$ were used as summands without first appearing as chain elements. The argument must be rebuilt from the definition of a star chain.