## Friday, June 29, 2012

### 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 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:

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.