ABBYY Cup 2.0 - Hard

Solutions for ABBYY Cup 2.0 - Hard (contest 178). 10/12 problems verified against sample I/O. Difficulty range: 1000-2300.

12 items

ABBYY Cup 2.0 - Hard

Type: Special | Problems: 12 | Verified: 10/12 | Rating range: 1000-2300 | Time: 24m 40s

Problem	Name	Rating	Tags	Solve Time	Verified
A1	Educational Game	1000	-	1m 53s	✓
A2	Educational Game	1000	greedy	1m 43s	✓
A3	Educational Game	1100	greedy	1m 58s	✓
B1	Greedy Merchants	1600	-	2m 15s	✓
C1	Smart Beaver and Resolving Collisions	1600	-	2m 43s	✓
C2	Smart Beaver and Resolving Collisions	1900	-	1m 48s	✓
C3	Smart Beaver and Resolving Collisions	2000	-	2m 38s	✓
D2	Magic Squares	1900	-	1m 58s	✓
E1	The Beaver's Problem - 2	1900	-	1m 41s	✓
E2	The Beaver's Problem - 2	2000	-	1m 47s	✗
E3	The Beaver's Problem - 2	2300	-	2m 17s	✗
F1	Representative Sampling	1800	-	1m 59s	✓

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Hard ›

CF 178A1 - Educational Game

We have an array of non-negative integers. In one move, we choose an index i with a[i] 0, decrease a[i] by one, and increase some position i + 2t by one. The destination index must have the same parity as i, because the distance moved is always even.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Hard ›

CF 178A2 - Educational Game

We are given a sequence of non-negative integers representing a game board. The task is to repeatedly perform moves that decrease one number and increase another number two steps ahead.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Hard ›

CF 178A3 - Educational Game

We have an array of non-negative integers. In one move, we pick an index i with a[i] 0, decrease a[i] by 1, and increase some position j by 1, where j - i must be even and j = i. The parity restriction is the core of the problem.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Hard ›

CF 178B1 - Greedy Merchants

We are given a connected undirected graph representing cities and roads in the Roman Empire. Each merchant wants to transport goods between two cities.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Hard ›

CF 178C1 - Smart Beaver and Resolving Collisions

We have a hash table with h cells numbered from 0 to h - 1. Every inserted object has a fixed hash value t. If cell t is occupied, we try the next candidate cell by repeatedly adding m modulo h: $$t, (t+m)bmod h, (t+2m)bmod h,dots$$ The first empty cell receives the object.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Hard ›

CF 178C2 - Smart Beaver and Resolving Collisions

We simulate a hash table that resolves collisions using linear probing with step size m. When an object with hash value t is inserted, we first try cell t. If it is occupied, we try (t + m) mod h, then (t + 2m) mod h, and continue until we find an empty position.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Hard ›

CF 178C3 - Smart Beaver and Resolving Collisions

We maintain a hash table with h cells numbered from 0 to h - 1. Every insertion starts from the object's hash value and probes cells by repeatedly adding m modulo h until it finds an empty slot.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Hard ›

CF 178D2 - Magic Squares

We are given exactly $n^2$ integers and must place them into an $n times n$ grid so that every row, every column, and both diagonals all have the same sum. The multiset of numbers cannot change, each value must appear exactly as many times as it appears in the input.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Hard ›

CF 178E1 - The Beaver's Problem - 2

We are given a noisy black-and-white image represented as an n × n grid. A value of 1 means a black pixel, and 0 means a white pixel. The image originally contained only circles and squares drawn in black on a white background.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Hard ›

CF 178E2 - The Beaver's Problem - 2

We are given a square image represented as an $n times n$ grid of pixels, where each pixel is either black (1) or white (0). Within this image are a few geometric shapes: circles and squares. Our goal is to count how many circles and squares appear.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Hard ›

CF 178E3 - The Beaver's Problem - 2

We are given a large binary image represented as an n × n grid. A value of 1 means a black pixel, and 0 means a white pixel. The black regions correspond to geometric figures. Every figure is either a circle or a square.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Hard ›

CF 178F1 - Representative Sampling

We are given a multiset of strings and must choose exactly k of them. The score of the chosen group is based on longest common prefixes between every unordered pair of chosen strings. If two strings share a prefix of length t, then that pair contributes t to the total score.