Codeforces Round 934 (Div. 1)

8 problems from Codeforces Round 934 (Div. 1) (contest 1943), difficulty 1300-3500. 1/8 solutions verified against sample I/O.

8 items

Codeforces Round 934 (Div. 1)

Div. 1 | 8 problems | 1/8 verified | Difficulty 1300-3500 | 10m 17s

#	Problem	Rating	Tags	Accepted	Time	✓
A	MEX Game 1	1300	games, greedy	21,471	1m 9s	✓
B	Non-Palindromic Substring	2000	hashing, implementation, math	4,540	1m 20s
C	Tree Compass	2300	constructive-algorithms, dfs-and-similar, greedy	2,600	1m 16s
D1	Counting Is Fun (Easy Version)	2400	brute-force, combinatorics, dp	1,950	1m 31s
D2	Counting Is Fun (Hard Version)	2800	combinatorics, dp	1,124	1m 9s
E1	MEX Game 2 (Easy Version)	2900	binary-search, brute-force, greedy	530	1m 13s
E2	MEX Game 2 (Hard Version)	3300	binary-search, greedy, two-pointers	371	1m 18s
F	Minimum Hamming Distance	3500	dp	140	1m 21s

Practice › Codeforces Solutions › Codeforces Round 934 (Div. 1) ›

CF 1943A - MEX Game 1

We are asked to analyze a two-player game on an array of non-negative integers. Alice begins with an empty array c, and on her turn, she takes any element from the initial array a and appends it to c. Bob, on his turn, removes any element from a but does not add it to c.

Practice › Codeforces Solutions › Codeforces Round 934 (Div. 1) ›

CF 1943B - Non-Palindromic Substring

We are given a string and multiple queries, each asking for a contiguous substring of the original string. For each query, we need to calculate a value f(t) for that substring t.

Practice › Codeforces Solutions › Codeforces Round 934 (Div. 1) ›

CF 1943C - Tree Compass

We are given a tree and an operation that does not act on a single node, but on a layer of nodes: if we pick a center vertex $v$ and a distance $d$, we recolor every vertex whose shortest-path distance from $v$ is exactly $d$.

Practice › Codeforces Solutions › Codeforces Round 934 (Div. 1) ›

CF 1943D1 - Counting Is Fun (Easy Version)

We are looking at arrays of length n, where each position can hold an integer between 0 and k. Every such array is considered a candidate, so the total universe is (k+1)^n. The notion of “good” is defined through an operation that subtracts 1 from a contiguous segment.

Practice › Codeforces Solutions › Codeforces Round 934 (Div. 1) ›

CF 1943D2 - Counting Is Fun (Hard Version)

We are asked to count certain arrays with bounded elements that satisfy a combinatorial property. Specifically, consider all arrays of length n where each element is between 0 and k.

Practice › Codeforces Solutions › Codeforces Round 934 (Div. 1) ›

CF 1943E1 - MEX Game 2 (Easy Version)

We are asked to simulate a two-player game on an array of integers, but with a compressed representation where we only know the frequencies of each integer.

Practice › Codeforces Solutions › Codeforces Round 934 (Div. 1) ›

CF 1943E2 - MEX Game 2 (Hard Version)

We are given a multiset of integers, but instead of listing it explicitly, we receive frequencies of each value from 0 up to some maximum m. Alice and Bob remove elements from this multiset until nothing remains.

Practice › Codeforces Solutions › Codeforces Round 934 (Div. 1) ›

CF 1943F - Minimum Hamming Distance

We are given two binary strings of equal length. The first string, call it the reference string, defines a constraint on how a valid target string must behave. The second string is the one we want to stay as close as possible to after we adjust it into a valid configuration.