Tuesday, September 22, 2005 Match summary
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.
The ProblemsGradingSystemUsed as: Division Two  Level One:
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; }To use the second grading scheme, we do the same thing except backwards: iterate from the end to the beginning, storing the lowest seen desired grade. DivisibilityRules Used as: Division Two  Level Two: Used as: Division One  Level One:
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[i1] * base) % divisorA good way to detect cycles in this case is to set up an array of used digits and mark each digit as you use it. Be careful about your stopping criteria. The most common error in this problem was to store only (1,3) for the rule (1,3,1,3,1,3...). This is a problem because then (1,3,3,3,3...) will be stored as (1,3) also, and result in an incorrect match. 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; }Once you've calculated the divisibility rule for the given base and divisor, you can move on to calculate the rule for every other digit in that base and compare them. It turns out that to compare rules, you need only calculate the first 50 or so multipliers, and in fact could calculate and compare rules simultaneously to shortcircuit, though those optimizations were not necessary. SetMetric Used as: Division Two  Level Three:
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 (candidatePostargetPos==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; }GradingGridIns Used as: Division One  Level Two:
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 notsoobvious 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^{4} 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. PolygonDecompositionUsed as: Division One  Level Three:
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 N2, 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(N1,K1) 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(N1,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(Ni,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,Km1)+f(i+1,Km) ways. In short, then, to compute f(N,K), we do the following: f(N,K) += f(N1,K1); f(N,K) += f(N1,K); for (int i = 1; i < N1; i++) { for (int m = 1; m < K; m++) { f(N,K) += f(Ni,m)*(f(i+1,Km1) + f(i+1,Km)); } }Everything must be taken modulo 1000000000, of course.
By Enogipe 
