JOIN
 Match Editorial
SRM 247
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.

Division 2 had a much easier set with high success rates. As in division 1, a TopCoder veteran, kmd-10 took first place. He was followed by first time competitor {dano} in second and galkovsk in third.

# The Problems

TriangleType
Used as: Division Two - Level One:
 Value 250 Submission Rate 288 / 299 (96.32%) Success Rate 224 / 288 (77.78%) High Score jambon_vn for 246.17 points (3 mins 33 secs) Average Score 207.73 (for 224 correct submissions)

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.

FracCount
Used as: Division Two - Level Two:
 Value 500 Submission Rate 219 / 299 (73.24%) Success Rate 174 / 219 (79.45%) High Score Jsub for 483.18 points (5 mins 20 secs) Average Score 343.17 (for 174 correct submissions)

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:
 Value 1000 Submission Rate 111 / 299 (37.12%) Success Rate 72 / 111 (64.86%) High Score kmd-10 for 862.70 points (11 mins 43 secs) Average Score 576.07 (for 72 correct submissions)

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.

Musical
Used as: Division One - Level One:
 Value 300 Submission Rate 198 / 237 (83.54%) Success Rate 153 / 198 (77.27%) High Score John Dethridge for 278.86 points (7 mins 56 secs) Average Score 178.56 (for 153 correct submissions)

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 1-i/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 (1-i/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*(n-1))/(n-1) or ceil(pos*(n-1))/(n-1). 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.

WordTrain
Used as: Division One - Level Two:
 Value 500 Submission Rate 75 / 237 (31.65%) Success Rate 21 / 75 (28.00%) High Score ardiankp for 384.84 points (16 mins 37 secs) Average Score 298.20 (for 21 correct submissions)

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).

Next, we can use dynamic programming to compute the output. For each word, find the longest sequence that ends at that word by looking back at all of the previously computed sequences:

```    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:
 Value 1000 Submission Rate 26 / 237 (10.97%) Success Rate 17 / 26 (65.38%) High Score Yarin for 772.90 points (16 mins 26 secs) Average Score 577.90 (for 17 correct submissions)

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

If we know dp[k][j], then we can consider making a segment out of the gems from k+1 to i. If the sum of those gems is not as high as the value of the segment designated as the lowest sum segment, then those gems do not form a valid segment. Otherwise, we know that one possible value for dp[i][j+1] is max(dp[k][j],sumOfGems(k+1..i)). In other words, we have added on segment, making j+1 total, the last one of whose sum is sumOfGems(k+1..i). Since we already know the best way to arrange the first j segments, the value of the largest segment must either be the value of the largest from those j, or else the value of the new segment.

```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[a-1] + gems[a-1];
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 j-1 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 j-1 segments with k gems
if(v[i]-v[k] < min || dp[j-1][k] == 0)continue;
int t = Math.max(dp[j-1][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.length-1] = 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(M2) ways to pick the initial segment. The three inner loops clearly has a runtime of O(M2*N). Since all of the parameters are bounded by 50, this gives us an overall runtime around 505. 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.

By lbackstrom
TopCoder Member