Manthan 2011

5 problems from Manthan 2011 (contest 67), difficulty 1800-2600. 5/5 solutions verified against sample I/O.

5 items

Manthan 2011

Special | 5 problems | 5/5 verified | Difficulty 1800-2600 | 9m 26s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Partial Teacher	1800	dp, graphs, greedy	2,479	2m 6s	✓
B	Restoration of the Permutation	1800	greedy	944	1m 59s	✓
C	Sequence of Balls	2600	dp	745	1m 24s	✓
D	Optical Experiment	1900	binary-search, data-structures, dp	1,777	1m 53s	✓
E	Save the City!	2500	geometry	342	2m 4s	✓

Practice › Codeforces Solutions › Manthan 2011 ›

CF 67A - Partial Teacher

We have a line of students, and for every adjacent pair we know only the relative order of their marks. If the relation character between positions i and i + 1 is: - L, then student i must receive strictly more toffees than student i + 1 - R, then student i + 1 must receive…

Practice › Codeforces Solutions › Manthan 2011 ›

CF 67B - Restoration of the Permutation

We are given a permutation A of numbers from 1 to n. For every value i, we know a number b[i]. This number describes how many elements appear before i in the permutation and are at least i + k. The condition is attached to the value itself, not to the position.

Practice › Codeforces Solutions › Manthan 2011 ›

CF 67C - Sequence of Balls

We are given two sequences of balls, labeled by lowercase letters: the original sequence A and the target sequence B. We want to transform A into B using four types of operations: inserting a ball, deleting a ball, replacing a ball, or swapping two adjacent balls.

Practice › Codeforces Solutions › Manthan 2011 ›

CF 67D - Optical Experiment

Each ray enters the box through one hole on the left side and exits through one hole on the right side. The order of holes on both sides matters.

Practice › Codeforces Solutions › Manthan 2011 ›

CF 67E - Save the City!

We are given a simple polygon listed in clockwise order. The first two vertices form a horizontal edge AB, and every other vertex lies strictly on the same side of that edge. Along the segment AB, every integer-coordinate point is a possible location for a watchtower.