Monday, November 24, 2014

This week in competitive programming

I've already covered the results of the TopCoder Open 2014 in my earlier posts (first, second), which was one the biggest tournaments of the year and certainly the things will now quiet down a bit before 2015. Coincidentally, last week witnessed the finish of a similar long-running sporting event: the World Chess Championship. It might not be entirely accurate to draw parallels between competitive programming and chess because the chess grandmasters use a much more highly specialized skill compared to the somewhat general abstract thinking required to come up with new algorithms at contests. Nevertheless, last night's game 11 of the championship was reminiscent of the challenge phase of the TCO: at move 27, Anand decided to go for an exchange sacrifice since the game was heading into a draw otherwise, and he just wanted to add more randomness to the result. In a similar fashion, it seems pretty obvious in hindsight that I should've made a couple quick challenges in the beginning of the TCO finals challenge phase since I didn't have anythng to lose but had so much to gain if at least one was successful. It didn't work out for Anand, and would not work out for me as well, but he did at least try :)

A couple of days after the TCO, Codeforces Round 278 continued the competitive week (problems, results, top 5 on the left). Top 3 in this round have all been at TCO in different roles - a Marathon finalist, an Algorithm problemsetter, and an Algorithm finalist. Congratulations to Tiancheng on the victory in his first algorithm round after a 3-month break!

Finally, Open Cup 2014-15 Stage 4 took place on Sunday (results, top 5 on the left). The two teams that seem to be the strongest Russian ACM ICPC teams this year have swapped places once again at the top, ITMO 1 claiming the top spot with a very respectful margin over the Tapirs. The Open Cup season will now take a 3-week break as Russian ACM ICPC teams prepare for the NEERC (North-Eastern European Regional Contest) that takes place on December 7.

I've skipped this Open Cup round because I got stuck in Chicago for almost 24 hours on my way back from the TCO due to some technical difficulties with the plane. At the same time, this allowed me a chance to take a walk in Chicago (I've never been there before) and see how real winter looks in the United States as the temperature was well below the freezing point. Well, it's all nice and friendly!

Thanks for reading, and check back next week!

Thursday, November 20, 2014

TCO 2014 Algorithm Finals day

TopCoder Open 2014 Finals have concluded earlier today (results with statements accessible by clicking the point value, top 5 on the left). Gennady has completed his full sweep of 2014 trophies, while I came in second place. Looking back at how the contest went, there were several ways I could've squeezed the first place:
  • I could've solved the 1100. This is the most obvious way, and yet the most difficult since it's still not clear to me how long the solution would take to write. The problem itself had very simple and beautiful statement: given the integer scores of N (up to 500000) teams, calculate the number of possible rankings if the score of each team either stays the same or increases by exactly 1, and ties a broken by the team number. The basic idea for the solution is also quite straightforward: there are 2N ways to either add 1 to each score or not, and it takes quite specific conditions for two different sets of scores to lead to the same ranking, so we should carefully avoid counting those specific cases. However, the devil is in the details - I had most code ready by the end of the coding phase, but it's still not clear how long it would take to debug it. Because of that, we don't know if opening the 1100 earlier would've lead to better or worse results, so we can't tell which strategy was better this time :)
  • I could've found one more challenge than Gennady. I've actually found the issue in bmerry's 550, but somehow hesitated to challenge, which was clearly a mistake. But in order to find the second challenge I had to beat Endagorion or tourist on one of the 350 challenges, and it was quite hard since I was reading the 350s in the wrong order: from highest score to lowest.
  • I could've spent less time on the 550. Somehow analyzing the problem on paper took a very long time, even though there was no algorithmic difficulty: the standard approach for solving such problems, considering what happens if we swap two adjacent instances, worked very well.

(Picture on the left from the TopCoder website: spectators are watching the coding phase)

Well, better luck next time :) Misof has written his awesome commentary for the finals, go check it out! And of course, check back in the beginning of next week for the weekly summary.

Wednesday, November 19, 2014

TCO 2014 Algorithm Semifinals day

Today was a long day for the Algorithm competitors at the TopCoder Open. It started at 9am with Semifinal 1 (results with statements accessible by clicking the point value, top 5 on the left). The medium problem was the highlight of the round for me: you were given a single number N up to 1018, and were asked to come up with any (unrooted) tree that has exactly N automorphisms and at most 200 vertices. First, one has to think how to find the number of authomorphisms of a tree, and discover that it's always a product of several factorials  Then, you need to find a way to represent N as a product of several factorials. And finally, one had to construct a tree with the given "degree of freedom". All in all, instead of just coming up with one brilliant idea that solves the problem immediately, here you have to analyze and use your creativity several times to arrive at a working solution.

Another interesting aspect of this semifinal is the strategy battle. Lyrically has followed his usual hard-easy-medium approach, and that gave him an edge over the standard easy-medium-hard strategies of other contestants who didn't manage to solve all three.

Semifinal 2 took place four hours later at 1pm (results with statements accessible by clicking the point value, top 5 on the left). Once again, going for the hard has turned out to be a good idea as Endagorion has pushed Egor down to the Wildcard round.

The Wildcard Round followed at 6:30pm (results with statements accessible by clicking the point value, top 5 on the left). This time going after the hard problem didn't work out for qwerty787788, but he only went for it afer unsuccessfully solving the medium for quite some time — so maybe he could've qualified if he had started with the hard?..

Overall, I feel like today's rounds point in the direction of opening the hard problem earlier than usual. The benefits are quite tangible: in case there's no time to solve all three, it's better to have easy+hard than easy+medium. And in case the hard is completely unsolvable, you will probably have guessed that after 30 minutes or so, and by that time you can look at the scoreboard to estimate how much time one needs to solve easy+medium, to avoid fighting with the hard for too long. The risks are slightly increased, too: it might happen that you need a bit more time than average for easy+medium, and will be left with just the easy. Alternatively, you might overestimate your ability and keep pushing the hard hoping to get it in time and fail afterwards.

What is the strategy you think I should use tomorrow in the Finals? Please vote in my Google+, and present your reasoning in comments if it differs from the above!

Just 8 contestants are left standing in the TCO: bmerry, Egor, Endagorion, lyrically, Petr, tourist, wata, WJMZBMR. The Finals happen tomorrow, November 19, at 1pm Pacific time. There will probably be live coverage in Misof's blog, which already has awesome commentary on today's semifinals — go check it out! And of course, check my blog tomorrow for the news after the finals end :)

Tuesday, November 18, 2014

This week in competitive programming

Open Cup 2014-15 Stage 3 was the only contest of the week (results, top 5 on the left). The Tapirs team from the Moscow State University have shown once again that the ITMO 1 team is not impossible to beat this year. Congratulations!

Problem B was a beautiful exercise of combining several well-known ideas into a good solution. You were given a road network of some mythical country represented as an undirected graph with at most 200000 nodes and edges, with each edge having a length in kilometers. Some nodes were special — they contained petrol stations. Then, you were given a series of at most 200000 requests of the form "Is it possible to get from node A with a petrol station to node B with a petrol station using a car that is capable of traveling at most C kilometers without refueling?" for different values of A, B and C. Can you answer all those requests using just 2 seconds of CPU time in total?

Late on Sunday, the TopCoder Open 2014 (official blog, official photos) started in San Francisco. You can see the introductory video to the left, configured to start right where TopCoder Open victories are compared to the Moon landing :) But you can of course watch it from the beginning, it's just over 1 minute in length.

The organizers have decided to take advantage of the nicely competitive algorithm competition format, and added several more algorithm rounds to entertain the spectators. On Sunday, the Celebrity Algorith Match gathered 8 past greats. Each competitor has nominated a charity, and the charity of the winner would get the $10000 prize. You can guess the winner from the picture on the left :)

Four "Pickup Algorithm Rounds" where all spectators can participate are also on the schedule. I guess the original idea might've been to get the spectators from the "outside world" interested in algorithmic programming contests, and it's working to some degree as people with completely new TopCoder handles are taking part. The top of the standings, however, is still taken by people with "target" rating working for different companies in the Bay Area :)

Monday is the Marathon day, with 12 finalists competing for 12 hours trying to design the best possible route for a plane putting out a forest fire. You can pretty much understand the problem from this video showing one of the solutions at work. The current standings change often, and the margins are not too slim, suggesting that the final round problem was once again picked perfectly: enough ideas to explore in 12 hours, yet very easy to get going and with wonderful visualization. Great job!

Thanks for reading, and check back tomorrow for the news about Algorithm semifinals. Please ask any questions you might have about the TCO in comments!

Monday, November 10, 2014

This week in competitive programming

Codeforces Round 276 took place on Wednesday (problems, results, top 5 on the left). The round was unfortunately hit by technical issues, but Mikhail 'Endagorion' Tikhomirov still solved all problems, and in a proper sequence to claim the first place - congratulations!

Wide-Siberian Olympiad happened the previous week, but the results were not immediately available then, so here they are (problems, onsite results, merged results, top 5 on the left). Now we can clearly see that the ITMO 1 domination is alive and kicking, but I'd like to also point out the amazing performance of Saratov SU 1 team who were the only team to solve problem 9, and did it with just 4 minutes to go.

Three Subregionals Cup has finished this week (Moscow results, Western results, Northern results, overall results, top 5 on the left). It was an online competition organized by Yandex using the problemsets of three NEERC Subregionals, where the teams actually taking part in one of the subregionals automatically got their results merged with the online competitors. Once again, ITMO 1 is the clear winner, and three Moscow SU teams in the top 5 show that qualifying to the ACM ICPC 2015 World Finals in Morocco is still wide open for Moscow SU teams since just one team from each university can qualify.

And finally, the 2014 TopCoder Open is just around the corner - it starts next Sunday, November 16! This time it's happening in San Francisco, making it much easier for past algorithmic contest participants now working in the Bay Area (pictured on the left) to attend, so hopefully this will be a big reunion :) I will cover the events in this blog, so check back next week!

Monday, November 3, 2014

This week in competitive programming

Formally speaking, last week had just one contest that I'd want to cover - the second stage of the Open Cup, also known as the Wide-Siberian olympiad. However, its results are not available because the award ceremony has not happened yet, so it will have to go into the next week's summary.

However, TopCoder SRM 638 happened very early this Monday, which can be attributed to the last week in some timezones (problems, results, top 5 on the left). Judging from the scoreboard, it was a very wild contest, so congratulations to Kazuhiro for overcoming most difficulties and claiming the first place!

Let's also return to one of the problems I've shared in the past: you're given a positive integer M, and need to come up with an instance of the knapsack problem which has exactly M solutions. More precisely, M is up to 1018, and you have to find at most 200 positive integers ai, each up to 500, and another positive integer W up to 500, so that exactly M subsets of {ai} sum to W. Some ai might be equal, but they are still treated as different for the purpose of subsetting.

Here's how one might approach this problem: what are the standard tricks allowing us to "assemble" an arbitrary number up to 1018? Well, probably the most famous way of assembling numbers is positional notation: represent the number as the sum of powers of some base, for example 2 or 10. In order to apply it in our problem, we have to learn how to achieve powers of base, and how do we achieve the sum.

Let's concentrate on the second part first. In order to achieve summation, we can apply the following observation: out of all numbers greater than W/2, at most one will be used in any subset that sums to W. That means that if we have some set of numbers {ai} which has X subsets that sum to W and Y subsets that sum to some other number V that is less than W/2, the set of numbers {ai}+{W-V} will have exactly X+Y subsets that sum to W.

So if we had a way to find a set {ai} such that there are less than M subsets that sum to W, and all powers of two are found as the number of ways to achieve sum number less than W/2, we can add at most log(W) numbers and achieve exactly M ways to assemble W by representing the extra ways we need to add as the sum of powers of two.

However, it's not entirely clear how to achieve the powers of two for smaller numbers. But since we have quite a lot of room - we can have 200 numbers in our set, and log(1018) is about 60 - we don't need exact powers of two! The only thing we need is such set {ai} that the number of ways to achieve small numbers is sufficiently dense in the logarithmic scale. If that is the case, then applying the greedy algorithm - repeatedly taking the largest number that doesn't take us over the required sum - to represent M as the sum of those numbers will yield less than 200 numbers in all cases.

Having made this observation, we can try serveral possibilities for the set {ai} on our computer and output the number of ways to assemble 1,2,... using those numbers - our goal for those numbers of ways is to grow with roughly constant exponential speed. The set that worked for me during the actual contest was: 70 random numbers, each between 1 and 5, with 5s being more likely and 1s being less likely (the exact formula I used was "5 - random.nextInt(random.nextInt(5) + 1)"). Such set yielded the following number of ways to achieve 0,1,2,... as the sum:

1
3
9
24
69
194
464
...

769063368889619578
893415583044613189
1034306623895263056

The last number is greater than 1018 and is the number of subsets that sum to 99. Also, since we have 70 numbers up to 5, their sum is at most 350, so if we put W=500, there will be 0 ways to achieve that sum using only our 70 small numbers, and we can then add appropriate numbers between 402=500-98 and 500 to the set to achieve exactly M subsets that sum to W using the addition trick described above.

Please tell if something isn't clear from my explanation, or if you have alternative approaches you want to share. Also, of course, check back next week for the results of the Wide-Siberian olympiad and other contests! Finally, here's some Zurich fall mood for you:


Monday, October 27, 2014

This week in competitive programming

The second round of voting for the new name of this blog happens in my Google+ - please help me choose!

TopCoder SRM 637 took place on Thursday (problems, results, top 5 on the left, my screencast). The hard problem in this round had an interesting blend of requiring both an algorithmic insight, and an "ad-hoc" insight making use of the fact that everything happens on a grid.

You were given a 30x30 grid, each cell colored using one of 62 colors in such a way that all cells covered by the same color form a single 4-connected region. Each color is given to exactly one of the two players. If the first player has a 4-connected path from the left side of the grid to the right side of the grid using only cells of his colors, she wins. If the second player has a 4-connected path from the top side of the grid to the bottom side of the grid using only cells of his colors, she wins. It's obvious that both players can't win at the same time. But is it possible that neither player wins, given the grid coloring?

One of the first ideas that come to mind from previous contest experience is that lack of 4-connected path from left to right is equivalent to existence of a 8-connected path from top to bottom (is there a canonical link that explains this duality?), so essentially we have to find two non-intersecting 8-connected paths, one from top to bottom, and one from left to right, such that each color is used in at most one path. Can you see how to proceed from here?

Codeforces Round 275 happened a day later (problems, results, top 5 on the left). Problem B was quite simply stated and presented a nice, if not very difficult, algorithmic challenge. There's a hidden array of 100000 non-negative integers up to 230-1, and the only things you know about it are bitwise ANDs of its consecutive subarrays, for at most 100000 subarrays each given by the left and right boundaries. You need to find at least one array with such subarray bitwise ANDs or report that none exists.

Quite a few official ACM ICPC competitions are also happening these days. In particular, NEERC Saratov (results, the participants of the offical competition are marked as "ghosts") and Moscow (onsite results, online results) subregionals had online mirrors that let us get an early glimpse at the relative strength of various Russian ACM ICPC teams this season. So far, the Tapirs team from the Moscow State University is the one to beat. Another interesting thing about those and other subregional scoreboards is the teams that are missing from them: the obvious one is that tourist's team did not participate in the online mirrors, but they are still planning to participate in the Northern subregional as far as I know; but there are actually two strong teams who look to be skipping this year's official ACM ICPC contests completely: the strongest Nizhny Novgorod State University team and the strongest Ural Federal University team, placed fourth and fifth in the latest Petrozavodsk training camp. This is an (unintended?) side effect from the rule that lets each person participate in the ACM ICPC World Finals at most twice.

Finally, let's come back to a puzzle from last week to explain the solution. The puzzle was: given an undirected graph where the degree of each vertex is at most 5, prove that it's possible to color its vertices using 3 colors in such way that each vertex has at most one adjacent vertex of the same color as itself. The approach we'll take is very straightforward: start from arbitrary coloring of all vertices using 3 colors, for example a completely random one, then gradually improve it until it satisfies the restriction of at most 1 adjacent vertex of the same color for every vertex. In order to improve, we pick any vertex that has at least 2 adjacent vertices of the same color, and fix its color. Since its degree is at most 5, there a color that at most one of its neighbors has, so we pick that color for the fix. One might even think that doing this once for each vertex is enough — but that's not true, since by fixing one vertex we might break its neighbor, more precisely the one with the color we're fixing our vertex to. Given this knowledge, it's not clear anymore why the fixing process terminates at all. That's when the magic happens: we can notice that each fix decreases the number of edges where both ends have the same color! We get rid of at least two such edges, and introduce at most one. Because of this, the total number of fixes does not exceed the total number of edges.

Thanks for reading, and see you next week!