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 10¹⁸ 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 10⁹ 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!

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!

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(N³), but this problem required a O(N²) 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(N³/logN). However one had to find one more speedup and solve the problem in  O(N³/log²N) - 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(N²) 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(N²) 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(N²) 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!

This week in competitive programming

There were no big online contests this week, but the last and strongest European ACM ICPC regional, the NEERC, happened on Sunday (problems, results, online mirror results, top 5 on the left). The two favourites, SPb ITMO 1 and Moscow SU Tapirs, did not disappoint - congratulations!

I've set problem G together with pashka. You can find the full statement on page 9 of the PDF, but the general idea was that you had to write a program that would always win as the second player in Gomoku against a pretty weak strategy. Of course, since the first player has a guaranteed win in this game, the strategy you're playing against has to be weak. More precisely, the strategy considered all possible moves, and evaluated the resulting position for each move, picking the move that leads to the best position modulo some random noise. When evaluating a position, the strategy considered each horizontal, vertical and diagonal of five cells, and tried to minimize the number of such rows where the other player has four marks and it had none. To break ties, it tried to maximize the number of such rows where it had four marks and the other player had none. To break ties again, it tried to minimize the number of rows where the other player had three marks and it had none, and so on.

The ITMO 1 team made the biggest progress in this problem, creating a strategy that won about 95% of the games. However, you had to win 100 games in order to get this problem accepted, and the chance of that was around 0.5%, and they didn't get so lucky. Here are three short videos: ITMO 1 winning a game, ITMO 1 losing a game, and the reference solution - spoiler alert! - winning a game (in all cases the contestant's strategy is playing blue circles):

    

I've also enjoyed problem E a lot - see the full statement on page 7 of the PDF. It was also centered around a game, this time a much simpler one: Rock-paper-scissors. 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.

Can you see how to do it? How many states does your machine need in the worst case if the input machine has N states? Can you prove that such number of states is asymptotically minimal? Can you see a simple randomized solution with the same number of states?

You can try to submit those two problems, as well as 9 others, at the online mirror.

All other European regionals are also over by now: the SEERC (problems, results), the CERC (problems, results, Russian training camp mirror results), the SWERC (problems, results, online mirror results), and the NWERC (problems, results, online mirror results). Congratulations to Lviv NU Penguins, University of Zagreb, UPC 1 and University of Copenhagen Lambdabamserne on the victories! The intersection between different online mirrors is rather small, but the general feeling is that the two top NEERC teams are the strongest in Europe this season.

Thanks for reading, and check back next week!

This week in competitive programming

This week was relatively calm, with just one contest: TopCoder SRM 639 (problems, results, top 5 on the left, my screencast). The screencast is quite evenful in its second part: at 57:30 in the screencast, I was at the top of the standings with all problems solved and 1304 points, and was about to relax until the end of the contest. But then I've decided to quickly write a stress test comparing the output of my solution for the 1100 problem with the output of a simple-but-slow solution, and that changed everything. I've found that my solution had a bug, had to diagnose and fix it quickly (it turned out to be very very stupid, of course), and then had to go all-in at the beginning of the challenge phase with blind challenges.

All challenges were on the easy problem, which went like this: two players are playing a game with several rounds. The winner of the first round gets 1 point, the winner of the second round gets 3 points, then 5 points, and so on. Given two numbers x and y, is it possible that after some number of rounds the first player has x points and the second player has y points? If yes, then what is the smallest number of rounds the first player could've won?

If the scores for the rounds were 1, 2, 3... instead of 1, 3, 5, ..., then there would really be no corner cases and no challenge opportunities. However, the use of odd numbers resulted in a few tricky situations, in particular no player can score exactly 2 points now, and thus many greedy algorithms failed. In fact, just 138 out of 496 submitted solutions turned out to be correct. Can you see how to overcome this difficulty?

In addition to hosting the SRM, TopCoder has uploaded the TCO 2014 "Epilogue" video this week — check it out!

The ACM ICPC North-Western European Regional Contest happens today, most other European ACM ICPC regionals happened earlier, with the sole exception of the Russian and ex-USSR regional NEERC which takes place next Sunday. I will try to summarize the results of all European regionals in the next week's summary, so check back in 7 days!

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!

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 2^N 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.

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 10¹⁸, 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 :)

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!

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!

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 10¹⁸, and you have to find at most 200 positive integers a_i, each up to 500, and another positive integer W up to 500, so that exactly M subsets of {a_i} sum to W. Some a_i 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 10¹⁸? 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 {a_i} 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 {a_i}+{W-V} will have exactly X+Y subsets that sum to W.

So if we had a way to find a set {a_i} 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(10¹⁸) is about 60 - we don't need exact powers of two! The only thing we need is such set {a_i} 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 {a_i} 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 10¹⁸ 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:

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 2³⁰-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!

This week in competitive programming

Let's start with a poll: what would be a good name for this blog? Vote in my Google+, and suggest other options in comments! Now, back to business:

TopCoder SRM 636 on Tuesday had quite diverse problemset (problems, results, top 5 on the left). The easy was a pretty straightforward implementation involving several nested loops and a standard way to find sums of sub-rectangles of a given grid in O(1) after precomputation. The medium was a very unexpected application of linearity of expectation — such problems never cease to amaze me! The hard was a "professional" problem requiring both an insight and quite careful implementation to get right, which I haven't managed this time.

Even if my solution for the hard didn't fail with both timeout and wrong answer, I would only get second place. The first place is undisputedly Endagorion's — great job Mikhail!

The new season of the Open Cup started on Sunday with the Grand Prix of Saint Petersburg (results, top 5 on the left). I don't think the problemset is available online yet, but one of the problems was a very simply stated mathematical puzzle that I can share here:

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.

Another problem has introduced a new concept that I don't remember seeing in programming contests before: you were asked to implement a strategy for a game, but instead of beating the optimal play of the opponent, your strategy had to beat random play of the opponent in at least 290 out of 300 rounds. Are you aware of similar programming contest problems?

Overall, this was a nice contest — kudos to the problemsetters!

Codeforces Round 274 (problems, results, top 5 on the left) happened right in the middle of the Open Cup round, so everybody had to pick only one of the two. As evident from the scoreboard, there was still quite fierce competition and Bruce ended up on top with 200+ point margin — congratulations!

Bayan Elimination Round wrapped up the highly competitive Sunday (results, top 5 on the left). I don't think the problems are available online, and I did not participate myself, but quite a few strong algorithmists did. Kazuhiro, one of the problemsetters of TopCoder SRM 636 mentioned above, has topped the scoreboard with a substantial margin — well done! This contest was notable for its highly unusual advancement system: only the top one coder from each of top 20 countries would advance to the onsite finals, essentially splitting the competition into many intra-country micromatches. Now quite a lot of people got to feel like many Moscow State University teams feel each year at the ACM ICPC regionals :)

Thanks for reading, and check back next week!

This week in competitive programming

Codeforces Round 272 was the only regular contest during the last week (problems, results, top 5 on the left). The problemset consisted of two relatively simple mathematical problems A and B solved with formulas that can be figured out using pen and paper, two dynamic programming problems C and D that had a few tricky implementation details to take care of, and an extremely tedious O(nlogn) data structure problem E that did not require anything more complicated than a stack and binary search, but needed more than an hour to implement and had a lot of possible plus/minus one errors to make.

There was another online contest held on Saturday, Marathon24, which is very similar in format to Challenge24: mostly solving optimization problems instead of pure algorithmic ones, the online part takes 5 hours but people who advance will participate in a 24-hour onsite competition. I didn't participate, but some quite strong teams did; I'm not sure if the final results are available online since the standings mention that they are still frozen. Maybe somebody reading this blog can confirm if the final results are already available?

Thanks for reading, and check back next week!

This week in competitive programming

The final round of Russian Code Cup 2014 took place on Saturday (problems in Russian, results, top 5 on the left), but it went without the official onsite event like we had last year, as the organizers decided to cancel the onsite part and hold the final round online. The monetary prizes were still up for grabs, and Gennady has claimed the biggest one with just 2 minutes to go!

Problem C was the highlight of the competition for me. You were given a positive integer M, and were asked to come up with an instance of the knapsack problem which has exactly M solutions (well, to be precise, M had to divide the number of solutions, but all approaches I know yield exactly M). More precisely, M was up to 10¹⁸, and you had to find at most 200 positive integers a_i, each up to 500, and another positive integer W up to 500, so that exactly M subsets of {a_i} sum to W. Some a_i might be equal, but they are still treated as different for the purpose of subsetting. I encourage you to try solving this problem, you can submit your solutions at the Codeforces gym!

TopCoder SRM 635 took place later in the evening (problems, results, top 5 on the left). This round had problem statements in English unlike the Russian Code Cup, but the top 3 were exactly the same, Gennady claiming the first place thanks to the ultra-fast solution for the hardest problem.

That problem went like this; how many sequences of integers between 1 and 4 exist such that adjacent numbers are different, and there are exactly n₁ ones, n₂ twos, n₃ threes and n₄ fours? n₁ and n₂ are up to 200, n₃ and n₄ are up to 50000. Similar problems appear in competitions time and time again, but every time they turn out surprisingly difficult to implement. Can you see an approach that leads to a simple implementation?

Bayan 2015 Contest Warm Up happened on Codeforces on Sunday (problems, results, top 5 on the left). Conratulations fotile96, hogloid and sankear on solving all problems!

Thanks for reading, and see you next week!

This week in competitive programming

Another quite typical week drifted past, with a TopCoder round and a Codeforces round. First, TopCoder SRM 634 took place very early on Friday morning (problems, results, top 5 on the left). The early start was too much for me, but I want to congratulate mikhailOK and piob on solving all three problems and thus leaving the rest of the competition far behind — great job!

Codeforces Round 270 occupied the Sunday evening (problems, results, top 5 on the left). The problemset had a very nice common background story: each problem explained how one can come up with problems of this type — consider reading them all if you look for inspiration for creating new problems.

The hardest problem brought an interesting aspect of the programming competitions into the limelight: sometimes the expected algorithms get so complicated that the constant hidden in the O-notation of their running time is so big that solutions that are very straightforward and efficiently implemented can be faster even despite worse asymptotic complexity. In this particular problem, the reference solution from the editorial has complexity O((nlogn)^1.5), while most, if not all, accepted solutions have complexity O(n²). With n as high as 200000, one might think that the extra square root of n will dominate, but since the n squared solutions are very straightforward and thus can easily be optimized, for example using bitwise operations, this is not the case.

ilyakor's accepted solution is the fastest, solving the worst testcase in just 2.5 out of 7 seconds by reusing a publicly available SSE3-based code for counting the number of elements in a bitset — a great use of all available resources to solve the problem! But as far as programming competitions in general are concerned, we've mostly given up on separating O(n²*polylog(n)) algorithms from O(n³) ones, and it's sometimes even difficult to separate O(n*polylog(n)) algorithms from O(n²) ones. It's a pity since we eliminate a large class of quite beautiful algorithms and data structures this way :( Any ideas on reversing the trend?

Thanks for reading, and check back next week!

This week in competitive programming

TopCoder SRM 633 took place on Wednesday (problems, results, top 5 on the left). The hard problem was nice, but the medium problem was even nicer — kudos to the problemsetter, cgy4ever! You were given two trees with the same set of vertices, each vertex had a (possibly negative) score assigned to it, and you needed to find a subset of vertices that is connected according to both trees and has the highest total score. The question is very simply stated, and yet the solution is quite challenging and creative — that's how great programming contest problems look like! Can you see it?

A flawless peformance by Gennady guaranteed him a clear first place. Great job!

Codeforces Round 268 happened on Saturday (problems, results, top 5 on the left). I've skipped this round but I can still see that Pavel achieved a commanding victory thanks to 10 challenges in a contest where many top scores couldn't find any — amazing!

We've also had some very nice developments in http://hamiltonianplumber.appspot.com/ during the week: +Boris Minaev found a creative way to break the 2-opt heuristic with random restarts. To quote him:

"my idea is very simple - creating a big test is hard, so we can create a small test (for example with 10 vertices) and then repeat it 5 times. By repeating I mean placing vertices of different groups far from each other. In such test case the correct order will be (visit all vertices of 1st group) -> (visit all vertices of 2nd group) -> ... (visit all vertices of 5th group). If we now look at number of iterations that 2-opt solution need to find a correct answer, it would be something like (number of iterations it needs to find a solution for one group)^5.

So we just need to create a small test where 2-opt solution works bad. This we can do with just a stress-tesing. It's easy to find a test which needs ~10 iterations of 2-opt, which gives ~10^5 iterations in total."

This testcase forces the heuristic to make 230932 attempts before finding the shortest path for the first time:

{690, 9932, 10000690, 10009932, 20000690, 20009932, 30000690, 30009932, 40000696, 40009883}

{1175, 1327, 1564, 2263, 2715, 7246, 7674, 7997, 8334, 8511, 10001175, 10001327, 10001564, 10002263, 10002715, 10007246, 10007674, 10007997, 10008334, 10008511, 20001175, 20001327, 20001564, 20002263, 20002715, 20007246, 20007674, 20007997, 20008334, 20008511, 30001175, 30001327, 30001564, 30002263, 30002715, 30007246, 30007674, 30007997, 30008334, 30008511, 40001663, 40003713, 40003852, 40007375, 40008436, 40009682, 40009842}

// please don't upload it to the server just for the sake of getting to the scoreboard — it actually requires quite a lot of resources to judge!

If you want to test your hamiltonian path implementation, you can construct the actual graph using the first part of the code in http://hamiltonianplumber.appspot.com/source.html.

And finally, it's time for some celebration as this is the 52nd post titled "This week in competitive programming" (here's the first one), meaning that this weekly programming contest review has been going for an entire year! I guess the expected question is: what do you think I should improve in this blog?

Hoping for sincere feedback, and see you next week in any case!

More on the Hamiltonian Plumber

This Sunday, I've launched a website with the goal of learning about good testcases that break a heuristic solution for a decisive TopCoder Open problem that can be reduced to Traveling Salesman: http://hamiltonianplumber.appspot.com/

So far, nobody except myself has submitted a testcase that makes the solution do at least two iterations — in other words, greedy improvement works in all submitted testcases. This is quite disappointing, so I'm wondering what's the reason for that. It could be:

1. The challenge is not interesting enough, so people either don't bother at all or try a few manual tests.
2. The website is confusing, so people don't understand what's really going on.
3. The website is broken, so people submit good testcases but they are scored incorrectly.
4. Something else? Please share what you don't like about the challenge!

Let me also share a simple strategy that allows to get a score higher than 1.0. It's actually quite straightforward - we can just try random big tests until we find one that scores more than 1.0. One might need to try several tests before that happens, and doing that using the website is slow and clumsy. However, the website actually has the code available for download (http://hamiltonianplumber.appspot.com/source.html), so one can quickly craft a local stress-test and find a case that requires many attempts. Since you don't know the hidden random seed, a testcase that requires two attempts on your machine might still be solvable in one on the server, but if you find a testcase that needs ten attempts, chances are your score on the server will be more than 1.0, too.

This week in competitive programming

There were no regular competitions this week, so it's a good time to return to a past problem.

Let's talk about TopCoder Open 2014 Round 3A hard problem "PlumbersCoins" (previous post).

In short, the problem statement is: you are given at most 50 interesting points on a line that you need to visit in any order starting from point 0. In addition to moving along the line at one unit per second, you can use teleports between the given pairs of locations. The teleports are non-interleaving (if one teleport connects points a < b, and the other connects points c < d, then either b < c or d < a), and there are at most 25 teleports, each taking exactly one second to use. What's the shortest time required to visit all interesting points?

During the competition, I didn't notice that the teleports are non-interleaving, and thus the problem became much harder. The only thing I could come up with was reducing the problem to the Traveling Salesman problem, so I coded a heuristic solution for the Traveling Salesman problem that I remembered from IOI 2002 practice problem "red": start with a random path and repeatedly reverse its subpaths while the solution improves, then repeat everything until we run out of time. Surprisingly, this solution passed the system tests!

But then I started to think: is this really surprising? Does there exist a valid testcase that makes this solution fail?

I'm relying on you to find out :) Here's a website where you can try your testcases:

http://hamiltonianplumber.appspot.com/

Please remember to sign in at the bottom of the page to be included in the scoreboard (and so that others can't see your last testcase :))