Codeforces Round #127 - really slow or really sleepy?

Even when I end up loosing points in this match I found the problem set very nice and fun. I couldn't fix the problem B during the match and as usual, after the time finish just took me couples of minutes to find my mistake, lucky me :)

A. LLPS

http://codeforces.com/contest/202/problem/A

You are given a lowercase string. Find the lexicographically Largest Palindromic Subsequence.

The strategy to solve this problem was greedy. Let's solve it for an example first to spot the pattern. Given the string yzyaucyarzy our answer is the subsequence zz. Because we are looking the lexicographically largest string is a good idea start with the values that has highest lexicographical value in the string. In addition, because we pick a multiple instances of the same letter that string is without doubt is a palindrome. Once we are done with the z's the question is there another way to add more letters to this palindrome subsequence and get a lexicographically larger palindrome? the answer is no. Imagine now we are trying to add the y's to our subsequence. Because is a palindrome subsequence we can not simply add them to the end, that will make the string non-palindrome (e.g. zzyy) to maintain the palindrome constraints we need to add more letters into the middle of the subsequence. Is easy to see that all the string's that are valid palindromes using the previous mention strategy are not lexicographically larger than the string zz, some examples are {zyyz, zyz, zyryz}. This lead us to the conclusion of just pick the letters with the highest lexicographically value in the given string as our answer.

The constraints of this problems were really small, the largest string has at most 10 characters. The brute force approach is to generate all the possible subsequences of the string which is analogous to generate all the possible subsets of characters. Given the constraints all the possibles subset upperbound is at most \(2^{10} = 1024\) iterations which is really low. For each subsequence (or subset) we keep the lexicographically largest palindrome that we find.

B. Brand New Easy Problem

http://codeforces.com/contest/202/problem/B

You are given the work as a judge in a programming contest. Your task is to classify a problem as new or similar to an old one. If the problem is similar to a previous problem founded in the contest archive you should measure the similarity according to the following metric:

$$\text{p} = \frac{n(n-1)}{2} - x + 1$$

Where \(n\) is the number of words in the original problem, \(x\) is the number of inversions between the original problem and a permutation subsequence of the original problem founded in a problem of the contest archive.

This problem can be solved with brute force. A good strategy to have in mind for any problem is to always exploit the lower constraint. For this problem the really low \(n = 4\) open that possibility. The idea is for each problem that belongs to the problem archive we compare it with all the possible permutations of the problem that we are evaluating. If we find a permutation that is a subsequence of a problem of the archive we calculate the similarity and keep record of the most similar problem so far. The only thing left to explain is how to calculate the inversions of a given subsequence? a simple way is to have a map<string,int> that give us the position of a word in the original problem. Once we have this for any given permutation of the original problem we can normally calculate the inversions using the values in the map.