JOIN
 Match Editorial
SRM 139
Tuesday, 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.length-1)/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((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)));}
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+w-xx,-w-yy),Math.min(dist(x,y,-xx,-200-yy),dist(x,y,-w-yy,-200-w+xx)))));
}
```
By brett1479
TopCoder Member