Saturday, June 18, 2005 Match summary
Division 1 had a pretty hard problem set, as a great number of coders received 0 points. At the end of the challenge phase, it looked like Yarin would come out on top, with an impressive time on the hard problem. However, his medium submission failed system tests and he ended up in fourth place. Veteran John Dethridge ended up taking the match, followed by jvpardon in second, and halyavin in third, competing in only his third SRM. The ProblemsTriangleTypeUsed as: Division Two  Level One:
First, you need to sort the three dimensions so that you can apply the formulas in the notes, using x, y and z where x ≤ y ≤ z. Once you do this, you pretty much just need to make sure that you spell the return values correctly. FracCountUsed as: Division Two  Level Two:
Since the numerator can not be more than 1000, the return is always relatively small. In fact, example 2 shows that the largest return is only about 300,000. As a result, it is easy to use brute force to generate all fractions in the list up to numerator/denominator. Simply use two nested loops to generate all numerators (the outer loop) and denominators (the inner loop) up to the fraction represented by the input. As you generate the fractions in the list, you need to check that the greatest common denominator of the numerator and denominator is 1. int cnt = 0; for(int i = 2; ; i++)for(int j = 1; j<i; j++){ if(gcd(i,j) == 1)cnt++; if(j==numerator && i == denominator)return cnt; }The gcd function can be written quite concisely as: int gcd(int a, int b){return b == 0 ? a : gcd(b , a%b);}Speller Used as: Division Two  Level Three:
This was rather easy as far as div 2 hard problems go. You simply need to generate all of the numbers from 1 to 100, as specified, and then see which one is closest to the input. To generate the numbers, you should have three arrays of strings for the ones, tens, and teens. Having the strings in order in arrays makes it easy to generate the correct string from a number by either looking them up directly or by combining the appropriate two strings. To check the distance between two strings, just compare each character one at a time. MusicalUsed as: Division One  Level One:
This problem tripped up a lot of coders. However, the last sentence of the problem provides the key to solving it. Since the child farthest from a chair is the loser, we simply need to calculate the distance from each child to the chair closest that child. To do this for a particular child, first compute the position of the child. We can say that child i starts 1i/n, where the distance around the circle is 1 (this makes then evenly spaced, and in the correct order). After time seconds, the child advances time/10 to position (1i/n+time/10) mod 1. Next, we compute the distance to the nearest chair from this position. A simple way to do this is to compute the distance to every chair, as there are at most 25 of them. Alternatively, you can compute that the nearest chair is at either floor(pos*(n1))/(n1) or ceil(pos*(n1))/(n1). A lot of coders made the mistake of sending the children in the wrong direction, with A following B instead of the other way around. WordTrainUsed as: Division One  Level Two:
The first step in this problem is to reverse some of the words so that the
front of the train car is the same as the front of the word. This can be done
by always using the lexicographically earlier of the input word and its
reverse, which has the added benefit of being the correct direction for the tie
breaking rules on the output. Once the words are all facing the proper
direction, you can sort them in a particular way that makes the problem quite
simple. Sort primarily be the first letter of each word. When ties occur, put
the words whose first and last characters are the same earlier. When ties still
remain, break them lexicographically. This order is the same as the order the
words will have in the output (meaning that the output words are a subsequence
of the words when sorted like this). for(int i = 0; i<cars.length; i++){ best[i] = cars[i]; for(int j = 0; j<i; j++){ if(cars[i].charAt(0) == cars[j].charAt(cars[j].length()1)){ best[i] = better(best[i],best[j]+""+cars[i]); } } ret = better(ret,best[i]); } return ret;Necklaces Used as: Division One  Level Three:
We can use brute force to find one of the segments, which we will denote
as the segment with the smallest sum. Starting with this segment, we can
use dynamic programming to minimize the sum of the largest segment,
subject to the constraint that all segments have sum at least as high as
the initial segment we found via brute force. The idea is to compute the
best way to use k gems to make j segments such that all
of the segments have a sum at least as large as the segment designated as
the lowest sum segment. For a particular smallest segment, we can call
this value dp[k][j]. public int inequity(int n, int[] gems){ int[] v = new int[gems.length+1]; int ret = Integer.MAX_VALUE; for(int x = 0; x<gems.length; x++){ int min = 0; //precompute the sum of gems[0..a] for each a for(int a = 1; a<v.length; a++)v[a] = v[a1] + gems[a1]; for(int y = 0; y<gems.length ;y++){ min+=gems[y]; //gems[0..y] forms the segment with smallest sum, min int[][] dp = new int[n+1][gems.length+1]; dp[1][y+1] = min; //dp[1][y+1] represents the best and only way //to arrange the first y gems in one segment //now loop over j  add segments for(int j = 2; j<=n; j++){ //loop over i  the number of gems used to make j segments for(int i = y+1; i<=gems.length; i++){ //loop over k  the number of gems used to make j1 segments for(int k = y+1; k<i; k++){ //first make sure that the gems from k+1 to i form a valid //segment and that it is possible to make j1 segments with k gems if(v[i]v[k] < min  dp[j1][k] == 0)continue; int t = Math.max(dp[j1][k],v[i]v[k]); //t holds a possible value for dp[j][i] if(dp[j][i] == 0  t < dp[j][i]){ dp[j][i] = t; } } } } //If it was possible to make n segments using this //initial segment, minimize the return value if(dp[n][gems.length]!=0){ ret = Math.min(ret,dp[n][gems.length]min); } } //rotate the gems array 1 position to keep things simple int t = gems[0]; for(int a = 0; a+1<gems.length; a++)gems[a] = gems[a+1]; gems[gems.length1] = t; } return ret; }An analogous solution treats the initial segment chosen via brute force as the largest segment, instead of the smallest. Both algorithms are about the same in terms of coding difficulty, and have the same runtime. If M is the number of gems, then there are O(M^{2}) ways to pick the initial segment. The three inner loops clearly has a runtime of O(M^{2}*N). Since all of the parameters are bounded by 50, this gives us an overall runtime around 50^{5}. This should make you somewhat leery, as it is around 300 million, and experienced TopCoders will tell you this is approaching the time limit. However, the innermost operations are pretty simple, and the worst case runtime is under half a second for the Java solution above. 
