|
Match Editorials |
Monday, January 29, 2007
Match summary
This match was pretty uneven, with standard easy and medium problems and a particularly tough hard that only 2 coders were able to solve.fatit and TICKET_112022 were the only 2 to get any points for the hard problem, earning them spots in first and second place respectively. The difference between them was almost only the hard, since they had pretty similar performances on both the easy and the medium. Third place was taken by fpavetic, who got pretty good scores on the easy and the medium and, with the help of the succesful challenge, pulled ahead of all the other coders who did not solve the hard.
The Problems
HowManyBirthdays
Used as: Division One - Level One:
This problem was pretty easy, but if you didn't follow the instructions precisely it was also easy to get wrong. The easiest and fastest way to solve the problem is to avoid parsing the dates. Since we are only interested in whether or not the date is equal to today we can just compare the string after the first space of each member of friends with the string today. If they are equal, we append the name to the result vector. After that, all you need to do is to sort the vector alphabetically, a function that all languages have embeded. Most coders that failed this problem forgot about sorting the results or failed at trying to manually parse the input. Always try to use embeded libraries for parsing.
Value 250 Submission Rate 206 / 222 (92.79%) Success Rate 179 / 206 (86.89%) High Score exod40 for 249.26 points (1 mins 33 secs) Average Score 223.23 (for 179 correct submissions)
See tomekkulczynski's code for an implementation.
GoodAndBadPostmen
Used as: Division One - Level Two:
Like the easy, this problem was fairly straightforward but had the potential to be tricky. The basic idea is a greedy approach. The last constraint basically give away the problem: "Each element of black will contain at least one postman who is not in white." If you understood that constraint, you probably knew how to solve the problem.
Value 500 Submission Rate 149 / 222 (67.12%) Success Rate 68 / 149 (45.64%) High Score fpavetic for 461.27 points (8 mins 22 secs) Average Score 331.59 (for 68 correct submissions)
First, we mark every postman in white as good. Then, we iterate each element of black and if there is exactly one postman that is not in black, we add him to the set of "bad postmen" (is important not to count him, because we may get the conclusion that a given postman is bad many times in different elements of black). Appart from that, insert every postman into a set to know the total number. To wrap up, simply return as first coordinate the size of the good postmen's set, as second the size of the bad postmen's and as third the size of all postmen's set less the previous two numbers.
Check out the solution by fatit for code on this problem. To help you follow it, s1 is the set of good postmen, s2 is the set of non-good (bad or unknown) postmen and bad is the set of bad postmen.
AcidRain
Used as: Division One - Level Three:
I've said it before, but it bears repeating: This problem was difficult. Not so much for the ideas that were needed, but because there was a lot of code to be written and a couple of little details to take care of.
Value 1100 Submission Rate 8 / 222 (3.60%) Success Rate 2 / 8 (25.00%) High Score fatit for 580.13 points (34 mins 12 secs) Average Score 509.82 (for 2 correct submissions)
Looking at the 10 upper bound for the x coordinate immediately got many coders thinking of an exponential solution, which was indeed what was needed. Since you can only place a cover with integer endpoints, it's clear that covering the rain at all integer points in the range is enough.
The first part of the problem was doing some parsing, and getting [B,E] to [0,E'] by performing a translation substracting B from every element of both b and e. From now on, E = E'. Now, we see that we have to cover the E-1 points 1,2,..,E-1. We will define a function f that, given a subset of those points and a height, calculate the best way to block the rain that is falling exactly at that subset of the points and at the given height. Clearly, the answer of the question is f(ALL,maxy) where ALL means the entire set {1,..,E-1} and maxy is the maximum y coordinate.
The base cases shouldn't give you much trouble. It's clear that f(empty,Y) is 0 for any Y and f(X,0) is invalid for non-empty X. We'll set f(X,0) to infinite to make it work (this trick of setting to a worse than anything value the invalid cases works in almost every DP or memoized recursion).
Now, we have to see how to calculate f(X,Y) for a non-empty X and a postive Y. First, take the actual configuration of shields at that height. Each configuration can be expressed as a subset of {0,...,E-1} where a belongs to the set if and only if there is a piece of shield in the segment [a;a+1] (we'll represent this set with a boolean vector S of E positions numbered 0,...,E-1). Iterating all existent shields, keep only those with height exactly Y and iterate each segment and for each segment b-e set S[b]=S[b+1]=...=S[e-1]=true. That gives the current configuration. Now, iterate all possible configurations (every superset of that represented by S) and for each configuration calculate which points will have water falling once it passes the current height (you know which points drop water on top of that configuration by looking at X). The overall cost of a given configuration is C+f(NX,Y-1) where C is the number of shield segments that are not in the current configuration (the added shields) and NX is the set of points in which the water will continue to fall. Take the minimum of those for all possible configurations and you are done.
The runtime analysis for this says that you have a range for f with 2E-1*maxy and at each place you need to try at most 2E configurations getting to an overall runtime of 22*E-1*maxy. maxy can be pretty big, but since the order is the only thing that matters, you can remap every Y coordinate to a number between 1 and 50 and then get the algorithm to run on time by memoizing the function. The remapping can be done simply with the following C++ code (or pretty similarly in other languages):
set<int> ys; for(int i=0;i<y.size();++i) ys.insert(y[i]); int j=0; for(int j=0;!ys.empty();ys.erase(ys.begin()),j++) for(int i=0;i<y.size();++i) if (y[i]=*ys.begin()) y[i]=j;For an example of code with an iterative approach see any of the solutions by the winners:
- fatit's solution.
- TICKET_112022's solution.
