Wednesday, October 13, 2010

TCO 2010 Algorithm Semifinal 2

Here will go the comments for Algorithm Semifinal 2 of TopCoder Open 2010.

12:56 - announcement complete, 3 minutes before the start. Will be looking at rng_58's screen during the first minutes.

13:00 - Into the fray!

13:01 - the easy problem: given several points on the plane, what is the maximal possible f(X) over strings X of the given length L consisting of "LRUD" characters. f(X) is defined as the probability of a robot starting at (0,0) will end at one of the given points if it performs each command with probability 1/2.

13:02 - L is up to 50, the number of locations is also up to 50. Thinking...

13:07 - rng_58 has started coding. It seems that the solution is quite straightforward: iterate over the number of "L", "R", "U" moves - the number of "D" moves is the rest. Then we need add up the probabilities of hitting each cell, which can be calculated using pre-calculated arrays of "what is the probability to get number x if we sum a (-1)'s and b (1)'s, each with probability 1/2". We need O(50^3) for calculating these arrays, and then O(50^3) possible strings will take just O(50) time each, which should be fast enough.

13:09 - rng_58 seems to have coded exactly this, probably has an off-by-one error somewhere.

13:11 - found the bug, submitted! ACRush and PaulJefferys have submitted as well. rng_58 is testing the maxtest and verifying the code, not moving on to the next problem yet.

13:12 - here goes another problem (not sure if it's medium or hard): given an even amount (up to 50) of boxes with given amount of gold and cost for each, you need to split them into two halves such that each half has the same (n/2) amount of boxes, and the sum of average costs per gram for the two halves is the minimum possible.

13:14 - the amounts and costs are up to 500.

13:27 - Suppose we fix the total weight of all boxes in one half. Then we sum two fractions where the sum of numerators is constant, and the denominators are given. It's obvious that to minimize this sum, we need to minimize the numerator of the fraction with the lower denominator. That leads us to the following DP: out of first a boxes, we took b boxes with total weight w - what is the lowest total cost to achieve that (we can get the highest by looking at the complement)? This should have running time of 50*50*50*500 which seems too big. rng_58 seems to have coded and submitted this. He hasn't tested it on maxtest yet.

13:28 - he's ran the maxtest, and the solution is very fast. Why?

13:29 - probably since 50 should actually be 25 in the above formula.

13:29 - rng_58 still doesn't feel confident enough to go to the hard. Let's take a look at the hard ourselves.

13:30 - the problem statement of the hard is amazingly simple. Given three arrays A, B and C of at most 34 elements each, find the number of ways to choose at least k indices such that if we sum the values of A, B and C for the chosen indices, the A's sum is the largest.

13:32 - as dzhulgakov correctly suggests, 34 suggests this will be meet-in-the-middle :)

13:33 - rng_58 is still thinking about this, and so are we.

13:35 - there's a cool constraint that k isn't more than 7, so all sufficiently large sets are allowed. Inclusion-exclusion? We're at a crossroads :)

13:36 - the numbers are up to a billion, so no help here. Let's forget about k first and solve the problem about the total number of ways.

13:43 - together with Dmytro, we seem to have solved the one with no k: if we build a vector (A[i]-B[i], A[i]-C[i]) for each i, we need to calculate the number of sets of vectors such that their sum is in the 1st quadrant (has both coordinates positive). Suppose we split all vectors in two halves, and calculated all possible sums for each half. Then we iterate over the sums of the first half in the order of increasing x-coordinate, and build a range-sum tree by y-coordinate of the vectors from the second half that add up to a positive x-coordinate with the ones we've chosen from the first set. Then we need one range-sum query to find the number of elements in the second half that will pair with the given element from the first half.

13:50 - and now let's remember about k. Since k is small, we can instead find the number of sets with less than k elements, and subtract it from the overall count. And in order to do that, we can modify the above meet-in-the-middle algorithm so that splits the sums for each half into buckets with the given amount of indices, and... Wait! Since 34*33*32*31*30*29/1*2*3*4*5*6=1344904, we can just iterate over all subsets of at most k-1 elements and verify the condition for them. So this part of the problem is very easy :)

13:53 - now that we're done with the problems, let's take a walk to other people's monitors and discuss the submitted solutions.

13:54 - ACRush was struggling with TL in his hard solution, and now he's getting WA on one of the examples.

13:55 - People have pointed out that the range-sum tree is tricky here since the values are pretty huge, so you need to "compress" the indices and be very careful.

13:56 - there's a Studio competitors announcement during the round over the loudspeakers. That should be extremely annoying to the contestants.

13:57 - ACRush has fixed the bug and submitted! (or maybe it was not a bug but just some debugging run?)

13:59 - RAD seems to be getting memory limit in the medium. No wonder, since it seems to be a requirement to do the DP remembering only 2 outermost rows instead of all of them :)

14:00 - liympanda is also debugging his hard problem, but he has a binary search inside his solution for some reason. Maybe it's just for compressing the coordinates?

14:01 - no, he's using it to calculate the answer. That looks strange.

14:03 - griffon is still struggling with the easy. That strategy doesn't work, as I've rigorously proven in the first round :)

14:04 - PaulJefferys seems to be generating all sums, so that should be the part of meet-in-the-middle. He still has a long way to go.

14:05 - ACRush seems to be debugging his hard on a testcase of his own. I'm not sure if he's just testing it or if he's found some issue.

14:08 - Onufry submits the hard! His solution has very funny 6 nested loops in the end to iterate over all combinations to take the k parameter into account.

14:10 - going back to rng_58 - he seems to have got the solution ready, was testing it for some time, and finally submits!

14:12 - rng_58 prepares a large testcase and tests his solution...

14:13 - works in 0.229s!

14:14 - tomekkulczynski seems to have the correct idea in the hard as well, and he's also splitting the sums into buckets as we've suggested above before we saw the easier approach for the k part.

14:15 - 9 minutes to go in the round. ACRush and rng_58 have three, tomek, Paul and gmark have the first two, Onufry had only the hard, griffon has nothing, all others have only the easy.

14:17 - wata is doing the hard, and seems to work on some kind of meet-in-the-middle. However, the past 24-hour marathon seems to have taken its toll and he's writing code quite slowly. Somehow ACRush doesn't seem affected :)

14:19 - it's a bit sad that we can't view the competitors' code now, as we could endlessly speculate about possible bugs. Well, we'll have to watch them during the challenge phase and do our best!

14:21 - meanwhile, liympanda submits the hard.

14:22 - PaulJefferys is reading up some STL docs. I'm guessing he ran into problems with the range-sum tree. He seems to have given up.

14:24 - most people seem to be debugging frantically in the last minute. Onufry still can't get his easy to pass the examples. izulin submits the medium. A good challenge target?

14:27 - the problems all seem to be more difficult on the time limit side and not on the correctness side; so I'd expect all challenges, if any, happen because of time limits.

14:31 - izulin's medium is downed by RAD. ACRush has looked at it before that but decided not to challenge.

14:32 - rng_58 seems to be reading the chat history to verify if izulin's easy has already been challenged (I'd guess for time limit?). Hey, you can use right click --> history for that!

14:33 - another good shot by RAD! Onufry goes down. Let's look at RAD's screen :)

14:34 - a point for RAD - he first checks the history to make sure the problem hasn't already been challenged, as in that cases chances are probably much lower. That's what I should be doing!

14:35 - unsuccessful challenge on liympanda. RAD's challenge for the hard seems to be just large and random. So there's high chance liympanda will pass the systest.

14:36 - judging by RAD's successes, we'll see quite a few solutions failing systests as well.

14:37 - ACRush is looking at tomek's 500 very carefully.

14:39 - another two unsuccessful challenges for RAD. That probably makes sense since he's (almost?) the lowest scorer on the easy.

14:39 - tomek brings Paul's easy down! Yes, I expect the systests to be quite eventful.

14:44 - Paul says his easy has failed because the coordinates in the input can be up to 100, even though the length of the string is at most 50, so he only had a small array and probably died because of strange out-of-bounds access results.

14:46 - RAD told that his goal was at least +125, so he just challenged almost blindly. Worked out for +100, but not anymore :(

14:49 - everybody waiting for the results. It seems that ACRush and rng_58 are pretty solid, and will get into the finals even with one problem failing.

14:50 - actually that's not true. rng_58 can be fourth if his hard fails.

14:51 - so the systests only brought w_'s easy down. The finalists are ACRush, rng_58 and liympanda. tomekkulczynski, gmark, PaulJefferys and izulin go to the wildcard.

15:00 - Ivan Metelsky the Algorithm Coordinator told that the results for the second semifinal are as expected, while they wanted much more people to solve the medium in the first semifinal. Stupid me for not opening it :(

15:02 - speaking about the hard problem of the first semifinal - people have rightly pointed out that the inner DP actually runs in O(25*25), for the total running time of 1000*25^3, which is fast enough. The author of the problem can solve the problem in 1000*25^2 - so here's some homework for you :)

15:03 - that's about it for the semifinals! Stay tuned later today for the coverage of the Wildcard round that starts in 3 hours 30 minutes.


  1. rng_58 opened medium.

  2. Also mention at the end.. what happened to you in SF#1 ?