|
Algorithm Semifinal Room #3 - 06.28.07 2:00 PM EDT By Petr TopCoder Member 9:40 - 19 minutes before the match, the competitors are already on the stage, and most are preparing their template code. 9:41 - they might be trying to hide the disappointment with not the very best breakfast :) 9:47 - the spectators start to gather in the Arena, too. There are 47 people in the room already. 9:49 - make that 58. 9:51 - Andrew_Lazarev has noticed quite unusual scores for the problems: 275, 450, 1000. Like the total unpredictableness of this round wasn't enough. 9:54 - Eight Russians today, including 4 SPb IFMOers. 9:55 - they're lining up the contestants again. 9:56 - the second semifinal champion Vitaliy is offering his expert advice today. 9:59 - 91. 10:03 - the easy seems to be a greedy problem - we should always do the jobs that have the most time remaining. Although this requires a bit of accuracy to implement. 10:07 - pashka has submitted the easy. His solution is even more simple than greedy - he's doing binary search on the answer, then just checking that all the tasks limited to the first x seconds give at least x*k processor time. Marvellous! 10:10 - SnapDragon, Vedensky and darnley have submitted the easy, too. 10:10 - the 450 problem seems to be quite simple DP - what is the maximal achieveable lcm when using the powers of first k prime numbers, and having the cost of s. 10:13 - Revenger, ploh and andrewzta submit. 10:14 - however, determining the maximal required cost might be a little tricky. 10:16 - and here goes bmerry. 10:17 - still nobody has opened the hard problem. The spectators are getting anxious to see it. 10:21 - Andrew_Lazarev didn't use that DP, he is doing "what is the minimal possible sum to get lcm r with n first numbers". The state space is bigger, but it seems like that works, too. 10:23 - Andrew_Lazarev and tmyklebu have submitted the 450. 10:25 - tmyklebu seems to be using the DP I suggested. 10:29 - not sure if tmyklebu's checking the numbers up to 37 is enough. LCM(1,2,..,37)=5342931457063200>10^15, but does that guarantee that no larger numbers will be required? 10:31 - nicka81 and HiltonLange submit the 275, darnley resubmits it. Let's read the hard problem. 10:35 - Vedensky and tmyklebu have two problems submitted already. 10:35 - ainu7 provided a testcase that seems to require number 59 in the medium: 2^7 3^3 5^2 7 11 13 17 19 23 29 and 10^15. To quote him: "10^15 / (lcm of that numbers) = 53.xxx, and single number 59 will be enough." So tmyklebu's (resubmitted) code and Andrew_Lazarev's code are wrong. 10:39 - bmerry, pashka and andrewzta submit the medium, too. 10:39 - the hard seems to be doable today. As ivan_metelsky has noticed, there're no more than 3^10 reachable boards, and thus one should only accurately do the game analysis. 10:46 - ploh submits the medium, too. He's using the primes up to 59, that passes the worst currently known testcase, put probably there are worse ones? 10:47 - Andrew_Lazarev submits the easy. Now 7 people have the first two, 5 people have only the first, and 4 still lack submissions. 10:51 - bmerry has memoization commented out in his 450. Was that intentional? 10:54 - half an hour left. Waiting for the 1000 submissions to pour in. Generally, the round flow seems to be quite standard. 10:56 - still no luck for ainu7 with inventing a tougher testcase in the Arena. 10:58 - I believe memoization might not be really necessary here, so bmerry should be safe. 11:02 - finally a testcase seemingly requiring 61 from ainu7. Too bad for ploh. 11:03 - ardiankp has noted that "initial LCM of bmerry's solution might overflow". Seems so. Will this round end up also having most people with only one problem? 11:05 - a 67 testcase exists as well. 11:07 - falagar and ltdtl submit their mediums after about 20 minutes of no submits. 11:08 - 11 people have compiled the hard. 11:09 - Revenger submits the medium. 11:11 - and even the 14-th placed darnley could become first if he submits the 1000. Pretty close race. 11:14 - finally a submission from Gluk. 11:14 - all the coders trying to do the 1000 might make it difficult for them to challenge 450s, and challenging 450s might turn out to be a better strategy here. 11:16 - bmerry and darnley submit the hard, and gain the top two spots. bmerry will even remain first without his 450. 11:16 - and he gets a chance to find his bug and resubmit now. 11:17 - finally a submission from yava, no more zero scores. 11:22 - any last-second drastic changes adrift?.. 11:22 - as misof has noticed, SnapDragon's chances on advancing to the wildcard with his score of 260 on the easy are quite good. 11:24 - tmyklebu submits the hard to regain second place. 11:25 - Andrew_Lazarev resubmits the medium, but changes the limit from 50 to 40. Wrong way. 11:25 - the coding is over. 11:29 - darnley still didn't open the medium. Is he planning not to challenge it? 11:29 - challenge phase starts! 11:30 - pashka's 450 is down, as is tmyklebu's 1000. andrewzta's 450 is down, too. 11:30 - Andrew_Lazarev's 450 is down. The two remaining 1000s survived several challenges. 11:32 - ltdtl's 450 is down. 11:33 - bmerry's 450 is down. At least that was expected. 11:34 - tmyklebu's 450 is down, too. 11:35 - yava's 450 is down, too. +150 for nicka81. 11:36 - falagar and Revenger lose their mediums, too. Will any 450 stand? 11:40 - darnley has challenged pashka's 250 in the last seconds. I expect some more 250s to fail during the systest. darnley says it was a precision issue. 11:44 - the systests are in. 11:45 - no passing submits for the bottom 7, ok for 250 for the 9th. 11:46 - bmerry and darnley in the finals, ploh, Vedensky, nicka81 and SnapDragon in the wildcard. 11:55 - easy and hard for the finalists, easy and medium for the first two wildcarders, and only easy for 3 more people. Quite good distribution, although there're only 9 positive scores, and 2 of those only because of challenges. 11:58 - ploh's wrong solution wasn't caught by the systests, but that made no difference as he would be in the wildcard anyway. 11:59 - join us today at 4:00 PM PDT at petr.mitrichev.ru/r4.html for the live coverage of the wildcard round. 12:04 - it turns out that andrewzta's and pashka's 250s (and probably some more) have failed due to floating-point precision issues. Long story short, when finding a zero point of a monotonic function by binary search, and when that function is zero on a whole segment, one should use EPS to find the rightmost zero (as was required in this problem). Doing binary search without any EPS will yield you to some zero point, but not the rightmost one. |
