Yandex.Algorithm 2011: Round 2

Solutions for Yandex.Algorithm 2011: Round 2 (contest 86). 5/5 problems verified against sample I/O. Difficulty range: 1600-2700.

5 items

Yandex.Algorithm 2011: Round 2

Type: Special | Problems: 5 | Verified: 5/5 | Rating range: 1600-2700 | Time: 11m 50s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Reflection	1600	math	2m 9s	✓
B	Tetris revisited	2200	constructive-algorithms, graph-matchings, greedy	2m 5s	✓
C	Genetic engineering	2500	dp, string-suffix-structures, trees	2m 12s	✓
D	Powerful array	2200	data-structures, implementation, math	3m 46s	✓
E	Long sequence	2700	brute-force, math, matrices	1m 38s	✓

Practice › Codeforces Solutions › Yandex.Algorithm 2011: Round 2 ›

CF 86A - Reflection

We are given two integers, l and r. For every number n inside this interval, we build another number called its reflection. The reflection is created digit by digit. Every decimal digit d becomes 9 - d.

Practice › Codeforces Solutions › Yandex.Algorithm 2011: Round 2 ›

CF 86B - Tetris revisited

We have a rectangular board where some cells are already blocked by and the remaining cells . must be covered by polyominoes. The allowed pieces are extremely flexible: any connected shape consisting of 2, 3, 4, or 5 cells may be used, with arbitrary rotations and reflections.

Practice › Codeforces Solutions › Yandex.Algorithm 2011: Round 2 ›

CF 86C - Genetic engineering

We are given several short DNA fragments over the alphabet {A, C, G, T}. A longer DNA string is considered valid if every position of the string belongs to at least one occurrence of one of the given fragments. The fragments may overlap arbitrarily.

Practice › Codeforces Solutions › Yandex.Algorithm 2011: Round 2 ›

CF 86D - Powerful array

We are given an array of positive integers and many interval queries. For each query [l, r], we look only at the subarray between those indices and compute a value called its power. If a number x appears k times inside the subarray, then x contributes k² x to the answer.

Practice › Codeforces Solutions › Yandex.Algorithm 2011: Round 2 ›

CF 86E - Long sequence

We are asked to construct a special kind of binary sequence, called a recurrent binary sequence. Each term in this sequence is either 0 or 1, and for a given integer k, there exist coefficients c₁, c₂, …, cₖ, also 0 or 1, such that every term from the k-th onward is a…