Manthan 2011

Solutions for Manthan 2011 (contest 67). 5/5 problems verified against sample I/O. Difficulty range: 1800-2600.

5 items

Manthan 2011

Type: Special | Problems: 5 | Verified: 5/5 | Rating range: 1800-2600 | Time: 9m 26s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Partial Teacher	1800	dp, graphs, greedy	2m 6s	✓
B	Restoration of the Permutation	1800	greedy	1m 59s	✓
C	Sequence of Balls	2600	dp	1m 24s	✓
D	Optical Experiment	1900	binary-search, data-structures, dp	1m 53s	✓
E	Save the City!	2500	geometry	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.