Match Editorial

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

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;
}
                              

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;
}
                              

Value	1000
Submission Rate	76 / 175 (43.43%)
Success Rate	52 / 76 (68.42%)
High Score	vegeta for 915.05 points

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.

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.

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)))));
}