Educational Codeforces Round 157 (Rated for Div. 2)

Solutions for Educational Codeforces Round 157 (Rated for Div. 2) (contest 1895). 4/7 problems verified against sample I/O. Difficulty range: 800-3100.

7 items

Educational Codeforces Round 157 (Rated for Div. 2)

Type: Div. 2 | Problems: 7 | Verified: 4/7 | Rating range: 800-3100 | Time: 13m 43s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Treasure Chest	800	math	1m 50s	✓
B	Points and Minimum Distance	800	greedy, math, sortings	1m 38s	✗
C	Torn Lucky Ticket	1400	brute-force, dp, hashing	1m 27s	✗
D	XOR Construction	1900	bitmasks, constructive-algorithms, data-structures	2m 49s	✓
E	Infinite Card Game	2300	binary-search, brute-force, data-structures	1m 54s	✗
F	Fancy Arrays	2600	combinatorics, dp, math	2m 19s	✓
G	Two Characters, Two Colors	3100	binary-search, data-structures, dp	1m 46s	✓

Practice › Codeforces Solutions › Educational Codeforces Round 157 (Rated for Div. 2) ›

CF 1895G - Two Characters, Two Colors

We are given a binary string where each position carries a value depending on how we color it. Every character can be painted either red or blue. If we choose red at position $i$, we earn $ri$. If we choose blue, we earn $bi$.

Practice › Codeforces Solutions › Educational Codeforces Round 157 (Rated for Div. 2) ›

CF 1895D - XOR Construction

We are given the XOR values between consecutive elements of an unknown permutation. Let the required permutation be $b$. For every adjacent pair, we know $$bi oplus b{i+1} = ai.$$ The array $b$ must contain every integer from $0$ to $n-1$ exactly once.

Practice › Codeforces Solutions › Educational Codeforces Round 157 (Rated for Div. 2) ›

CF 1895F - Fancy Arrays

We are counting arrays of length n consisting of non-negative integers. Adjacent values may move by at most k in either direction. An array is considered fancy if at least one element belongs to the interval $$[x, x+k-1].$$ The task is to count all such arrays modulo $10^9+7$.

Practice › Codeforces Solutions › Educational Codeforces Round 157 (Rated for Div. 2) ›

CF 1895E - Infinite Card Game

Each test case describes two players who each own a fixed set of cards. Every card has two numbers, an attack and a defence. A card can defeat another card if its attack is strictly greater than the other card’s defence. The game starts when Monocarp chooses one of his cards.

Practice › Codeforces Solutions › Educational Codeforces Round 157 (Rated for Div. 2) ›

CF 1895A - Treasure Chest

The number line contains three important positions. Monocarp starts at position 0, the chest is at position x, and the key is at position y. To open the chest, Monocarp must eventually be standing at the same position as the chest while already carrying the key.

Practice › Codeforces Solutions › Educational Codeforces Round 157 (Rated for Div. 2) ›

CF 1895B - Points and Minimum Distance

We start with a multiset of $2n$ integers. The task is to use every number exactly once and pair them up, forming $n$ ordered pairs. Each pair becomes a point in the plane, where the two values are interpreted as its $x$ and $y$ coordinates.

Practice › Codeforces Solutions › Educational Codeforces Round 157 (Rated for Div. 2) ›

CF 1895C - Torn Lucky Ticket

We are given a collection of ticket fragments, each represented as a string of digits from 1 to 9. A lucky ticket is defined as a string of even length where the sum of digits in the first half equals the sum in the second half.