TopCoder Open 2012 Semifinal 2 Commentary

15:03 - that’s it for Semifinal 2. Join me later today for the coverage of the Wildcard round at http://www.timeanddate.com/worldclock/fixedtime.html?msg=TCO+2012+Wildcard&iso=20121002T18&p1=867!

15:01 - results: dzhulgakov’s 275 and 950 fail, kalinov’s 500 and 950 fail, marcina007’s 500, wata’s 500. shangjingbo, marek.cygan, andrewzta to the finals, meret, Kankuro, Dmitry_Egorov, dzhulgakov to the wildcard.

14:48 - kalinov’s 500 will also fail.

14:42 - dzhulgakov says his hard solution fails.

14:40 - waiting for systests.

14:38 - nika says that several mediums will time out, and contestants themselves know that. Meanwhile andrewzta’s 500 goes down, and there are two more -25s.

14:37 - Right! Now everybody can see the submissions and it’s actually non-competitors who look at leaders’ solutions. (14:37:34) qiuiuu> spectators are interested in top submissions actually.

14:35 - no more action yet, we’re in the middle of the challenge phase.

14:32 - lots of people are reading shangjingbo’s and kalinov’s solutions. As in the first semifinal, solutions of leaders are attracting more interest, which looks illogical to me.

14:31 - (14:31:03) System> marcina007 unsuccessfully challenged shangjingbo's 500-point problem.

14:25 - dzhulgakov also submits the 950 with 30 seconds to go. The current situation: shangjingbo 1375, kalinov 1285, marek.cygan 1145, andrewzta 1084, dzhulgakov 1047. The only less-than-50 gap is between andrewzta and dzhulgakov. Waiting for challenge phase!

14:20 - andrewzta submits the 950. As things stand, he’s still fourth and needs two challenges to overtake the 3rd place, but solutions may fail at systest, you know :)

14:19 - Marek’s solution is the same as ours and kalinov’s. Kankuro has his solution timing out (and it has a weird “for (int t = 24; t >= 5; --t)” loop :)), andrewzta gets wrong answer and is trying to add more and more debug output.

14:14 - Marek submits the hard, 3 people with all problems now. Lining up nicely for the finals, but I’d guess there will be more submissions as the end approaches.

14:06 - pieguy opened hard abandoning his medium. wata had not opened easy, so he is either still working on medium or trying to finish hard.

14:04 - So his solution has complexity of 47 (for k) times 47*4 (for number of bad events happening) times 4 (for number of bad events on this team). The problem is solvable for much larger constraints!

13:59 - Here's how shangjingbo's solution works. We'll do inclusion-exclusion, with the basic event being “rabbit X gives a carrot to someone from his team”. Then how do we count the number of cases with T such events happening? We’ll do a DP over “first k teams, T events”. For a new team, we iterate over how many rabbits in that team give a carrot to someone in his own team, and multiply that by 4*3*.. to account for giving that carrot to different people on his team, and by c[rabbits][num] to account for different rabbits on the team taking part.

13:59 - Meanwhile we have shangjingbo and kalinov with all 3 problems, meret, andrewzta, marek.cygan, dzhulgakov and Kankuro with easy and medium, wata with medium only, pieguy, marcina007 and Dmitry_Egorov with just easy. wata is the only one that had not followed easy-medium-hard approach.

13:49 - Studio finalists are introduces quite loudly. Not sure how algo semifinalists could think about problems currently.

13:48 - shangjingbo submits the hard. His solution is even simpler than what we wrote below, he has just 47*(47*4) states in his DP. kalinov is writing something similar to our solution, but his solution doesn’t work on examples yet. meret is writing some solution which has a DP state of “5 numbers with sum up to 47”. Nobody else is writing code for 950.

13:45 - dzhulgakov also submitted medium.

13:44 - andrewzta is sitting with his notebook and pencil, trying to figure out 950.

13:43 - Marek has submitted the 500.

13:42 - Nothing changed during recent minutes, we are now into the second half of the contest.

13:36 - wata abandoned hard and switched to the medium instead.

13:34 - Easy and hard are DPs if we don’t have issues in our solutions, medium does not involve any standard approach.

13:32 - Medium submissions started to flow in, kalinov, shangjingbo, meret and andrewzta currently submitted and moved on to the hard.

13:31 - actually, 16 can be replaced by 4 since we’re just interested in how many team members are receiving the carrots, not which ones. We just have to be careful to multiply by appropriate coefficients to make sure we’re counting all possibilities.

13:28 - the complexity seems to be: 47 for the boundary position, 47*4 (actually 47*4/2) for the left-to-right number, 47*2 for the right-to-left number, 2^4=16 for the subset of this team that will receive carrots, 4 for the number of carrots from this team that go to the right (all remaining go to the left), and 4 for the number of carrots for this team arriving from the right. All in all, that’s 47*47*2*47*2*16*4*4=106314752, so that should work.

13:27 - here’s our idea for 950: let’s do a DP over “how many carrots cross the boundary between team x and team x+1 from left to right, and how many cross that boundary from right to left”.

13:26 - kalinov and shangjingbo submitted medium.

13:25 - All competitors but wata submitted easy and opened medium, wata still works on hard. This commentary is brought to you by Egor, who’ll be helping me during the rest of this round.

13:25 - 950: There are n teams with 4 players each, and each team brought 0<=a_i<=4 carrots. Find the number of ways to distribute the carrots in such a way that each carrot is given from a team to a different team. All carrots are considered distinct.

13:22 - actually, that solution was wrong, as ACRush has pointed out. The correct solution is: iterate over the set of “important” bits, and then just check if there’s a number that has one important bit set and all others cleared, for all important bits.

13:13 - 500: a set of numbers is called good when all bitwise ors of its subsets are different. What is the subset of the given set of numbers that is good and has the maximum sum of elements? Egor solved it in about 30 seconds: the “good” condition is equivalent to “each number has at least one bit that is zero in all other numbers”, so we can do a DP over “maximum sum of subset of first k numbers that have the given mask of bits as their chosen bits”.

13:11 - Three submissions for 275: shangjingbo, pieguy, meret.

13:05 - Problem statements as contestants open them: http://apps.topcoder.com/forums/?module=Thread&threadID=763801&start=0&mc=2.

13:03 - it looks to be a straightforward DP. For each segment of balls, we determine whether it's possible to remove that segment completely. To check that, we iterate over which two balls will be removed the last, and they separate that segment into subproblems.

13:01 - The 250 problem: you are given n balls (n is odd), each marked with either “left” or “right”. In one turn, you take one non-boundary ball and remove it and the ball to the left or right from it, correspondingly, until there’s one ball left. Which balls could be the last one left in the end?

12:56 - announcements are done, 3 minutes before start. There are several in-form competitors in this round: meret has won Google Code Jam just several months ago, Kankuro has won Russian Code Cup a month ago.

12:49 - There are two Java coders in this round as well: andrewzta and wata. In the first round the Java coders took the first and last place :)

12:48 - There are 11 contestants in this round. Burunduk1 couldn’t come, and he told that too late to rearrange everything.

12:48 - 275, 500, 950.

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

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.

TopCoder Open 2012 - more arena flyovers

Here are some more videos that illustrate how TopCoder Open works.

TopCoder Open 2012 - arena video overview

Here's a less serious view at TopCoder Open 2012 - a standard "overview of arena" video, this time from a flying camera though :) Unfortunately the arena is quite dark and picture quality is quite bad. I'm trying to explain what's going on in the audio.

TopCoder Open: problem difficulty

Tomorrow is the first day of TopCoder Open 2012, and I'll try to blog on its algorithm track.

Here's a small analysis of TopCoder Open problem difficulty.

Let's consider the time taken to solve the problem as the ultimate measure of problem difficulty. Then, we can estimate the difficulty of, say, a medium problem in a TopCoder Open semifinal by comparing the solving time for this problem for each competitor with the solving time for other medium problems for the same competitor. More precisely, for each competitor in each TopCoder Open onsite round, I've compared the solving time for each problem with the solving time for this competitor in all rounds that took place in the same year, and the percentage of problems that were easier plus half the percentage of problems that were of the same difficulty is the declared measure of difficulty of the onsite problem for this competitor. The median of those numbers over all competitors is the difficulty of the onsite problem.

Here's the result:

TCO '03 Semifinals 1 98% 69% 79%
TCO '03 Semifinals 2 89% 81% 73%
TCO '03 Semifinals 3 92% 87% 68%
TCO '03 Semifinals 4 82% 78% 82%
TCO '03 Finals 91% 90% 81%
TCO04 Semifinal 1 87% 80% 67%
TCO04 Semifinal 2 92% 79% 67%
TCO04 Semifinal 3 84% 51% 64%
TCO04 Wildcard 66% 88% 72%
TCO04 Finals 86% 79% 87%
TCO05 Semi 1 91% 76% 64%
TCO05 Semi 2 90% 71% 64%
TCO05 Semi 3 78% 81% 64%
TCO05 Wildcard 88% 81% 64%
TCO05 Finals 91% 77% 74%
TCO06 Semi 1 93% 77% 69%
TCO06 Semi 2 75% 77% 68%
TCO06 Semi 3 88% 77% 70%
TCO06 Wildcard 66% 84% 71%
TCO06 Finals 66% 85% 77%
TCO07 Semi 1 65% 79% 68%
TCO07 Semi 2 89% 77% 66%
TCO07 Semi 3 86% 83% 65%
TCO08 Semifinal 1 64% 81% 62%
TCO08 Semifinal 2 85% 79% 63%
TCO08 Semifinal 3 76% 80% 63%
TCO08 Wildcard 94% 44% 66%
TCO08 Championship 96% 86% 64%
TCO09 Semifinal 84% 59% 60%
TCO09 Championship 95% 87% 56%
TCO10 Semi 1 89% 84% 61%
TCO10 Semi 2 87% 75% 53%
TCO10 Wildcard 81% 86% 57%
TCO10 Final 90% 54% 61%
TCO11 Semifinal 1 74% 73% 55%
TCO11 Semifinal 2 91% 84% 57%
TCO11 Wildcard Round 87% 90% 56%
TCO11 Championship Round 83% 78% 62%

You can see that the numbers for the hard problem are lower than those for easy and medium; the reason is that I consider "not solved" to be equal to "not solved", and thus when a person solves just 60% of all hards, the perceived difficulty of any problem will not exceed 80%.

With that effect in mind, the above list reveals that 'easy' problems are hovering around 90% mark (more difficult than 90% SRM 'easy' problems), while 'medium' problems are sometimes around 80-85% difficulty but sometimes have huge drops to just average difficulty, around 50%.

Another interesting slice of the same data is the list of competitors ordered by decreasing average difficulty of onsite problems. Here's the list, limited to only those competitors with at least 5 onsite rounds:



PaulJefferys - 6 rounds - 58%
reid - 5 rounds - 59%
tomekkulczynski - 5 rounds - 64%
Eryx - 6 rounds - 65%
gawry - 7 rounds - 66%
Yarin - 5 rounds - 67%
bmerry - 7 rounds - 67%
nicka81 - 5 rounds - 67%
antimatter - 5 rounds - 70%
liympanda - 6 rounds - 70%
ACRush - 8 rounds - 71%
Im2Good - 5 rounds - 71%
Ying - 5 rounds - 71%
ploh - 6 rounds - 71%
grotmol - 6 rounds - 72%
marek.cygan - 10 rounds - 72%
John Dethridge - 9 rounds - 73%
cyfra - 5 rounds - 73%
misof - 5 rounds - 74%
andrewzta - 7 rounds - 75%
tomek - 10 rounds - 75%
SnapDragon - 8 rounds - 77%
Petr - 11 rounds - 81%

So for PaulJefferys and reid, the onsite rounds are actually not much more difficult than normal rounds (I guess partially because they don't do much SRMs, and thus "normal" rounds are the TCO qualification rounds for them), while I'm actually the one who struggles the most at the onsites :)

Russian Code Cup 2012

Tomorrow is the day of the final round of Russian Code Cup (http://russiancodecup.ru/). Just several days before Gena turns 18, our last chance as Egor puts it :) There will be live broadcast on the website. I need your support! Click for date/time in all timezones.

This event itself is just marvelous! Today was mostly board game day, met a lot of friends, the atmosphere is amazing. Here's a picture from the event's place:

Here are some more recent TopCoder screencasts (double-click on the video for full screen):

SRM 548:

SRM 547:

TCO12 Round 3A:

SRM 531:

SRM 529: