VK Cup 2012 Finals (unofficial online-version)

5 problems from VK Cup 2012 Finals (unofficial online-version) (contest 212), difficulty 1500-3000. 1/5 solutions verified against sample I/O.

5 items

VK Cup 2012 Finals (unofficial online-version)

Special | 5 problems | 1/5 verified | Difficulty 1500-3000 | 9m 48s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Privatization	3000	flows, graphs	228	2m 20s
B	Polycarpus is Looking for Good Substrings	2300	bitmasks, hashing, implementation	368	1m 54s	✓
C	Cowboys	2100	combinatorics, dp, math	486	1m 28s
D	Cutting a Fence	2500	binary-search, data-structures, dsu	614	1m 8s
E	IT Restaurants	1500	dfs-and-similar, dp, trees	2,196	2m 58s

Practice › Codeforces Solutions › VK Cup 2012 Finals (unofficial online-version) ›

CF 212A - Privatization

We are given a bipartite graph. One side contains Berland cities, the other side contains Beerland cities, and every flight is an undirected edge between the two countries. Each edge must be assigned to one of t private companies.

Practice › Codeforces Solutions › VK Cup 2012 Finals (unofficial online-version) ›

CF 212B - Polycarpus is Looking for Good Substrings

We are given one long lowercase string s. For every query, we are also given a set of characters C. Among all substrings of s, we only care about those whose set of distinct characters is exactly C. From those substrings, we must count how many are maximal by inclusion.

Practice › Codeforces Solutions › VK Cup 2012 Finals (unofficial online-version) ›

CF 212C - Cowboys

We are given a circular arrangement of cows, each cow facing exactly one of its two neighbors. Represent the circle as a binary string where each character describes direction: one symbol means “point to clockwise neighbor” and the other means “point to counterclockwise…

Practice › Codeforces Solutions › VK Cup 2012 Finals (unofficial online-version) ›

CF 212D - Cutting a Fence

We are given a long strip of vertical planks, each with a fixed height. For any contiguous segment of planks of fixed length $k$, Vasya paints a rectangle whose height is determined by the shortest plank inside that segment.

Practice › Codeforces Solutions › VK Cup 2012 Finals (unofficial online-version) ›

CF 212E - IT Restaurants

We are asked to place two types of restaurants on a tree-shaped city map in such a way that no two adjacent junctions host different types, each junction hosts at most one restaurant, and each network has at least one restaurant.