Match Editorial

Match summary

Qualification 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 Problems

Value	250
Submission Rate	701 / 720 (97.36%)
Success Rate	598 / 701 (85.31%)
High Score	winy for 249.49 points (1 mins 17 secs)
Average Score	225.05 (for 598 correct submissions)

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

Value	500
Submission Rate	451 / 720 (62.64%)
Success Rate	290 / 451 (64.30%)
High Score	hyyylr for 480.06 points (5 mins 50 secs)
Average Score	339.95 (for 290 correct submissions)

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:

1. Construct the list of all critical points in increasing order: x[0] < x[1] < ... < x[K-1].
2. For each two neighboring critical points x[i] and x[i+1] calculate the amount c[i] of radio stations, which can be heard while travelling between these points. Note, that radio station j can be heard between points x[i] and x[i+1], if left[j] ≤ x[i] and x[i+1] ≤ right[j].
3. Iterate through all possible pairs (x[i], x[j]) of critical points. For each pair, check whether the segment between x[i] and x[j] is entertaining (it will be entertaining if each value c[i], c[i+1], ..., c[j-1] is greater or equal to k). Select the longest among entertaining segments and return its length.

Java implementation of this algorithm follows:

public int longestEntertainingSegment(int[] left, int[] right, int k) {
    // part 1
    Set xSet = new HashSet();
    for (int i=0; i < left.length; i++) {
        xSet.add(left[i]);
        xSet.add(right[i]);
    }
    int[] x = new int[xSet.size()];
    int K = 0;
    for (int xVal : xSet)
        x[K++] = xVal;
    Arrays.sort(x);
        
    // part 2
    int[] c = new int[K-1];
    for (int i=0; i < c.length; i++)
        for (int j=0; j < left.length; j++)
            if (left[j] <= x[i] && x[i+1] <= right[j])
                c[i]++;
                    
    // part 3
    int res = 0;
    for (int i=0; i < x.length; i++)
        for (int j=i+1; j < x.length; j++) {
            boolean ok = true;
            for (int t=i; t < j; t++)
                if (c[t] < k)
                    ok = false;
            if (ok)
                res = Math.max(res, x[j] - x[i]);
        }
            
    return res;
}

Value	1000
Submission Rate	181 / 720 (25.14%)
Success Rate	114 / 181 (62.98%)
High Score	GHY for 882.27 points (10 mins 40 secs)
Average Score	532.12 (for 114 correct submissions)

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 non-empty 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:

• First letter of the uncompressed form of the word is equal to the first letter of the uncompressed form of S, i.e. first = first(S).
• Last letter of the uncompressed form of the word is equal to the last letter of the uncompressed form of T, i.e. last = last(T).
• If the last(S) ≠ first(T), then all blocks in the uncompressed forms of S and T remain as blocks in the uncompressed form of concatenation ST, i.e. count = count(S) + count(T).
• If the last(S) = first(T), then the last block in the uncompressed form of S and the first block in the uncompressed form of T will be merged together in one block in the uncompressed form of contatenation ST, i.e. count = count(S) + count(T) - 1.

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

• first = first(S);
• last = last(S);
• count = X * count(S), if first(S) ≠ last(S);
• count = X * count(S) - X + 1, if first(S) = last(S).

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