This week in competitive programming

Saturday night was the competition time this week, starting with TopCoder SRM 647 (problems, results, top 5 on the left, my screencast). The hard problem had a very simple and interesting statement, might've looked as a relatively straightforward maximum flow application, but it came with an unexpected twist that foiled many experienced competitors. You were given a directed graph where each arc has a cost, one of the vertices is marked as starting point, and one as ending point. You needed to pick a subset of arcs with the smallest total cost such that every path from the starting point to the ending point (including paths that pass through the same vertex or arc more than once) passes through arcs from this subset exactly once.

The idea that we can use minimum cut theory to find this subset looks natural. But just applying minimum cut algorithms on the given graph doesn't fit the bill: it is indeed guaranteed that we will cross every cut at least once when walking from the starting point to the ending point, but we might also cross a cut twice or more, and this is not allowed by the problem statement. The usual recipe in situations like this is adding auxiliary infinite arcs to the graph which will essentially limit the set of cuts we look at, since the minimum cut will obviously contain no infinite arcs. Can you see how to add infinite arcs to this graph to solve the problem?

Just a few hours later Facebook Hacker Cup 2015 Round 2 narrowed the field of competitors to just one hundred algorithmists (problems with Facebook login, results with Facebook login, top 5 on the left, my screencast). Once again, the really punishing scoring model meant making sure that the solutions are correct was more important to qualifying than solving problems fast. Nevertheless congratulations to Ivan on claiming the first place! The competition at the ACM ICPC World Finals is going to be very fierce this year.

 

Somewhat orthogonally, here are a couple of pictures from my recent touristic visit to London. Quite different skies and quite different surroundings, London is full of everything :) Thanks for reading, and check back next week!

This week in competitive programming

Contrary to last week's serenity, this week has been really busy in terms of contests. Early on Monday, Codeforces Round 285 started the sequence (problems, results, top 5 on the left). Competitors in places from second to fifth remained within one successful challenge from each other, but Boris was not within reach and achieved a commanding victory - congratulations!

TopCoder SRM 645 happened later on Monday (problems, results, top 5 on the left, my screencast). The medium problem required careful logical thinking to apply several relatively easy steps in sequence to obtain a working solution. You were given two sets of points on the plane, of the same size, which was at most 50, and also exactly three magic points on the same plane. In one step, you were allowed to pick one of the three magic points, and rotate all points in the first given set by 180 degrees with the selected magic point as the center of rotation. Note that all points are rotated at the same time and with the same center of rotation. Is it possible to obtain the second set of points via zero or more such steps from the first set of points?

TopCoder SRM 646 continued the fun early on Friday (problems, results, top 5 on the left). Tiancheng continued to show impressive form (previous post) and climbed into the 3rd spot (shared with Tomek) in all-time SRM wins stats - awesome performance, both this week and in the past years!

Facebook Hacker Cup Round 1 occupied 24 hours on the weekend (problems with Facebook login, results with Facebook login, top 5 on the left, my screencast). Of course, one didn't need to spend that much since the problems were relatively simple. The challenge, as usual with the Hacker Cup, was in the format that punishes every mistake very heavily: since the round lasted for 24 hours, many competitors who would not solve these problems in tighter time constraints got a chance to steadily work towards solving all four, and that, in turn, meant that most likely all 500 qualifying spots would be taken by people who solved everything, and thus almost any mistake could mean a good bye to the Hacker Cup. The cutoff ended up being 75 points, not 100 points, but still mistakes in solving the hardest "Corporate Gifting" problem were punished with elimination. Because of this, this round brought slightly different qualities into the limelight: testing one's solutions very carefully, the ability to read the statement without any omissions, and having a good proof for each and every mathematical solution. To put it another way, it was all about patience :)

Finally, Codeforces Round 286 ended the week late on Sunday (problems, results, top 5 on the left, my screencast). After reading all problems, I was unable to come up with an algorithm to any of the five problems, which is quite unusual for Codeforces since problems A and B are usually not that difficult. Given that all problems required thinking, I've decided that I might as well go after the one that was scored the highest, and that turned out to be too optimistic. The problem simply asked to count the number of palindromes of the given length (up to 10⁹) containing the given string (of length at most 200) as a subsequence (not necessarily as a substring - i.e. the characters don't have to be consecutive), modulo 10007.

You can see my slow progress towards a solution in the screencast: at about 37 minutes mark of the screencast, I've implemented a slow solution and automatic period detection, hoping that the answers for consecutive lengths would form a sequence with a short period - but they would not. Then, at about 50 minutes into the screencast, I came up with the idea that the slow solution can actually be improved by considering segments of palindrome before the next match of the subsequence at once, and thus separating the result into a large sum of products of powers of 24, 25 and 26 (more details probably in a later post), but after implementing this part around 1 hour 1 minute mark I've realized that I still have no idea how to quickly compute the sum I reduced the problem to. Around 1 hour 12 minute mark I've realized that this sum can be computed by taking 200 relatively small matrices to a large power modulo 10007, something we can do relatively quickly. I've finished the implementation and submitted around 1 hour 22 minute mark - only to learn that the solution is still too slow. Some more thinking led me to the idea of computing all 200 numbers I need using just one matrix power, but the matrix unfortunately became bigger, and thus the solution was still about 50% slower than needed. 1.5x was already in the 'non-asymptotic' speedup area, so I've switched to speeding up matrix multiplication, first by using the modulo operation less often, and then by taking advantage of the fact that the matrix had corners of zeroes that didn't need to be recomputed. That has finally enabled me to make a successful submission at 1 hour and 49 minutes into the contest, with too little time left to solve any other problem.

In the meantime, Ilya has solved the remaining four problems and claimed the victory - congratulations!

And finally, let me finish this post with something different: a chess puzzle! More specifically, I want to share a wonderful gem of a chess website, lichess, that provides a training area with puzzles like this one: http://en.lichess.org/training/23280.

Their idea is that since many people are playing chess against each other on their website, they can simply find "interesting" situations in those games automatically - probably when computer could see a unique sequence of good moves in a position that's losing otherwise - and present those situations as puzzles that make people learn real-world chess tactics, not just apply abstract backtracking skills. Quite fittingly, all puzzles are asking you to find the best move for Black/White, not to find a mate in three or something like that, since the former is what actually matters in real chess games. In particular, the puzzle referenced above was taken from this blitz game, where the real black player could not find the right sequence of moves and lost.

The puzzles also have the usual up/down voting buttons, so as hundreds and thousands of people are going through them, the system can become even more intelligent and suggest only quite interesting puzzles to most. The puzzle linked above and shown on the left was presented to me recently, and I've enjoyed solving it - did you?

Also, I can't help but wonder if we can come up with similar training approach for algorthmic programming based on the enourmous base of contest solutions that we've accumulated over the years.

Thanks for reading, and check back next week!

This week in competitive programming

Qualification Round of Facebook Hacker Cup 2015 took place last weekend. There was no direct competition, though, since it lasted for 72 hours and featured three relatively easy problems, and you needed to solve just one to advance to the next round, so people were not competing against one another. It still has a scoreboard (available only after logging in to Facebook), and you can see the top 5 who rushed to solve the problems as soon as they were available on the left, out of 940 contestants who solved all three.

Let's return to problem "Nanobugs" mentioned in the last week's post: you have n (at least 20 and at most 50) coins, some of which are fake. Your friend knows that either a or a+1 coins are fake (a is between 1 and 3, and is given). You know the fake coins exactly, but you don't want to reveal that knowledge to your friend. Instead you want to prove your knowledge to your friend by proving that there are exactly x (either a or a+1) fake coins without revealing the status of any particular coin - neither fake nor real. The only method you can use for your proof is a very limited subset equality testing device: it takes two non-interesecting subsets of coins of the same size, and tells whether both subsets have the same amount of fake coins or not.

I will describe the idea of the solution invented by my teammate Andrey Halyavin. First case is when just 1 coin is fake. In this case the friend knows that there are 1 or 2 fake coins. If the total amount of coins is even, then we can start by comparing one half of all coins with another half, with the result being of course that the two halves are not equal. What does your friend learn from this? One of the halves has all real coins, and another half has either 1 or 2 fakes, but he doesn't know which half, so we haven't yet revealed the status of any particular coin. Now let's continue similar comparisons, i-th comparison putting coins i, i+1, ..., i+n/2 on one side and all remaining coins on the other side. All of them will of course return "not equal" since exactly one coin is fake. Your friend still doesn't learn anything about the status of any particular coin, but the theory that there are 2 fake coins falls apart - since in that case at least one comparison would put them on different sides, and we'd get an "equal" result. So we've successfully convinced the friend that there's just 1 fake coin without revealing anything about any particular coin.

What to do if there's just one fake coin but the total number of coins is odd? It's not hard to see that the task is impossible. Every comparison has to leave at least coin aside. If that comparison returns an "not equal" result, then the coins left aside must be real, since there's just one fake coin, so we will have to reveal their status if we are to prove that there's exactly one fake coin. An if that comparison returns an "equal" result, then the coins participating in the comparison must be real.

Now let's describe a solution for the case where there are either 2 or 4 fake coins (the alternative that we want to disprove is 1 or 3 fake coins). If the total number of coins is even, then the solution is very simple: let's just split all coins into two equal sides, and compare them equal. This obviously means that the total number of fake coins is even, but we haven't revealed anything about the status of any particular coin, so we're done.

Handling the case where the total number of coins is odd is slightly more complex. Let's describe another solution for the case where the total number of coins is divisible by 5 and at least 10. We'll assemble a structure consisting of two "flowers" (pictured on the left): one (x, y) flower and one (y, x) flower. A (x, y) flower contains a center containing x coins, and four petals each containing y coins, for the total of x+4y coins. Similarly, a (y, x) flower contains y+4x coins, so we have 5x+5y coins in total. x and y can be arbitrary positive integers.

Now we'll do 4 comparisons, each comparison will put x+y coins on each side. The left side will be the center of the first flower and one of its petals, and the right side will be the center of the second flower and one of its petals. The resulf of each comparison will be "equal". First, it's not hard to see that we learn that the centers of the flowers contain the same number of fake coins: if one center had more fake coins, then the other flower must have compensated for that in each petal, and we'd get at least 4+1=5 fake coins, and we know we have at most 4. Having seen that, it's not hard to see that the corresponding petals of the flowers also have the same amount of fake coins, since they compare equal modulo the centers which are also equal. But that means that the total number of fake coins is even since we have found a match for every group with the same number of fake coins - and that mean we've proven what we needed to our friend. Note that we have not revealed the status of any particular coin: we have many ways to pick an arbitrary even number of fake coins in the centers and petals.

This solution only works if the total number of coins is divisible by 5, but we also have a solution for the case where the number of coins is divisible by 2, and both of those solutions simply prove that the total number of fake coins is even. So we can just put two such solutions side by side and achieve a solution for any n=5p+2q where p and q are at least 3, and it's not hard to see that any odd number above 20 can be represented in this manner (for example as 15 plus an even number). So we've finally solved the 2 and 4 cases completely.

The only remaining case is 3 fake coins. I will not describe the solution in detail here, but it's conceptually similar to the 2 or 4 case, but instead of proving that the total number of fake coins is even we will prove that it divides evenly by 3, using three flowers with three petals each instead of two flowers with four petals each - two (x, y) flowers and one (y, x) flower.

Thanks for reading, and check back next week! Also please share your impressions about Andrey's solution or the alternative solutions you see in comments.

This week in competitive programming

Codeforces Good Bye 2014 round wrapped up the year on Tuesday (problems, results, top 5 on the left, my screencast). In following with the spirit of 2014, tourist claimed the top spot - and in fact the entire top 3 are the top 3 by rating. My hopes to catch Gennady were at the highest level at this moment in the screencast: I've finished writing problem F at 1:06 into the contest, and the scoreboard showed that Gennady has not yet submitted it. Just a few seconds later, it turned out that my solution didn't pass pretests and I had to implement a stress-test to find the bug, whereas the scoreboard was just refreshing very slowly and Gennady has in fact submitted 10 minutes ago ;)

The New Year started together with the New Year Prime Contest (problems, my description from 2013), as usual consisting of problems that were offered at Russian ACM ICPC-style competitions in 2014 but have NOT been solved by anybody. The contest will be running for another week, so you can still try your luck at the toughest problems of 2014: login link, you need an Open Cup login to participate. If you don't have one, you can email new.opencup[guess what]gmail[guess what]com asking for one. Here are the current standings.

Problem 43 "Nanobugs" is mostly a mathematical puzzle: you have n (at least 20 and at most 50) coins, some of which are fake. Your friend knows that either a or a+1 coins are fake (a is between 1 and 3, and is given). You know the fake coins exactly, but you don't want to reveal that knowledge to your friend. Instead you want to prove your knowledge to your friend by proving that there are exactly x (either a or a+1) fake coins without revealing the status of any particular coin - neither fake nor real. The only method you can use for your proof is a very limited subset equality testing device: it takes two non-interesecting subsets of coins of the same size, and tells whether both subsets have the same amount of fake coins or not. Can you see the way to use comparisons to prove the number of fake coins without revealing any particular fake or real coin?

Spending winter vacation doing what you like the most, together with people who share your interests, is also the central idea of the Summer Informatics School in Winter. Summer Informatics School itself (website in Russian) is organized during the summer school break, offering high school students to continue their education in algorithms and programming for 3 weeks, each day filled with 4 hours of studying and endless hours of fun events and sports together with other high school students who enjoy learning about algorithms. In addition to learning, the students find new friends and form a new community that is active well beyond the 3 weeks of school itself, and past students often become teachers later. I was never a student at this school, but I was a teacher three times - the picture on the left is from 2004, illustrating that I was judging a soccer game in addition to teaching algorithms. In the years past the school has been growing tremendously, and these days more than half of the winners of the Russian Olympiad in Informatics have a Summer Informatics School participant t-shirt.

The winter session, lasting for just 10 days since the winter school break is short, is happening for the seventh New Year in a row - it begins in late December and lasts until the second week of January. It gathers the same students who have participated in the preceding summer session, and it keeps the same study-and-have-fun-together format, but with a winter twist: many outdoor sports are replaced with museum visits and sightseeing, although this year cross-country skiing and ice skating are also covered. And of course, the New Year night is always something special!

I'm no longer participating in this school, but I still admire both the teachers and the students for the amazing community they have built - congratulations to all of you, and have fun in the remaining days of ЛКШ.Зима!

Also, since the post is very long, I'd like to reiterate that I want to improve my English writing, and thus will appreciate if you bring up any issues you notice with my English in the comments below. Thanks in advance!