Qualification Round 2 Tuesday, August 21, 2007 Match summaryQualification Round 2 of TCCC07 attracted 729 competitors, so the struggle for the top 550 spots was a bit less intense than Qual Round 1 but it was still very exciting. The complexity of the problems and the amount of submissions were quite close to Qual 1, but the challenge phase proved to be much more eventful, with 175 successful challenges. The newcomer fangge from China took first place with an impressive 1653.14 points, thanks to a fast solution on the hard and a bunch of challenges  five of them successful and four that weren't. Second place was also taken by a newcomer, 4umep from the Russian Federation. lyt was only 12.79 points behind and took third place. The cutoff to advance was 201.75. Congratulations to the 550 coders who qualified for Online Round 1, and good luck to those who are trying to do so in Qualification Round 3! The ProblemsAlmostPerfectNumberUsed as: Division One  Level One:
The solution of this problem consists of two parts. The first part is to implement the function, which returns the sum of all proper divisors of given integer N: public int getSum(int N) { int sum = 0; for (int i=1; i < N; i++) if (N % i ==0) sum += i; return sum; } The second part is to iterate through all integers from left to right, inclusive, and count the number of almost perfect by k among them: public int count(int left, int right, int k) { int cnt = 0; for (int i=left; i <= right; i++) if (Math.abs(getSum(i)  i) <= k) cnt++; return cnt; }EntertainingSegment Used as: Division One  Level Two:
There are many correct solutions to this problem. I'll describe the one that is not the most efficient, but is the easiest to understand and implement. Consider all start and finish points of radio stations ranges (let's call these points critical). Note that while we travel between two neighbouring critical points, we can always hear the same set of radio stations. Therefore, if some entertaining segment doesn't start in critical point, we can move its start to the nearest critical point from the left, and the segment will still be entertainig. The same holds for the finish point  it can be moved to the nearest critical point from the right. This argument proves that the optimal entertaining segment starts and finishes in some critical points, because otherwise we can always increase its length. The established property of optimal entertaining segment allows us to solve the problem in the following three steps:
Java implementation of this algorithm follows: public int longestEntertainingSegment(int[] left, int[] right, int k) { // part 1 SetBlockCounter Used as: Division One  Level Three:
To solve this problem, we will write a recursive function that takes a compressed word as its input, and returns the triple (first, last, count), where first is the first letter of the uncompressed form of the word, last is its last letter, and count is the amount of blocks in the uncompressed form of the word. The function will need to determine which rule among three possible was applied last to compress the word and to perform some actions depending on the chosen rule. 1st rule is applied if the word consists of exactly one character. This case is the most trivial. If the word is "A", then we return the triple ('A', 'A', 1), otherwise we return the triple ('B', 'B', 1). 2st rule is applied if the word can be represented as ST, where both words S and T are nonempty and contain equal amount of opening and closing brackets (possibly, zero). In this case we need to call the function recursively for words S and T to obtain triples (first(S), last(S), count(S)) and (first(T), last(T), count(T)). To calculate the resulting triple (first, last, count), let's note that:
3rd rule is applied if 1st and 2nd rules are not applicable. In this case the word has the form (X,S). The resulting triple is calculated as follows (the argumentation is similar to the argumentation for the 2nd rule):
The Java implementation of this algorithm is provided below: public class BlockCounter { class Triple { public char first, last; public long count; public Triple(char first, char last, long count) { this.first = first; this.last = last; this.count = count; } } public Triple rec(String word) { // case 1 if (word.length() == 1) return new Triple(word.charAt(0), word.charAt(0), 1); // case 2 int sum = 0; for (int i=0; i+1 < word.length(); i++) { if (word.charAt(i) == '(') sum++; if (word.charAt(i) == ')') sum; if (sum == 0) { Triple a = rec(word.substring(0, i+1)); Triple b = rec(word.substring(i+1)); return new Triple(a.first, b.last, a.count + b.count  (a.last == b.first ? 1 : 0)); } } // case 3 long X = word.charAt(1)  '0'; Triple a = rec(word.substring(3, word.length()  1)); return new Triple(a.first, a.last, X * a.count  (a.first == a.last ? X  1 : 0)); } public long countBlocks(String word) { return rec(word).count; } } 
