Get Time
statistics_w  Match Editorial
SRM 324
Wednesday, October 25, 2006

Match summary

This 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 all-time 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 Problems

Alliteration rate it discuss it
Used as: Division Two - Level One:
Value 250
Submission Rate 436 / 474 (91.98%)
Success Rate 296 / 436 (67.89%)
High Score ystar for 249.84 points (0 mins 43 secs)
Average Score 200.31 (for 296 correct submissions)

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))))
    return res;

PalindromeDecoding rate it discuss it
Used as: Division Two - Level Two:
Value 500
Submission Rate 390 / 474 (82.28%)
Success Rate 365 / 390 (93.59%)
High Score dymu for 498.47 points (1 mins 34 secs)
Average Score 395.93 (for 365 correct submissions)
Used as: Division One - Level One:
Value 250
Submission Rate 414 / 419 (98.81%)
Success Rate 408 / 414 (98.55%)
High Score kalinov for 249.16 points (1 mins 39 secs)
Average Score 227.94 (for 408 correct submissions)

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:

  • Create string a, equal to the substring of string s between positions 0 and i.
  • Iterating through string t in inversed order (from the last character to the first), add all characters of t to a.
  • Concatenate string a with the tail of string s (starting at position i).

    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 rate it discuss it
    Used as: Division Two - Level Three:
    Value 1000
    Submission Rate 254 / 474 (53.59%)
    Success Rate 200 / 254 (78.74%)
    High Score hhllnnnn for 957.83 points (6 mins 0 secs)
    Average Score 694.53 (for 200 correct submissions)

    The main trick in this problem is to switch the input from "customer-based" to "product-based". The input is given to us as an array of strings, where the i-th character in the j-th string is '1' when the i-th product was bought by the j-th customer. Lets transpose the input, so each product will correspond to a string, with the i-th character of this string being '1' only the i-th 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 SA and SB) can be put into one bundle if every customer bought neither of them or both of them. That is, if the i-th character of SA is '1', then the i-th character of SB must be '1' too. Similarly, if the i-th character of SA is '0', the i-th character of SB also must be '0'. In other words, products A and B can be put into one bundle only if strings SA and SB 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);
    	return ret.size();

    TournamentPlan rate it discuss it
    Used as: Division One - Level Two:
    Value 500
    Submission Rate 375 / 419 (89.50%)
    Success Rate 263 / 375 (70.13%)
    High Score Krzysan for 495.69 points (2 mins 39 secs)
    Average Score 398.16 (for 263 correct submissions)

    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.

  • Induction start is with n = 2, and is trivial - cause for 2 competitors there is only 1 game.
  • Assume we proved the hypothesis for all numbers 2.. (n - 1), and now are going to prove this for some n > 2 competitors.

    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 n-1 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;
    	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 rate it discuss it
    Used as: Division One - Level Three:
    Value 1000
    Submission Rate 141 / 419 (33.65%)
    Success Rate 36 / 141 (25.53%)
    High Score Petr for 968.90 points (5 mins 7 secs)
    Average Score 502.67 (for 36 correct submissions)

    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.

    • If the sequence starts from several equal characters, we can safely reduce them one by one to have only 1 such character, and the optimal encoding will not change -- for example, we can reduce "1111010110" -> "111010110" ->... -> "1010110". (Here, the bold characters represent the part which is going to be transformed, and the italic chars represent the result of the transformation). Why? Lets look how these leading characters can be used. If some of them are used as the right part of some palindrome, this means that the whole palindrome consists of the same characters (because there are not different characters left to them), and encoding it will not be better than just reducing all the leading characters one by one. Now consider the left part of the palindrome ("1110000110" -> "111000"). Due to the rules of encoding, the right part of the encoded palindrome immediately disappears. Therefore, we can reduce the corresponding characters in the right part, then encode the updated right part ("1110000110" -> "10000110" -> "1000010" -> "1000010" -> "1000") and these changes will not affect any of the future encodings on the sequence.
    • After the first transformation we have a sequence that starts from several different characters ("1010..." or "0101..."). This sequence can be split in two parts. In the first part, every pair of consecutive characters is different ("01010..."), and this part is as long as possible (so, it continues until we either find a pair of equal characters or the input sequence ends). As soon as we find a pair of two consecutive equal characters, everything starting from the second character of this pair can be removed using palindrome encoding. Also, neither character of the first part can be removed. To remove any character of this part we need to find an even-length palindrome -- in such a palindrome, the middle 2 characters will be equal, which isn't the case for the first part of the sequence.
    To prove that everything except the first part can be deleted, lets see the following algorithm. First, in the second part, reduce any sub-sequence of consecutive equal characters to just one such character. For example, if the sequence is "01011000110100111", then the first part is "0101" and the second is "1000110100111", which must be reduced to "1000110100111" -> "1010101". After this action, the sequence will be of the following form (the first part is bold):
    The 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])
    		s = s.Substring(1);
    	for (int i = 1; i < s.Length; ++i)
    		if (s[i] == s[i - 1]) {
    			s = s.Substring(0, i);
    	return s.Length;

    By Olexiy
    TopCoder Member