A Makoto week

TopCoder Open 2016 Final fell on the Nov 21 - Nov 27 week (problems, results on the left, analysis by Bruce). The final results have all finalists sorted by rating, with one notable exception: rng_58 has completely dominated the field, already winning on the first two problems but also adding the 1000-pointer to make it clear that others don't stand a chance. Extremely well done! With this result, Makoto is 3 out of 3 for TCO finals.

Here's what the 1000-pointer was about. You are given an undirected graph with at most 14 vertices. You make at most 50000 copies of this graph, without any edges between them, to obtain a bigger graph (with at most 14*50000 vertices). Then, you replace the resulting graph with its complement: for each pair of vertices connected by an edge, you remove that edge, and for each pair of vertices that don't have a connecting edge, you add one. How many Hamiltonian paths does the complementary graph have, modulo 998244353?

Codeforces resumed its contests after a month-long break with Round 381 on Wednesday (problems, results, top 5 on the left, analysis). TooDifficult continued his streak of victories, adding this round to the last two TopCoder SRMs. Amazing consistency!

On Saturday, a brand new international onsite competition called Code Festival and ran by AtCoder took off in Tokyo. It has featured a diverse set of competitions, with the Code Festival 2016 Final being the closest to traditional rounds (problems, results, top 5 on the left, online mirror results, analysis). Only current and recent university students were allowed to join, nevertheless the field was top-notch. Facing very tough competition, tourist rose to the challenge and won in style by being the only one to solve all tasks. Congratulations!

Open Cup 2016-17 Grand Prix of Europe on Sunday has completed the run of 5 consecutive Open Cup weekends (problems, results, top 5 on the left, CERC results on the same problems, analysis). This time ITMO 1 was head and shoulders above everybody, winning 11-9 (11-10 if you take CERC into account) - really unbelievable result! My team in particular got stuck after solving 8 problems in 3 hours, and couldn't solve any of the remaining 4 tasks in the last 2 hours. Also notable is Makoto solving 9 problems single-handedly. He was really on a roll that week :)

Problem B in this round relied on a sound yet not widely known theoretical fact. You were given a bipartite graph with at most 20 vertices in each part (40 together). A set s of its vertices was called nice if there existed a matching that covers it - in other words, such that for every vertex from s there was an adjacent edge that belongs to the matching. Note that it's not necessary for each end of the matching edges to be in s. Each vertex also had an integer weight. Your goal was to count the number of nice sets (out of at most 2⁴⁰ total sets) with total weight exceeding the given threshold t.

Finally, Codeforces Round 382 wrapped up the week on Sunday night (problems, results, top 5 on the left, analysis). The coders in places from 3rd to 5th could've grabbed the first place if they could simply finish solving all problems in time, and that seems to have been quite doable, with more than 30 minutes left for Haghani and overtroll, and more than an hour left for MainDullMoeHand for just one problem - but they couldn't, and jcvb submitted his last problem with just 5 minutes to go to claim the victory. Well done!

In my previous summary, I have mentioned the problem that threw TCO 2016 Semifinal 2 into turmoil. You are given 1000 positive integers up to 10¹⁸. You need to find any subset of those integers with the following two properties:

1. Bitwise and of all integers in the subset is zero.
2. For any two integers in the subset, their bitwise and is not zero.

The problem statement sounds so simple, and yet the solution is very hard to spot, so let me describe it. Since the bitwise and of all integers in the sought subset is zero, for every bit (position in the binary representation) at least one of the numbers in the subset doesn't have it set. Here comes the key idea: if there exists any such subset, then there exists such subset and a bit such that exactly one of the numbers in the subset doesn't have this bit set. Why? Because when for each bit at least two numbers don't have it, we can remove any number from the subset without violating properties 1 or 2.

Now the problem becomes polynomial instead of exponential. Let's iterate over which bit will be present in all numbers except one, and which number will not have it. Which other numbers could we take into the subset? The numbers that have the chosen bit set and also have non-zero bitwise and with the chosen number. Property 2 will then always hold since all of those numbers have the chosen bit and thus non-zero bitwise ands, And for property 1, more numbers is always better, so we can afford to just take all numbers described above! We just need to check if their overall bitwise and (together with the first chosen number) is zero, and if yes, we have found our answer.

One reason this solution seems quite hard to spot is that it operates in a counter-intuitive manner. On the first step, we're reducing our subset to achieve the desired property. But on the second step, we're actually expanding it back.

Thanks for reading, and check back soon for the last week's summary!