Match Editorial

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

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

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)

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:

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;
}

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 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 i-th character of S_A is '1', then the i-th character of S_B must be '1' too. Similarly, if the i-th character of S_A is '0', the i-th 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();
}

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.

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;
}

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.

1010...011010...10
or 
1010...011010...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;
}