Monday, September 1, 2014

This week in competitive programming

Last week had two international programming contests. The first one was Codeforces Round 263 on Tuesday (problems, results, top 5 on the left), won by WJMZBMR who was the only one able to solve all problems without mistakes. Great job!

Then, TopCoder SRM 631 took place on Saturday night (problems, results, top 5 on the left). The hardest problem was a data structure problem: you were given a rooted tree, and had to handle two types of requests: pick any subtree of the tree, detach it from the tree and attach it somewhere else in the tree; given two nodes in the tree such that one node is an ancestor of the other, find the maximum number of a vertex on the path between them.

Such problems usually have several working approaches:
  • implement all operations in a straightforward O(n) manner, so that the entire problem needs O(n2). This is too slow, but we can then optimize the constant hidden in the O-notation a lot and squeeze it under the time limit.
  • implement all operations using a complex data structure so that they take O(log(n)), so that the entire problem needs O(n*log(n)). This is usually the fastest approach, but it might require a very complex data structure - in this case, one could use a link/cut tree.
  • use sqrt-decomposition so that each operation takes O(sqrt(n)), for the total running time of O(n*sqrt(n)). In this particular problem sqrt-decomposition means splitting all queries into blocks of sqrt(n), and shrinking the tree to only contain interesting vertices for each block of queries.
I like sqrt-decomposition more for this problem since it's really easy to implement.

Thanks for reading, and check back next week!

Monday, August 25, 2014

This week in competitive programming

Last week was very quiet, with just the TopCoder SRM 630 on Friday (problems, results, top 5 on the left). Egor has beaten the SRM-at-5am odds and won the round by just 1.02 points - congratulations! I was not brave enough to take part in the middle of the night, so I don't have any insights to share about the problems.

Thanks for reading this short summary, check back next week for a more interesting post :)

Saturday, August 16, 2014

This week in competitive programming

On Tuesday, TopCoder SRM 629 has fulfilled two characteristic features of a good ICPC contest: nobody solved all problems, but each problem was solved by somebody (problems, results, top 5 on the left, my screencast). These properties are not as important for the TopCoder format, of course, since the score of a problem decreases with time, and thus even if several people solve all problems, they are still differentiated quite well.

Two things made this possible: the easy problem had a very subtle trick, while the hard problem was just hard.

The easy problem had a real-world statement: you have a rectangular hole in the ground, and want to cover it completely using several rectangular boards, placing each board in such a way that its sides are parallel to the sides of the hole. In order for the boards not to fall into the hole, you want to place the boards in such a way that all four corners of each board are not inside the hole and not on its boundary. Given the size of the hole and the sizes of the boards you have, what is the smallest number of boards you need to cover the entire hole?

When a problem has a statement that relies on common sense instead of formal maths, one needs to formalize the statement before solving the problem. In this case, we need to formalize the "all four corners are outside the hole" part and the "covers completely" part. And the main trick is that those two are formalized differently: for all corners to be outside the hole, we need the height of the board to be strictly greater than the height of the hole (or the same for width), while covering the hole completely requires that sum of the widths of the boards is greater than or equal to the width of the hole (or the same for height). It was very easy to miss the "or equal" in the second formalization, and many competitors including the match winner K.A.D.R made that mistake. And because the formalization step is usually quite simple and boring, we're simply not used to looking for mistakes in that step - so even re-checking the solution won't help since one would compare the program to the formalized version of the problem in one's head, and find no discrepancies.

The hard problem asked about a very simple thing: given N, K and MOD, calculate S(N,K) modulo MOD, where S(N,K) is the sum of all possible products of exactly K different integers, each between 1 and N. For example, S(3,2) = 1*2+1*3+2*3 = 11. It's not hard to come up with the following reccurrence relation: S(N,K) = S(N-1,K)+N*S(N-1,K-1) - it represents whether we take the number N into the product or not. However, N was up to 109, and K was up to 2000, so simply using that formula would be too slow.

K.A.D.R has come up with a brilliant insight which I want to share with you. He has noticed that when we fix the value of K, S(N,K) is a polynomial in N. For example, S(N,1)=N*(N+1)/2=1/2*N2+1/2*N. It's not hard to prove by induction that S(N,K) is a polynomial of degree 2K. One might now start constructing this polynomial in order to find its value for the given N - but that is quite hard, too. What Iaroslav did instead was to simply compute the value of this polynomial in points 1, 2, ..., 2K: S(1,K), S(2,K), ..., S(2K,K) can be computed in O(K2) time using the above recurrence relation very easily. And computing the value of a polynomial of degree 2K in point N given its values in 2K points can be done using a standard interpolation algorithm in O(K2), too!

Congratulations Iaroslav on this amazing solution and on winning the match!

On Friday, the Google Code Jam became yet another major contest won by Gennady in 2014 (problems, results, top 5 on the left). The Code Jam's scoreboard has loosely followed the pattern of the recent Yandex contest: at the end of the competition, Gennady was in 3rd place behind Evgeny 'eatmore' and Ivan 'mystic'. However, as the system test results for the large inputs were announced, it turned out that they were both incorrect in their attempts at solving F-large, while all of Gennady's submissions stood and he won the contest. Once again, making sure that one's solution are correct paid off - congratulations!

Second-placing Evgeny was really close to winning - the code he used for F-small looks good in general and should be able to solve F-large just as well - but his submission failed, indicating that he probably has some very small bug somewhere.

Among the problems of the final round, I've enjoyed problem D the most. You have up to 100 different candies, and for each pair of candies you prefer one of them to the other. Your preferences are not necessarily transitive - you might prefer A to B, B to C, and C to A. You're trying to pick your most favorite candy by considering all candies one by one and comparing each candy with the "current best" candidate. It's not hard to see that the candy chosen to be the most favorite depends on the order you consider the candies in. For example, in the above triangle, processing the candies in order ABC will lead to candy C being declared the most favorite, while ACB will make B look like the best candy. Given the matrix of preferences, and one specific candy, can you make that candy your favorite by considering all candies in the right order? If yes, you also need to find the lexicographically smallest such order.

The picture of Gennady on the right is from this article (which does have a few inaccuracies - but good job on publishing the article so quickly!)

Thanks for reading, and see you next week!

Tuesday, August 12, 2014

This week in competitive programming

Tourist has started the week in his usual fashion by winning Codeforces Round 260 on Friday (problems, results, top 5 on the left). He has participated in just 4 regular Codeforces rounds in 2014 - and he has won them all. Amazing consistency!

TopCoder Open Algorithm Round 3B, like most TCO rounds, took place on Saturday (problems, results, top 12 on the left, my screencast of the parallel round). Twelve more spots in one of the most prestigious tournaments in competitive programming were given out. The problemset was destined to make the contestants very nervous :) The 500 problem did not require any sophisticated algorithms or ideas, but required a small insight and a lot of attention to detail. Most contestants tried to solve it - but just 4 contestants managed to solve it correctly (3 out of those 4 are in the top 12 to the left), while many top rated favorites had a bug in their solutions and failed. This problem also played a very important part for some people who didn't solve it, as they were able to challenge a lot of incorrect solutions and gain a spot in top 12 that way.

The 1000 problem, on the other hand, had a really simple problem statement but required great combinatorial prowess. 4 out of 5 people who submitted it got it right, so it was a safe ticket to the TopCoder Open - provided you could actually get a solution that passes the example cases. Congratulations to wata on solving it very quickly and winning the round with a commanding margin!

The problem asked to count the number of trees on the given vertices (at most 50) that share at least the given number of edges with one specific given tree. Can you do it?

Finally, MemSQL Start[c]UP 2014 Final Round was held on Sunday (problems, onsite results, online results, top 5s on the left). The onsite round was for those willing to travel to the MemSQL office in San Francisco, and the online round was for the rest of us, using the same problemset. This time the problemsetters didn't worry that much about having easy problems in the set, so the first three problems all had a hundred thousand numbers in the input and required O(n) or at least O(nlogn) solutions. This has unexpectedly bitten the contestants using Java since two out of those three problems involved sorting hundred thousand integers - and it turned out that using Arrays.sort is not good enough, since it uses a deterministic quicksort algorithm and thus can be made to work in O(n2) by a specially crafted testcase. Sure enough, some contestants did come up with such testcase. Lessons learned: either shuffle the array before sorting using time-based randomness, or use Arrays.sort on arrays of objects, not primitives, since that version is not quicksort.

The hardest problem was not solved, is still not solved by anybody in the problem archive, and I still have no clue how to solve it. You are given a rooted tree of at most 250 vertices, and each node of the tree is either a leaf or has exactly two children. Each leaf has a number associated with it. Two players, maximizer and minimizer, are playing a game by making turns in order. At each turn, a player must pick a node with two children that are both leaves, erase those leaves, and pick one of their two numbers as the number for the node. The game ends when just the root is left in the tree, and the score of the game is the number picked for it. Maximizer wants to maximize the score, while minimizer moves in the other direction. What will be the score if both players do their best?

Thanks for reading, and see you next week!

Monday, August 4, 2014

This week in competitive programming

This week had two rounds, both on Friday. Yandex.Algorithm 2014 Final round (results, top 5 on the left) took place in Berlin, where 22 best contestants competed for the grand prize. I was competing there as well, and could have placed above tourist - had all of my blind submissions passed. Unfortunately, my solution for problem C turned out to have a very simple bug which I've missed in the end-of-contest rush, so I fell to the 7th place. It's probably even more disappointing for s-quark, who submitted problem C in the open and thus had several attempts to fix his bugs and claim the first place.

Anyway, congratulations to Gennady! He has won all 2014 tournament onsites he has participated in: Facebook Hacker Cup, Kotlin Challenge, Yandex.Algorithm. Three more to go - Google Code Jam in August, Russian Code Cup in October, and finally the TopCoder Open in November. The picture on the left is from the official news feed.

Amazingly, the problems were not too difficult. They don't seem to be public online. The four problems that were enough to win the competition were about sorting, backtracking, simple maths and quite standard Dynamic Programming. They did require a great deal of accuracy to get right, which was especially challenging given the open/blind format of the competition.
Codeforces Round 259 (problems, results, top 5 on the left) thus became a bit of a consolutation round to me. Problem D which decided the round boiled down to the following nice Dynamic Programming subproblem: you are given 220 numbers. For each position i between 0 and 220-1, and for each distance j between 0 and 20, what is the sum of the numbers with such indexes k that k and i differ in exactly j bits? The time limit is 6 seconds.

Thanks for reading, and see you next week! Last week, I've promised a detailed post on TopCoder Open Round 3A hard problem which had failed to materialize so far - but I still hope to publish it soon.

Tuesday, July 29, 2014

This week in competitive programming

TopCoder SRM 628 took place on Tuesday (problems, results, top 5 on the left). The TopCoder admins are having a hard time finding good problems, so they've ran just two SRMs this month instead of the usual four. I've skipped this round, while Gennady didn't, and he has claimed the first spot in the overall TopCoder rating as the result after winning this round - congratulations!

On Saturday, there was another TopCoder round - TopCoder Open 2014 Round 3A (problems, results, top 12 on the left, my screencast). Just 12 people advanced to the onsite finals in San Francisco, all listed on the left - congratulations to all! I've managed to squeeze out the first place in the last seconds by submitting a heuristic solution for the hard problem (TopCoder login required to view it). I want to discuss my solution in a separate post later this week, but in the meantime, here's what the problem was about: you were given at most interesting 50 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?

On Sunday, Codeforces ran MemSQL Start[c]UP 2014 Round 1 (problems, results, top 5 on the left). The round featured one quite technical problem that highlighted a flaw in my preparations: problem E required a suffix structure, like a suffix tree, a suffix array or a suffix automaton to be solved. While I do know in theory how all of those work, using them in practice is always painful for me and takes a lot of time. The reason for that is mostly the fact that those data structures were quite new back when I was actively learning new things in competitive programming, and I haven't caught up with the recent developments in the area. I can definitely do better - and this contest is another good reason to actually figure those data structures out and be ready to use them.

The problem went like this: you are given three strings of total length up to 300000. For each length L, how many triplets of substrings of these three strings exist such that all three substrings are equal and have length L? If a substring appears several times in a string, its occurrences are counted separately.

Thanks for reading, and check back next week!

Monday, July 21, 2014

This week in competitive programming

As advertised, the week started with IOI 2014 (problems, results, top 5 on the left). I like the problem "Game" a lot, since it's both interesting to solve and has a very simple but unusual setting. Two players are playing a game on N vertices. On each turn, the first player picks a pair of vertices, and the second player has to either draw an edge connecting them, or declare that there's no edge connecting them. The first player asks about each of N*(N-1)/2 pairs exactly once, and his goal is to figure out whether the graph will be connected after the game ends; the second player's goal is to keep the connectedness (ugly word, but is there a better choice?) of the graph unknown until the very last answer. N is up to 1500, time limit for the entire game is 1 second.

IOI and other high school competitions are well-known for tasks where the contestant has to implement one player of a game, and the judges provide the other player. However, a usual setting in games like this one would be for the competitor to be the player asking questions, and the jury to be the player giving answers - but in this case it's exactly the opposite: the contestant had to implement a strategy for the second player that would always win. Can you see such strategy?

The problems in general turned out a bit too easy, and did not allow to determine the single winner - three competitors solved all of them. Congratulations Scott, Ishraq and Yinzhan! (Scott did stand out by achieving the perfect score just 2 hours into the first day and just 3 hours into the second day)

On the weekend, Codeforces Round 257 gathered a big crowd of 3000+ participants (problems, results, top 5 on the left). Congratulations to semiexp on the victory!

Thanks for reading, and check back next week!