Match Editorials

Match summary

The online round 2 of TCHS tournament 2008 was a bit more exciting than round 1, because non-zero score was not enough to advance this time. It turned out that even two solved problems did not guarantee advancement. So the coders needed to show their best to either have two fast problems, or have some challenges, or solve the hard. Fortunately, the problems were not very difficult with more than 50 coders solving all three problems correctly.

After the challenge phase neal_wu took the lead, thanks to solid time on all three problems, and +150 on challenges. Loner had a better score on each problem, but was not so successful during the challenge phase, so he came in second. And yuhch123 who already has an amazing 2800+ rating in Algorithm competition finally turned yellow in High School, coming third despite his 1000 resubmit, thanks to two successful challenges.

The Problems

Value	250
Submission Rate	168 / 178 (94.38%)
Success Rate	144 / 168 (85.71%)
High Score	Zuza for 249.50 points (1 mins 17 secs)
Average Score	229.43 (for 144 correct submissions)

Basically all we need for this problem is standard data structures. Most modern languages, including those available at TopCoder, have powerful libraries that can do most of the work.

The code in Java follows. It uses TreeSet to keep words that appear in query. It both removes duplicates, because it is Set, and sorts the words alphabetically, because it is OrderedSet. To quickly look up whether the word is common, it is convenient to store all words in another Set.

    public String[] preprocess(String query, String[] common) {
        StringTokenizer st = new StringTokenizer(query);
        Set<String> words = new TreeSet<String>();
        Set<String> commonWords = new HashSet<String>();
        commonWords.addAll(Arrays.asList(common));
        while (st.hasMoreTokens()) {
            String s = st.nextToken();
            if (!commonWords.contains(s)) {
                words.add(s);
            }
        }
        return words.toArray(new String[words.size()]);
    }

To learn the way to do similar things in C++ you can read C++ STL tutorial part 1 and part 2.

Value	500
Submission Rate	141 / 178 (79.21%)
Success Rate	109 / 141 (77.30%)
High Score	ahyangyi for 493.94 points (3 mins 9 secs)
Average Score	403.25 (for 109 correct submissions)

First let us note that the definition of the triangular sequence doesn't use the order on its elements. So if we reorder elements of a triangular sequence arbitrarily, we still get a triangular sequence.

Let the numbers x, y and z satisfy 0 < x ≤ y ≤ z. To check whether they satisfy the triangular inequality it is sufficient to check whether x + y > z. Indeed, y + z ≥ x + z > x, and x + z ≥ x + y > y, so the only non-trivial inequality is whether x + y > z.

Now let us have a criteria that the sequence b[0], b[1], ..., b[n-1] where b[0] ≤ b[1] ≤ ... ≤ b[n - 1], is triangular without checking all triples of indices. If n ≤ 2, the sequence is triangular for sure, so let n ≥ 3. It is necessary that b[0] + b[1] > b[n - 1]. It is also sufficient, indeed, since for any 0 ≤ i < j < k < n we have b[i] + b[j] ≥ b[0] + b[1] > b[n - 1] ≥ b[k]. Therefore, for n ≥ 3 the sequence b[0] ≤ b[1] ≤ ... ≤ b[n-1] is triangular if and only if b[0] + b[1] > b[n - 1]

Let us sort all elements of the given sequence, let a[0] ≤ a[1] ≤ ... ≤ a[n-1]. Consider the optimal triangular subsequence a[i₁], a[i₂], ..., a[i_m] where 0 ≤ i₁ < i₂ < ... < i_m < n. Note that the subsequence a[i_m-m+1], a[i_m-m+2], ..., a[i_m] is also triangular, because a[i_m-m+1]+a[i_m-m+2] ≥ a[i₁]+a[i₂] > a[i_m] and it has the same length. Thus we only have to consider contiguous subsequences of the sorted original sequence. The O(n²) solution is immediate - check all i and j such that 0 ≤ i < n and i + 2 ≤ j < n, and for each pair check whether a[i] + a[i+1] > a[j]. Among those subsequences that satisfy the inequality choose the longest one. The code follows.

    public int longest(int[] a) {
        Arrays.sort(a);
        int n = a.length;
        int r = Math.min(a.length, 2);
        for (int i = 0; i < n; i++) {
            for (int j = i + 2; j < n; j++) {
                if (a[i] + a[i + 1] > a[j]) {
                    if (j - i + 1 > r) {
                        r = j - i + 1;
                    }
                }
            }
        }
        return r;
    }

Though O(n²) is more than sufficient for the given constraints, there exists a faster algorithm. Let us give its sketch, leaving details to the reader. For each i from 0 to n - 1 let us find right(i) - maximal possible j such that a[i], ..., a[j] is triangular. It is clear that right(i + 1) ≥ right(i), so if we know right(i) we only need to consider j from right(i) to n - 1, and if a[i], ..., a[j] is not triangular, neither is a[i], ..., a[j + k] for any k > 0, so we can stop searching as soon as we find j such that a[i], ..., a[j] is not triangular. So if we maintain two indices i and j, such that a[i], ..., a[j] is the longest contiguous triangular subsequence starting at a[i], we only need to increase i and j. Therefore it can be implemented in O(n). Combined with O(n log n) for sorting, it gives O(n log n) algorithm for the problem.

Value	1000
Submission Rate	68 / 178 (38.20%)
Success Rate	59 / 68 (86.76%)
High Score	sluga for 989.45 points (2 mins 56 secs)
Average Score	671.55 (for 59 correct submissions)

This problem has a lot of solutions of various asymptotic time. We will consider some of them, from worse to better.

First let us try to use the fact that we have n, k ≤ 20, so we can run subset dynamic programming. Let us call the way to assign numbers from 1 to n to some of the k positions a partial arrangement. Let i run from 0 to k, and m from 0 to 2ⁿ-1. Denote as a[i][m] the number of partial unfixed arrangements that have numbers assigned to positions from 1 to i, inclusive, where m is the mask of the used numbers: the j-th bit of m is set to 1 if j is used in the arrangement. Clearly, a[0][0] = 1, and a[0][m] = 0 for m ≠ 0.

To learn a[i][m] we run through all j such that the j-th bit is set in m, and if j ≠ i we add a[i-1][m xor (1 << (j-1))] to a[i][m] (here x xor y means bitwise exclusive or of x and y). The answer to the original problem is the sum of a[k][m] for all m.

This solution runs in O(nk2ⁿ) which may a bit too slow for the given constraints. Some coders used the fact that the number of possible inputs is small, and precalculated all answers. But actually there are ways to speed up the algorithm to make it run in time.

For example, we may note that the first index i is not needed - given m we can learn how many positions are already assigned in the partial arrangement counting the bits in m. This gives us O(n2ⁿ) solution which already passes system tests. But we can do better. Let us now switch to solutions that are polynomial in n and k.

Consider all arrangements of k from n (not necessarily unfixed). This number is n(n - 1)(n - 2)...(n - k + 1). Denote this numbers as a[n][k]. Some of them have fixed point, so they need not be counted. The number of arrangements that have fixed point at 1 (1 is put to slot 1) is a[n - 1][k - 1] since we must arrange n - 1 number left to k - 1 slots left. So is the number of arrangements that have fixed point 2, ..., fixed point k. So we must subtract k * a[n - 1][k - 1] from a[n][k].

But we have subtracted some arrangements more than once - those that have two or more fixed points. There are a[n-2][k-2] arrangements that have fixed points at both 1 and 2, the same number of arrangements have fixed points at both 1 and 3, etc. The number of ways to choose 2 positions from k is called choose 2 from k and is equal to the corresponding binomial coefficient. Let us denote it as c[k][2], so we must add back c[k][2] * a[n - 2][k - 2]. But we have now added some arrangements more than once, those that have at least 3 fixed points...

The generalization of such reasoning is inclusion-exclusion principle. Using it, we have the answer be equal to sum for t from 0 to k of (-1)^t * c[k][t] * a[n - t][k - t].

This solution can be implemented in O(nk) using Pascal triangle to calculate c[n][k], or even in O(k) if we note the formulas c[k][t + 1] = c[k][t] * (k - t) / (t + 1) and a[n - t - 1][k - t - 1] = a[n - t][k - t] / (n - t), so we have a way to get the next term from the previous one in O(1).