Get Time
high_school  Match Editorials
Monday, July 31, 2006

Match summary

Submission rates were pretty high - more than 90% of the contestants submitted the first two problems and more than a half of them submitted the hard. Most of hards were down after the first couple of minutes of the challenge phase, giving some points to strong challengers. After the system tests, Zuza took home his second HS SRM win with tomekkulczynski and RuslanSM rounding out the top three.

The Problems

ExcitingGame rate it discuss it
Used as: Division One - Level One:
Value 250
Submission Rate 81 / 83 (97.59%)
Success Rate 74 / 81 (91.36%)
High Score Zuza for 249.19 points (1 mins 37 secs)
Average Score 230.43 (for 74 correct submissions)

Solution to this problem is just a simple simulation. Make sure you start counting from 1 (not from zero) and that you switch to classmate 0 after classmate with number (nClassmates - 1).

        public int howMany(int nClassmates, int nTimes, int who) {
        int ans = 0;
        for (int i = 0; i 

SimpleCompressor rate it discuss it
Used as: Division One - Level Two:
Value 500
Submission Rate 75 / 83 (90.36%)
Success Rate 53 / 75 (70.67%)
High Score Burunduk3 for 487.08 points (4 mins 39 secs)
Average Score 367.97 (for 53 correct submissions)

In this problem coders were asked to show their ability to use recursion. If we want to uncompress a string s, the basic cases are the following ones:

  • s is empty. In this case return will be just an empty string.
  • s starts with a letter (like "Atail"). In this case we can uncompress the first letter and the tail of s independently. The uncompression of a letter is just the same letter, and to uncompress the tail of s we recursively call method uncompress(s.substring(1)). To get the final return value, we append the result of the recursive call to the first character.
  • If s starts with an opening bracket, we need to find the corresponding closing bracket. We iterate through the characters of s counting opening and closing brackets, and stop when the number of the closing brackets is equal to the number of opening brackets. Now we process the string inside the brackets in the way it described in the statement and append the uncompressed tail of string s.
  • Java implementation of this approach follows:
            public String uncompress(String s) {
            // Empty string
            if (s.length() == 0) return "";
            char c = s.charAt(0);
            // s starts with a letter
            if (Character.isLetter(c))
            return c + uncompress(s.substring(1));
            // We are looking for the correspondent bracket.
            int cnt = 1;
            int i = 0;
            do {
            if (s.charAt(i) == '[') cnt++;
            if (s.charAt(i) == ']') cnt--;
            } while (cnt > 0);
            String ans = "";
            String temp = uncompress(s.substring(2, i));
            for (int j = 0; j <(s.charAt(1) - '0'); j++) ans += temp;
            return ans + uncompress(s.substring(i + 1));

    ProductsMatrix rate it discuss it
    Used as: Division One - Level Three:
    Value 1000
    Submission Rate 47 / 83 (56.63%)
    Success Rate 10 / 47 (21.28%)
    High Score Zuza for 940.39 points (7 mins 14 secs)
    Average Score 710.41 (for 10 correct submissions)

    A lot of coders tried to brute force this problem by generating all elements of matrix A, writing them into a big array and sorting it. Unfortunately, the resulting array can contain up to 100000*100000 elements, which is way too many numbers to even try to generate them all.

    The problem asks us to find the number at the k-th position in the array. Lets look at the inverted problem - given a number, find its position in the array (or, if array doesn't contain this number, find the position where it would be inserted to keep array sorted). If we can solve this inverted problem, we can use binary search to solve our main problem (if you are not familiar with binary search, you can read our tutorial). To find the position of a number X in the final array, we need to find how many elements of the array are not greater than X. This number is the same as the number of elements of matrix A which are not greater than X.

    The easiest way to find this number is to iterate through all rows of matrix A. Really, row i of matrix A contains n elements - i, 2*i, 3*i, ..., n*i. If X is greater or equal than n*i, then row i contains n elements not greater than X. If X is smaller than n*i, then row i contains (X / i) elements which are not greater than X (proving this fact is left to the reader). To find the total number of such elements in matrix A, we iterate through all rows of the matrix and sum up the numbers for each row. If you are able to find this number, the binary search implementation becomes really short. For a clean C++ implementation of this approach, see Zuza's solution.

    By Olexiy
    TopCoder Member