TopCoder Open 2012 Wildcard Commentary

19:53 - That’s it for today! Join us tomorrow for the coverage of the ultimate round - the finals! http://www.timeanddate.com/worldclock/fixedtime.html?iso=20121003T13&p1=867.

19:52 - It’s easier to tell which solutions passed than which failed :) iwi’s 1000, meret’s 500, SergeiFedorov’s and dzulgakov’s 250s. That’s it. iwi and meret to the finals!

19:49 - it looks like most 250s were indeed brought down by d=2. The results are being announced now!

19:40 - Kankuro also loses 25 in the dying minutes, on Romka's 500.

19:39 - both meret and Romka got -25 from Dmitry_Egorov's 500.

19:36 - and meret brings down SergeiFedorov's 500. Will we have two non-zero scorers to advance to the finals? :)

19:35 - Romka brings down sdya’s 500.

19:34 - dzhulgakov brings down Dmitry_Egorov's 250.

19:34 - sdya is not reading solutions, seems to have given up.

19:31 - Kankuro brings down sdya’s 250. What about 500s?

19:30 - Challenge is on! Surprisingly, no blind challenges. SergeiFedorov brings down _Romka_’s 250 and meret’s 250, but it seems that he reads them.

19:26 - Apparently iwi’s easy tries to approach (0,0) from (x,y) somewhat greedily. Is it an obvious failure or is that greedy actually some kind of gcd?.. We’ll find out soon. His code contained return “I hate math”; at some point :)

19:25 - Last seconds of coding phase were quite eventful - [[iwi]] submitted easy and SergeiFedorov resubmitted medium. [[iwi]] is the current leader.

19:24 - _Romka_ resubmits the medium, and drops to the last place. Yeah, I’d guess there’s plenty of space for bugs there as well. Looking forward to challenge phase.

19:19 - not much more action, just 4 minutes left. Everybody except iwi has 250+500, iwi has just 1000.

19:14 - SergeiFedorov submits the medium after giving up on the hard and it’s the fastest by far! He’s now in first place.

19:13 - apparently the sample cases for 250 don’t include the “all coordinates odd” case (for example d=2). I predict a lot of challenge fun :)

19:11 - iwi’s 250 is not working, he’s debugging.

19:06 - we’ve missed that dzhulgakov has resubmitted the 250. Promising for challenge phase?.. It looks like challenges will be very important if there’s nobody with 3 tasks.

19:04 - 20 minutes left. I’d say iwi is actually in a great position, as most competitors can’t get their 1000 working - many already coded up some DPs.

19:03 - SergeiFedorov gave up on hard and moved to medium.

18:59 - I guess we can speed things up by considering where will the first letter of large string go. It’s either removed at some point, in which case we get a suffix of large string and the same small string, or mapped to the first letter of the small string. So this can get us a DP on (suffix of large, suffix of small), although it’s not clear to me if we can still manage not to overcount solutions where one of consecutive letters is removed several times. Maybe we should add something like “last removed letter” to the state?.. Anyway, it’s too late to think about this.

18:57 - I can’t see iwi’s solution now, but wata tells its complexity is 50^3, not 50^6 as my proposition below.

18:54 - Currently _Romka_, sdya, Kankuro, meret, Dmitry_Egorov and dzhulgakov submitted easy and medium (and all moved on to the hard), [[iwi]] submitted hard and moved to the easy, SergeiFedorov submitted easy and moved to hard.

18:49 - So the rough approach for the 1000 is: let’s count the number of ways to obtain a substring of the small string from a substring of the large string. We do that by checking which character will be removed last, which leaves us with two substrings of the large string that should be matched somehow to the small substring, so we also have to check all ways to split the small string into two. One challenge is not to count things twice with consecutive equal letters, but that should be doable although I’m too lazy now to figure out how. Another challenge is running time: currently we have something like (50^3/6)*(50^3/6) - (the number of ways to choose a substring and a letter in it)*(the number of ways to choose a substring and a split point in it), which is about 500 million which might be too slow. But in reality we have more restrictions like length of large substring should be at least length of small substring which divides everything by 2 more, and the same for both halves which should divide by something like 2 further, bringing the total running time under control?..

18:43 - About 1000: let’s go from the long string to obtain the short string. The only way we can confuse two removals is when there’s a string of consecutive equal letters in the long string. In that case, removing each of those letters produces the same string, so we should always remove the first one of them. Still don’t know what to do next...

18:39 - forgot to post the link to statements: http://apps.topcoder.com/forums/?module=Thread&threadID=763830&start=0&mc=2

18:36 - 250 and 500 solved by Romka.

18:35 - the complexity of that solution is 50*2500 (maximum number of steps)*50(number of equations to check on each step). We can check each equation in O(1) time using hashing.

18:30 - 500 does look straightforward-ish. We will construct all strings from the end. We take any equation, and if one of its parts has more letters known in the end than the other, we reconstruct the missing letters. We repeat this until we can’t reconstruct anything, or until one of the strings is of length more than 2500. In the latter case, there’s no solution (we’ve entered an infinite cycle), and in the former case, our current suffixes are a valid solution, and the smallest one.

18:28 - Meanwhile 7 people submitted easy and [[iwi]] works on hard. Also SergeiFedorov switched to hard after easy.

18:25 - Here’s why the solution for the easy works. If we have a jump by (a,b), then we have jumps by (2a,0) and (0,2b), and also jump by (b,a). Thus, we can get jumps (2g,0) and (0,2g). Then if there’s a jump (2kg, (2m+1)g) then we can get to (0,g) using those two jumps. Otherwise, all jumps are ((2k+1)g,(2m+1)g) and we can get to (g,g) but can’t get to (0,g).

18:22 - 500: We have a system of equations a_i = b_i + c_i, where a_i and b_i are variables, c_i are constants, + is string concatenation (like s = t + “a” and t = u + “b”). We need to find the minimal sum of lengths of its solution.

18:19 - So together with Egor we kind of figured out the 250. Suppose the gcd of all coordinates of all possible jumps is g. Then there are two cases: if at least one jump has an even coordinate (after division by g), then we can get to any point where both coordinates are divisible by g. If all jumps have odd coordinates after division by g, then we can get to any point where both coordinates are divisible by g and their sum is divisible by 2g.

18:09 - Apparently my thinking gets slower as the day comes to an end. It’s kind of obvious that you have to generate all integer vectors of length sqrt(d), but where to go from there?..

18:07 - Romka has just submitted 250! I still have no clue how to solve it.

18:02 - 1000: let’s consider sequence of strings good if for each applicable i s_i is s_{i + 1} with one letter erased. You have two strings, how much different sequences exists with this two string as first and last element? String lengths are up to 50.

18:00 - 250: one starts at (0, 0) and can jump to other integer points. Each jump should be exactly sqrt(d) in length. Is it possible to get to (x,y)?

17:56 - meret has coded max flow to warm up and in case it shows up at the contest. Three minutes before start.

17:44 - One more comment from Gennady Korotkevich (made before the semifinals) - he said that almost anyone could win, but if forced to bet on somebody, he’d bet on meret. Well, now meret has to qualify from the Wildcard to live up to the expectations :)

17:43 - 250, 500 and 1000.

17:41 - Hi! This is live commentary for TopCoder Open 2012 Algorithm Wildcard Round. The round will start in about 20 minutes. I will update this post with new comments, and so will Egor who’s joining me again.