Match Editorial

In the 270th SRM the coders in both divisions had to face a problem set with non-standard point values: 250-600-900 in Division 2 and 300-600-900 in Division 1. In both divisions their medium problem had the highest failure rate and it offered a lot of great challenge opportunities.

Before the challenge phase started, in Division 1 roughly 50 coders submitted all three problems. But many of them missed hidden catches in the medium problem or their solutions of the hard problem failed on some boundary cases. After the eventful challenge phase was over and the system tests claimed their share of the submitted solutions, only four coders were left with all three tasks solved. Out of them, bmerry claimed fourth place, andrewzta was third and krijgertje (with the help of 7 successful challenges) was second.

In Division 1 this match had a clear winner. Petr made 5 successful challenges, had the fastest time on the hard problem and won the match by well over 250 points. His final score 1764.09 is the seventh highest total score ever.

In Division 2 the winner was a newcomer – elhipercubo, thanks to a solid time on all three problems, followed closely by gc0, motono and 11 other coders who managed to solve all three tasks.

The Problems

Value	250
Submission Rate	260 / 292 (89.04%)
Success Rate	220 / 260 (84.62%)
High Score	elhipercubo for 249.12 points (1 mins 41 secs)
Average Score	214.48 (for 220 correct submissions)

This problem was as simple as it gets. Maybe the only thing worth noting is: don't reinvent the wheel. If there is a library function for a problem, use it.

In this case, most programming languages include a function to remove duplicate elements from a (sorted) list. A very nice and simple way to solve this task in C++ is to convert the input vector into a set (it gets sorted and duplicates are removed), back into a vector and output its third element (or -1).

int thirdBestPrice(vector prices) {
  set S ( prices.begin(), prices.end() );
  vector V ( S.begin(), S.end() );
  if (V.size() < 3) return -1;
  return V[2];
}

int thirdBestPrice(int[] prices) {
  Arrays.sort(prices);
  int cnt = 1;
  for (int i = 1; i < prices.length; i++) if (prices[i] != prices[i - 1] && ++cnt == 3) 
    return prices[i];
  return -1;
}

Value	600
Submission Rate	184 / 292 (63.01%)
Success Rate	49 / 184 (26.63%)
High Score	fir for 553.66 points (8 mins 21 secs)
Average Score	377.27 (for 49 correct submissions)

The moral of the story for this task is: don't use "real" numbers if you don't have to.

The problem was solvable by brute force: For each round number between the bill and the amount I have, calculate the tip and check whether its size is appropriate. (As an optimalization, you may stop as soon as the tip exceeds 10% of the sum you pay).

However, there is also a solution in constant time. Let B be the value of the bill and S the sum I pay. Then the tip is S-B. For it to be appropriate, this value must be between S/20 and S/10, inclusive. We get two inequalities: S/20≤S-B; S-B≤S/10. We may rewrite these equations to get S≥20B/19 and S≤10B/9.

In other words, sums that lead to an appropriate tip lie in the interval [20B/19, 10B/9]. The boundaries of this interval are not necessarily integers. To get integral bounds, we take the ceiling of the lower bound and the floor of the upper bound. Now we only have to compute the number of round sums in this interval, which is a pretty easy task.

public static int possiblePayments(int bill, int cash) {
  // compute the smallest and largest valid sums
  int minPay = bill + (bill + 18) / 19; // this is the ceiling of the lower bound
  int maxPay = bill + bill / 9;
  if (cash < maxPay) maxPay = cash;
  
  // adjust the bounds to be round
  while (minPay % 5 != 0) minPay++;
  while (maxPay % 5 != 0) maxPay--;

  int result = 0;
  if (maxPay >= minPay) result = 1 + (maxPay - minPay) / 5;
  return result;
}

Value	900
Submission Rate	45 / 292 (15.41%)
Success Rate	34 / 45 (75.56%)
High Score	Nitz for 601.23 points (22 mins 32 secs)
Average Score	453.49 (for 34 correct submissions)

Value	300
Submission Rate	219 / 267 (82.02%)
Success Rate	200 / 219 (91.32%)
High Score	Krzysan for 265.20 points (10 mins 34 secs)
Average Score	181.95 (for 200 correct submissions)

There are not many tasks that can be shared as an easy problem in Division 1 and a hard problem in Division 2, but the results show that this was one of them. It required some thinking before you started to write code, but once you saw how to solve this task, the code becomes pretty straightforward. As a consequence, this problem had a pretty high success rate in both divisions.

First of all, suppose that I know the exact scores for each of the countries. How to compute the place of a given country? Simply, it's one plus the number of countries that had a higher total score.

Knowing this, how to compute the best possible placement for some country C? We start by finding the worst announced coder. Let his score be S. Now the best scenario for C is that each of its missing contestants scored S-1 points and all the other missing contestants scored zero. This uniquely determines the score of each of the countries, hence we can compute the best possible placement for C.

When looking for the worst possible placement the computation is reversed, i.e., contestants from C score zero and all the others score S-1 points.

Note: The presented solution was quadratic in the number of countries. There is a linear time solution. We leave it as an exercise for the readers.

Value	600
Submission Rate	123 / 267 (46.07%)
Success Rate	13 / 123 (10.57%)
High Score	krijgertje for 521.53 points (11 mins 22 secs)
Average Score	421.98 (for 13 correct submissions)

Tricky, tricky, tricky! I don't remember seeing such a low success rate for quite a while... The number of submissions was much higher than I expected – and as the success rate shows, many of the coders weren't alerted by the high point value and they didn't spend enough time testing their solutions.

This task offered quite a lot of different opportunities to make a mistake – and many of them weren't covered by examples in the problem statement. If you stopped to think about this problem and discovered them, they could be (and in many cases they were) converted into "killer" test cases for the challenge phase.

The first step towards a correct solution is to construct a directed graph, where the value of each edge is its travel cost minus the profit in the destination city. In this graph we are interested in the shortest walk from our origin to our destination.

The simple case is when destination is not reachable. But if it is reachable, there may be no shortest walk in the graph, because of negative cycles. This was the problematic case we had to detect. (In the original problem statement, this was the "endless profit" case.)

What are these negative cycles we just mentioned? If the salesman discovers a cycle with a negative sum of edge costs, he may start going around this cycle, making an arbitrarily large profit. Of course, the occurrence of a negative cycle somewhere in the graph is not a sufficient condition to output "endless profit" – the cycle must be reachable from the origin and the destination must be reachable from the cycle.

So basically the problem boils down to detecting negative cycles reachable from the origin. If there is one such that the destination is reachable from it, we have the endless profit case, otherwise the shortest walk from origin to destination is a path (i.e., it visits no vertex twice) and it can be found using some standard algorithm.

Author's solution uses the algorithm by Bellman and Ford to compute the shortest paths from origin and detect reachable negative cycles. Then all vertices reachable from them are found using a simple breadth-first search. In the contest, some of the coders solved this task using the algorithm by Floyd and Warshall. Both are standard textbook algorithms, if you don't know them, there are lots of online resources on this topic.

Value	900
Submission Rate	95 / 267 (35.58%)
Success Rate	20 / 95 (21.05%)
High Score	Petr for 829.69 points (8 mins 24 secs)
Average Score	578.73 (for 20 correct submissions)

This problem wasn't as nasty as other geometry problems, but still many of the solutions failed due to precision problems and/or handling some boundary cases incorrectly.

The circle part is simple, its diameter (=twice the given radius) mustn't exceed either dimension of the frame. The interesting part were the rectangles.

Basically, there were three possible approaches. The first one is iterative: Take the small rectangle and start to rotate it in small steps. After each rotation, measure its projection on both coordinate axes and check whether it currently fits the frame or not.

Submitting such a solution is a gamble. It may pass, if you are lucky, but it may very easily fail. And the prepared set of test cases contained both hand-crafted and autogenerated cases meant to cause such solutions to fail. As far as I was able to find out after the match, most such solutions failed.

A second, far better way, was to employ binary search on the correct angle. Imagine a rectangle lying on its longer side. If we start rotating it, its projection on the x axis will start to shrink. What we want is to find the smallest angle such that the rectangle fits into the frame horizontally... and check whether for this angle the rectangle fits also vertically.

Doubles are precise enough for this solution to work reliably, as long as we choose a suitable margin for error tolerance. In the challenge this was probably the best solution.

The third possibility was to compute the correct angle directly. Here we had to be extremely careful so that we don't overlook some special corner case.

As the author of this task, I had to make sure the outputs are correct. Thus I had to choose a fourth possibility – do some exact computation, using integers only! My code follows, with some explanation below.

  // small rectangle: c*d, large rectangle: a*b 

  if (c<=a && d<=b) return "YES";
  if (c<=b && d<=a) return "YES";

  // let
  // f: y = (b-x)c / d
  // g: y = -xd/c + a
  // we want a point [x,y] lying below f,g such that x>0, y>0, x^2+y^2 = c^2

  // check whether one of the lines cuts away the whole arc
  if (a <= c && a <= d) return "NO";
  if (b <= c && b <= d) return "NO";

  // now we are interested in whether they intersect... 
  // ... and whether the intersection point lies outside the arc

  // parallel if c==d, but this case should already be handled
  long kc = b*c - a*d;
  long km = c*c - d*d;
  
  long xc = c * kc;
  long yc = a * km - d * kc;

  if (xc*xc + yc*yc < km * km * c * c) return "NO";
  return "YES";

The idea? Either the sides of the "small" rectangle are parallel with the sides of the "large" rectangle, or not. The first case is easy to check. For the second case, we may assume that both endpoints of a side with length c touch the large rectangle. Why? Consider an arbitrary correct placement of the small rectangle inside the large rectangle. We may now move it (without rotating it) until the endpoints of a side of our choice touch the large rectangle.

In the corner of the large rectangle we get a right triangle with the hypotenuse c. Let x and y be the lengths of the other two sides. Using x and y we can easily compute the width and height of the rotated "small" rectangle. None of them may exceed the corresponding dimension of the "large" rectangle. This leads to two linear inequalities for x and y. We compute whether they have a solution such that x*x + y*y = c*c. If yes, the "small" rectangle can be rotated and the answer is positive, otherwise the answer is negative.