Sunday, January 25, 2015

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!

Thursday, January 22, 2015

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 loginresults 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 109) 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!

Wednesday, January 14, 2015

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.

Monday, January 5, 2015

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 (problemsmy 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!

Sunday, December 28, 2014

This week in competitive programming

2014 is coming to an end, but the algorithmic competitions are still in full swing. Codeforces Round 284 happened on Christmas Eve (problems, results, top 5 on the left). Top 5 is full of usual suspects, and this time Egor Suvorov is on top - congratulations!

TopCoder SRM 643 picked up the competitive spirit right after the Christmas holidays (problems, results, top 5 on the left). Both the easy and the medium problems required ad-hoc solutions that were easy to get wrong - I got trapped twice, resubmitting both problems - so the round was decided during the challenge phase. zerokugi and wleite achieved amazing +425 points from challenges each (9 successful + 1 unsuccessful), but zerokugi also got both problems correct and claimed the first place - awesome performance!

The easy problem asked you to factor a number up to 1018 into a product of primes, but with some extra help: you were already given every other factor in sorted order, starting from the smallest factor, then the 3rd smallest factor, and so on. The most probable mistake here was accidentally doing 109 operations for a tricky testcase and thus running out of time.

The medium problem studied a table zeroes and ones with two rows and at most 200 columns. In one operation, you could either change a single element to be equal to one of its adjacent elements by row or column, or change an entire column to be equal to one of its adjacent columns, or change any horizontal contiguous segment in one of the rows to be equal to the corresponding segment of another row. In this problem there are a lot of different correct greedy and dynamic programming solutions, but even more different incorrect greedy and dynamic programming solutions.

I was aware that both problems were tricky before the challenge phase. Given that I knew only one way to fail the first problem, and a lot of ways to fail the second problem, I've decided that it would be much easier to look for the mistake in the first problem and tried to challenge those solutions. In hindsight, this was obviously a wrong decision, for the following reason: despite there being many possible mistakes in the second problem, every mistake means that we're handling some small pattern incorrectly. So if we take a random 2x200 table, it will most probably contain the corresponding bad pattern for every possible mistake, and we can just challenge all solutions blindly and very quickly without actually finding what each mistake is.

It seems that making good logical decisions for the challenge phase is still tough for some reason :) Thanks for reading, and check back in 2015!

Sunday, December 21, 2014

This week in competitive programming

Just two rounds happened this week, both on Wednesday. The first was TopCoder SRM 642 (problems, results, top 5 on the left). Given that the total time between the start of the SRM at 5am Moscow time and the end of the following Codeforces round at 9:30pm Moscow time was 16 hours 30 minutes, it was quite hard to participate in both while maintaining a healthy sleep schedule, so I've passed on the SRM :) Nevertheless, anta showed that my fears were unfounded by winning the SRM and placing fourth in the Codeforces round - great job!

Codeforces rounds with problems by Endagorion are becoming a trademark of their own because of interesting and diverse problems, and Round 283 was no exception (problems, results, top 5 on the left, my screencast). Baz93 claimed the first place thanks to the super-fast solution for problem D. You were given two (not necessarily convex) polygons, each rotating around a point with the same angular speed in the same direction (those rotation centers could be different for the two polygons, and could be outside the corresponding polygon), and needed to determine whether they will ever intersect or touch. Each polygon had at most 1000 vertices. The problem requires both a geometrical insight, and some computational geometry mastery - can you see the insight?

I was going to describe the solution to the Open Cup problem discussed in last week's summary, but I was beaten to it in comments by +Ilya Kornakov and +Andrey Kolosov, so you can check them out instead :) The other problem mentioned in last week's summary, about counting triangles containing the origin, was solved in NlogN using the following insight: instead of counting triangles containing the origin, let's count the triangles NOT containing the origin. Each of those triangles is contained in some half-plane containing the origin, so if we rotate the half-plane slowly, then every time a new point arrives in the half-plane, we should increment the result by (n-1)*(n-2)/2, where n is the current number of points in the half-plane, thus accounting for all triangles containing the newly arrived point.

Thanks for reading, and check back next week!

Wednesday, December 17, 2014

This week in competitive programming

TopCoder SRM 640 (problems, results, top 5 on the left) opened the week's competitions on Tuesday. Three "targets" participated in the round but they couldn't get into the top 5, while the winner Zero_sharp was just 31st by rating going into the round, and got the first place (and became 16th by rating among the participants) thanks to the challenge phase performance - congratulations!

TopCoder SRM 641 (problems, results, top 5 on the left, my screencast) happened at almost the same time two days later. This time tourist took no chances with great coding phase performance and two successful challenges to boot. The victory also allowed him to claim the first place in the TopCoder ratings - congratulations!

The easy problem in this round featured a well-known, but still beautiful, trick. You were given N points on a plane, and needed to count how many triangles with vertices in those points contain point (0, 0) inside them. This is of course very easy to do in O(N3), but this problem required a O(N2) solution. Many contestants went a step further and solved it in O(NlogN) - can you see that improvement?

Codeforces Round 282 (problems, results, top 5 on the left) gathered the best algorithmists on Saturday. Only two contestants - tourist and Endagorion - managed to solve the hardest problem E, but tourist has added three more correct problems and three successful hacks to win the round with a big margin - congratulations once again!

On Sunday, OpenCup 2013-14 Stage 5 (problems, results, top 5 on the left) became a contest where tourist's team participated but didn't win, for a change, although they were very close with two more problems solved but not accepted.

One of those problems, problem I, went like this: you were given three polynomials f(x), g(x) and h(x), defined over Z/2Z (remainders modulo 2), each polynomial's power was at most 4000, and needed to compute another polynomial: f(g(x)) mod h(x). Polynomials over Z/2Z are just sequences of bits, and thus it's not hard to see how to use bitwise operations to perform this task in O(N3/logN). However one had to find one more speedup and solve the problem in  O(N3/log2N) - and I think this is a very instructive problem to teach those speedups, so I encourage you to look for that solution.

Finally, let's go back to NEERC's problem E from the last week's summary. To remind, it was centered around the Rock-paper-scissors game. You were given a description of a finite-state machine where each state has one move associated with it (rock, paper or scissors), and three transitions corresponding to three possible moves of the opponent. The initial state of that machine was unknown. You had to create another finite-state machine in the same format that would beat the first machine at least 99% times in the long run, irrespective of the first machine's initial state.

Suppose we know the initial state of the first machine. Then beating it 100% of the time is very easy: we create a machine with the same number of states as the first machine, each state has the winning move for the corresponding state of the first machine (rock for scissors etc), and we actually care about just one transition out of three for each state: the one that happens when we win - we should transition to the state corresponding to the state the first machine transitions when it loses.

But we don't know the initial state. Let's assume the initial state is state 1, and build the above always-winning machine. What will happen if the initial state was in fact state 2? Well, since we know the first machine, we can emulate the process. One of the two things can happen: either we still win 100% of the time (this can happen, for example, if states 1 and 2 of the first machine are isomorphic), or we lose at some point. When we lose, our machine reaches a transition that we haven't yet defined. What we can do now is to add another N states to our machine with the same transitions between them that lead to always winning if we're in the right state, and direct the "losing" transition we just encountered to the appropriate state of those N, so that we would lose just once if the initial state was state 2.

We can now do the same with state 3, with a small difference: when we lose, it might happen that we lose for the first time in the same way as we did with state 2. In this case the "losing" transition is already defined, and we can't override it for state 3. In this case we should continue playing until we lose again (or make sure we never lose anymore, in which case we're fine), and this time we would be using the second set of N states and thus the first losing transition will be undefined and we'll be able to add another N states to take caret of initial state 3 of the first machine.

Doing the same for all states of the first machine, we obtain a finite state machine that has at most O(N2) states and loses at most N-1 times for any initial state of the first machine, where N is the number of states of the first machine.

There are still several questions that I don't know the answer for. Is it possible to build a machine with less than O(N2) states? If not, then what's an example first machine that requires so many states?

Finally, let me describe a slightly different solution to the contest problem that was used by many teams at the NEERC. Since it's easy to construct the finite state machine that always wins if we know the initial state, let's simply do the following: whenever we lose, let's just jump to a random state. Then sooner or later we'll jump to the appropriate state by luck and will keep winning ever since. Of course, the finite state machines don't allow random jumps. If we pick a random but specific jump for each losing transition, this will not be good enough, since those jumps might form a loop quite easily. To combat that, let's make several copies of the winning machine, for example N copies to have the same O(N2) states as the previous solution did, and assign different random jumps for losing transitions out of each copy. This way the chance of accidentally forming a loop from losing transitions is much lower, and we'll most likely randomly reach the correct state at some point.

This raises another question which I don't know the answer for: is it possible to actually estimate how likely is this solution to pass?

Thanks for reading, and see you next week!