Wednesday, September 28, 2011

TCO 2011 Algorithm Finals live coverage


16:29 - and it’s over, and I guess so is this coverage. Thanks for following! Thanks a lot to TopCoder, to all organizers and problem preparers, and to all participants and sponsors. It was a great event!

16:28 - Studio champion is abedavera.

16:25 - Mod Dash winner is Yeung.

16:23 - no changes in Marathon standings compared to the provisional results. Final sequence: Psyho, wata, ainu7, jdmetz, nhzp339, ploh, ACRush, chokudai, wleite, Rizvanov_de_xXx, RAVEman, komiya.

16:21 - full results: rng_58, bmerry, nika, ACRush, mikhailOK, PaulJefferys, [[iwi]], lyrically.

16:20 - now algorithms. lyrically’s 250 fails. PaulJefferys’ 250 fails. Everything else stands. rng_58, bmerry, nika!

16:11 - the awards ceremony has started. The first category up is design.

16:07 - and one more system test preview: lyrically says that he discovered a timeout for his 250 during the intermission - his solution had an additional log-factor.

16:04 - the reasons for resubmissions were also revealed: nika resubmitted because of special handling for 1xn, where the sum is exactly 0 or 9*n. mikhailOK resubmitted because of no handling of “n solutions” at all. And ACRush resubmitted because one of the arrays in his solution was up to 600, and numbers that arise might be up to 1000. He says that his original version might also still work, since those big numbers are never useful for a correct solution.

16:01 - and a shocker: this is actually rng_58’s last match as a participant for some time! He will be joining mystic_tc to help run SRMs from October.

15:57 - some news from the floor: first, the three Japanese guys did not agree on the strategy beforehand - it was a coincidence. Second, PaulJefferys said he was just 3 minutes away from finishing the 1000. Third, lyrically had the “no -1” case working very quickly, and was debugging the -1 case for the last half hour - and it is actually the easier case!

15:35 - no more announcements for now, the awards ceremony is scheduled for 16:00. I would expect algorithm finals results at 16:30 or so.

15:32 - they have also announced winners of a raffle, which I won’t post here.

15:19 - they started to announce the winners... of various side competitions. The winner of the MemSQL poker tournament is 7ania7 (prize: MacBook Air), the winner of the treasure hunt is mikhailOK (prize: trip to TCO2012), the winner of FIFA tournament is nika (prize: trip to TCO2012), the winners of the amazing race are theycallhimtom, pieguy, mikhailOK (prize: trip to TCO2012), the winner of the holiday photo contest is mikhailOK (prize: trip to TCO2012).

15:18 - rng_58 says he didn’t test his 1000, but the last two challenges have really increased the confidence it’s correct.

15:15 - ACRush says that his solution before resubmission might be correct as well: it had a DP array that went up to 600, but the input might contain numbers up to 999. But when the input contains a number more than 450, the answer is no solution, and his solution most probably would still return no solution. So 1xn was not the reason for his resubmission.

15:11 - mikhailOK says that his resubmitted solution still has a bug: when the number of solutions is 0 modulo 10^9+7, but not 0 proper, it will return wrong answer. But I doubt that will fail the systests.

15:09 - ACRush and lyrically both challenge rng_58’s solution, most probably on a random testcase. It survives!

15:08 - the rumor has it that the reason for mikhailOK’s resubmit was that he actually didn’t cover the “n solutions” case at all.

15:07 - lyrically still seemingly testing his own 250 solution on a large testcase. Maybe he wants to make sure it’s non-trivial.

15:06 - 3 and a half minutes to go in the challenge phase. I still expect challenges, at least at the last minute.

15:05 - rng_58 still very calm and doesn’t bother to read 500s.

15:05 - no, [[iwi]] actually started to read the 500s again.

15:04 - [[iwi]] is not challenging as well. Just moves a window around the screen repeatedly.

15:03 - rng_58 is not challenging. He just looks at the scoreboard.

15:02 - everybody reads 500s. No action there yet.

15:00 - nika brings down [[iwi]]’s 1000-pointer. This looks to be a blind challenge.

15:00 - challenge has begun! 10 minutes that may bring a lot of news.

14:55 - ACRush is preparing testcases for 500. bmerry is preparing the 1xn testcase for 500, which makes us think his solution handles it correctly. lyrically is preparing a random large testcase for 250.

14:54 - [[iwi]] submits the 1000-pointer with less than 1 minute to go! Unfortunately, that’s only enough for 7th place. The order before the challenge phase is rng_58, bmerry (3 challenges below), PaulJefferys, ACRush, nika, mikhailOK, [[iwi]], lyrically.

14:53 - rng_58 opens the 500-pointer - the only way to reach him is through challenging, so I guess he needs to try to steal those challenges away from others, too.

14:52 - Free ice cream has shown up outside the arena

14:51 - nika has been coding a stress-test to compare his solution against a dumb one, a pretty good move I guess. He could also generate some challenge cases that way. ACRush is also testing the 500, then 250 - he abandoned the 1000.

14:48 - rng_58 submits the easy to move into first place. He didn’t test anything except the examples, but for 250 that should be enough.

14:46 - we’re sorry for no updates recently - the internet connection is very flaky here, and goes off for several minutes from time to time.

14:45 - very exciting last 10 minutes. rng_58 must be really nervous now. lyrically still has a good chance at submitting the 1000, too.

14:36 - rng_58 submits the hard, and lyrically submits the easy! rng_58 will be in the lead if he solves the easy in the remaining 17 minutes. I don’t anticipate any of the 5 “usual strategy” guys to even come close on solving the 1000.

14:35 - the Japanese contestants’ strategic move makes the contest really exciting. Kudos!

14:33 - he resubmits, and opens the 1000. Everybody is working on 1000 except lyrically who’s solving 250. Top 5 are: bmerry, PaulJefferys, ACRush, nika, mikhailOK.

14:32 - mikhailOK still debugging his solution. I guess he wants to make sure he resubmits it just once.

14:30 - all 3 Japanese coders seem to be implementing the solution we described below. [[iwi]] has implemented everything except “-1” case, and is passing some of the examples. lyrically has got all examples except the last one passed, but decided to open the 250 - maybe to switch subjects for a short time. rng_58 has written lots of code that looks correct, too - but I’m not sure how close he is to submitting.

14:25 - it looks like mikhailOK has found the same bug, and is fixing his code now, one more resubmit coming I guess. This might be actually quite important at the challenge phase as two of the guys didn’t resubmit :)

14:22 - mikhailOK also submits and moves into third place. Now 5 coders have two problems submitted and 3 have none. But those 3 might actually still be on a winning strategy, since almost any score on 1000 will be higher than those scores on 500, and 250 is really quick to code.

14:20 - and nika also resubmits and opens the 1000. Now the top 4 are bmerry, PaulJefferys, ACRush, nika. We think that the reason for resubmits might be 1xn testcases since those should be handled separately.

14:19 - PaulJefferys also submits 500 to get into third place, and opens the 1000.

14:18 - ACRush has been testing the 500 for a long time, and finally resubmitted! Meanwhile, bmerry has submitted the 500 as well. The top 3 are: nika, bmerry, ACRush. bmerry and ACRush are reading the hard, nika still hasn’t opened it.

14:12 - the solution for the hard is still quite tedious since one has to deal with “-1” as well.

14:10 - nika is the first to submit the 500! He’s now in the lead. ACRush submits the 500 as well, but score is lower and he’s still in 2nd place. Both guys didn’t open the 1000 yet.

14:07 - so here’s the deal (mostly by Vitaliy): every of the 2^18 ways gives you the following information: we can go from position X to position X+delta for all X in some segment [L, R] (which is derived from the fact we must not go outside the borders). Now, we put all ends of those segments for both halves into one set of events, sort them, and go from left to right. We maintain how many segments are there open now for each delta in each half, and that allows us to quickly find the number of combinations for the current X, for the total running time of 18*2^18 or something similar.

14:03 - I’m surprised that nobody has submitted the medium yet. We must be missing something. The hard seems to be some kind of meet-in-the-middle (we just iterate over all 2^18 ways for each half), but we can’t figure out how to combine the halves yet.

13:55 - one hour to go. In the hard problem, we’re not asked about “permutations” exactly: several cards may go into one slot. The slots are numbered.

13:54 - meanwhile, 5 coders have submitted the easy, in this order: ACRush, nika, bmerry, PaulJefferys, mikhailOK. The 3 Japanese coders are still solving the hard, the rest are solving the medium.

13:46 - the medium problem: you start with a 50x50 grid of digits, and calculate sums of “crosses”: c_ij = sum(a_lm where l equals i or m equals j). You now need to reconstruct the original grid, and return it, or return the number of solutions if there are multiple solutions (or no solution if there are none). This one looks to be obvious as well: if we sum all “crosses” corresponding to one row, we will sum all numbers in that row n times, and all other numbers once. By subtracting two of those, we can find the difference between every two rows, and similarly for columns. Then, we iterate over the sum for the first row and for the sum of the first column. After that, we know the sum in every row and the sum in every column, and then we know all numbers (row + column - cross = number). Since the sum of first row plus sum of first column is the first cross plus a small number, there are only 450*10 cases to check for those two sums, and each case can be checked in 50*50 operations, which should be fast enough.

13:41 - the Japanese coders will now know that 250 is very easy, so their strategy seems to be quite solid.

13:39 - nika submits the easy for 230.88 points.

13:36 - ACRush submits the easy for 240.80

13:34 - the size of the board in the easy is 20x20, there are 20 throws. So I guess one has to calculate the expected probability when there are n throws left and the current difference in scores is m, and then iterate over all possibilities for the throw and choose the one that gives the best winning probability, resulting in a simple DP.

13:34 - in the hard Number of slots is not greater than 10^6, Di are up to 10000. Also there is information “card 1 can be Dn positions right or left to the card n”.

13:32 - the hard problem statement: count the number of card permutations (modulo “some large number”), where you are given the information like “card i+1 can be exactly Di positions right or left to the card i”. There are also special cases: Di = 0 - two cards must be at the same position, Di = -1 - card positions may be arbitrary. Number of cards is not greater than 36.

13:31 - the easy problem statement: you are given a rectangular board of digits, and you throw darts at it. At each throw, you select a 3x3 square and your dart hits each of its cells with probability 1/9. There are two players that throw darts one after another, and the one who scores more wins. In case of a tie, a fair coin is tossed. What is the probability that the second player will win after the given number of throws?

13:30 - all 3 Japanese contestants have opened the hard problem!!! All others start with easy.

13:28 - the introduction is over, 10 seconds to go!

13:25 - contestants are lining up for an introduction, in alphabetical order :)

13:23 - 6 minutes to go, still no loud introduction. Are they going to skip it?

13:20 - here are the results of a prediction contest that a Russian programming contest news website ran (before the semifinals took place): http://158.250.33.215/~ejudge/showvote.cgi?data=tco2011

13:17 - 12 minutes before the start.

13:14 - today, the coverage is provided by Petr, KOTEHOK, marek.cygan and Vitaliy. If you have any questions for us, I guess the best way to ask them would be in the Competition Arena, in the room where all contestants are (“2011 TCO Algorithm - Championship Round”). Contestants won’t see them (and our clever answers), don’t worry!

13:12 - lyrically seems to have just coded an efficient max-flow implementation. PaulJefferys is solving the easy problem from the first semifinal (which is the only practice round available, I guess).

13:08 - 7 out of 8 contestants use C++, and they’re busy writing long lists of #include’s. MikhailOK, being the only Java coder, has nothing to do and spends his time just thinking about nothing. Go Java! Go Russia!

13:02 - waiting for the main event to start. Contestants were just allowed on stage. See http://petr-mitrichev.blogspot.com/2011/09/topcoder-open-2011.html for a small overview of who competes today!

TopCoder Open 2011

The most prestigious event for individual algorithmic programmers is taking place right now in Hollywood, Florida - it's TopCoder Open 2011 time. I have already been eliminated (twice :)), but that means I will provide live coverage for the finals, where 8 best coders will compete. Here are the participants (in alphabetical order):

[[iwi]] from Japan, currently ranked 43rd in the world. He's already advanced to the TCO semifinals twice, in 2008 and 2009, but this is the first time he made it to the finals.
ACRush from China, currently ranked 3rd in the world. He has already been in the TCO finals twice, in 2008 and 2010, but is still to score his first win.
bmerry from South Africa, currently ranked 4th in the world. He has also been in the TCO finals twice, in 2007 and 2010, but haven't won yet.
lyrically from Japan, currently ranked 9th in the world. I think it's his first trip to the TCO - and he got through to the finals (the semifinal also happens onsite).
mikhailOK from Russia, currently ranked 26th in the world. It is also his first trip to the TCO.
nika from Georgia, currently ranked 7th in the world. He's already been to the TCO semifinals back in 2008, but it's his first time in the finals.
PaulJefferys from the United Kingdom, currently ranked 19th in the world. He's also been in the TCO finals last year, in 2010.
rng_58 from Japan, currently ranked 5th in the world, and the current TopCoder Open champion - he won in 2010, and is the only finalist to have won previously. He has never been to the TCO before last year.

Tune in to this blog today at 13:30 TopCoder time (click the link for other timezones) for live coverage, in less than 4 hours!

Tuesday, September 27, 2011

TCO 2011 Algorithm Semifinal 2 commentary

14:51 - The results have been announced. ainu7’s 600, Kankuro’s 900 and ACRush’s 250 and 900 failed. [[iwi]], rng_58 and ACRush advance to the finals, unbing, nika, mikhailOK and Kankuro to the wildcard. That's it for this commentary!

14:47 - Kankuro’s 600 has integer overflow. We know nothing about other solutions that might fail.

14:44 - scoreboard after challenge phase:


14:43 - scoreboard before challenge phase:


14:40 - he also tried to challenge Kankuro’s 900, also unsuccessfully. That’s it for the challenge phase!

14:39 - RAD. tried to challenge [[iwi]]’s 900, unsuccessfully.

14:38 - unbing brought down Kankuro’s 600. That moves him into 5th place on preliminary standings!

14:38 - rng_58 and ainu7 stopped reading others’ solutions, other ten contestants are still trying to find some bugs.

14:37 - Let me remind that this blog is actually a team effort :) Petr, KOTEHOK, bmerry and Vitaliy trying to bring you the latest information.

14:36 - R.A.D.’s 250 is still popular, but may be it’s too large to be safely challenged.

14:35 - most of the challenge phase is over, just 4 minutes remaining. It’s just 10 minutes at the onsite rounds. I still expect a few last-second challenges, though.

14:34 - Two contestants are reading Kankuro’s 600, but seems that they do not see a bug there.

14:32 - Four contestants are reading solutions of ACRush. What are they trying to find there?

14:32 - ACRush tries to break ainu7, but unsuccessfully.

14:31 - mikhailOK’s 600 is successfully challenged by ACRush.

14:30 - Contestants like to read 250, 600 and 900 of the others nearly equally. The most popular viewed solutions are Kankuro’s 900 and R.A.D.’s 250.

14:29 - 40 seconds before Challenge phase.

14:28 - ACRush is doing something with a large random case of many numbers. Kankuro has tested his 600 and got a negative number, his solution seems to be wrong. Some contestants are watching history and write test generators.

14:25 - Coding phase has ended. Some people think that 600 must be the most challengeable problem though there are seven sample tests. We’ll see in the few minutes.

14:23 - Kankuro has submitted 900 and now he is second in the scoreboard with all three problems complete. Some other contestants are still testing their solutions, but they seem not to pass the samples.

14:19 - the scoreboard is: ACRush, [[iwi]], Kankuro, mikhailOK, rng_58, nika, ainu7, unbing, LayCurse, pieguy, _Romka_, RAD.

14:18 - ACRush is the first to submit 900 for 551.77, [[iwi]] follows closely after him, but just for 383.96. It is enough to put him into second place, though.

14:13 - nika was one of the first to open 900, but now he has some five-dimensional dynamic programming uniformly filling his screen, seems that it is very hard to debug

14:13 - ainu7 has resubmitted his 600.

14:12 - rng_58 submits the medium. He’s in 4th place after ACRush, Kankuro and mikhailOK.

14:11 - ACRush finally compiled his solution for 900, but it did not pass the first sample

14:09 - RAD. submits the easy. Is there time still left for him to solve another problem? He opens the 600 with 15 minutes to go.

14:07 - ainu7 submits the medium for 305.75 - he still doesn’t have the easy. He opens the hard.

14:06 - finally milkhailOK was the third to submit his 600 scoring 276.88 points

14:04 - mikhailOK has passed large sample cases 5 and 6 in 600. He also has a function “getStupid” in his code which may be used in something like stress-tester.

14:03 - there seems to be not much difference caused by 600/900 instead of 500/1000, as all scores on 600 are low and it seems most likely that all scores on 900, if any, will be higher.

14:02 - mikhailOK is testing 600 and it seems to pass at least some non-trivial cases, may be we can expect submit from him after some time; most of others are still coding something.

13:57 - most of contestants working on 900 have just non-moving flashing cursor in their code, they might be thinking of something; though [[iwi]] is writing something like a testing-code.

13:57 - at this point, I think it should be pretty obvious to the contestants that many 600s and 900s may fail, so accuracy will be the deciding factor. I guess there are two main strategies - make sure you get one absolutely correct and forget about the second, or submit two hoping that at least one is correct :) Not many have the second strategy available, though.

13:54 - Kankuro was the second to submit 600 (337.64 points). He still continued to test it for some time, then finally opened 900.

13:54 - 30 minutes left.

13:53 - ACRush is writing his 900 pretty fast.

13:52 - [[iwi]]’s 900 works on some cases, but on sample case 2 it gives a negative answer.

13:51 - RAD. and ainu7 are the only contestants still to submit anything.

13:50 - it seems like at least three contestants are testing their 600, but it does not work even on small cases.

13:48 - the feeling is that the 600/900 in this round are completely about implementing an intuitively easy solution that is really hard to implement.

13:45 - ACRush submits the 600 after testing it for a very long time!

13:42 - Vitaly has suggested a nice implementation of 900 solution: you can compress coordinates, enumerating them from 1 to 300, make 300x300 matrix, then go from top to bottom, monitoring the current segment on the corresponding y-coordinate, expanding it when there is a point outside its current border of the segment, and shrinking the segment, if there is no point in the whole rectangle lying to the left from the left border of the segment (or to the right from the right border) and completely downside to the current y.

13:36 - but this seems to be fixable if handled carefully. Let’s build the “left border” and “right border”. If they don’t intersect, we’re done. Whenever they intersect, we may choose either path. Let’s try to formalize this :)

13:34 - however, the below solution for 900 has a problem: suppose we have points (0,9),(1,10),(9,0),(10,1). Then “minimal” paths from (1,10) to (10,1) and from (0,9) to (9,0) interfere. The correct solution in this case is to take cells (1,9) and (9,1) and an arbitrary path connecting them.

13:31 - it looks like nika abandoned the 600 and is working on the 900.

13:28 - the last problem doesn’t seem very difficult as well. Let’s consider the topmost point, the leftmost point, the bottommost point and the rightmost point. Then we just need to connect those in the following way: consider going from topmost point to leftmost point. It looks like this:
#
#
###
###
#####
#####
and so on. So we just need to find all points (x,y) such that there’re no other point (x’,y’) such that (x’>=x) and (y’>=y).

13:23 - [[iwi]] went straight from the 250 to the 900. It looks like a variant of convex hull, where the points are discretised. A set is convex if one of the shortest paths between A and B (for any A, B in the set) through the lattice grid is contained within the set. The return value is the area. The constraints on the given coordinates are quite large (~10^9). There are up to 300 input points.

13:20 - there’s lots of corner cases there, though.

13:18 - half of the contestants submitted 250, four of them are opened 600 but did not start coding

13:18 - and chains of odd lengths are basically counted by “layers”. Cells with x>=maxx-dx and y>=maxy-dy have chain of length 1, then chains with (x>=maxx-3*dx, y>=maxy-3*dy, and at least one of x
13:15 - the 600 seems easier than 250. All cells can be split into chains (by connecting (x, y) with (x+dx, y+dy) and (x-dx, y-dy)). For every chain that doesn’t have any coin, the answer is the size of the chain divided by 2 - either 0 or 1 cells in each chain will be unused. For chains that have coins, they are effectively split into smaller chains. So the only thing we need to find out is how many chains of odd length are there.

13:15 - ACRush submits the 250 for 223.21.

13:09 - nearly half of the contestants started coding, nika submitted his solution and gained 239.26 points

13:12 - nika has opened the 600. There is a chessboard (very big - up to 10^9 by 10^9) with some coins on it. You need to find out how many times you can place a coin on (x, y) and another on (x + dx, y + dy) such that you never place a coin on a square which already has a coin. dx and dy are given (also up to 10^9). The initial set of coins has up to 50 coins.

13:10 - column player can win in that situation because at her move, there are more columns than rows, so it’s always possible to choose one that doesn’t spoil the invariant.

13:09 - and question marks don’t add much - since the condition is independent for every row, it’s a pretty simple one to check even in the presence of question marks.

13:09 - nika gets the first submission on the 250.

13:07 - collectively, we’ve invented a solution: the column player wins if in each row, there is at least one cell of her color. The row player wins, if there is at least one row that is all of her color (or, in other words, if it is not true that each row there is either a cell of column player’s color or of the draw color).

13:05 - nika is starting to write solution, the others are still reading the statement

13:04 - matrix is 50x50. People don’t seem to know how to solve this yet.

13:02 - Everybody is starting with the easy problem.

13:01 - the easy problem is: given a NxN matrix with each cell colored with one of 3 colors, two players play the following game: 1st player crosses out a row, then 2nd player crosses out a column, and so on N-1 times until just one cell is left. If that cell is one color, the first player wins, the second color - the second player wins, the third color - a draw. Some of cells are ‘?’, meaning they are of each color with equal probability. What is the probability that each player wins?

12:59 - feel free to ask questions in Arena’s Chat Room 1.

12:58 - Contestants are finally at their positions. Best of luck to them!

12:57 - minus 3 minutes.

12:55 - Looks like there are 250, 600 and 900 point problems.

12:54 - Competitors are standing in the line preparing to be called to the stage. Intro is beginning.

12:49 - During setting up, people write often some well-known algorithms. One of most popular algorithms during this time is min-cost flow. Some people just write templates or solve practice

12:44 - Petr, Vitaliy and KOTEHOK writing this commentary today. bmerry might also offer some insight.

12:38 - People are setting up their workstation and writing solution templates.