TopCoder Open 2012 Semifinal 1 Commentary

11:07 - that’s all for Semifinal 1. Join me later today for Semifinal 2, and then for the Wildcard! Semifinal 2 starting time: http://www.timeanddate.com/worldclock/fixedtime.html?msg=TCO+2012+Semifinal+2&iso=20121002T13&p1=867

11:06 - and the results are in! Tom’s 250 and Dlougach’s 1000 did fail indeed, so did Tom’s 500. All other solutions passed. Egor, ACRush, RAVEman to the finals, iwi, SergeiFedorov, Romka and sdya to the wildcard round.

10:56 - not much news from contestants. It looks like Tom’s 250 and Dlougach’s 1000 will fail, no news about other solutions.

10:49 - PaulJefferys got -25 on Tom’s 500 (not 250 which we know to have a bug), and on iwi’s 500, sdya got -25 on dolphiningle’s 500 in the last seconds. Waiting for systest!

10:47 - sdya killed exod40's 500. Apparently his resubmit was not for nothing.

10:45 - Since the difference between 7th and 8th place is 60 points now, it looks like it’s almost riskless for 7th or 6th place to challenge blindly.

10:43 - No more challenges yet, most people are reading Egor’s and ACRush’s solutions.

10:40 - Romka has killed Dlougach’s 250.

10:38 - dolphinigle has resubmitted both his 250 and his 500, sdya has resubmitted his 500. It would seem that dolphinigle has the best chance at challenging.

10:35 - And Dlougach submits 250 just 7 seconds before the end! Now it’s Egor, ACRush, Dlougach at the top. MikhailOK suggests the best challenge opportunity is integer overflow in 250.

10:33 - Some other contestants from China are recording ACRush's duplicate screen using a camera on their laptop. And he does submit his 1000 just 1 minute before the end! Egor has given up on his stresstesting since his stupid solution doesn't work on the first sample.

10:24 - Egor is writing a stupid solution for 1000 to compare with his solution on random testcases - great thinking! I think that's the best thing he can spend his time on now. Meanwhile, Dlougach submits 1000, not sure if he has changed his matrix to be of size k or have optimized his solution in some other way.

10:15 - And Egor submits 1000! I was right that his solution looks good.

10:10 - ACRush, Egor and Dlougach all seem on the right track in the 1000 - they have matrix power, and they have some formulas for the matrix. Actually, Egor seems to be the closest to our solution as his matrix has explicit formulas and has size k, which is the right thing to do. ACRush computes the matrix in some complicated way which doesn’t work. Dlougach seems to have the examples passing, but his matrix is not of size k but of size k^2, which presumably causes timeouts.

10:03 - ACRush, Egor and SergeiFedorov solved 250+500, iwi solved 500, everybody else except Dlougach solved 250, Dlougach still working on 1000. His projected score on 1000 is approaching scores everybody else has on 500, though.

9:59 - most people are implementing something with disjoint-set-union structure for the 500, so it seems that everybody is on the right track and we’ll see many 500 solutions, so many people will try to solve 1000 and thus it’s possible all three finalists will solve everything.

9:51 - ACRush and Egor have 250+500, everyone but the two people who started with 1000 have 250.

9:47 - 1000 solution - it was right there, but we were missing it for some time :) So we should do a DP with “how many last numbers are linearly independent” as the state. It’s straightforward to count how many ways are there to transition from a state to another state, since all situations are essentially the same: if we know that x last numbers are linearly independent, it doesn’t actually numbers what the numbers are themselves. And of course we do fast matrix power to handle that n can be up to 10^9.

9:39 - Meanwhile, ACRush has submitted 250 and 500 and 7 other people have submitted 250.

9:37 - The problem statement looks like Burrows-Wheeler Transform, but it doesn’t seem relevant to the solution.

9:34 - The 500: given a prefix of a permutation, find the lexicographically smallest permutation with that prefix that is one big cycle. I’ve test-solved this problem before the TCO so I already know the solution, but it’s actually quite straightforward anyway. When placing each unknown number in the permutation, we place it to the smallest possible number unless that number would form a cycle, in which case we place the second smallest possible number - it will not form a cycle in that case.

9:31 - it seems that Tom’s solution in 250 has an overflow bug.

9:26 - Essentially, it means that each k consecutive numbers must be linearly dependent as vectors in Z_2^(log m). This is always true when k > log m. When k <= log m, it looks like when choosing the next number, the only thing that matters is the dimension of the space defined by the previous k-1 numbers.

9:24 - The 1000 problem: count how many ways are there to choose n numbers each up to m (where m is power of two minus one) so that for each consecutive segment of k of those numbers (segments [1st, 2nd, …, kth], [2nd, 3rd, …, (k+1)th], and so on) some non-empty subset of that segment xors to 0.

9:19 - Problem statements as contestants open them: http://apps.topcoder.com/forums/;jsessionid=0CE09A8F5F29689F1259D2D102B38B34?module=Thread&threadID=763756&start=0&mc=2.

9:18 - And ACRush readily submits the easy. It looks like there’s no catch, it’s indeed straightforward.

9:14 - This problem looks straightforward. The white connected components actually correspond to triples of consecutive equal characters in each string, and the ones adjacent to the boundary are those adjacent to the boundary in at least one string. So it looks like the answer is something like total_length_of_white_in_A*total_length_of_white_in_B*total_length_of_white_in_C+(same for black)-total_length_of_white_in_A_not_adjacent_to_bounary*(same for B)*(same for C)-(same for black).

9:11 - Dlougach and iwi start with 1000, everybody else with 250. 250 problem statement: you are given three strings A, B, C. Let’s color 3D cell (i,j,k) white if and only if A[i], B[j], C[k] are all the same. Now we need to count the number of white cells that are in the connected components adjacent to the boundary. A, B, C are up to 2500 characters.

9:08 - One minute before start.

9:05 - Spectators can log into the arena, but the contestants can’t see their messages. However, they can see who’s in the room. It looks possible to pass some information that way (as in “I will enter the room if your solution looks wrong”).

9:02 - Jessie tells everybody to line up for introductions.

9:02 - 250, 500, 1000.

8:58 - Almost nobody is preparing, people are just walking around and chatting.

8:54 - Jessie says ten minutes before start.

8:53 - There seems to be some admin activity onstage. Apparently one machine is not working?..

8:50 - Exclusive commentary from Gennady Korotkevich - it turns out Gena is closely following the TCO and is watching this semifinal. He says that it’s a pity that rng_58 doesn’t get to defend his title - couldn’t agree more.

8:48 - And here’s the (one of) prediction contest current standings: http://snarknews.info/showvote.cgi?data=tco2012.

8:45 - The overview of all semifinalists: http://snarknews.info/index.cgi?data=tco/2012/finalists&head=index&menu=index&year=2012&contest=tco&class=tco2012. This round includes those with “1” in the last column.

8:43 - It looks like we have two Java coders - Egor and theycallhimtom. Everybody else is in the ugly world of C++.

8:38 - The contestants started preparations. Not much to do since Arena and plugins are already set up, and there’s no Internet access to set up additional software. As usual, C++ coders are writing #includes.

8:33 - Hi! This is live commentary for TopCoder Open 2012 Algorithm Semifinal 1. They’ve just opened the arena but haven’t let the contestants to start preparations yet, so 12 anxious people are walking around :) I will post commentary by updating this post.