VK Cup 2022 - Отборочный раунд (Engine)

Solutions for VK Cup 2022 - Отборочный раунд (Engine) (contest 1781). 2/9 problems verified against sample I/O. Difficulty range: 800-3500.

9 items

VK Cup 2022 - Отборочный раунд (Engine)

Type: Special | Problems: 9 | Verified: 2/9 | Rating range: 800-3500 | Time: 20m 58s

Problem Name Rating Tags Solve Time Verified
A Parallel Projection 800 geometry, math 2m ✗
B Going to the Cinema 1000 brute-force, greedy, sortings 4m 37s ✗
C Equal Frequencies 1600 brute-force, constructive-algorithms, greedy 2m 4s ✗
D Many Perfect Squares 1800 brute-force, math, number-theory 2m 9s ✓
E Rectangle Shrinking 2300 binary-search, brute-force, data-structures 1m 52s ✗
F Bracket Insertion 2700 combinatorics, dp, math 1m 23s ✓
G Diverse Coloring 3200 constructive-algorithms, trees 3m 23s ✗
H1 Window Signals (easy version) 3200 - 1m 41s ✗
H2 Window Signals (hard version) 3500 - 1m 49s ✗
Practice › Codeforces Solutions › VK Cup 2022 - Отборочный раунд (Engine) ›

CF 1781G - Diverse Coloring

I see exactly where prior solutions fail: the minimal cable along the walls and ceiling/floor is not simply the Manhattan distance in x + y + h, because the cable can wrap around walls, reducing the total distance in x or y by traveling along the opposite wall.
codeforces competitive-programming constructive-algorithms trees Jun 9, 2026
Practice › Codeforces Solutions › VK Cup 2022 - Отборочный раунд (Engine) ›

CF 1781H2 - Window Signals (hard version)

We are working on a grid of size $h times w$, where each cell represents a window that can either be lit or dark. A configuration is simply a subset of cells chosen as “on”, with the restriction that at most two specific cells are forbidden from being used.
codeforces competitive-programming Jun 9, 2026
Practice › Codeforces Solutions › VK Cup 2022 - Отборочный раунд (Engine) ›

CF 1781H1 - Window Signals (easy version)

We are given a building with $h$ floors and $w$ windows on each floor, forming a grid of $h times w$. Every window can be either on or off, except for up to two broken windows that are permanently off.
codeforces competitive-programming Jun 9, 2026
Practice › Codeforces Solutions › VK Cup 2022 - Отборочный раунд (Engine) ›

CF 1781F - Bracket Insertion

We are asked to calculate the probability that a bracket sequence formed by repeated random insertions ends up being regular. The process starts with an empty string and runs for n steps. In each step, a new two-character string is inserted at a random position.
codeforces competitive-programming combinatorics dp math trees Jun 9, 2026
Practice › Codeforces Solutions › VK Cup 2022 - Отборочный раунд (Engine) ›

CF 1781B - Going to the Cinema

Each person has a threshold value $ai$. Their decision is completely determined by the final number of people attending the cinema. Suppose exactly $k$ people go.
codeforces competitive-programming brute-force greedy sortings Jun 9, 2026
Practice › Codeforces Solutions › VK Cup 2022 - Отборочный раунд (Engine) ›

CF 1781D - Many Perfect Squares

We are allowed to choose a shift value $x$, and this shift transforms every number in a fixed set by adding $x$. After shifting, we inspect how many of the resulting numbers become perfect squares.
codeforces competitive-programming brute-force math number-theory Jun 9, 2026
Practice › Codeforces Solutions › VK Cup 2022 - Отборочный раунд (Engine) ›

CF 1781E - Rectangle Shrinking

We are working on a very thin grid: only two rows, but an extremely large number of columns. Each input rectangle occupies some contiguous segment of columns and spans either row 1, row 2, or both.
codeforces competitive-programming binary-search brute-force data-structures greedy implementation two-pointers Jun 9, 2026
Practice › Codeforces Solutions › VK Cup 2022 - Отборочный раунд (Engine) ›

CF 1781C - Equal Frequencies

We are asked to transform a given string into a "balanced" string, where every character that appears does so the same number of times. The transformation should change as few positions as possible.
codeforces competitive-programming brute-force constructive-algorithms greedy implementation sortings strings Jun 9, 2026
Practice › Codeforces Solutions › VK Cup 2022 - Отборочный раунд (Engine) ›

CF 1781A - Parallel Projection

We are working inside a rectangular room shaped like a box. A point on the floor marks where the laptop sits, and a point directly above on the ceiling marks where the projector hangs.
codeforces competitive-programming geometry math Jun 9, 2026