A week with different analysis approaches

Before we turn to this week’s events, let’s come back to Qualification Round of Google Code Jam from last week that I’ve somehow forgot to mention (problems, results, top 5 on the left, analysis). The round has lasted for 27 hours and the time of submissions did not matter for qualification, but some contestants still tried to be as quick as possible – congratulations to kyc on being the fastest!

The Code Jam has continued this week with Round 1A (problems, results, top 5 on the left). This time one needed to be fast or solve all three problems in order get into the top 1000 and advance.  Sergey ‘Burunduk1’ Kopeliovich has demonstrated really impressive speed by solving all three problems in just 23 minutes – awesome job!

There were also plenty of other contests this week. On Tuesday, Codeforces Round 299 (problems, results, top 5 on the left) challenged everybody with some tricky-to-get-right problems – a lot of solutions have failed the system test, including two of myself. Problem C has highlighted one of the beautiful, if a bit standard, ideas of transitioning an algebraic problem into a geometric one.  Several duathletes are competing in a swimming+running duathlon. You know the swimming speed and the running speed of each duathlete, but you don’t know the swimming distance nor the running distance. Which duathletes could win or at least share the first place for some combination of swimming and running distances?

VK Cup 2015 Round 2 was also hosted by Codeforces (problems, results, mirror results, top 5 on the left). The “Never Sorry” team took matters in their own hands this time, being the only team to solve all problems and adding 5 challenges on top of that – amazing! Of course, this is still an early round and the real battle will be at the onsite competition in July.

SRM 656 was TopCoder’s event of the week (problems, results, top 5 on the left). baklazan4247 was the only contestant able to solve the hardest problem correctly, but that was not enough for the first place as he skipped the medium difficulty problem, and xudyh did not, solving it in just 8 minutes and earning the 3000+ "target" rating as the result - congratulations! He seems to have a blog in Chinese telling about his programming contest experiences, but the auto-translated version doesn't seem terribly accurate :)

And finally, the Open Cup Grand Prix of Three Capitals took place on Sunday (results, top 5 on the left). Problem F is a very nice example where using randomized algorithms is much more appropriate than deterministic ones. It went like this: you are given n 4-tuples of points on the plane, and m rectangles with sides parallel to coordinate axes. For each rectangle, you need to check if it contains exactly 2 points from each 4-tuple. In other words, if there’s at least one 4-tuple with 0, 1, 3 or 4 points inside this rectangle, then its answer is “No”, otherwise it’s “Yes”. Can you see how randomness makes this problem easy? On the other hand, can you see a deterministic solution?

Also last week in an offline discussion with Maxim Buzdalov, we’ve brought up the following topic: what’s the best way to do problem analysis at ACM ICPC training camps? The Russian “golden standard” of Petrozavodsk is to use chalk and blackboard to explain the main idea of the problem solution on the stage live, also recording the explanation on camera for future reference. Maxim has advocated for a slightly different approach, used for example at the NEERC: work through the analysis in advance, preparing a presentation with one or two slides per problem listing the key points  then talk through them during the actual analysis. The blackboard analysis tends to be more connected with the audience, since they feel as if they’re creating the solution together with the presenter, and thus are more likely to suggest fixes and improvements; it also requires comparatively little preparation from the presenter.  At the same time, the presentation helps a lot in case the presenter’s or the contestant’s English is not very good so verbal communication is much less effective, and it also leaves a much more convenient reference to use later compared to the video recording; the greater advance preparation makes it easier to avoid incorrect solutions and to present different approaches. Which way do you prefer? Vote at my Google+.

Thanks for reading, and see you next week!