Wednesday, October 17, 2007 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 ProblemsFancyGUIUsed as: Division One  Level One:
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 kth window count ++; if (count > N) result ++; } return result; }TwoWords Used as: Division One  Level Two:
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:
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 nonoverlapping 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"; }MonkeyTreeDistance Used as: Division One  Level Three:
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:
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: 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].
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.

