|
Match Editorial |
Thursday, January 25, 2007
Match summary
This 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 third-place finishers Gaizka and ebd both scored more than 100 points in challenges to earn their spots on the podium.
The Problems
VowelLatin
Used 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 non-vowels 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.
Value 250 Submission Rate 431 / 453 (95.14%) Success Rate 414 / 431 (96.06%) High Score ebd for 249.64 points (1 mins 4 secs) Average Score 223.63 (for 414 correct submissions)
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.
Value 900 Submission Rate 144 / 453 (31.79%) Success Rate 22 / 144 (15.28%) High Score lewha0 for 744.35 points (13 mins 35 secs) Average Score 471.74 (for 22 correct submissions)
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=mx-mn+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:
Value 500 Submission Rate 258 / 453 (56.95%) Success Rate 142 / 258 (55.04%) High Score mrinaldotnet for 462.90 points (8 mins 10 secs) Average Score 302.91 (for 142 correct submissions)
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.
Value 250 Submission Rate 337 / 349 (96.56%) Success Rate 257 / 337 (76.26%) High Score cypressx for 246.25 points (3 mins 31 secs) Average Score 196.37 (for 257 correct submissions)
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:
- Parse each string and accumulate in a dictionary a list of the services associated to each KindOfInput
- Sort the lists
- Sort the dictionary
- Iterate the dictionary and format the output
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.
Value 500 Submission Rate 262 / 349 (75.07%) Success Rate 59 / 262 (22.52%) High Score liympanda for 432.71 points (11 mins 34 secs) Average Score 285.84 (for 59 correct submissions)
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 base-26 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.
Value 1000 Submission Rate 54 / 349 (15.47%) Success Rate 15 / 54 (27.78%) High Score misof for 709.91 points (19 mins 57 secs) Average Score 514.19 (for 15 correct submissions)
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 non-infinite non-zero 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*(P1-P2)+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/(z1-z2). 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 counter-clockwise 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).
