Monday, December 5, 2016

A maze week

Last week was quite a bit calmer than its predecessors. On Monday, Code Festival 2016 wrapped up the festivities with its Grand Final (problems, results, top 5 on the left, online mirror results, analysis). It was W4yneb0t's day, as he managed to deny tourist a somewhat expected victory by solving the same amount of problems, but a more expensive set of them. Big congratulatons!

I did not cover a lot of ACM ICPC regionals this season, but now is a good time to start :) ACM ICPC 2016-17 NEERC took place on Sunday in St Petersburg, Barnaul, Tbilisi and Almaty (problems, results, top 5 on the left). One of the main events of the year for most of ex-USSR algorithmic competition community, and the main event of their entire algorithmic competition career for many teams who practice for multiple years for this one chance to advance to the World Finals. One can experience a very wide spectrum of emotions just by watching the NEERC award ceremony where some teams are full of joy and are not at all shy to share that moment with everybody, while others ruminate over the far-reaching consequences of just one bad day. Nevertheless, the community stays very close and friendly, and kudos to everybody for keeping the spirit going! And last but not the least, congratulations to the team SPb SU Base on the victory!

Problem I was left unsolved in the onsite competition, and it's a pity since I find it really beautiful. It's an interactive problem where your program explores a maze with at most 20 rooms which look exactly the same. Each room of the maze has the same amount m (also at most 20) of outgoing one-way passages which also look exactly like one another, arranged in a circle. The only way not to get completely lost in this maze is to use the fact that each room also has a movable rock. Initially there's a rock is in the center of each room. When you leave a room, you can put the rock next to any outgoing passage, and moreover, you can choose whether to put it to the left or to the right of this passage (that means that there are 2m ways to put it). If you ever arrive in this room again, you will see whether the rock is placed to the left or to the right of a passage - but since all passages look the same, you won't have any other information! So now you will be able express the number of the passage to take, and the number of the passage to move the rock to by the number in clockwise order starting from the one marked with the rock when you arrive. Your goal is to visit all rooms in at most 20000 steps.

The problem statement is quite abstract, so I encourage you to read in full in the PDF (problem I), especially the sample input/output. After you understand what's going on, however, I find it really exciting to solve!

In my previous summary, I have mentioned a CERC problem that had to do with bipartite matchings. 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 240 total sets) with total weight exceeding the given threshold t.

I won't describe its detailed solution, but I will mention the main idea that makes this problem tractable. At first sight, we have 240 sets which is way too much to handle one-by-one. However, it turns out that a set s consisting of some set x of vertices of the first part and some set y of vertices of the second part can be covered by a matching if and only if both x can be covered by a matching and y can be covered by a matching (but those don't have to be the same matching)! This idea allows to reduce the number of sets to consider to 220, which is tractable.

Thanks for reading, and check back for this week's summary! 

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 resultsanalysis). 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 240 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 1018. 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!

Sunday, December 4, 2016

An and-clique week

The Nov 14 - Nov 20 week was busier. TopCoder SRM 702 on Tuesday was the last chance to practice before the TopCoder Open weekend (problems, results, top 5 on the left, analysis). xudyh won the second SRM in a row, and was the only one to solve all three problems. Congratulations!

The onsite event of TopCoder Open 2016, one of the main tournaments of the year, started with Semifinal 1 on Saturday (problems, results on the left, analysis by Bruce). Top 3 advanced to the final round next Monday, and everything was essentially decided by the speed on the 500-pointer. The problem statement was extremely simple: one needs to construct any weighted directed graph with at most 20 vertices that has exactly the given amount k of different minimum cuts. k is up to 1000.

Open Cup 2016-17 Grand Prix of Dolgoprudny took place early on Sunday (problems, results, top 5 on the left). Team Past Glory retook the ground they lost to ITMO 1 in the overall standings a week ago - well done!

Finally, TopCoder Open 2016 Semifinal 2 determined 3 more finalists (problems, results on the left, analysis by Bruce). Unlike the first semifinal, which went more or less normal, this round was very unusual. For the first 10-15 minutes none of the participants, and almost none of the observers, could figure out how to solve the easiest 250-pointer problem. Because of that, the advancement in this round hinged on the ability to give up on a problem and clear one's head before the next one. It's worth mentioning that the 500-pointer was also in no way obvious. Congratulations to Enot on successfully navigating the tricky round and coming out on top!

Here's the problem that puzzled everybody. You are given 1000 positive integers up to 1018. 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.
Can you see the key solution idea?

In my previous summary, I have mentioned an easy problem: you are given an n times n grid of uppercase English characters, where n is at least 3. This grid was built in the following way: first, we fill it with n different characters in such a way that each row and each column has exactly one occurrence of each character. Then, we replace exactly one character in the entire grid with another character. Your goal is to figure out which character has been replaced, and what was there originally.

Here's a solution that's very easy to implement. First, we count the number of times each letter appears in the grid, and find letters that appear at least twice. Those are the original letters. Then, for each row and column of the grid we check if they contain at least one appearance of those letters. We will find exactly one row and exactly one column that will be missing one of those letters - and those are precisely the row, column and letter that we need to output.

Thanks for reading, and check back later for more!

Saturday, December 3, 2016

A cosplay week

The Nov 7 - Nov 13 week woke up late with AtCoder Grand Contest 007 on Saturday (problems, results, top 5 on the left, analysis). The problemset seems quite well-rounded, offering competitors a choice of different strategies. cospleermusora has figured out the winning strategy this time - start with the three hardest problems since they're worth a lot more points, and then solve whichever easy problems there's time for. Great idea and execution!

Open Cup 2016-17 Czech Grand Prix took the usual Sunday spot (results, top 5 on the left). The ITMO 1 team won again and started to create quite a gap at the top of the overall standings. Amazing performance!

Problem J in this round was very easy, and yet it required some thinking to avoid too many special cases in code. You are given an n times n grid of uppercase English characters, where n is at least 3. This grid was built in the following way: first, we fill it with n different characters in such a way that each row and each column has exactly one occurrence of each character. Then, we replace exactly one character in the entire grid with another character. Your goal is to figure out which character has been replaced, and what was there originally.

In my previous summary, I've mentioned an interactive Open Cup problem: the judging program has a hidden non-degenerate triangle. The coordinates of its vertices are integers not exceeding 1000 by absolute value. You're allowed to make at most 1000 queries, and your goal is to determine the coordinates of the vertices of the triangle. In each query, you choose a line (more precisely, a half-plane), and you're told the areas of the two parts this line splits the triangle into (one of them can be 0 if it doesn't intersect the triangle).

Here is the solution of our team, which we've created together with Michael Levin: first, we figure out the bounding box of the triangle, using binary search with horizontal and vertical half-planes. At least one of the corners of the bounding box is a vertex of the triangle, which we can find using a 45-degree half-plane which cuts off just one small corner from the bounding box.

When we know a vertex and a 90 degree angle containing the rest, we can use binary search by angle using lines passing through this vertex to find the lines containing the two sides. Finally, we can find the remaining two vertices by binary searching along one of the lines with half-planes parallel to the other line.

This solution has 4 steps, with the first and last step sharing the same binary search problem (given a direction, find the first half-plane with this direction that has non-zero intersection area), so one needed to implement 3 different functions for the interaction. On the good side, the solution doesn't have any special casing at all.

Do you know a simpler approach?

Sunday, November 20, 2016

Yet another triangle week

The first November week included the fifth stage of the 2016-17 Open Cup, the Grand Prix of Siberia (problemsresults, top 5 on the left). Team Havka-papstvo dominated the proceedings, and topped the cake with the only passing solution for the very tedious problem 10 - congratulations!

I'd like to highlight the interactive problem 3, which turned out to be the second most difficult. The judging program has a hidden non-degenerate triangle. The coordinates of its vertices are integers not exceeding 1000 by absolute value. You're allowed to make at most 1000 queries, and your goal is to determine the coordinates of the vertices of the triangle. In each query, you choose a line (more precisely, a half-plane), and you're told the areas of the two parts this line splits the triangle into (one of them can be 0 if it doesn't intersect the triangle). There are two steps to solving this one: figuring out how to do it, and then figuring out how to do it in such a way that the implementation isn't a nightmare :)

In my previous summary, I've described another triangle problem: you are given 200000 points on the plane which are guaranteed to be randomly placed within a bounding box, and need to find three points which form a triangle with the largest area.

The solution is surprisingly straightforward: we find the convex hull of the given points, and then try all triangles with vertices from the convex hull to determine the largest one. It is correct because it's not hard to see that when we fix 2 out of 3 vertices of the triangle, the third one needs to be as far from that line as possible, which means it's a farthest point in some direction, which means it's a vertex of the convex hull. And it is fast enough because it turns out that a set of random points has only O(logn) points on average on its convex hull (see this paper).

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

A triangle week

The last week of October was relatively busy. First off, TopCoder SRM 701 took place on Wednesday (problems, results, top 5 on the left, analysis). The top 3 could be a foreshadowing for the upcoming TCO 2016 Semifinal 2, but unfortunately xudyh could not make it to Washington (does anybody know why?). Nevertheless, congratulations on the SRM victory!

Then, AtCoder held its Grand Contest 006 on Saturday (problems, results, top 5 on the left, analysis). apiad has dominated the field by being the only one to solve all problems, and he has also demonstrated an unorthodox strategy by starting from the hardest problems - so he would've been first even if he didn't finish the 3 easier ones!

And finally, Open Cup 2016-17 Eastern Grand Prix took place on Sunday (problemsresults, top 5 on the left). SPb ITMO 1 team has jumped into a big lead in the overall standings after this round - congratulations!

Problem B was on the boundary of "oh, beautiful observation" and "oh, nasty trick" :) Which feeling does it leave you with? You are given 200000 points on the plane which are guaranteed to be randomly placed within a bounding box, and need to find three points which form a triangle with the largest area.

Thanks for reading, and check back soon for the November news!

A Canada week

The Oct 17 - Oct 23 week featured just the Canada Cup by Codeforces (problems, results, top 5 on the left, analysis). If not for challenges, just 5 points would've separated eatmore and tzupengwang - congratulations to both! I could not make this round, so I don't have anything to share about its problems.

Check back soon for the hopefully longer summary of the following week :)