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