Codeforces Round 938 (Div. 3)

Solutions for Codeforces Round 938 (Div. 3) (contest 1955). 5/8 problems verified against sample I/O. Difficulty range: 800-2300.

8 items

Codeforces Round 938 (Div. 3)

Type: Div. 3 | Problems: 8 | Verified: 5/8 | Rating range: 800-2300 | Time: 7m 51s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Yogurt Sale	800	math	54s	✓
B	Progressive Square	1000	constructive-algorithms, data-structures, implementation	49s	✓
C	Inhabitant of the Deep Sea	1300	greedy, implementation, math	1m 10s	✗
D	Inaccurate Subsequence Search	1400	data-structures, two-pointers	46s	✓
E	Long Inversions	1700	brute-force, greedy, implementation	51s	✓
F	Unfair Game	1800	dp, games, greedy	1m	✗
G	GCD on a grid	1900	brute-force, dfs-and-similar, dp	1m 6s	✓
H	The Most Reckless Defense	2300	bitmasks, brute-force, constructive-algorithms	1m 15s	✗

Practice › Codeforces Solutions › Codeforces Round 938 (Div. 3) ›

CF 1955A - Yogurt Sale

Maxim wants to buy exactly n yogurts from a store where a single yogurt costs a burles, but there is a promotion offering two yogurts for b burles. For each test case, we must calculate the minimum amount he can spend to buy exactly n yogurts.

Practice › Codeforces Solutions › Codeforces Round 938 (Div. 3) ›

CF 1955B - Progressive Square

We are given an $n times n$ grid that is fully determined by three values: the top-left cell, and two fixed increments that govern movement downwards and rightwards. Moving one step down always adds $c$, and moving one step right always adds $d$.

Practice › Codeforces Solutions › Codeforces Round 938 (Div. 3) ›

CF 1955C - Inhabitant of the Deep Sea

We are given a line of ships, each with some durability, and a fixed attack pattern that always targets the current leftmost surviving ship, then the current rightmost surviving ship, and repeats this alternation until a total of $k$ attacks have been made or all ships sink.

Practice › Codeforces Solutions › Codeforces Round 938 (Div. 3) ›

CF 1955D - Inaccurate Subsequence Search

We are asked to count subsegments of length m in an array a that are “good” relative to another array b of length m. A subsegment is considered good if, after rearranging its elements, at least k of them match elements from b.

Practice › Codeforces Solutions › Codeforces Round 938 (Div. 3) ›

CF 1955E - Long Inversions

We are given a binary string and an operation that flips a block of fixed length $k$, turning every 0 into 1 and every 1 into 0. We may apply this operation as many times as we want, but the chosen length $k$ is fixed for the entire process.

Practice › Codeforces Solutions › Codeforces Round 938 (Div. 3) ›

CF 1955F - Unfair Game

We are asked to maximize the number of games Bob can win in a repeated XOR game against Alice. The game is played on a multiset of integers containing only ones, twos, threes, and fours. Alice wins if the XOR of all remaining numbers is non-zero; otherwise, Bob wins.

Practice › Codeforces Solutions › Codeforces Round 938 (Div. 3) ›

CF 1955G - GCD on a grid

We are given a rectangular grid of integers. A move starts at the top-left cell and ends at the bottom-right cell, and at each step we can only go either one cell down or one cell right. Every such move sequence forms a monotone path.

Practice › Codeforces Solutions › Codeforces Round 938 (Div. 3) ›

CF 1955H - The Most Reckless Defense

We are given a grid where some cells form a fixed path from the top-left corner to the bottom-right corner. An enemy walks along this path one cell per second.