TopCoder Open 2012 Finals Commentary

16:09 - That's it about this TCO. See you next year! Feel free to ask me questions in comments, I'll do my best to answer.

15:57 - Marathon results! ainu7 is the champion, Psyho is second!

15:54 - Algorithm results! Both 500s and ACRush’s 250 fail. Egor, meret, RAVEman are the only non-zero scorers, in that order. Egor is the champion!

15:48 - They’ve announced design results (which were alredy known in advance), now development.

15:31 - I've taken a look at RAVEman's and andrew's 500s, and they both only consider moves by small_constant*first_vector+other_small_constant*second_vector. I fear that doesn't work for the following reason: when the vectors are very long, close in length to the size of the board, there can be two cells that can only be reached from one another via a linear combination with larger coefficients. So I'd bet on both 500s failing.

15:29 - They are starting announcements, but they usually do other tracks first and algorithm last.

15:21 - Waiting for systest. Currently RAVEman with just 500 first, andrewzta with just 500 second, Egor, meret and ACRush with just 250s from third to fifth. Let's hope at least the champion has one working problem :)

15:18 - ACRush one more -25 on RAVEman's 500, kills RAVEman's 250, -25 on meret's 250. Meret has got -25 on both standing 500s.

15:18 - Egor has got -25 in the meantime as well. Still above meret.

15:17 - And gets -25. Meret is also preparing the testcase for RAVEman’s 500.

15:15 - ACRush is preparing a testcase for RAVEman’s 500.

15:13 - assuming both remaining 500s will also fail, it's Egor vs meret challenge battle. Both have made their moves, still less than 50 separates them. ACRush gets -25 on Egor's 250.

15:10 - meret bring’s down marek’s 250, RAVEman brings down iwi’s 500, Egor brings down Andrew’s 250.

15:08 - admins are giving out a prize for another contest during intermission, using loudspeakers. What an AWFUL decision!

15:07 - RAVEman preparing a large and presumably tricky case for 500.

15:05 - iwi submits 500 but I'm not sure he has at least tested for TLE.

15:03 - marek.cygan doing nothing, meret writing his 1000, his solution has “layers” in it - we had an idea that involved layers, too, so that can be a correct solution.

15:02 - most people fight with not-passing-examples in 500.

15:00 - apparently RAVEman's 250 is wrong, and he's fixing it... And he resubmits!

14:59 - five minutes before the end. Marek has submitted and resubmitted his 250. I’m betting on many last-second submissions.

14:52 - actually nika’s hypothesis seems to be true and it’s even not hard to construct that ordering: let’s try all possibilities for the first vertex. Then, at every step the next vertex can be constructed by doing the following: if a vertex has more edges to the already constructed vertices then it’s closer to the last marked vertex. Also, if a vertex has less edges to the vertices yet to be constructed, then it’s also closer to the last marked vertex. And the only way both those numbers can be the same for two vertices is when they’re isomorphic. So we just reconstruct the ordering greedily.

14:45 - meanwhile, andrewzta and RAVEman have submitted the 500. I have a bad feeling about andrewzta's one, though, as he has probably patched his solution quickly to pass the sample case but he couldn't rewrite a large part of his solution since I've seen it.

14:44 - if that's true, then the solution is to handle groups of isomorphic vertices at once, and then the number of states will be really small - just linear.

14:42 - nika has the following conjecture for 1000: omitting isomorphic vertices, the ordering of vertices is uniquely determined up to a complete reversal.

14:41 - andrewzta's medium seems far from completion - he iterates over pairs of vectors but his check if the given pair of vectors gives a symmetry is too simple.

14:38 - shangjingbo’s 1000 is not working only on the last example case, which is huge. Poor guy :(

14:34 - RAVEman optimizing his 500, it’s working in 0.9s on what seems to be close to worst case. Will he submit soon?

14:29 - ACRush coding 500, meret coding 1000.

14:27 - Rustyoldman reports that iwi and andrewzta are coding their 500s.

14:18 - Meanwhile, ACRush resubmits 250. Current standings: Egor (with resubmit), RAVEman and meret (no resubmit), andrewzta and ACRush (with resubmit). ACRush has also opened the 500. RAVEman is coding on 500 and shangjingbo is coding on 1000.

14:15 - About 1000: maybe something like this can work - let’s start putting numbers from 1 to N. After we’ve put numbers from 1 to K, all that matters is which vertices are assigned the last D numbers, and which vertices have an assigned number at all. And because of the restrictions, I’d hope that the number of states will be quite small. But I’m not sure how to estimate that.

14:08 - Rustyoldman reports that nobody is still coding on 500 or 1000. meret submits 250.

14:06 - By the way, bmerry was test-solving 250 and 1000 in this round, and it took him 12 and 44 minutes respectively.

14:05 - RAVEman submits 250 as well. I’m trying to think about 1000...

14:02 - andrewzta submits 250, iwi gave up on 1000 and opened 500. ACRush went to 1000 after 250. Marek.cygan gave up on 500 and went to 1000. It’s 25 minutes into the contest and it’s weird we have just 3 submissions on the 250.

13:58 - about 250: First, we can forget about E by XORin S and E, and just making player A’s goal to achieve all zeroes. How can player A win? The only way is that the entire string has just one segment of consecutive ones. But how could B allow to make that happen? If the string has length of at least 5, it looks like B can always prevent that on his move, so when length is at least 5 we should just check if A can win in one turn, and when length is at most 4, the number of states is just 16 and we can analyze the entire game using the usual means.

13:55 - meanwhile, Egor submits and resubmits the easy, adding one more small “if” clause, ACRush submits the easy a bit later but has higher score because of Egor’s resubmit. Everybody who’s opened 500 and 1000 is working on paper.

13:51 - I’ve test-solved 500 before this contest. The basic idea is - any good tiling is defined by two “basic” shift vectors. In fact, if we fix the two basic shift vectors, then all vertices are split into groups of equal vertices, and we just need to check that all vertices in each group have the same color (it won’t be a problem to form a connected piece afterwards). Now all that remains is to iterate over all possible pairs of shift vectors and carefully check everything. This can be simplified further by noticing that we can always choose one of the basic vectors to be horizontal (but it might be up to size^2 in length then).

13:50 - formal problem statements: http://apps.topcoder.com/forums/?module=Thread&threadID=763920&start=0&mc=2.

13:47 - 500: A good tiling of the plane that is split into grid cells that are colored black or white is such tiling where each piece is a connected block of cells, all pieces are equal (will coincide after some transition), including colors, and the tiling itself is periodic (for each three tiles X, Y, Z there’s a tile at Z+(Y-X)). What is the smallest possible size of piece of a good tiling which has a given rectangle as its part?

13:45 - 1000: you are given a connected undirected graph with M vertices, and must assign distinct numbers from 1 to N (N >= M) to its vertices so that adjacent vertices have numbers differing by at most D, and non-adjacent vertices have numbers differing by at least D+1. How many ways are there to do that? N is up to 100, M is up to 50, D is up to 8.

13:43 - marek goes for 500, iwi and shangjingbo go for 1000, everybody else for 250.

13:41 - 250: you are given two strings S and E of the same length, consisting of ‘0’ and ‘1’ characters. Player A can (but is not forced to) choose its substring and change all ‘0’s to ‘1’s and vice versa. Player B can (but is not forced to) do the same for just one character. Player A’s goal is to obtain string E, and player B’s goal is to prevent him from doinh so. What is the minimum number of turns he needs (assuming both play optimally)?

13:37 - everything looks fine this time. Two minutes before start!

13:35 - based on this, spectators propose a new strategy: if meret and ACRush submit a problem very quickly, code maximum flow _before_ opening it :)

13:34 - ACRush has apparently been coding most of this time, implementing Dinic algorithm for maximum flow.

13:28 - not much happening now, people are relaxing, admins say everything will be fine this time :)

13:17 - Egor and andrewzta playing air hocket. Meret, [[iwi]] walking around the room. marek.cygan talking with friends. ACRush looked at something on a laptop and went walking with a surprised face. RAVEman talking with friends as well. Can’t find shangjingbo in the arena.

13:14 - the problems turned out to be more serious than expected. The new start time is 13:40. Hysterical laughing from contestants :)

13:12 - it looks like the contest won’t start at 13:15, too. The technical issues still unresolved. This must be a very nervous time for all contestants.

13:05 - admin announcement: The match will start at 13:15.

13:02 - Egor and andrewzta are playing "Cities": each player should name a city that has not been named before that starts with the last letter of the previous named city. So far: Moscow, Warsaw, Wrozlav, Voronezh, Hurghada, Athens, Sarajevo, Osaka, Astana, Amsterdam, Malmo, Orel, Ljubljana, Astrakhan, Novosibirsk.

13:00 - marek.cygan: "The winner will be the one who can find the problemset".

13:00 - 250, 500, 1000. No news on contest start time.

12:59 - it looks like the contest start is postponed, there’re some technical issues.

12:49 - 10 minutes before the start. Andrewzta showed up, now almost everybody is coding the easy problem from the wildcard round for practice, except meret who’s writing max flow again.

12:44 - Everybody is preparing except Egor and andrewzta - the two Java coders. One doesn’t need much preparation when there’s no necessary bolierplate :) Egor is already ready, andrewzta not yet here.

12:35 - Hi! This is live commentary for TopCoder Open 2012 Algorithm Finals. The round will start in about 25 minutes. I will update this post with new comments.