Wednesday, July 24, 2024

# Algorithm Semifinal Room #2 - 06.27.07 9:00 PM EDT

By Petr
TopCoder Member

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:55 - tomek and misof are the odds-on favorites, but I expect the others to give them a fight.

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:19 - jakubr, msg555 and gawry are in the race.

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:28 - Vitaliy and Astein have submitted the easy.

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:33 - misof and dmytro are also in with the easy. I'm quite surprised there's still that few submissions.

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:51 - abikbaev with another hard, gawry with the medium.

4:52 - either we don't understand something fundamental, or abikbaev's solution is wrong as well.

4:53 - misof and msg555 with the medium. misof now has the highest score on it.

4:54 - by "we" I mean Petr, andrewzta, pashka, Andrew_Lazarev, Vedensky. This commentary team was at some point supported by bmerry and SnapDragon, too.

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:58 - Astein and Vitaliy go with the medium. The contestants are starting to gather around the hard :)

4:59 - I believe tomek to be the main favorite today regardless of (possibly) upcoming hard submissions.

5:00 - and andrewzta reports that tomek is on the right track in the hard, he already has a bipartite matching function header.

5:03 - a submission on the medium by gevak. abikbaev has resubmitted his hard, although seemingly with no effect - still wrong.

5:04 - misof, VitalyGoldstein and marek.cygan come unexpected with ridiculously fast hard submissions. Let's see what they have.

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:21 - Astein's submission on the hard is somewhat in between misof's shortness and tomek's rightness. I still believe it will be either nobody, or only tomek.

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:25 - abikbaev takes the last submit prize from bladerunner with his 250.

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:30 - abikbaev's 250 is the first to fail, too. gevak the challenger returns :)

5:31 - dmytro's hard is down, a couple of unsuccessful challenges go in as well.

5:32 - VitalyGoldstein and misof forfeit their hards. It seems we were right.

5:33 - marek.cygan and abikbaev lose their hards as well. tomekkulczynski seems to be the most active challenger.

5:34 - jakubr adds Astein and bladerunner, while marek.cygan challenges Astein's 250.

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:45 - marian and jakubr pass, gevak fails.

5:46 - a lot of solutions fail, I can't type that fast.

5:46 - Vitaliy and tomekkulczynski in the finals.

5:47 - tomek, gawry, bladerunner and marek.cygan in the wildcard.

5:48 - Vitaliy has the easy and the medium, tomekkulczynski, tomek, gawry and bladerunner have only the medium, marek.cygan, jakubr, msg555, dmytro, misof and marian have only the easy.

5:49 - now that was unexpected. I will probably try to shed some light on why so many solutions failed later today.