ABBYY Cup 3.0

Solutions for ABBYY Cup 3.0 (contest 316). 6/12 problems verified against sample I/O. Difficulty range: 1100-2400.

12 items

ABBYY Cup 3.0

Type: Special | Problems: 12 | Verified: 6/12 | Rating range: 1100-2400 | Time: 30m 35s

Problem	Name	Rating	Tags	Solve Time	Verified
A1	Special Task	1100	greedy	1m 30s	✗
B1	EKG	1500	brute-force, dfs-and-similar	3m 27s	✗
B2	EKG	1600	dfs-and-similar, dp	3m 21s	✗
C1	Tidying Up	2200	flows	1m 56s	✓
C2	Tidying Up	2300	flows, graph-matchings	3m 19s	✓
D2	PE Lesson	2300	dp	3m 25s	✓
D3	PE Lesson	2400	dp, math	3m 11s	✓
E1	Summer Homework	1500	brute-force, data-structures	3m 8s	✓
F3	Suns and Rays	2200	constructive-algorithms, dfs-and-similar, implementation	2m	✗
G1	Good Substrings	1700	hashing, strings	2m 24s	✗
G2	Good Substrings	2200	string-suffix-structures	1m 48s	✗
G3	Good Substrings	2400	string-suffix-structures	1m 6s	✓

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316A1 - Special Task

We are given a string that represents a partially specified code. Each position in the string contributes constraints on what digit can appear there.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316B1 - EKG

We are given a set of people labeled from 1 to n, and each person may specify exactly one other person who must come immediately after them in a line. If this value is zero, the person does not specify who follows them, meaning their successor is not fixed.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316B2 - EKG

We are asked to reconstruct the possible positions of a specific beaver in a queue based on partial ordering information. Each beaver either knows who should be directly in front of them in the line, or does not know, represented by zero.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316C1 - Tidying Up

We are given a rectangular dressing room divided into n × m squares, where each square contains a single shoe. Every shoe belongs to exactly one pair, and each pair is represented by a unique integer appearing exactly twice in the grid.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316C2 - Tidying Up

We are given an $n times m$ grid where each cell contains an integer representing a “shoe pair ID”. Every ID appears exactly twice in the grid, so each number defines exactly two positions.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316D2 - PE Lesson

The problem describes a line of students, each holding a uniquely numbered ball. Each student can participate in at most one or two throws, and in each throw, two students exchange the balls they are holding.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316D3 - PE Lesson

We start with a line of students, each holding a uniquely numbered ball from 1 to n in order. The system evolves through operations where a teacher selects two students and swaps the balls they currently hold.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316E1 - Summer Homework

We maintain a dynamic array of integers where three kinds of updates and queries are mixed together in arbitrary order.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316F3 - Suns and Rays

The input is a binary image, essentially a grid where each cell is either background or part of a drawn object. Inside this grid, there are multiple disjoint shapes called suns.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316G1 - Good Substrings

We are given a main string s. From this string, we consider every possible substring and want to count how many distinct substrings are considered “good”. Whether a candidate substring t is good is not decided by properties of s itself, but by a small set of constraints.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316G2 - Good Substrings

We are given a main string $s$. We want to count how many different substrings of $s$ are “valid” under a set of constraints. Each constraint gives us another string $p$ and two integers $l$ and $r$.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316G3 - Good Substrings

We are asked to count the number of distinct substrings of a string s that satisfy a set of rules. Each rule consists of a string p and a range [l, r]. A substring t of s is good if, for every rule (p, l, r), the number of times t occurs in p lies within the given range.