VK Cup 2012 Round 3

5 problems from VK Cup 2012 Round 3 (contest 164), difficulty 1700-3100. 3/5 solutions verified against sample I/O.

5 items

VK Cup 2012 Round 3

Special | 5 problems | 3/5 verified | Difficulty 1700-3100 | 9m 50s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Variable, or There and Back Again	1700	dfs-and-similar, graphs	1,197	1m 51s	✓
B	Ancient Berland Hieroglyphs	2000	two-pointers	529	1m 30s	✓
C	Machine Programming	2400	flows, graphs	981	2m 16s	✓
D	Minimum Diameter	3100	binary-search, brute-force	276	2m 18s
E	Polycarpus and Tasks	3100		74	1m 55s

Practice › Codeforces Solutions › VK Cup 2012 Round 3 ›

CF 164A - Variable, or There and Back Again

We are given a directed graph where every node represents a program state. Each state does one of three things to a variable: 0 means the variable is ignored. 1 means the variable is assigned a new value. 2 means the variable is used.

Practice › Codeforces Solutions › VK Cup 2012 Round 3 ›

CF 164B - Ancient Berland Hieroglyphs

The problem involves two circular sequences of unique hieroglyphs. We are asked to "cut" these circles at some point to turn them into linear arrays, then find the longest contiguous segment from the first array that appears as a subsequence in the second array.

Practice › Codeforces Solutions › VK Cup 2012 Round 3 ›

CF 164C - Machine Programming

We have several jobs, each with a start time, a duration, and a profit. A machine that starts a job stays occupied for the entire interval from s through s + t - 1. At most k jobs may run simultaneously because we only own k machines. The goal is not to schedule all jobs.

Practice › Codeforces Solutions › VK Cup 2012 Round 3 ›

CF 164D - Minimum Diameter

We are given up to 1000 points on the plane, and we must remove exactly k of them. After removing those points, the remaining set should have the smallest possible diameter. The diameter of a set is the maximum Euclidean distance between any two remaining points.

Practice › Codeforces Solutions › VK Cup 2012 Round 3 ›

CF 164E - Polycarpus and Tasks

Polycarpus has a sequence of tasks, each with a start window, an end window, and a duration. Formally, task i is represented by (li, ri, ti).