Educational Codeforces Round 132 (Rated for Div. 2)

Solutions for Educational Codeforces Round 132 (Rated for Div. 2) (contest 1709). 4/6 problems verified against sample I/O. Difficulty range: 800-2500.

6 items

Educational Codeforces Round 132 (Rated for Div. 2)

Type: Div. 2 | Problems: 6 | Verified: 4/6 | Rating range: 800-2500 | Time: 22m 35s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Three Doors	800	brute-force, greedy, implementation	2m 3s	✓
B	Also Try Minecraft	900	data-structures, dp, implementation	11m 39s	✗
C	Recover an RBS	1800	constructive-algorithms, greedy, implementation	2m 39s	✓
D	Rorororobot	1700	binary-search, data-structures, greedy	1m 56s	✓
E	XOR Tree	2400	bitmasks, data-structures, dfs-and-similar	2m 30s	✗
F	Multiset of Strings	2500	bitmasks, brute-force, dp	1m 48s	✓

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

CF 1709B - Also Try Minecraft

We are asked to count, for every interval $[l, r]$, how many triples of distinct integers $i < j < k$ inside this interval satisfy a structural inequality involving their least common multiple: the LCM of the three numbers must be at least as large as their sum.

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

CF 1709F - Multiset of Strings

Think of all binary strings of length at most n as the nodes of a complete binary trie of depth n. Every node except the root receives a capacity cs between 0 and k. A multiset of binary strings of length exactly n assigns some multiplicity to every leaf.

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

CF 1709E - XOR Tree

We are given a tree with n nodes, each labeled with an integer. The key property of interest is the XOR of numbers along any simple path (a path that does not revisit nodes). A tree is "good" if every simple path has a nonzero XOR.

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

CF 1709D - Rorororobot

We are given a grid with $n$ rows and $m$ columns. Each column has some blocked cells at the bottom, specified by an array $a$ where $a[i]$ tells us how many cells at the bottom of column $i$ are blocked. The remaining cells are free.

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

CF 1709C - Recover an RBS

We are given strings consisting of three types of characters: opening brackets '(', closing brackets ')', and question marks '?'. The original string was a correct bracket sequence, also called a regular bracket sequence (RBS), but some brackets were replaced by question marks.

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

CF 1709A - Three Doors

We are given three doors, each with a unique lock number from 1 to 3. We also hold a key in our hand, and behind each door there may be another key or nothing. Two keys are hidden behind doors, and one key is in our hand.