Codeforces Round 934 (Div. 2)

Solutions for Codeforces Round 934 (Div. 2) (contest 1944). 2/7 problems verified against sample I/O. Difficulty range: 800-2800.

7 items

Codeforces Round 934 (Div. 2)

Type: Div. 2 | Problems: 7 | Verified: 2/7 | Rating range: 800-2800 | Time: 12m 51s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Destroying Bridges	800	graphs, greedy, math	55s	✓
B	Equal XOR	1100	bitmasks, constructive-algorithms	2m 13s	✗
C	MEX Game 1	1300	constructive-algorithms, games, greedy	3m 29s	✓
D	Non-Palindromic Substring	2000	hashing, implementation, strings	1m 22s	✗
E	Tree Compass	2300	constructive-algorithms, dfs-and-similar, greedy	1m 59s	✗
F1	Counting Is Fun (Easy Version)	2400	combinatorics, dp, math	1m 37s	✗
F2	Counting Is Fun (Hard Version)	2800	combinatorics, dp	1m 16s	✗

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

CF 1944F2 - Counting Is Fun (Hard Version)

We are asked to count arrays of length n with elements between 0 and k that can be reduced to all zeros using a specific operation. The operation allows selecting two distinct indices l and r and subtracting 1 from all elements between l and r inclusive.

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

CF 1944F1 - Counting Is Fun (Easy Version)

We are given an array of length $n$, where each position can independently take any value from $0$ to $k$. So the total universe is all $(k+1)^n$ arrays. The question is not about simulating the process directly.

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

CF 1944C - MEX Game 1

Alice and Bob play on a multiset of numbers. Alice and Bob alternately remove elements from the array, with Alice moving first. The difference is that whenever Alice removes a value, she also keeps it in her personal array c, while Bob simply deletes a value.

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

CF 1944E - Tree Compass

We are asked to color all nodes of a tree black using the fewest operations. Each operation lets us pick a node $v$ and a distance $d$, and it colors all nodes that are exactly distance $d$ from $v$.

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

CF 1944B - Equal XOR

This is a Type A problem: find all natural numbers $x$ satisfying a given condition. For a Type A problem, the solution must do two things: 1. Derive necessary conditions and prove that every solution must satisfy them. 2.

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

CF 1944D - Non-Palindromic Substring

We are given a string of lowercase English letters and a set of queries, each specifying a contiguous substring of the string. For each query, we are asked to compute the sum of all lengths $k$ for which there exists at least one substring of length $k$ that is not a palindrome.

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

CF 1944A - Destroying Bridges

We are asked to consider a network of islands where initially every pair of islands is connected by a bridge. There are n islands, numbered from 1 to n, and Everule lives on island 1. Dominater can destroy up to k bridges to reduce the number of islands that Everule can reach.