Match Editorial

The turnout for the 300th Single Round Match probably wasn't as high as some predicted, with "only" 639 registered coders. Both divisions saw rather hard problem sets, and most of the problems left just enough space for challenge opportunities.

In Division 1, tomek used this opportunity, and +175 points from the challenge phase gave him a comfortable lead before misof and Egor.

In Division 2, only four coders were able to finish the hard problem in time, and they took the top four spots. Also in this division the challenge phase altered the top of the standings. Three successful challenges meant that Joshik won today, followed by CandyShop, MartinMaas, and leiz.

The Problems

Value	250
Submission Rate	207 / 301 (68.77%)
Success Rate	103 / 207 (49.76%)
High Score	rasto6sk for 242.46 points (5 mins 2 secs)
Average Score	173.33 (for 103 correct submissions)

The first thing one should realize after reading the problem statement is that the whole allowed rectangle is large. More precisely, it is far too large for an approach that looks at all the grid points inside the rectangle. We have to come up with some idea.

The key observation is the following one: Suppose that [ax,ay] and [bx,by] are points with the given taxi distance. Neither the taxi distance, nor the Euclidean distance changes if we swap ax and bx. Thus we may assume that ax≤ay, and similarly that bx≤by. Moreover, neither of the distances changes if we move both points in the same direction by the same amount. Thus we may move the point [ax,ay] to [0,0].

We have just discovered that we only have to consider paths from [0,0] to some [x,y], with x,y≥0. Note that the taxi distance from [0,0] to [x,y] is (x+y). This means that once we know x, we may compute y as taxiDis-x.

We may now consider all allowed integer values of x, for each of them compute the corresponding y, check whether it is allowed, and if yes, compute the distance from [0,0] to [x,y].

• Why is it enough to consider integer values for x,y? The problem statement didn't say that a path from [0,0] to [3.4,2.6] was invalid... (Did you note this during the contest?)
• There is a constant-time solution that only considers a few cases. Find it.
  (Hint: We want the taxi path from [0,0] to [x,y] to be as straight as possible – the greater min(x,y) is, the shorter is the straight line from [0,0] to [x,y]. If [0,taxiDis] or [taxiDis,0] is inside the allowed rectangle, this is the optimal solution. How does the optimal solution look if the rectangle is not large enough?)

Value	500
Submission Rate	109 / 301 (36.21%)
Success Rate	35 / 109 (32.11%)
High Score	GAZZA for 406.50 points (14 mins 19 secs)
Average Score	265.62 (for 35 correct submissions)

Value	250
Submission Rate	284 / 297 (95.62%)
Success Rate	149 / 284 (52.46%)
High Score	misof for 234.85 points (7 mins 18 secs)
Average Score	174.51 (for 149 correct submissions)

Clearly, the right approach here is simply to simulate the process described in the problem statement. The input is small enough, so we may use some brute force in doing the simulation.

Instead of a circle, imagine a queue, starting with the first person in the input. As we count from 1 to k-1, we send the person from the beginning of the queue to its end. Now, remove the person at the beginning of the queue, walk through the queue to find the best match, and remove the match from the queue.

This process ends once we are not able to find a match, or once we run out of people.

C++ code follows.

string dates(string circle, int k) {
  vector<char> V;
  for (unsigned i=0; i<circle.size(); i++) V.push_back(circle[i]);

  string res;

  while (1) {
    // skip k-1 people
    for (int kk=0; kk<k-1; kk++) { 
      char ch = V[0];
      V.erase(V.begin());
      V.push_back(ch);
    }
    
    // take the next one
    char current = V[0];
    V.erase(V.begin());
    
    // find the match
    char match = 127;
    for (unsigned i=0; i<V.size(); i++) 
      if (islower(current) != islower(V[i])) 
        match <?= V[i];
    if (match == 127) break;
    
    // delete the match
    V.erase(V.find(match));
    
    res += ' ';
    res += current;
    res += match;

    if (V.empty()) break;
  }

  if (!res.empty()) res=res.substr(1);
  return res;
}

Value	1000
Submission Rate	12 / 301 (3.99%)
Success Rate	4 / 12 (33.33%)
High Score	Joshik for 670.35 points (22 mins 23 secs)
Average Score	573.48 (for 4 correct submissions)

It is easy to discover a necessary condition for the existence of a solution: The cars must be in the same circular order as the respective unloading places. Sadly, this condition is not sufficient for a solution to exist – consider the input "AcBdCaDb".

We will show that a greedy approach works for this task. In each step, select the lexicographically smallest car that can be moved to its final destination. Change the location of the car into a free space, and the corresponding unloading place will become an obstacle.

Why does this approach work? Clearly, if we find a solution, it will be the lexicographically smallest one. The question is, if this approach fails, how can we be sure that another approach won't work?

Imagine a general situation that looks like this:
....C.....c....
where our greedy algorithm wants to move the car 'c' into the unloading place 'C'. We will call the places between 'C' and 'c' the inner part, and the remaining places in the outer part.

Suppose that before this move there was a possible solution but after this move there is none. We will show that this leads to a contradiction.

The places between 'C' and 'c' are either empty, or they contain unloading places. This means that all cars (other than 'c') are in the outer part. If moving 'c' to 'C' changes the existence of a solution, it means that in any solution one of the unloading places in the inner part has to be occupied before 'c' moves.

Pick any solution and look at the moment when 'c' moves to 'C'. From the above observation we get that 'c' has to move through the outer part, as the inner part will contain at least one obstacle. However, if at this moment it is possible to reach 'C' by moving 'c' through the outer part, this means that all cars had to leave the outer part before. This is only possible if all other unloading places are in the inner part, and the initial situation looked as follows:
defgCHIDEFGchi
However, in such case starting by moving 'c' to 'C' does lead to a valid solution.

We have shown that if there is a valid solution and we greedily make the best move available, there will still be a valid solution. The implementation of the algorithm outlined in the second paragraph is fairly straightforward.

Value	500
Submission Rate	112 / 297 (37.71%)
Success Rate	77 / 112 (68.75%)
High Score	Egor for 471.83 points (7 mins 1 secs)
Average Score	284.53 (for 77 correct submissions)

This problem almost calls for a dynamic programming/memoization solution. But as soon as we start to look for one, nasty special cases will start to appear everywhere. So let's break the approach into simple steps to make sure nothing goes wrong.

First, we can get rid of one of the boundaries. Instead of counting jumpy numbers in [low,high], we can count jumpy numbers in [0,high] and subtract the count of jumpy numbers in [0,low-1]. We are left with a simpler problem: how to count jumpy numbers in [0,x]?

There are two possible approaches when building a jumpy number: either you add new digit to the beginning, or you add them to the end. In general, each of these approaches can be converted to a dynamic programming algorithm, or a recursive function that can be memoized.

We will present an algorithm that will add new digits to the beginning of a number. Let's illustrate it on a simple example first:

All 2-digit jumpy numbers starting with the digit 3 are 30, 31, 35, 36, 37, 38, and 39. Let X be any of these numbers. What digit can be added to the beginning of X? Clearly, this only depends on the first digit of X. In our case, the first digit is 3, thus we can use the digits 0, 1, 5, 6, 7, 8, 9.

Now suppose that we only consider jumpy numbers in [0,31442], and we already decided that the last digit of our jumpy number is 7. Then the rest of the number has to be a jumpy number from [0,3143], and its last digit must be "compatible".

This brings us to the idea of writing a memoized recursive function countJumpers(upperBound, lastDigit) that counts jumpy numbers that end in lastDigit and are at most equal to upperBound. For a clean implementation look at tomek's solution.

The nice thing about this task was that there were many different approaches. For example misof's solution generates the numbers in the other direction (using DP instead of memoization), Egor found that his solution runs in time without the need to memoize, in jmzero's solution you can find pre-computed values for upper bound=k*100000, and brute force used to count the rest, and so on.

Value	1000
Submission Rate	28 / 297 (9.43%)
Success Rate	12 / 28 (42.86%)
High Score	Abednego for 753.92 points (17 mins 28 secs)
Average Score	592.35 (for 12 correct submissions)

Let's start by looking at the winding number in more detail.

Suppose that P is a closed polyline, and X is a point not lying on P. Place a boy into the point X, and a girl somewhere on the polyline. Let the girl walk once around the polyline. During her walk, the boy will rotate so that he always sees the girl directly in front of him.

After the girl finishes her walk, the boy will be looking in exactly the same direction as when she started. However, it is possible that he made more turns in one direction than in the other. E.g., if P is a triangle with X inside, the boy will turn 360 degrees in one direction.

Let A be the total angle (in degrees) the boy turned counter-clockwise, and let B be the angle he turned clockwise. Then the winding number can be defined as (A-B)/360. The observation above proves that this is always an integer.

Given X and P, this leads us to an algorithm how to compute the winding number corresponding to X – process segments of P, and for each of them compute the angle the boy turned. The angle can be computed e.g. from the cross product of the boy's direction at the beginning and at the end of the segment.

However, winding number can be computed using integers only. Consider the classical algorithm (e.g., from the geometry tutorial) to determine whether a point lies in a polygon. The winding number is a generalization of this algorithm. Note that for simple polygons P, if X is inside, its winding number is 1 or -1, if X is outside, the winding number is 0. (Use the "boy and girl" example to visualize this. If the boy is inside, the girl walks once around him.)

In fact, the winding number is exactly a way how "inside" can be defined for closed polylines. The interesting thing is that the "intersections of a ray and a polygon" approach can be modified to compute the winding number. The only change is that we have to look whether we cross the ray going "downwards" or "upwards" A very thorough and readable explanation, including an integers-only implementation, can be found at the SoftSurfer Geometry Algorithms page.

Now, how to plug this information into our solution? We have to find the largest winding number of some point on the x axis. If the polyline crosses the x axis, it divides the x axis into several segments and two infinite rays. For points on the rays the winding number is clearly zero. For each segment, the winding number is the same for all its points.

Thus we get the following algorithm:

• find the intersections of the polyline P and the x axis;
• sort the intersections;
• for each segment between two neighboring intersections, compute the winding number for its midpoint

If we process the segments in order, we may even reuse the information about the ray-polyline intersections. This leads to an O(N log N) algorithm. Look at tomek's solution for an implementation of this approach. Alternately, look at misof's solution to see where a pre-written geometry library can get you.