This week in competitive programming

Before we dive into this week, let's finish the last week's review. Late last Sunday, SnarkNews Winter Series 2014 Round 5 came to an end (results, top 5 on the left). Unlike last round, submitting problems blindly turned out the be the best strategy in this round, and Egor easily won using it. One of the nicer problems was: you are given three bitstrings (strings of zeroes and ones) of length 100000. How many bitstrings have the same Hamming distance to all three given bitstrings (you need to output the answer modulo 10⁹+7)?

With this round, the entire Winter Series came to an end (results, top 5 on the left). tourist won with a big margin, mostly due to his flawless all-blind performances in the first two rounds.

The week proper started with two rounds on Monday. TopCoder SRM 607 (problems, results, my screencast, top 5 on the left) featured a very difficult hard problem, which nobody could solve, so everything came down to challenges. My strategy for the challenge phase was to look for incorrect DPs in the second problem, more specifically, I looked for DPs that don't seem to have "number of nested segments" as a DP parameter that can go up to 5000. This worked to find three incorrect solutions quickly, but it also had two false positives: two solutions had this parameter only go to 3000, but it turned out that they only stored the parameter divided by 10 (since the remainder of its division by 10 was reconstructable).

After a couple hours' break, Codeforces Round 228 gathered most of the same crowd (problems, results, my screencast, top 5 on the left). And exactly like in the earlier TopCoder round, the hardest problem was not solved, although this time several contestants came close, and the match results were decided on challenges. I couldn't get any, so I couldn't get into the top 5. The round had excellent problems, and I encourage you to try solving them all. Let me highlight problem D: given an integer k up to 10⁹, how many sets of non-negative integers exist such that all numbers in the set are at most k, and that for any two numbers in the set their bitwise xor is also in the set (you need to output the answer modulo 10⁹+7)?

On Thursday, the Petrozavodsk winter camp for ACM ICPC teams preparing for the World Finals came to an end (results, top 5 on the left). This amazing event is not just one contest, but rather nine contests spread over the past two weeks, together with lectures and winter Karelia sightseeing. tourist won the first place in the overall standings, ahead of the three three-person teams who will take part in the World Finals in June, but SPb SU 4 remain the main contender for the ICPC championship.

On Friday, TopCoder SRM 608 (problems, results, top 5 on the left) continued tomek's return to active participation in programming contests - and he's made it into the top 5 for the third SRM in a row. The medium difficulty problem asked an unusual question. We're given a directed graph, and the number of walks of length n in this graph is denoted as f(n). What is the smallest non-negative integer k such that f(n)=O(n^k) (big-O is explained in detail in Wikipedia)?

On Saturday, the Challenge 24 Electronic Contest (problems, results, top 5 on the left) has selected 27 teams that will join the last year's top 3 in Budapest for the actual 24-hour competition. Since my team has already qualified via placing in top 3 last year, we didn't participate. Psyho, one of the winning team's members, has shared his impressions on his blog. Bruce Merry did the same.

And finally, on Sunday, the Nothern Grand Prix of the Open Cup (results, top 5 on the left) featured a problemset from Andrew Stankevich. The problems are not published yet, and I don't want to spoil the contest for those who didn't see those problems yet, so I won't go into detail about them - I'll just say that the problemset was great, interesting and diverse.

Thanks for reading through this very long post (did you? :)), and see you next week!

P.S. I realize that I've been only writing about contest results and interesting problem statements lately, and didn't have time to explain problem solutions. I hope to get back to explaining solutions in the near future!