ABBYY Cup 3.0

18 problems from ABBYY Cup 3.0 (contest 316), difficulty 1100-2400. 12/18 solutions verified against sample I/O.

18 items

ABBYY Cup 3.0

Special | 18 problems | 12/18 verified | Difficulty 1100-2400 | 31m 4s

#	Problem	Rating	Tags	Accepted	Time	✓
A1	Special Task	1100	greedy	2,888	1m 18s	✓
A2	Special Task	1400	math	2,295	2m 20s	✓
B1	EKG	1500	brute-force, dfs-and-similar	1,498	1m 33s	✓
B2	EKG	1600	dfs-and-similar, dp	1,780	1m 3s	✓
C1	Tidying Up	2200	flows	592	2m 24s
C2	Tidying Up	2300	flows, graph-matchings	668	3m 26s
D1	PE Lesson	2300	brute-force, dp	606	2m 6s
D2	PE Lesson	2300	dp	542	1m 15s	✓
D3	PE Lesson	2400	dp, math	709	1m 1s	✓
E1	Summer Homework	1500	brute-force, data-structures	1,548	1m 30s	✓
E2	Summer Homework	2300	data-structures, math	432	2m 7s
E3	Summer Homework	2300	data-structures, math	572	1m 23s	✓
F1	Suns and Rays	2200	dfs-and-similar, implementation	197	2m 14s
F2	Suns and Rays	2300		177	58s	✓
F3	Suns and Rays	2200	constructive-algorithms, dfs-and-similar, implementation	197	57s	✓
G1	Good Substrings	1700	hashing, strings	1,085	1m 12s	✓
G2	Good Substrings	2200	string-suffix-structures	517	3m 7s
G3	Good Substrings	2400	string-suffix-structures	542	1m 10s	✓

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316C2 - Tidying Up

We have an n × m grid. Every cell contains one shoe, and every shoe pair number appears exactly twice in the whole grid. A configuration is considered tidy when the two shoes belonging to every pair occupy adjacent cells. Adjacency is by a shared side, not a corner.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316C1 - Tidying Up

We have a dressing room represented as a rectangular grid of size n by m, where each cell contains a single shoe. Every shoe belongs to a pair, and each pair appears exactly twice in the grid.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316G2 - Good Substrings

We are given a source string s. We are interested only in substrings that appear inside s, and we count each distinct substring once, regardless of how many times it occurs. A substring is considered good if it satisfies every rule.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316F1 - Suns and Rays

The problem presents an image encoded as a 2D grid of integers where 0 represents the background and 1 represents a sun, including its rays. Each sun consists of a central ellipse (or circle) and a number of rays protruding from it.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316E2 - Summer Homework

We are given an array of integers of size n, and a sequence of m operations of three possible types. The first type replaces a single element in the array with a new value. The second type queries the sum of a range where each element is weighted by Fibonacci numbers.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316D1 - PE Lesson

We have a line of n students, each holding a distinct ball numbered from 1 to n. Students can swap their balls with each other, but each student has a limit on the total number of throws they can participate in.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316A2 - Special Task

We are given a pattern string describing a decimal code. Some positions already contain fixed digits. Some positions contain ?, meaning any digit may be placed there. Some positions contain letters from A to J. Each letter represents a digit, but with two constraints.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316A1 - Special Task

The problem asks us to count how many numeric codes match a hint string that can contain fixed digits, wildcards, and letters representing digit equality constraints. Each character in the hint string represents a position in the safe code. A question mark ?

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316G3 - Good Substrings

We are given a main string $s$ and several constraints, each constraint consists of a pattern string $p$ and a numeric interval $[l, r]$.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316G1 - Good Substrings

We are asked to count the number of distinct substrings of a string s that satisfy a set of occurrence-based rules.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316F3 - Suns and Rays

The task is to analyze a binary image where 0 represents the background and 1 represents a sun or its rays. Each sun consists of a central ellipse (which may be rotated) and several rays extending outward as line segments from the ellipse’s boundary.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316F2 - Suns and Rays

The input is a pixel grid made of two values, where one value represents empty background and the other represents ink belonging to drawn objects.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316E3 - Summer Homework

We are maintaining an array that changes over time through point updates and range updates, while also answering range queries.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316E1 - Summer Homework

We are given an array of integers, and we need to process a sequence of operations that modify the array or query it in a special way. There are three types of operations: direct assignment of a value to an element, range sums weighted by Fibonacci numbers, and range increments.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316D3 - PE Lesson

We are given a line of students, each initially holding a distinct labeled ball from 1 to n. The only operation allowed is choosing two different students and swapping the balls they currently hold.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316D2 - PE Lesson

We are given a line of students, each initially holding a distinct labeled ball. The only operation allowed is to pick two students and swap the balls they currently hold.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316B2 - EKG

We are given a queue of n beavers, each numbered from 1 to n. Each beaver either knows who should be immediately in front of them, represented as a[i] (the number of that beaver), or does not know, represented as 0.

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316B1 - EKG

We are given a structure of people standing in a queue, but the queue is not fully known. Each person either clearly knows who stands immediately in front of them or does not know that information at all.