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.