VK Cup 2012 Qualification Round 2

Solutions for VK Cup 2012 Qualification Round 2 (contest 159). 5/5 problems verified against sample I/O. Difficulty range: 1100-1700.

5 items

VK Cup 2012 Qualification Round 2

Type: Special | Problems: 5 | Verified: 5/5 | Rating range: 1100-1700 | Time: 8m 47s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Friends or Not	1400	*special, greedy, implementation	1m 47s	✓
B	Matchmaker	1100	*special, greedy, sortings	2m 1s	✓
C	String Manipulation 1.0	1400	*special, binary-search, brute-force	1m 31s	✓
D	Palindrome pairs	1500	*special, brute-force, dp	1m 26s	✓
E	Zebra Tower	1700	*special, data-structures, greedy	2m 2s	✓

Practice › Codeforces Solutions › VK Cup 2012 Qualification Round 2 ›

CF 159A - Friends or Not

We are given a chronological log of private messages between users in a social network. Each record contains the sender, the receiver, and the timestamp of the message. Two users become friends if one of them replies to the other's message quickly enough.

Practice › Codeforces Solutions › VK Cup 2012 Qualification Round 2 ›

CF 159B - Matchmaker

We have two collections of objects. Markers are described by (color, diameter) and caps are also described by (color, diameter). A cap can be attached to a marker only if the diameters are equal.

Practice › Codeforces Solutions › VK Cup 2012 Qualification Round 2 ›

CF 159C - String Manipulation 1.0

We are given a string s and an integer k. The user initially registers a username t which is simply the string s repeated k times consecutively. After that, a sequence of edits occurs, each removing the p-th occurrence of a specified character from the current string.

Practice › Codeforces Solutions › VK Cup 2012 Qualification Round 2 ›

CF 159D - Palindrome pairs

We are given a string of lowercase letters and need to count the number of pairs of non-overlapping palindromic substrings. Formally, we are looking for tuples (a, b, x, y) such that the substring from a to b and the substring from x to y are both palindromes and b < x.

Practice › Codeforces Solutions › VK Cup 2012 Qualification Round 2 ›

CF 159E - Zebra Tower

We have n cubes. Every cube has a color and a size. We want to build a tower using cubes from exactly two distinct colors, and adjacent cubes in the tower must always have different colors. There are no restrictions on cube sizes or ordering.