Match Editorial

In Division 1, only Petr (1st) and andrewzta (2nd) managed to solve all three problems. evgeni was the third of the three to solve the 1000 pointer; his 500 was taken down in the challenge phase, though this did not cost him 3rd place. Special recognition to Hardcoder in 4th, who submitted only the 250 point problem, but racked up 11 successful challenges without any unsuccessful.

Gluk made a very strong Division 2 showing, finishing all three problems in just over 30 minutes, and passing his nearest competitor .Invader by over 150 points. First-timers wlodzislaw and Gassa came in 3rd and 4th and will be taking on Division 1 next match.

The Problems

Value	250
Submission Rate	217 / 326 (66.56%)
Success Rate	171 / 217 (78.80%)
High Score	kudlatyPL for 241.01 points (5 mins 31 secs)
Average Score	162.20 (for 171 correct submissions)

Since we are looking for the sum of the differences, and since every student will receive at least as high a grade in the first scheme as in the second, we may sum the grades in the first scheme and subtract those in the second. The students' scores are given in ascending order, with higher desired grades breaking ties between identical scores and coming first. So to find grades given that the desired grade is a lower bound on the actual grade for students of a certain score or higher (the first scheme), we may iterate from the beginning to end, storing the highest seen desired grade:

int sum = 0;
int highest = 0;
for (int i = 0; i < scores.length; i++) {
    if (grades[i]>highest) highest = grades[i];
    sum += highest;
}

Value	500
Submission Rate	102 / 326 (31.29%)
Success Rate	31 / 102 (30.39%)
High Score	ravi_kiran for 456.46 points (8 mins 56 secs)
Average Score	306.77 (for 31 correct submissions)

Value	250
Submission Rate	258 / 286 (90.21%)
Success Rate	126 / 258 (48.84%)
High Score	sql_lall for 243.77 points (4 mins 33 secs)
Average Score	192.49 (for 126 correct submissions)

Each multiplier in a divisibility rule is dependent only on the last multiplier, the base, and the divisor, simply:

m[0] = 1
m[i] = (m[i-1] * base) % divisor

m[0] = 1;
for (int i = 1; i < 1000; i++) {
    m[i] = (m[0]*base)%divisor;
    if (used[i]!=0) return m;
    used[i] = 1;
}

Value	1000
Submission Rate	88 / 326 (26.99%)
Success Rate	20 / 88 (22.73%)
High Score	agray for 949.59 points (6 mins 36 secs)
Average Score	676.45 (for 20 correct submissions)

A greedy approach will not work for this problem, and 20 elements is too many to try all possible permutations. The key here is to recognize that if target[i] < target[j] and candidate[k] < candidate[m], you should never need to match target[j] with candidate[k] and target[i] with candidate[m]. In other words, both sets may be sorted first and then matched in order, with certain elements in candidate skipped. Consider both lists sorted, and try swapping any two elements; you'll should see that this is at least a locally optimal arrangement. A recursive solution is most straightforward. At each stage, either match the next element of candidate with the next element of target, or skip the next element of candidate, whichever yields the best solution. Once all of target and all of candidate is used, you're done.

int recur(int[] target, int[] candidate, int targetPos, int
candidatePos) {
    if (targetPos==target.length) return 0;
    if (candidatePos-targetPos==candidate.length) return 9999999;
    int diff = candidate[candidatePos]-target[targetPos];
    if (diff<0) diff = -diff;
    int withoutUsingBlank =
recur(target,candidate,candidatePos+1,targetPos)+diff;
    int usingBlank = best(target,candidate,candidatePos+1,targetPos+1);
    if (withoutUsingBlank < usingBlank) return without;
    else return usingBlank;
}

Value	500
Submission Rate	114 / 286 (39.86%)
Success Rate	46 / 114 (40.35%)
High Score	John Dethridge for 360.65 points (19 mins 17 secs)
Average Score	238.05 (for 46 correct submissions)

There were two main parts to this problem: parsing and checking for nearly correct answers. The parsing was straightforward, if somewhat long, as long as you made sure to catch certain not-so-obvious cases such as "1 2" (malformed) and "123." (not malformed). To avoid double imprecision problems, either use epsilons or keep all values in fraction form. Convert ".123" to a numerator, 123, and a denominator, 1000, for example. The second part was most easily solved by trying all possible inputs (there are only 13 allowed characters and only 13⁴ allowed strings). You should already have a way to tell if an answer is malformed and to extract its value if not, so it is a simple matter to generate every possible four character string, check to see if it is malformed, and if not extract its value. Sorting all of the values, we have a tool to determine whether some answer is the closest to one of the range bounds. Again, epsilons or fractions are very necessary to keep imprecision in check.

Value	1000
Submission Rate	8 / 286 (2.80%)
Success Rate	3 / 8 (37.50%)
High Score	Petr for 733.23 points (18 mins 37 secs)
Average Score	645.12 (for 3 correct submissions)

There were two methods used to solve this problem, only one of which runs in time. It should be fairly clear from the outset that this is a dynamic programming (or recursion with memoization) problem. The question is how to subdivide a problem into smaller ones. We will use a table of results for polygons of size N split into K different polygons: f(N,K). First of all, if K==1, there is always 1 way; if K is less than 1, there are 0 ways; if K is more than N-2, there are 0 ways; and if N is less than 3, there are 0 ways. Now for the recursive case: Consider a polygon of size N to be cut into K pieces. Choose one vertex. Either there will be a cut through that vertex or there will not be. Suppose there is not. Then either that vertex will be part of a triangle or it will not. If it will be part of a triangle, then there are f(N-1,K-1) ways to cut the remainder. If it won't, then we can envision that vertex 'collapsed' into a line joining the two adjacent vertices, and there are f(N-1,K) ways to cut the remainder. Now suppose the vertex will be cut. Then starting at one of the adjacent vertices and indexing (starting with 0) the other vertices in order around the polygon, for each way of cutting the polygon, there is some vertex with the smallest index i that is on the other end of a cut through our chosen vertex. After cutting, the polygon made of the larger vertices can be cut in f(N-i,m) ways with m the number of polygons it will be cut into. The polygon made of the smaller vertices needs to be constrained to make sure that the chosen vertex is never cut through. We've seen how to do that in the first case; since this new polygon will have i+1 vertices, it can be cut in f(i+1,K-m-1)+f(i+1,K-m) ways. In short, then, to compute f(N,K), we do the following:

f(N,K) += f(N-1,K-1);
f(N,K) += f(N-1,K);
for (int i = 1; i < N-1; i++) {
    for (int m = 1; m < K; m++) {
        f(N,K) += f(N-i,m)*(f(i+1,K-m-1) + f(i+1,K-m));
    }
}

By Enogipe
TopCoder Member