Match Editorial

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

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

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)

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];

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)

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.

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.