Wednesday, October 25, 2006 Match summaryThis SRM, being the last start before the upcoming GCJ finals, attracted a lot of strong coders, including 6 (out of the total 10) targeteers. The expected battle didn't happen because of Petr, who needed only a bit more than 12 minutes to submit all 3 problems. In addition to getting another spot among the alltime highest total scores, Petr regained the top line in the Algorithm Ranking. In Div 2, newcomer lazlo won the round by a solid margin over more experienced members sunempire, fabrizyo, arnstein and moonli, all of whom were close in the race for the second place.
The ProblemsAlliterationUsed as: Division Two  Level One:
The most difficult part of this problem is to avoid counting the same alliteration twice. For example, the input {"A", "ate", "apple"} contains only 1 alliteration, though two pairs of consecutive words ("A" + "ate", and "ate" + "apple") start from the same letter. To implement this, we can count all such pairs of words in which both words start from the same letter, but the word directly before this pair started from another letter. With this trick we avoid counting the same alliteration multiple times. Java implementation of this approach follows: public int count(String[] words) { int res = 0; for (int i = 0; i < words.length  1; i++) { if (Character.toLowerCase(words[i].charAt(0)) == Character.toLowerCase(words[i + 1].charAt(0)) && (i == 0  Character.toLowerCase(words[i].charAt(0)) != Character.toLowerCase(words[i  1].charAt(0)))) res++; } return res; }PalindromeDecoding Used as: Division Two  Level Two: Used as: Division One  Level One:
To solve this problem you just need to carefully implement the algorithm described in the statement. The basic step you need to implement here is inserting a reversed string into another string at some position. For example, if you need to insert the reversed string t at position i of string s, you can: The complete solution of this problem consists of several string conversions, using the indices from the input: public String decode(String code, int[] position, int[] length) { String ans = code; for (int i = 0; i < position.length; i++) { String res = ans.substring(0, position[i] + length[i]); for (int j = length[i]  1; j >= 0; j) res += ans.charAt(position[i] + j); ans = res + ans.substring(position[i] + length[i]); } return ans; }ProductBundling Used as: Division Two  Level Three:
The main trick in this problem is to switch the input from "customerbased" to "productbased". The input is given to us as an array of strings, where the ith character in the jth string is '1' when the ith product was bought by the jth customer. Lets transpose the input, so each product will correspond to a string, with the ith character of this string being '1' only the ith customer bought the corresponding product. Building a string for each product from the input, we receive a new array of strings, with the length of each strings being equal to the number of elements in the input, and the number of new strings being equal to the length of each element of the input. For example, if the input is {"1010", "1100"} (example 1 from the problem), the new array will be {"11", "01", "10", "00"}. Now let's check when two products can be put into one bundle. As the statement says, product A and product B (which correspond to strings S_{A} and S_{B}) can be put into one bundle if every customer bought neither of them or both of them. That is, if the ith character of S_{A} is '1', then the ith character of S_{B} must be '1' too. Similarly, if the ith character of S_{A} is '0', the ith character of S_{B} also must be '0'. In other words, products A and B can be put into one bundle only if strings S_{A} and S_{B} are equal. If any number of products correspond to the same string, then all of them can be put into one big bundle. Also, if two products correspond to different strings, they can never be put in the same bundle. Therefore, the number of different bundles is the same as the number of different strings in the new array: public int howManyBundles(String[] data) { HashSet<String> ret = new HashSet(); for (int a = 0; a < data[0].length(); a++) { String temp = ""; for (int b = 0; b < data.length; b++) temp += data[b].charAt(a); ret.add(temp); } return ret.size(); }TournamentPlan Used as: Division One  Level Two:
Consider a more general problem, where each competitor is assigned some cost Ci, and travelling a unit of distance costs him Ci dollars. We are to find the minimal cost necessary to play the tournament (you can see that initial problem is a special case of this general problem, where all costs are equal to 1). By induction on the number of competitors n, we will prove that there exists an optimal solution where all games are played at the same intersection. Consider the two competitors A and B playing the first game. After they played their game, they both have to play against the same opponents, so they continue on the same path. This can be seen as that A and B are substituted by one competitor with a weight which is the sum of the weights of A and B and a starting location, which is the location of the game between A and B. Now we have n1 competitors left. By the induction hypothesis we know there exists an optimal solution, where all games are played at one intersection. Since the triangle inequality holds for the manhattan distance, A and B can go to that intersection immediately and play their game there. We proved that all games of the tournament can be played at the same intersection, now we need to find the exact location of this intersection. Consider an intersection located at street X, with K players starting at streets with numbers less than X, and L competitors starting at streets with numbers bigger than or equal to X. If we move the intersection to the street with number (X  1), the total distance travelled by the competitors will decrease by (K  L) (obviously, the distance will increase if L > K), and it will decrease by (K  L) with each street until numbers K and L will change (this happens when we move to a street where one of the competitors starts). Similarly, if the number M of the competitors who start at streets with numbers greater than X will be greater than the number of the competitors who start at streets with numbers less than or equal to X, we can decrease the total distance by moving the intersection towards streets with higher numbers. Therefore, the optimal intersection (where the competitors travel the smallest distance) is located at a street where one of the competitors starts, and it can not be moved in either direction  so, the optimal intersection is located at the median street. Since the same thoughts can be applied to avenues as well, we know all the games are played at the intersection of the median avenue and the median street, and the solution for the problem becomes amazingly short: public int getTravelDistance(int[] street, int[] avenue) { int n = street.length; Arrays.sort(street); Arrays.sort(avenue); int distance = 0; for (int i = 0; i < street.length; i++) distance += Math.abs(street[i]  street[n/2]) + Math.abs(avenue[i]  avenue[n/2]); return distance; }PalindromeEncoding Used as: Division One  Level Three:
The solution to this problem is amazingly short  the difficult part is to find the correct algorithm and prove that it will work (of course, the latter is not necessary as long as you trust your intuition). We will find the optimal encoding in 2 steps.
1010...011010...10 or 1010...011010...101The final transformations are similar in both these cases  we reduce "10"s from the right part one by one, ("1010...011010...10" > "1010...011010" > "1010...0110" > "1010...01"). If two '1's are left at the right end, we reduce the second of them ("1010...1011" > "1010...101"). Petr's C# solution follows: public int getLength(string s) { while (s.Length > 1) { if (s[0] != s[1]) break; s = s.Substring(1); } for (int i = 1; i < s.Length; ++i) if (s[i] == s[i  1]) { s = s.Substring(0, i); break; } return s.Length; } 
