VK Cup 2012 Round 1

Solutions for VK Cup 2012 Round 1 (contest 161). 5/5 problems verified against sample I/O. Difficulty range: 1300-2500.

5 items

VK Cup 2012 Round 1

Type: Special | Problems: 5 | Verified: 5/5 | Rating range: 1300-2500 | Time: 11m 9s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Dress'em in Vests!	1300	binary-search, brute-force, greedy	1m 15s	✓
B	Discounts	1700	constructive-algorithms, greedy, sortings	2m 13s	✓
C	Abracadabra	2400	divide-and-conquer	2m 37s	✓
D	Distance in Tree	1800	dfs-and-similar, dp, trees	3m 13s	✓
E	Polycarpus the Safecracker	2500	brute-force, dp	1m 51s	✓

Practice › Codeforces Solutions › VK Cup 2012 Round 1 ›

CF 161A - Dress'em in Vests!

We are tasked with equipping as many soldiers as possible with bulletproof vests. Each soldier has a preferred vest size, but they are willing to tolerate deviations within a given range. Specifically, the i-th soldier can wear any vest with a size between a[i] - x and a[i] + y.

Practice › Codeforces Solutions › VK Cup 2012 Round 1 ›

CF 161B - Discounts

We have a collection of items sold in a supermarket. Every item has a price and a type. Type 1 means the item is a stool, type 2 means it is a pencil. Polycarpus owns exactly k shopping carts, and every cart must contain at least one item.

Practice › Codeforces Solutions › VK Cup 2012 Round 1 ›

CF 161C - Abracadabra

The infinite string in this problem is built recursively. Start with: In general: The alphabet contains 36 symbols: The full string after 30 steps has length: $ For k = 30, the length is about 10^9, which matches the input bounds.

Practice › Codeforces Solutions › VK Cup 2012 Round 1 ›

CF 161D - Distance in Tree

We are given a tree with n vertices, meaning a connected graph with no cycles, and a number k. The task is to count how many pairs of distinct vertices are separated by exactly k edges.

Practice › Codeforces Solutions › VK Cup 2012 Round 1 ›

CF 161E - Polycarpus the Safecracker

We are given several prime numbers. Each prime represents the first row of a square matrix of digits. If the prime has length n, then the matrix is n × n. The matrix must satisfy two conditions. First, every row interpreted as a decimal number must itself be prime.