JOIN
 Match Editorial
SRM 357
Thursday, July 12, 2007

## Match summary

ACRush easily cruised through the field to victory. TopCoder and web-casting veteran John Dethridge came second with a 100+ gap, and yiuyuho rounded out the top three, finishing almost 300 points behind John. Ukrainian fellows roma and Vedensky had a close race for the fourth place, with roma being a bit faster.

In Division 2, ush and Cristiano had significantly more points than all other competitors, followed by shadowdancer851 in third place.

# The Problems

MnemonicMemory
Used as: Division Two - Level One:
 Value 250 Submission Rate 480 / 532 (90.23%) Success Rate 443 / 480 (92.29%) High Score einstein41389 for 246.52 points (3 mins 23 secs) Average Score 189.00 (for 443 correct submissions)

As often happens with Division 2 easy problems, an accurate implementation is all you need to solve this problem. Let's do this step by step. First, words of the same length must be used in lexicographical order. This can be achieved by sorting the dictionary at the very beginning and using words of the same length in the order they'll appear in dictionary after sorting. Second, you can not use each element of dictionary more than once. To assure this, we'll keep an array of booleans, where the i-th element will be true if and only if the i-th element of dictionary was already used in our mnemonic representation. When you have done these two points, the rest is trivial:

```Arrays.sort(dictionary);
boolean[] used = new boolean[dictionary.length];
for (int i = 0; i < number.length(); i++) {
int dig = number.charAt(i) - '0';
for (int j = 0; j < dictionary.length; j++)
if (!used[j] && dictionary[j].length() == dig) {
// here we add an extra leading space before the very first word, we'll take care of it later
ans += (" " + dictionary[j]);
used[j] = true;
break;
}
}
return ans.trim(); // to throw out the extra leading space
```

Hotel
Used as: Division Two - Level Two:
 Value 500 Submission Rate 250 / 532 (46.99%) Success Rate 83 / 250 (33.20%) High Score neha_gedela for 471.72 points (7 mins 2 secs) Average Score 332.36 (for 83 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 437 / 454 (96.26%) Success Rate 330 / 437 (75.51%) High Score sluga for 247.36 points (2 mins 56 secs) Average Score 212.48 (for 330 correct submissions)

This one is a classical DP problem. The state of DP is the number of customers you need to attract. If the number of customers C is non-positive, you can get them with a cost of 0. If the number of customers C is positive and you have already found the optimal costs for all smaller numbers, the solution is simple: check all cities from the input and try to attract customers[i] for the cost of cost[i]. Since you already know the cost of attracting (C - customers[i]) customers, you can find the optimal answer for C as the minimum of all (bestCost(C - customers[i]) + cost[i]). As an implementation detail, we can shift all numbers in bestCost array by 100, to avoid going out of bounds:

```
int[] bestCost = new int[minCustomers + 101];
for (int i = 1; i <= minCustomers; i++) {
bestCost[i + 100] = 100000000;
for (int j = 0; j < cost.length; j++)
bestCost[i + 100] = Math.min(bestCost[i + 100], bestCost[i + 100 - customers[j]] + cost[j]);
}
return bestCost[minCustomers + 100];
```

WebsiteRank
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 42 / 532 (7.89%) Success Rate 3 / 42 (7.14%) High Score Cristiano for 596.08 points (27 mins 42 secs) Average Score 500.14 (for 3 correct submissions)
Used as: Division One - Level Two:
 Value 500 Submission Rate 335 / 454 (73.79%) Success Rate 75 / 335 (22.39%) High Score ACRush for 453.24 points (9 mins 19 secs) Average Score 256.32 (for 75 correct submissions)

The main part of this problem is to find for each link from site A to site B whether we should count votes for site A towards site B or we should discard this link. To solve this question, we build the graph of the network, which has an edge from vertex A to vertex B if and only if site A directly links to site B. Then we build the transitive closure of this graph and start checking all edges of the initial graph one by one. An edge A->B of the graph should be discarded if the transitive closure of the graph has an edge from B to A. As the result we will receive an acyclic graph.

Having that done, the problem becomes quite easy. We start calculating votes for each of the sites, starting from the sites which do not have any incoming links. For each such site, we a) add its number of votes to each of the sites it links to, and b) destroy all edges outgoing from it. We are done when we compute the number of votes for all websites (or, at least, for the website we are interested in).

I must note that the simplest implementation of transitive closure algorithm (Floyd-Warshall) may time out on big cases. Therefore, you need to either use Dijkstra or an optimized FW implementation. See ACRush's code for a clean (and the fastest) solution for this problem.

ChipArea
Used as: Division One - Level Three:
 Value 1100 Submission Rate 16 / 454 (3.52%) Success Rate 8 / 16 (50.00%) High Score ACRush for 809.91 points (18 mins 26 secs) Average Score 664.53 (for 8 correct submissions)

We are asked to find the area of the largest empty rectangle. This rectangle can't be enlarged, so it must have on its edges points from the input or edges of the wafer. Let's assume the rectangle we search for has a point on its left edge. If we have a fixed point and we want to find the largest empty rectangle with this point (x0, y0) on its left side, then we can go through the points to its right in x sorted order and update two variables: top and bottom. Let's say we've reached point (x1, y1), now the rectangle with the left upper corner (x0, top) and with the right lower corner (x1, bottom) is the largest rectangle that starts from x0, ends at x1, and doesn't contain any point. It is possible for a point to the right of (x0, y0) to have the same y0 so we have to be careful for this case, although the successful solutions don't seem to take care of it. We have now a simple O(n) algorithm that finds the largest empty rectangle if we know a point on its left side. We can end the search when it's clear that the next areas are smaller than the largest area we found so far; this pruning helps a lot because of the distribution of points in the problem. Now we can solve the problem in O(n^2) time. This complexity seems big for when n is about 25000 but the accepted solutions all used this idea.

ivan_metelsky, who tested the problem, has a solution which works in O(n log^2 n): If we want to find the largest rectangle that contains point (x, y) and doesn't contain any point in the input then if we have the points (x', y') and (x", y") in the input, where x < x' < x" and y < y' < y", then we don't care about point (x", y"). This holds for the other quadrants as well. If we have n points sorted by their y coordinate, then we can find the points we do care about in O(n). If the points are randomly distributed, then the number of points we care about is O(log n). After we found the interesting points we can use the previous idea to find the largest rectangle that contains point (x, y) in O(log^2 n).

Knowing this we can solve the problem using divide and conquer: first we divide space and points with a vertical line in two equal rectangles and recursively find the largest empty rectangles in each of the two rectangles, then we want to find the largest rectangle some part containing the separating line. The second step can also be solved with divide and conquer, by splitting horizontally the line in two then solving those problems, and finally find the largest empty rectangle that contains the point of intersection of the vertical and horizontal lines. This solution is O(n log^2 n) but the randomness of the input is important.

By Cosmin.ro
TopCoder Member