VK Cup 2012 Finals (unofficial online-version)

Solutions for VK Cup 2012 Finals (unofficial online-version) (contest 212). 1/5 problems verified against sample I/O. Difficulty range: 1500-3000.

5 items

VK Cup 2012 Finals (unofficial online-version)

Type: Special | Problems: 5 | Verified: 1/5 | Rating range: 1500-3000 | Time: 9m 48s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Privatization	3000	flows, graphs	2m 20s	✗
B	Polycarpus is Looking for Good Substrings	2300	bitmasks, hashing, implementation	1m 54s	✓
C	Cowboys	2100	combinatorics, dp, math	1m 28s	✗
D	Cutting a Fence	2500	binary-search, data-structures, dsu	1m 8s	✗
E	IT Restaurants	1500	dfs-and-similar, dp, trees	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.