Match Editorial

In Division I antimatter and bladerunner were on fire, as they both finished all 3 problems in under 30 minutes. However, as it is often the case, fast code is not always good code and both had to resubmit their Easy problems. After the coding phase, CristopherH looked certain to win his first SRM with an impressive score of 1500.67, but that was about to change...

The challenge phase was fast and furious with many Easy problems challenged by one simple case. A number of coders gained over 100 points in those frenetic 15 minutes. It was 5 successful challenges by Yarin and WishingBone which propelled them into first and second, respectively. System tests brought even more destruction, failing nearly half of Medium problems. At the end of the day, it was Yarin on top with 1562.66, closely followed by WishingBone and CristopherH.

Division II coders had a more relaxing SRM with few difficulties on the first two problems. Once again, it was the Hard problem which separated the best from the rest, as there were only 8 coders who passed it. The division was won by dilap who scored 1513.41 and gained the highest rating change doing so. He was followed by first-timer roma and DimaGer, who has gained an amazing 468 rating points from last two SRMs!

The Problems

Value	250
Submission Rate	158 / 183 (86.34%)
Success Rate	121 / 158 (76.58%)
High Score	Uranium-235 for 244.15 points (4 mins 24 secs)
Average Score	203.73 (for 121 correct submissions)

This problem was relatively easy if you simply followed instructions from the problem statement and did not try to take any risky shortcuts. The most difficult part of the problem was avoiding index out of bounds errors, especially when dealing with bus stops and side streets. An easy way to handle such errors was to "pad" the street like so in Java:

street = "*" + street + "**";

All we have to do now is loop through all the characters in street (without the first and last two) and count all valid '-' positions:

   for (int i=1; i<street.length()-2; i++) 
   {
      char current = street.charAt(i);
      char previous = street.charAt(i-1);
      char next = street.charAt(i+1);
      char next2 = street.charAt(i+2);

      if (current=='-' &&
         next!='B' && next2!='B' &&
         previous!='S' && next!='S')
         count++;
   }

Value	500
Submission Rate	137 / 183 (74.86%)
Success Rate	107 / 137 (78.10%)
High Score	eldering for 468.08 points (7 mins 31 secs)
Average Score	349.98 (for 107 correct submissions)

This problem dealt with sets and three of their most common operations: union, intersection and symmetric difference. Many coders may want to keep their code for future reference, because set operations tend to crop up in many applications. For example, Kruskal's algorithm for finding the minimum spanning tree uses union of sets when adding new edges to the final solution.

C++ coders had a slight advantage in this problem, because set operations are part of the standard package (see Karshikinpa's solution in the practice rooms). Then again, I don't think many used it during the contest. In Java it is easiest to use one of the built in classes like TreeSet, HashSet, ArrayList or Vector. Although I will demonstrate the solution with a Vector class, any of the above would do the job.

To implement the union operation we add all the elements from set A to our result, then loop through set B and add all of its elements which are not already in result:

   for (int i=0; i<A.length; i++)
      result.add(""+A[i]);
   for (int i=0; i<B.length; i++)
      if (!result.contains(""+B[i])) result.add(""+B[i]);

To implement the intersection operation we loop through set A and add all of its elements, which can be found in set B:

   for (int i=0; i<A.length; i++)
      for (int k=0; k<B.length; k++)
         if (A[i]==B[k]) result.add(""+A[i]);

Symmetric difference can be found by taking the union of A and B and then removing all the elements that belong to the intersection of A and B. I leave this as an exercise to the reader. In general, coders did well on this problem. However, some failed because they did not properly handle the case with empty sets.

Value	1000
Submission Rate	42 / 183 (22.95%)
Success Rate	8 / 42 (19.05%)
High Score	dilap for 758.50 points (17 mins 13 secs)
Average Score	593.04 (for 8 correct submissions)

Value	500
Submission Rate	96 / 118 (81.36%)
Success Rate	48 / 96 (50.00%)
High Score	antimatter for 476.07 points (6 mins 25 secs)
Average Score	369.51 (for 48 correct submissions)

It should not take long to realize that this is the longest increasing subsequence problem. Intuitively, we could produce all possible sequences, find all increasing sequences, and then find the longest of those sequences. However, this is not a very good idea, because the number of sequences we need to consider for input of size n is 2^n - 1. Since n can be as high as 50, such a solution would definitely time-out. Recursion is another way to solve this problem, but as many coders found - it also timed-out.

So how do we solve this problem? Well, we use the power of dynamic programming of course. We begin by creating two auxiliary arrays S and L. S[i] will store the longest increasing subsequence that ends with prices[i], while L[i] will store the total number of ways of achieving S[i].

We can notice a recurrence relationship:

The longest increasing subsequence ending at prices[i] can be formed by appending it to the longest increasing subsequence to the left of i that ends on a number smaller than prices[i].

We also notice the following:

The total number of ways of achieving the longest increasing subsequence ending at prices[i] is equal to the sum of the total number of ways of achieving the longest increasing subsequence ending at prices[j], where j<i and prices[j] < prices[i].

Based on the above relationships we can derive the following pseudo-code:

   initialize int[] out to {0,0}

   for all i<prices.length
      initialize temp to 0
      for all k<i
         if prices[k]<prices[i] then temp = Max{temp, S[k]}
      for all k<i
         if S[k] == temp and prices[k]<prices[i] then increment L[i] by L[k]
      if L[i] is still 0 then L[i] = 1
      S[i] = 1 + temp
      out[0] = Max{out[0], S[i]}

   for all i<prices.length
      if S[i] == out[0] then increment out[1] by L[i]

   return out

To compute each S[i] value we must make (i-1) comparisons. Thus, the time complexity of this algorithm is O(n^2). By using advanced data structures we can improve the complexity to O(n*log(n)). Surprisingly, this problem has parallels with real-world applications. The same algorithm is used for finding common subsequences in DNA strands, and is closely related to spelling correction algorithms.

Value	250
Submission Rate	117 / 118 (99.15%)
Success Rate	50 / 117 (42.74%)
High Score	tjq for 248.12 points (2 mins 28 secs)
Average Score	204.51 (for 50 correct submissions)

Many coders submitted this problem, but surprisingly not many of those solutions stood the rigorous test of challenges and system tests. In fact, this problem had the lowest success rate for any non-level 3 problem over the past 10 competitions! The case which was most often overlooked occurred when 2*hamburgers<=panSize. For this case, solutions returned 5, while 10 was the expected answer.

Some coders like ZorbaTHut and sjelkjd simulated the problem, but there is a much shorter solution. Nevertheless, it will probably require some convincing before you can see that it works. We notice that there are five distinct cases:

1. If hamburgers == 0 then we do not need to fry anything and we should return 0.
2. If hamburgers<=panSize then all the hamburgers can be fried in one go and we should return 10.
3. If panSize divides evenly into hamburgers (i.e. hamburgers%panSize == 0) then we have no tricks up our sleeves and must fry all hamburgers consecutively in batches of panSize. In this case we should return (hamburgers/panSize)*10.
4. If the last batch of hamburgers is not more than half of panSize (i.e. hamburgers%panSize<=panSize/2) then we can save some time by using the trick described in examples. This involves frying hamburgers from the last batch on their first side together with half of hamburgers from the previous batch on their second side. After that, the remaining hamburgers from the previous batch are fried together with the hamburgers from the last batch on their second sides. This trick saves us 5 minutes, so we could return (hamburgers/panSize+1)*10-5.
5. For all remaining situations, we have too many hamburgers in the last batch to do anything with. In this case we return (hamburgers/panSize+1)*10.

It turns out that cases 1, 3, 4 and 5 can be all simplified to one single statement:

5*(int)Math.ceil(2.0*hamburgers/panSize);

For a short solution see writer's solution in the practice rooms.

Value	1000
Submission Rate	32 / 118 (27.12%)
Success Rate	13 / 32 (40.62%)
High Score	ChristopherH for 792.27 points (15 mins 24 secs)
Average Score	560.00 (for 13 correct submissions)

Given a set of points we can easily construct the set containing distances between each pair of points. However, it is a much more difficult task going backwards - i.e. constructing the set of points from a given set of distances. This problem is called the Turnpike Reconstruction problem.

As far as I know there is no solution to this problem that is guaranteed to run in polynomial time. Since a general algorithm is unavailable, we are forced to use a more "guess-and-check" method, such as backtracking. Like many other backtracking algorithms, this solution involves having a driver function and a recursive function.

In the driver function we sort distances into ascending order and initialize the points array to the correct number of points. This can be done using a simple while loop or the quadratic formula: N = (int)(1+Math.sqrt(1+8*distances.length))/2. Because this is a backtracking algorithm it is important to keep track of distances already used so that we don't try to use the same distance more times than it occurs in the input. The easiest way to implement this is to create an int[] tally of size 1000001, where tally[i] represents the number of distances of length i. If the distances array has only one element then we can simply return {0,distances[0]}. Otherwise we set the first point to 0, the last point to the largest distance and the second point to the difference between largest and second largest distances. If the second point exists in distances then we run the recursive function, otherwise the set of points cannot be constructed and we return an empty int[].

The function prototype for the recursive call can look like this in Java:

void place(int[] points, int[] tally, int left, int right);

Each call, the function assumes that points have not yet been placed between left and right inclusive. We begin by attempting to set points[left] to points[N-1] - largest unused distance. We make sure that all the distances between this new point and the points already placed have not been used yet. If this is the case, then all those distances are removed (by decrementing values in tally) and we recurse with the call place(points, tally, left+1, right). Otherwise, we attempt to set points[right] to the largest unused distance. Once again we make sure that all the distances between this new point and the points already placed have not been used yet. If this is the case, then all those distances are removed and we recurse with the call place(points, tally, left, right-1). If we reach the situation where setting points[left] or points[right] are both impossible then we must backtrack. This is achieved by incrementing elements in tally back to their original values. We continue recursion until all distances have been considered. If all distances have been placed successfully then we have a working solution that we return, otherwise the set of points cannot be constructed and we return an empty int[].

It is important to note that the problem specifically asks us to find the lexicographically earliest set of points. We can be sure that our solution achieves that, because the recursive function always places the smallest possible point, and only if that doesn't work does it go on to place a larger point.

Now to the analysis. First, we must show that the above algorithm is correct. The step which may seem questionable is to always choose the largest unassigned distance at each step of the recurrence, and use only that distance to find the next point. However, we can see that this is correct by induction. Clearly, the first point has to be 0, and the last point has to be the largest distance in the input. Now, the inductive step is to show that, after some subset of points has been placed, if that subset is part of a correct solution, the next point must be either at the largest unused distance, or the maximum distance minus the largest unused distance. If there were not a point at either of those locations, then the largest unused distance must be a distance from some other point. However, since this point isn't the smallest or the largest, there would have to be a largest unused distance for this to work. Perhaps a diagram will make this clearer. Assume we have an input whose largest distance is 8, and in our recursion, we have placed a point at 4. Now, at the current step of our recursion, the largest unused distance is 3:

0---1---2---3---4---5---6---7---8
x---------------x---------------x

If the distance of 3 is a distance from the point at 5, then there would have to also be a distance of 4+3=7 (from the point at 0), or of 8-4+3=7 (from the point at 8). So, from this, it should be clear that we need only try to place a point at one of two locations in each step of our recurrence. Thus, the running time of our algorithm has a worst case which is O(2^n), which is plenty fast for n<=10. It turns out that the runtime is usually much better than this. In fact, the following website claims that the runtime seems to be O(n^2 log n): http://www.cs.fiu.edu/~weiss/cop3337_f99/assignments/turnpike.pdf

However, proving this seems to be pretty hard, though my experiments seem to support the claim that the algorithm is much better than exponential. For a reference implementation see writer's solution in the practice rooms.