
Match Editorial 
SRM 139Tuesday, March 18, 2003
Match summary
This SRM featured a set of unique problems that gave many coders a hard time. The division
1 medium, a numerical analysis problem, had a few tricks that caught many competitors.
The division 1 hard asked coders to embed a path on the surface of a rectangular solid.
At first glance, the problem seems trivial, but rectangular solids aren't as simple as they look.
As a result, few coders solved all of the problems correctly. Once the challenge phase was over,
antimatter led the pack with SnapDragon close behind. In division 2, a newcomer by the name of
aneubeck beat all competitors with an impressive 1673.43.
The Problems
Serpentine
Used as: Division 2  Level 1:
Value 
350 
Submission Rate 
137 / 175 (78.29%) 
Success Rate 
87 / 137 (63.50%) 
High Score 
aneubeck for 336.53 points 
To solve this problem we have to keep track of the position in the current row, and which direction
the row is going. Using these two pieces of information we can calculate our column and thus
produce the returned string. Code such as this will do the trick:
String column(String s, int width, int index) {
String ret = "";
for (int pos = 0, col = 0, dir = 1; pos < s.length(); col+=dir) {
if (col<0  col >= width) dir = dir;
else {
if (col == index) ret+=s.charAt(pos);
pos++;
}
} return ret;
}
HalfRange
Used as: Division 2  Level 2:
Value 
500 
Submission Rate 
99 / 175 (56.57%) 
Success Rate 
60 / 175 (60.61%) 
High Score 
MPhk for 482.69 points 
Here we are trying to find the smallest range that contains at least half of the numbers. I
t is useful to realize that the bounds of the range must be numbers in the list. Using
this information, we first sort the list. Then, we loop through checking values that enclose
half the list. The closest pair becomes our range. This concept is shown in the following code:
int halfRange(int[] data) {
java.util.Arrays.sort(data);
int start = 0, end = (data.length1)/2, score = data[end]data[start];
for (;end!=data.length;start++,end++) score = Math.min(score,data[end]data[start]);
return score;
}
Tourney
Used as: Division 2  Level 3:
Value 
1000 
Submission Rate 
76 / 175 (43.43%) 
Success Rate 
52 / 76 (68.42%) 
High Score 
vegeta for 915.05 points 
Used as: Division 1  Level 1:
Value 
300 
Submission Rate 
138 / 138 (100.00%) 
Success Rate 
125 / 138 (90.58%) 
High Score 
sjelkjd for 296.31 points 
The most popular way to solve this involved using 2 lists: a current list, and a next list.
Looping through the current list 2 at a time you check for the word "bye". If you find it,
the other team in the pair is added to the back of the next list. If not, you determine which
of the pair to add based on the current element of the winnings parameter. Once you have
exhausted the current list, you assign the next list to the current list, clear the next list,
and repeat the process. The winner is the last team left.
Errors
Used as: Division 1  Level 2:
Value 
500 
Submission Rate 
118 / 138 (85.51%) 
Success Rate 
39 / 118 (33.05%) 
High Score 
dgarthur for 454.65 points 
Given a particular operation to perform, you try every combination of adding or subtracting
the error from each operand. Given all these results you can figure what the maximum and
mininum possible values are. Subtracting the min from the max you arrive at the required
range size. The only catch is the division operation. If the denominator error
(parameter/1000) is greater than or equal to the measured denominator value,
the range may potentially be infinite, so return "INFINITY". Otherwise return the
properly formatted result.
Skyscraper
Used as: Division 1  Level 3:
Value 
900 
Submission Rate 
50 / 138 (36.23%) 
Success Rate 
12 / 50 (24.00%) 
High Score 
SnapDragon for 560.64 points 
Many tricks lie beneath the surface of this problem even though the solution is very
easy to type. The actual code can comfortably fit on 3 lines. The basic trick is
realizing all possible ways to run the wire when calculating the distances. The
following pictures may illuminate the topic:
Case 1: Case 2: Case 3:
_______________ ________________   
   Top Right   
Front Right  _______________ Back Right 
   Front  ___________
     Top 
     _____
Front
 
 
Case 4: Case 5:
__________
Right   
_________________  
Back Top  Right 
________________________ ______
Left Front  Top 
   ____________
   Left Front 
     
     
  
Each picture above represents one of the cases that must be considered when measuring the
distance from a point on the front, to a point on the right. In each picture above,
the rectangular solid has been taken apart and laid flat to illuminate the way to measure
the distance. The following code handles all 5 of these cases:
int dist(int x1, int y1, int x2, int y2) { return (int)Math.ceil(Math.sqrt((x2x1)*(x2x1)+(y2y1)*(y2y1)));}
int wire(int w, int x, int y, int xx, int yy) {
return Math.min(dist(x,y,200+xx,yy),Math.min(dist(x,y,200+yy,xx),
Math.min(dist(x,y,200+wxx,wyy),Math.min(dist(x,y,xx,200yy),dist(x,y,wyy,200w+xx)))));
}
By
brett1479
TopCoder Member