Algorithm Semifinal Room #2 - 06.27.07 9:00 PM EDT
3:49 - the competitors have already been given some time to prepare their computers for the battle. We're at ten minutes before the start.
3:53 - the competitors are being called up for the pre-contest lineup announcement.
3:57 - no announcement yet. Will it run in time?
3:58 - the announcement has been canceled, the competitors proceeded to the stage. The round starts soon.
4:00 - GO, GO, GO!
4:02 - the easy is a geometrical problem, and those are never too easy. Although this one is pretty straightforward. Let's hope precision will not be an issue today.
4:05 - the medium is a probability problem. Once you get acquainted with the statement it should not be too complicated to code, as the idea is pretty straightforward.
4:07 - 243.26 for tomek on the easy. I expect him to blaze through the medium as well. The hard may become a decider in this round.
4:16 - bladerunner starts the pursuit. Meanwhile, the discussion on the hard has led to the following outcome: it should finally be reducible to bipartite matching (i.e., for some k the k first elements should have the same match quality, and the next should have a greater match quality - that gives us the graph for the matching. That way we check if some prefix of the solution can be completed. I understand this is not even a solution sketch, but still :))
4:21 - more on the hard: practically, we need to iterate over all possibilities to split candidate into three parts: those elements that stay in place, those that get replaced but keep the same match quality, and the remaining ones. Having fixed such a split, we get a bipartite matching problem when checking if such a split is possible. Having written the possibility function, we get the answer by calling it for the increasing answer prefixes. These two steps can probably be bundled together to increase the speed, too. Generally, this problem will require a lot of accuracy but still seems to be doable during the round.
4:24 - VitalyGoldstein submits the medium and takes the lead.
4:25 - marek.cygan has submitted the easy, too.
4:29 - Andrew_Lazarev suggests that the medium seems to include some nasty difficulties when some following player has equal probabilities of winning regardless of her decision. Or will this never happen?
4:31 - tomek regains the lead by submitting the medium.
4:40 - Olexiy helped to resolve the aforementioned difficulty by pointing out the important constraint: "The probabilities of a contestant winning if they decide to stop or spin again will differ by at least 1e-6, unless both probabilities are zero." So this is not an issue here.
4:46 - bladerunner has submitted the hard, but his solution seems not to take care of the case when some match qualities are equal. The examples don't test anything, so the solution can easily be wrong.
4:47 - marian has submitted the easy. No resubmits as of yet.
4:50 - I stand corrected by Quelloquialism, jakubr has resubmitted his 250. Meanwhile, marek.cygan and tomekkulczynski have submitted the medium. tomekkulczynski is still struggling with the easy, though.
4:52 - either we don't understand something fundamental, or abikbaev's solution is wrong as well.
4:55 - This contest seems to be balanced much better than the previous one. I like that.
4:56 - Although, as Vedensky pointed out, if the hard proves to be too difficult, the challenges will get too much weight.
4:59 - I believe tomek to be the main favorite today regardless of (possibly) upcoming hard submissions.
5:06 - all the five submissions on the hard look alike. We are probably missing something and the problem is really easier than it seems.
5:07 - or they all are missing something.
5:09 - at least misof's seems to be wrong for sure. Probably we can try to construct a testcase to fail it?
5:12 - these submissions constitute a great ground for an interesting challenge phase.
5:13 - the Arena discussion has come to the conclusion that tomek has missed an 'r' in the easy problem, whatever it means.
5:15 - and that probably puts him on the border of elimination as well. However, he still has a chance to finish his 1000 to become (probably) the only one to solve it correctly.
5:16 - another lightning-fast seemingly-wrong submission on the hard by dmytro.
5:18 - the easy problem sample tests only features +-1 circle radii. The contest seems to be very miserly with the testcases, which is quite strange for an onsite.
5:20 - tomek submits the hard. Now that's a proper solution, 3 pages of code.
5:24 - however, the 500 is the problem that gets the last submission. bladerunner, having started with the 1000, finally managed to complete all three.
5:26 - the challenge phase starts in 3 minutes.
5:27 - will somebody go blind?
5:29 - some resubmits on 250 went unnoticed. Probably it will turn out not to be so easy?
5:31 - dmytro's hard is down, a couple of unsuccessful challenges go in as well.
5:35 - tomek's hard has survived one challenge.
5:35 - the scoreboard is still very tight.
5:37 - the main remaining question is whether tomek's hard will stand. If not, he will probably even miss the wildcard.
5:38 - there were still no challenges on the medium problem - probably a lot of those will fail, too?
5:40 - a wise last-second challenge by tomekkulczynski, as -25 didn't hurt him at all. It was unsuccessful, unfortunately. The exciting challenge phase is over, let's wait for the systests.
5:43 - it is actually quite surprising that many top competitors submitted wrong solutions on the hard. Probably it's the tension.
5:45 - the systest results are ready.
5:46 - a lot of solutions fail, I can't type that fast.
5:49 - now that was unexpected. I will probably try to shed some light on why so many solutions failed later today.