Thursday, January 25, 2007 Match summaryThis match had an unusual and tough set of problems written by dgoodman . Both medium problems were tricky, with many corner cases that led to an overall accuracy lower than we are used to. The hards were also no walk in the park, with both being solved by less than 5% of the participants.In division 1, speed in the problems was the key. Of the top three, ploh was the only one that took points out of the challenge phase, but as it turned out he didn't even need them and would have won without them. In second place wasPetr, who was pretty fast on the tricky medium, and third place went to Abednego. Division 2 was a different story. While the champion of this round, lewha0, relied only on his speed in the problems, second and thirdplace finishers Gaizka and ebd both scored more than 100 points in challenges to earn their spots on the podium. The ProblemsVowelLatinUsed as: Division Two  Level One: This problem was pretty straightforward  you only needed to follow the rules carefully. The best way to do it is to take two passes over the input string: In the first pass collect all nonvowels and go appending them at the end of the result; on the second pass do the same with the vowels. With this approach you mantain the original order of both groups. A similar approach was to do only one pass but have two accumulated results and return their concatenation. For details of this method see ebd's fastest solution. MostLikely Used as: Division Two  Level Three: This problem was a simpler version of the division 1 medium, so if you liked it, go try that one in the practice room for a more challenging version. The basic idea was to calculate, for each possible rank, the number of your possible scores that would achieve that spot, take the greatest of those, and remember whether it is repeated or not. A tricky thing to notice is that if there are n other players then there are n+1 possible ranks for you. The best approach for implementing this is to add a strong player that always beats you and a weak player whom you always beat. That way your rank will surely be situated between two other players. Then, sort the other players by greatest score and, at each place, count how many scores within your range will give you a spot between them (or tied with the low one of them, is the same for you). This can be done with simple math, illustrated in the C++ code that follows: int likelyRank(vector <int> sc, int low, int high) { int best=0,r=1,n=sc.size()+1; sc.push_back(1); sc.push_back(high+1); sort(sc.begin(),sc.end()); reverse(sc.begin(),sc.end()); for(int i=0;i<n;++i) { int mn=max(sc[i+1],low),mx=min(high,sc[i]1); if (mn>mx) continue; int t=mxmn+1; if (t>best) { r=i+1; best=t; } else if (t==best) r=1; } return r; }ServiceNames Used as: Division Two  Level Two: Used as: Division One  Level One: Good knowledge of your language played a major role in this problem, as the C++ short program by cypressx shows. Follow the instructions carefully and you'll be on your way. Really carefully. I mean it. The most important parts of this problem were before and after coding: Good reading of the problem statement so you didn't miss any detail, and good testing since the provided examples didn't test everything you needed. In this case, the problem for many coders was that they forgot to sort the services within each KindOfInput and the examples didn't cover that case. A good practice if you like to submit fast is to test a little more after submitting  it's better to have a corner case fix resubmitted 2 or 3 minutes later than 45 or 50, with much more elapsed time and much less points. Getting to the solution, the basic idea was to simulate what the problem asked:
LikelyWord Used as: Division One  Level Two: As mentioned above, this problem is a trickier version of the division 2 hard; if you liked it, go try that one in the practice room for a more relaxing version. The idea in this case was the same as the division 2 version, but the math for this case is more difficult. To add some first and last words, you can add the empty one (it beats everything) and a string consisting of m>k zs. At each space between two words, you can treat the boundaries of the spot as if they were base26 numbers (completing with a's or shortening both strings appropiately) and then the number of strings between them is simply the difference between those numbers. After doing that, see if you need to add the string that is equal to each of them in this spot (if the string wasn't actually of length k originally, you may want to include the prefix or extension of length k of each of them). For details on this and a good implementation see Petr's nice, short and clear code. Shadow Used as: Division One  Level Three: This was a tricky problem with many corner cases, so it had to be programmed carefully, though the main point was not very difficult. I'll outline the steps based on Abednego's approach. First, we'll detect infinite and zero cases, and then find the solution for the rest. If the tree is just one point or a line, it's clear we must return zero. If the light is inside the tree, it's clear we must return infinite (1). Both those cases can easily be checked. If the tree is just a rectangle, we must check if its coplanar with the light. This is easy because the tree is aligned with the axis, so the plane is either x=A, y=A or z=A, where A is the value of the tree in the particular coordinate for which both its points are the same. The check, then, is done by seeing if the light also shares this plane, comparing the light's own value for that same coordinate. If both are the same, then the light is coplanar and the shadow will be a line, so we return 0. Otherwise, we continue as if the tree was a solid with positive volume. Finally, if the light is below the tree, we must return 0 because there will be no shadow. If the light is over the lower level of the tree but below the higher level, and it does not fall in the previously described categories, then the shadow will be infinite, so we return 1. For noninfinite nonzero cases, we must find the vertices of the polygon that the shadow covers. These are some of the projections on the plane Y=0 of the lines that pass through each of the eight vertices of the tree and the light. To find such points, the best way is to express the lines as L*(P1P2)+P2, in which P1 and P2 are the two points and L is a variable (the line consists of all points that result of given a real value to L). Finding the point with Z=0 is then easy by setting L=z2/(z1z2). For more detail about this, see its function on the above quoted code. To find out which vertices are part of the polygon, run a convex hull on all projections (after playing for a while with the possibilities you'll convince yourself that the shadow is always convex). Then, since after the convex hull the points are already sorted in clockwise or counterclockwise order, you can calculate the surface as the sum of the areas of a triangulation based on any point (see the code for details on this). 
