Match summary

sluga won the match thank to an amazing 945.38 points on the hard problem. Two reds rounded out the first three: Zuza finished second, and tomekkulczynski ended up in third.

The relatively large number of participants led to real competition -- there were 104 coders and only 100 slots for advancement! Unfortunately, however, only 97 participants were able to earn a positive score and move on.

The Problems

LargestCountry

Used as: Division One - Level One:

Value 250

Submission Rate 102 / 104 (98.08%)

Success Rate 88 / 102 (86.27%)

High Score sluga for 249.24 points (1 mins 34 secs)

Average Score 235.76 (for 88 correct submissions)

The problem just requires you to count how many times each of the uppercase letters occurs in the given array of strings, then to choose the letter that occurs the most times. In case of a tie, choose the smallest letter.

C++ code follows:

string getLargest(vector <string> worldMap) {
    char ch;
    pair <int, char> ret;
    int cnt[256];
    int i, j;
    memset(cnt, 0, sizeof(cnt));
    for (i = 0; i < worldMap.size(); i++)
        for (j = 0; j < worldMap[i].size(); j++)
            if (worldMap[i][j] != ' ') cnt[worldMap[i][j]]++;
    ret = make_pair(0, 'A');
    for (ch = 'A'; ch <= 'Z'; ch++) ret = min(ret, make_pair(-cnt[ch], ch));
    return (string)"" + ret.second;
}

ChangingSeats

Used as: Division One - Level Two:

Value 500

Submission Rate 80 / 104 (76.92%)

Success Rate 74 / 80 (92.50%)

High Score tomekkulczynski for 495.12 points (2 mins 49 secs)

Average Score 397.19 (for 74 correct submissions)

This one can be solved by brute force due to the low constraints. Iterate over the seats and try to move all the people to seats around the current one.

C++ code follows:

int getDistance(string s) {
    int ret, cur, n, i, j, k;
    n = s.size();
    ret = 2000000000;
    for (i = 0; i < n; i++) {
        cur = 0;
        // going to the right from i, k stores the last empty position
        for (k = j = i; j < n; j++) if (s[j] == 'X') cur += j - k++;
        // going to the left from i, k stores the last empty position
        for (k = j = i - 1; j >= 0; j--) if (s[j] == 'X') cur += k-- - j;
        ret = min(ret, cur);
    }
    return ret;

Of course, brute force is not the only solution to this problem. Now, when the challenge is over and you have a bit more time, try to find a mathematical solution for this problem.

LatticeCrossword

Used as: Division One - Level Three:

Value 1000

Submission Rate 37 / 104 (35.58%)

Success Rate 32 / 37 (86.49%)

High Score sluga for 945.38 points (6 mins 54 secs)

Average Score 586.99 (for 32 correct submissions)

This problem was also solvable by a brute force approach because of the relatively low constraints. There are four possible relative positions of the words in the resulting crossword - top, bottom (both for horizontal words), left and right (both for vertical words), and there are 4! = 24 ways to assign a position to each word from the input.

Now we need to compute all thhe possible crosswords. This can be done by brute-forcing over all possible starting positions of all words (taking into account that the words have length of 15 and their starting positions can be more than 15 cells apart):

Java code follows:

int go(String[] data) {
    int ans = 0;
    for (int c = -15; c < 16; c++)
        for (int r = 2; r <= 15; r++) {
            int ri = Math.min(data[0].length(), data[1].length() + c);
            for (int i = Math.max(c, 0); i < ri; i++) {
                int cnt = count(data[0], data[1], data[2], r, c, i);
                for (int j = i + 2; j < ri; j++)
                    ans += cnt * count(data[0], data[1], data[3], r, c, j);
            }
        }
    return ans;
}

int count(String a, String b, String w, int r, int c, int c1) {
    int res = 0;
    for (int i = r - w.length() + 1; i <= 0; i++)
        if (w.charAt(-i) == a.charAt(c1) && w.charAt(r - i) == b.charAt(c1 - c))
            res++;
    return res;
}

By gevak
TopCoder Member