|
Match Editorials |
Saturday, August 16, 2008
Match summary
Only 79 highschoolers participated in the match. They were faced with rather standard problem set, without any tricky problems. Somewhat unexpectedly, almost the same number of coders correctly solved the medium and the hard problems. crazyb0y won the round thanks to the fastest submission on the easy and not much slower one on the hard along with two successful challenges. Jby_Yeah and boris.grubic rounded up the top three.
The Problems
ProblemSetter
Used as: Division One - Level One:
Value 250 Submission Rate 70 / 79 (88.61%) Success Rate 64 / 70 (91.43%) High Score crazyb0y for 246.20 points (3 mins 32 secs) Average Score 191.41 (for 64 correct submissions)
This problem was just a simple simulation of the process described clearly in the statement. We have to check all triples of problems and choose the one which is the best for our purposes. The only thing to remember is to search the triples in the correct order so we choose the triple with the easiest easy, the hardest hard and the easiest medium possible. Of course we can also check the triples in any order by using tie breaker explicitly, but that requires much more effort.
SegmentDisplay
Used as: Division One - Level Two:
Value 500 Submission Rate 42 / 79 (53.16%) Success Rate 27 / 42 (64.29%) High Score bbi5291 for 467.92 points (7 mins 32 secs) Average Score 330.71 (for 27 correct submissions)
What do we have here? We have some number of segments and we know how many segments we need for each digit. The standard option is to choose any digit for the first position and try to make the rest of the number with the rest of the segments. With dynamic programming we can count how many numbers can be formed with different numbers of segments. The intuition seems to be very easy. If A(k) denotes how many different numbers can be formed with k segments and we choose a digit that needs p segments, then the rest of the number can be formed by A(k - p) ways. So to calculate A(k), we should just check all the possibilities for the first digit and sum up all the ways. The only tricky part were the leading zeros, but it didn't melt up things much. See the fastest submission by bbi5291 for a reference.
NumberPartition
Used as: Division One - Level Three:
Value 1000 Submission Rate 30 / 79 (37.97%) Success Rate 26 / 30 (86.67%) High Score sim40_sh for 923.48 points (8 mins 19 secs) Average Score 656.17 (for 26 correct submissions)
This problem wasn't much more complicated than the previous one. The first thing we should concern is how to count how many different partitions there are for a given number. The approach for this part of the problem is almost the same as in the medium. If we're partitioning number p, we have to choose the smallest number in the partition. It may be any number between 1 and p, inclusive. If we choose q, then the rest of the parition will be the partition of p - q with the smallest number being bigger than or equal to q. Quite standard two-dimensional dynamic programming solution will solve the problem for us. Let A(p, q) denote the number of different partitions of p with the smallest number in each partition being at least q. Then, of course
A(p, q) = sum for all i from q to p ( A(p - i, i) )Ok, so we know how to count different partitions of a given number. Now we want to costruct them. That's also not so hard. We have to determine the first number in the partition. We know how many partitions there are that have 1 at the first place, how many have 2 at the first place and so on. So we know in which group is the k-th one we're looking for. As we know the first number, we know which partition from those that have the same first number is the one we're interested in. We just have to subtract from k the number of partitions that have smaller first number. Now, if we subtract this first number we found from n, we are left with smaller problem and we can solve it in exactly the same way. See a nice and clear implementation of the above by crazyb0y for a reference.
The alternative way of solving this problem is to note that k can't be big (the limit is 1,000,000, and in fact the number of partitions when n=50 is even less - 204,226). So we can implement recursive brute force algorithm which generates absolutely all partitions and stop it when k of them were generated.
