Codeforces Round 934 (Div. 1)

Solutions for Codeforces Round 934 (Div. 1) (contest 1943). 1/8 problems verified against sample I/O. Difficulty range: 1300-3500.

8 items

Codeforces Round 934 (Div. 1)

Type: Div. 1 | Problems: 8 | Verified: 1/8 | Rating range: 1300-3500 | Time: 10m 17s

Problem	Name	Rating	Tags	Solve Time	Verified
A	MEX Game 1	1300	games, greedy	1m 9s	✓
B	Non-Palindromic Substring	2000	hashing, implementation, math	1m 20s	✗
C	Tree Compass	2300	constructive-algorithms, dfs-and-similar, greedy	1m 16s	✗
D1	Counting Is Fun (Easy Version)	2400	brute-force, combinatorics, dp	1m 31s	✗
D2	Counting Is Fun (Hard Version)	2800	combinatorics, dp	1m 9s	✗
E1	MEX Game 2 (Easy Version)	2900	binary-search, brute-force, greedy	1m 13s	✗
E2	MEX Game 2 (Hard Version)	3300	binary-search, greedy, two-pointers	1m 18s	✗
F	Minimum Hamming Distance	3500	dp	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.