|
Algorithm Wildcard Round - 06.28.07 9:00 PM EDT By Petr TopCoder Member 3:49 - ten minutes before the start of the wildcard round. As usual for the wildcard, the competition is even tougher than that of the semifinals. Good luck to all contestants! 3:55 - as always, andrewzta will be helping me today. 3:56 - in fact, the wildcard is probably the most intense competition here. When people lose in the semifinals, some of them get a second chance. When people get to the finals, they are really competing at the best level they can, and nervousness steps away. But in the wildcard, people get more nervous than ever, as many of them feel they 'should' get to the finals. 4:01 - the competition has started. 11 competitors read the easy, tomek reads the hard. 4:08 - the easy problem is finding the inverse of a power series, which is achieved by applying simple formulas, and the only difficulty is that the answer is expected to be presented precisely with fractions. JongMan has already submitted it. 4:11 - another concern here might be intermediate values not fitting long long bounds, but that seems to be impossible given the answer's numerator and denominator are bounded by 100000 and all the denominators are obtained from the powers of start[0] (and thus the common denominator will not be too big). 4:14 - marek.cygan, gawry and SnapDragon have submitted the easy, too. All the four submissions look similar. 4:16 - in fact, I don't see an easy formal proof of the intermediate numbers not overflowing long long. Just a feeling. 4:16 - bladerunner submits. 4:19 - and resubmits. 4:19 - the medium turns out to be an implementation problem. Let's see if I can find some easy way to do it. 4:20 - Ying, nicka81 and ploh submit the easy. 4:22 - I don't see anything easier than keeping track of the current 'picture' by having a set of 'important' coordinates where the thickness changes. That requires a bit of accuracy and involves some corner cases, but is not too difficult after all. 4:24 - liympanda and lovro have also submitted the easy. 4:26 - SnapDragon has compiled some clever solution for the 550. He has noted that one can actually solve two one-dimension cases (for the horizontal folds and for the vertical ones) and multiply the results. That makes the solution quite easy to implement. 4:30 - Vedensky submits the easy, Snap is in with the medium. 4:35 - tomek is the only one with zero points now. 4:35 - andrewzta suggested a solution for the hard problem. The last paragraph from the problem statement implies that every query contains a number from some of the recent adds (like the last 10), and thus we can do the following DP: what is the minimal possible cost of remaining operations, if the first k add operations were performed in such a way that the skiplist has x elements, and the subset A of the last 10 adds were added to the skiplist. The state space is n^2*2^10, and n can be as much as about 600, so this won't probably be enough. However, as Per suggested, we really don't need to keep the size of the skiplist, because the answer depends on that number linearly (i.e., is C+a*x for some constants C and a): every time we put a number in the cache, all the remaining costs increase by one. 4:46 - no submission recently. 4:50 - the medium from Vedensky, and the hard from tomek. Strangely enough, he opens the easy then. 4:53 - tomek's solution is pretty much like what we've invented here. 4:58 - gawry, ploh and lovro submit the medium. gawry and Vedensky are not compressing the coordinates - so they could probably time out, because the processing can get as long as about 800*100000 iterations. Some borderline situation here. SnapDragon, ploh and lovro do compress the coordinates. 5:02 - it seems that the situation will change soon as we see more submissions on 950. 5:02 - and nicka81 does that change. tomek has submitted the easy, too. 5:04 - nicka81's code seems to decide whether to keep an item in the skiplist with some sort of greedy procedure. I believe it should be wrong. 5:07 - Ying has submitted the 950, too. His DP dimensions look right :) 5:11 - 15 minutes to go. Will tomek submit the medium? Will SnapDragon submit the hard? 5:13 - marek.cygan submits the medium. However, he will need several challenges to get back in play. 5:16 - tomek compiles the medium, without compressing the coordinates, too. SnapDragon submits the hard, although his solution seems to be wrong in the same way as nicka81's. 5:18 - in fact, SnapDragon does some backtracking when his greedy routines don't work in some sense. A really complicated solution here. 5:19 - tomek submits the medium. 5:21 - John Dethridge has arrived. He'll be doing the webcast tomorrow. 5:21 - currently we have only 4 people not submitting the medium - nicka81 and Ying got the hard instead, and liympanda and bladerunner still didn't advance further than the easy. 5:23 - SnapDragon is using the Arena to generate some tough testcases. 5:25 - no last-second submissions this time, the coding is over. 5:25 - currently the top two are far ahead, however should any of them fail the cost of a single challenge might be immensely big. 5:30 - the challenge is underway, lovro's medium has died. 5:30 - as are gawry's and marek.cygan's. Is that TL? 5:31 - JongMan is at +100, Vedensky at +50. Still no action at the top. 5:32 - Vedensky loses his medium, too. Meanwhile, tomek gets -25. 5:33 - another fine shot by JongMan, it's ploh now. 5:33 - SnapDragon's medium is down! Even if tomek is safe, the fight for the second spot is wide open. 5:39 - little action recently. Another -25 for tomek. 5:39 - SnapDragon has left his workstation. He left a note saying his hard will fail. 5:42 - the challenge is over, waiting for the systests. 5:44 - it's JongMan and tomek in the finals, in that order. 5:44 - the problems surviving systests are: tomek's and JongMan's mediums, and all the easys except tomek's Ying's and Vedensky's. 5:46 - we're leaving now. The coverage of the finals tomorrow will be petr.mitrichev.ru/r5.html at 1:30 PM PDT! |
