Match Editorials

Match summary

With 102 registrants, 13 of them were newcomers, the TopCoder High School Single Round Match 42 started, and 91 contestants competed. The contestants were confronted with a straightforward easy problem. The code was so simple and readable that all buggy solutions but one were successfully challenged. The medium problem was implementation tricky. The medium and hard problems presented an entertaining challenge phase, then the system test came after all to reorder the division summary.

The first two problems in addition to 100 point challenges, put mosrecki in the third place. The hard problem was somehow counter-intuitive, and only two submissions passed the system test. The first place went to Zuza, thanks to his fastest hard problem submission (besides the other two successful ones and six successful challenges). Followed by henryy in the second place having solved all three problems successfully.

The Problems

Value	250
Submission Rate	84 / 91 (92.31%)
Success Rate	74 / 84 (88.10%)
High Score	Zuza for 248.95 points (1 mins 50 secs)
Average Score	213.87 (for 74 correct submissions)

The problem proved to be pretty straight forward. It required a careful implementation. The problem asked to return the number of pixels, above which lie more than N windows. So, one implementation goes by passing over all pixels, counting the number of windows above it, and if the number exceeds N, increasing the return value by one (as one pixel was found meeting the required condition). The small limits of the problem made of the time limit no issue. As a notice, most of the failing submissions resulted from looping from (0, 0) to (99, 99) instead of (1, 1) to (100, 100). Here goes a sample Java solution:

public int totalDarkArea(int N, int[] x1, int[] y1, int[] x2, int[] y2)
{

    int result = 0;
    for (int x = 1 ; x <= 100 ; ++x)

        for (int y = 1 ; y <= 100 ; ++y)
        {

            int count = 0;
            for (int k = 0 ; k < x1.length ; ++k)

                if (x >= x1[k] && x <= x2[k] && y >= y1[k] && y <= y2[k])

                    // The pixel (x, y) lies beneath the k-th window
                    count ++;
            if (count > N)

                result ++;
        }
    return result;
}

Value	500
Submission Rate	71 / 91 (78.02%)
Success Rate	31 / 71 (43.66%)
High Score	ahyangyi for 483.87 points (5 mins 13 secs)
Average Score	363.47 (for 31 correct submissions)

Having 71 submissions, 11 submissions were successfully challenged, and 31 submbissions failed the system result. Most of the failing solutions were due to buggy implementations. However, there is a safe and clear way to break the problem down correctly. The problem asked if the two strings word1 and word2, which have wildcard characters ('?'), can be found in statement without overlapping. Finding only one word in the base string is easy, just check if that word is a substring of the base string (considering the wildcards). Then, how to find two words? The string statement can be split into two strings in N+1 ways (where N is its length). For all splits, try to find word1 in the first part, and word2 in the second part. Try also to find word2 in the first part, and word1 in the second part. Following is the C++ coded solution:
Note that the C++ substr function arguments are the beginning position and the substring length (not the ending position).

bool match (string a, string b)
{

    // match (a, b) is true only if a = b, considering the wildcards
    for (int i = 0 ; i < a.size() ; i++)

        if (a[i] != '?' && b[i] != '?' && a[i] != b[i])

            return false;
    return true;
}

int find (string phrase, string word)
{

    // find (phrase, word) returns 1 if the word was found in the phrase
    if (word.size() > phrase.size()) return 0;      // can not be found

    for (int i = 0 ; i <= phrase.size() - word.size() ; i++)

        if (match (phrase.substr (i, word.size()), word)) return 1;

    return 0;
}

string howMany (string statement, string word1, string word2)
{

    int result = 0;
    // result is the maximum number of words found non-overlapping
    
    for (int split = 0 ; split <= statement.size() ; split++)

        result = max (result, find (statement.substr(0, split), word1)
                            + find (statement.substr(split), word2));

    
    for (int split = 0 ; split <= statement.size() ; split++)

        result = max (result, find (statement.substr(0, split), word2)
                            + find (statement.substr(split), word1));

    
    if (result == 2) return "both";
    if (result == 1) return "one";

    return "none";
}

Value	1000
Submission Rate	34 / 91 (37.36%)
Success Rate	2 / 34 (5.88%)
High Score	Zuza for 837.50 points (13 mins 2 secs)
Average Score	685.93 (for 2 correct submissions)

Although it has a low success rate, this problem has many correct approaches. I will mention two correct approaches, neither one of them was used in the passing solutions.

First approach:
Binary search on the return result works fine for this problem. Assume the answer for the problem is that the minimal maximum distance between all pairs of monkeys is u. That means for all d > u, there exists at least one line y = N, where the maximum distance between all pairs for monkeys is less than d. Also, for all d < u, one can not achieve more than the optimal answer, and thus there exists no such line. So, the approach is to binary search on the answer d. That transforms the given problem into this problem:
For the given monkeys, and an assumed distance d, is there a line y = N, where the maximum distance between all pairs of monkeys is less than d? In the sample solution given, this transformed problem is solved by the function can. Noticing that the distance between a pair of monkeys i and j is either constant and independent of N if they were in the same tree, or if the line is in between the two monkeys, this distance is used in the solution as dx + dy. Otherwise, the distance increases by 2 over dx + dy for each unit of distance to the nearest monkey. That means, for each pair of monkeys and a distance d, we can limit an interval [a, b] for which any line y = N, a <= N <= b, the distance between the pair is less than d. Intersecting the intervals for all pairs of monkeys gives the answer for the function can, which is true, if and only if the intersection interval is non-empty. Follows a C++ sample solution:

bool can (long long d, vector <long long> x, vector <long long> y)
{

    // The intersection interval:
    long long down = -10000000000LL, up = 10000000000LL;

    
    // Intersect the intervals for all pairs of monkeys
    for (int i = 0 ; i < x.size() ; i++)

        for (int j = 0 ; j < i ; j++)
        {

            long long dx = abs (x[i] - x[j]);

            long long dy = abs (y[i] - y[j]);

            if (dx == 0) // same tree
            {
                if (dy >= d) return false;
            }

            else
            {
                if (d < dx + dy + 1)

                    return false;
                long long w = d - dx - dy - 1;

                down = max (down, min(y[i], y[j]) - w / 2);

                up = min (up, max(y[i], y[j]) + w / 2);
            }
        }

    return down <= up;
}

string minimalMaximumDistance (vector <int> xd, vector <int> yd)
{

    int N = xd.size ();
    vector <long long> x (N), y (N);

    
    for (int i = 0 ; i < N ; i++)
    {

        x[i] = xd[i];
        y[i] = yd[i];
    }

    
    long long low = 0, high = 10000000000LL;

    
    while (high - low > 1)
    {
        cout << high << " " << low << endl;

        long long mid = (low + high) / 2;
        if (can (mid, x, y))

            high = mid;
        else
            low = mid;
    }

    
    stringstream ss;
    ss << low;
    return ss.str();
}

Second approach:
The second approach requires solving a major part of the problem algebraically on paper. At most 50 monkeys are located in the world. So, there is at most 50 unique values of the y-coordinate. That breaks down the problem into this simpler form:
Between y = a and y = b (inclusive), no monkeys are located except for the boundaries. Calculate the line on the form y = N, a <= N <= b, where it makes the largest distance as small as possible. This is what the function "distance" does in the following solution:

In each interval, all pairs of monkeys can be divided into 3 categories:
1) the pair of monkeys where both are in different directions from any line y = N, or they are both situated in the same tree.
2) the pair of monkeys where both are above any line y = N
3) the pair of monkeys where both are below any line y = N

So for a pair of monkeys i, j:
Case 1: the distance is constant and doesn't depend on the line position. The maximum is not dependant on the location of the vertical line, and as we seek its maximum, the maximum value is stored in maxconst.
Case 2: the two monkeys are both above: That means the distance function = (y[i] - N + y[j] - N + abs (x[i] - x[j])), for a line y = N. We also want to get the maximum of this value, so we store maxup = y[i] + y[j] + abs(x[i] - x[j]). Now, the maximum distance for all such pairs equals: maxup - 2N
Case 3: the two monkeys are both below: similarly storing maxdown = - y[i] - y[j] + abs(x[i] - x[j]). Therefore, the maximum distance for all such pairs equals: maxdown + 2N

Now, for N, such that a <= N <= b, find N that minimizes the value: "max (maxconst, maxup - 2N, maxdown + 2N)". maxconst can be eliminated from the search process and handled later as it is independent of N. So:

max (maxup - 2N, maxdown + 2N) =  maxup - 2N      if maxup - 2N >= maxdown + 2N
                                  maxdown + 2N    if maxdown + 2N > maxup - 2N
Reduces to:
max (maxup - 2N, maxdown + 2N) =  maxup - 2N      if maxup - maxdown >= 4N
                                  maxdown + 2N    if maxup - maxdown < 4N
Reduces to:
max (maxup - 2N, maxdown + 2N) =  maxup - 2N      if N <= (maxup - maxdown) / 4
                                  maxdown + 2N    if N > (maxup - maxdown) / 4

Here appears the value critical = (maxup - maxdown) / 4. The rest is that trying the following lines as the optimal lines: y = critical, y = critical + 1, y = critical - 1, y = a or y = b. Only if critical, critical + 1, or critical - 1 lie in the interval [a, b].
For other values farther than [critical - 1, critical + 1], the maximum grows over the minimal value. as maxup - 2N will increase if N decreased, or maxdown + 2N will increase if N increased. Therefore, they should be greedily eliminated from the search.
The algorithm runs three nested loops over all of the monkeys and it is O (n^3), which makes it under the time limit.
Follows a sample implementation in C++, where the function maximum gets the value of the maximum distance for all pairs of monkeys given maxdown, maxup and maxconst, and a suspected line y = N.

const long long BIG = 1000000000000000LL;

long long maximum (long long maxu, long long maxd, long long maxc, long long N)
{

    return max(maxc, max(maxu - N - N, maxd + N + N));
}

long long distance (vector <long long> x, vector <long long> y

                            , long long a, long long b)
{
    // a < b AND no monkeys between y = a, y = b

    long long ans = BIG;
    long long maxup = -BIG, maxdown = -BIG, maxconst = 0;

    for (int i = 0 ; i < x.size() ; i++)

        for (int j = 0 ; j < x.size() ; j++)
        {

            if (x[i] == x[j])
                maxconst = max (maxconst, abs(y[i] - y[j]));

            else if (y[i] <= a && b <= y[j])

                maxconst = max (maxconst, y[j] - y[i] + abs(x[i] - x[j]));

            else if (y[j] <= a && b <= y[i])

                maxconst = max (maxconst, y[i] - y[j] + abs(x[i] - x[j]));

            else if (y[i] >= b && y[j] >= b)

                maxup = max (maxup, y[i] + y[j] + abs(x[i] - x[j]));

            else if (y[i] <= a && y[j] <= a)

                maxdown = max (maxdown, - y[i] - y[j] + abs(x[i] - x[j]));
        }

    
    // Handling of some special cases:
    // No maxup, use a (the lower limit):
    if (maxup == -BIG)
        return max (a + a + maxdown, maxconst);

    // No maxdown, use b (the upper limit):
    if (maxdown == -BIG)
        return max (- b - b + maxup, maxconst);

    
    long long critical = (maxup - maxdown) / 4;
    if (a <= critical && critical <= b)

        ans = min(ans, maximum (maxup, maxdown, maxconst, critical));

    
    if (a <= critical + 1 && critical + 1 <= b)

        ans = min(ans, maximum (maxup, maxdown, maxconst, critical + 1));

    
    if (a <= critical - 1 && critical - 1 <= b)

        ans = min(ans, maximum (maxup, maxdown, maxconst, critical - 1));

    
    ans = min(ans, maximum(maxup, maxdown, maxconst, a));

    ans = min(ans, maximum(maxup, maxdown, maxconst, b));

    return ans;
}

string minimalMaximumDistance (vector <int> xd, vector <int> yd)
{

    int N = xd.size ();
    vector <long long> x (N), y (N);

    
    for (int i = 0 ; i < N ; i++)
    {

        x[i] = xd[i];
        y[i] = yd[i];
    }

    
    set <long long> y_pos (y.begin(), y.end());    // Include all y values

    y_pos.insert (-BIG/10);
    y_pos.insert (BIG/10);

    
    vector <long long> ys (y_pos.begin(), y_pos.end());

    
    long long ans = BIG;
    for (int i = 0 ; i < ys.size() - 1 ; i++)

        ans = min(ans, distance(x, y, ys[i], ys[i+1]));

    
    stringstream ss;
    ss << ans;
    return ss.str();
}

For a third working approach, that uses ternary search, refer to henryy's solution. This solution essentially assumed that the maximum distance for all pairs of monkeys according to the ground y = N, as a function of N, to have only one minimum point (or multiple successive points). This assumption could be either proved by an extension to the second approach. Or one have to believe in his intuition and goes for coding it.