Thursday, April 27, 2006 Match summary 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 ProblemsTaxiUsed as: Division Two  Level One:
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 taxiDisx. 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]. Homework.
Used as: Division Two  Level Two: Used as: Division One  Level One:
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 k1, 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 k1 people for (int kk=0; kk<k1; 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; }CircleOrder Used as: Division Two  Level Three:
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: 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: 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. JumpyNumUsed as: Division One  Level Two:
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,low1]. 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 2digit 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 precomputed values for upper bound=k*100000, and brute force used to count the rest, and so on. AllWoundUpUsed as: Division One  Level Three:
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 counterclockwise, and let B be the angle he turned clockwise. Then the winding number can be defined as (AB)/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 integersonly 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:
If we process the segments in order, we may even reuse the information about the raypolyline 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 prewritten geometry library can get you. 
