Algorithm problems for dummies: Petr Mitrichev's blog

TCO 2011 Algorithm Finals live coverage

2011-09-28T21:04:00.067+04:00

16:29 - and it’s over, and I guess so is this coverage. Thanks for following! Thanks a lot to TopCoder, to all organizers and problem preparers, and to all participants and sponsors. It was a great event!

16:28 - Studio champion is abedavera.

16:25 - Mod Dash winner is Yeung.

16:23 - no changes in Marathon standings compared to the provisional results. Final sequence: Psyho, wata, ainu7, jdmetz, nhzp339, ploh, ACRush, chokudai, wleite, Rizvanov_de_xXx, RAVEman, komiya.

16:21 - full results: rng_58, bmerry, nika, ACRush, mikhailOK, PaulJefferys, [[iwi]], lyrically.

16:20 - now algorithms. lyrically’s 250 fails. PaulJefferys’ 250 fails. Everything else stands. rng_58, bmerry, nika!

16:11 - the awards ceremony has started. The first category up is design.

16:07 - and one more system test preview: lyrically says that he discovered a timeout for his 250 during the intermission - his solution had an additional log-factor.

16:04 - the reasons for resubmissions were also revealed: nika resubmitted because of special handling for 1xn, where the sum is exactly 0 or 9*n. mikhailOK resubmitted because of no handling of “n solutions” at all. And ACRush resubmitted because one of the arrays in his solution was up to 600, and numbers that arise might be up to 1000. He says that his original version might also still work, since those big numbers are never useful for a correct solution.

16:01 - and a shocker: this is actually rng_58’s last match as a participant for some time! He will be joining mystic_tc to help run SRMs from October.

15:57 - some news from the floor: first, the three Japanese guys did not agree on the strategy beforehand - it was a coincidence. Second, PaulJefferys said he was just 3 minutes away from finishing the 1000. Third, lyrically had the “no -1” case working very quickly, and was debugging the -1 case for the last half hour - and it is actually the easier case!

15:35 - no more announcements for now, the awards ceremony is scheduled for 16:00. I would expect algorithm finals results at 16:30 or so.

15:32 - they have also announced winners of a raffle, which I won’t post here.

15:19 - they started to announce the winners... of various side competitions. The winner of the MemSQL poker tournament is 7ania7 (prize: MacBook Air), the winner of the treasure hunt is mikhailOK (prize: trip to TCO2012), the winner of FIFA tournament is nika (prize: trip to TCO2012), the winners of the amazing race are theycallhimtom, pieguy, mikhailOK (prize: trip to TCO2012), the winner of the holiday photo contest is mikhailOK (prize: trip to TCO2012).

15:18 - rng_58 says he didn’t test his 1000, but the last two challenges have really increased the confidence it’s correct.

15:15 - ACRush says that his solution before resubmission might be correct as well: it had a DP array that went up to 600, but the input might contain numbers up to 999. But when the input contains a number more than 450, the answer is no solution, and his solution most probably would still return no solution. So 1xn was not the reason for his resubmission.

15:11 - mikhailOK says that his resubmitted solution still has a bug: when the number of solutions is 0 modulo 10^9+7, but not 0 proper, it will return wrong answer. But I doubt that will fail the systests.

15:09 - ACRush and lyrically both challenge rng_58’s solution, most probably on a random testcase. It survives!

15:08 - the rumor has it that the reason for mikhailOK’s resubmit was that he actually didn’t cover the “n solutions” case at all.

15:07 - lyrically still seemingly testing his own 250 solution on a large testcase. Maybe he wants to make sure it’s non-trivial.

15:06 - 3 and a half minutes to go in the challenge phase. I still expect challenges, at least at the last minute.

15:05 - rng_58 still very calm and doesn’t bother to read 500s.

15:05 - no, [[iwi]] actually started to read the 500s again.

15:04 - [[iwi]] is not challenging as well. Just moves a window around the screen repeatedly.

15:03 - rng_58 is not challenging. He just looks at the scoreboard.

15:02 - everybody reads 500s. No action there yet.

15:00 - nika brings down [[iwi]]’s 1000-pointer. This looks to be a blind challenge.

15:00 - challenge has begun! 10 minutes that may bring a lot of news.

14:55 - ACRush is preparing testcases for 500. bmerry is preparing the 1xn testcase for 500, which makes us think his solution handles it correctly. lyrically is preparing a random large testcase for 250.

14:54 - [[iwi]] submits the 1000-pointer with less than 1 minute to go! Unfortunately, that’s only enough for 7th place. The order before the challenge phase is rng_58, bmerry (3 challenges below), PaulJefferys, ACRush, nika, mikhailOK, [[iwi]], lyrically.

14:53 - rng_58 opens the 500-pointer - the only way to reach him is through challenging, so I guess he needs to try to steal those challenges away from others, too.

14:52 - Free ice cream has shown up outside the arena

14:51 - nika has been coding a stress-test to compare his solution against a dumb one, a pretty good move I guess. He could also generate some challenge cases that way. ACRush is also testing the 500, then 250 - he abandoned the 1000.

14:48 - rng_58 submits the easy to move into first place. He didn’t test anything except the examples, but for 250 that should be enough.

14:46 - we’re sorry for no updates recently - the internet connection is very flaky here, and goes off for several minutes from time to time.

14:45 - very exciting last 10 minutes. rng_58 must be really nervous now. lyrically still has a good chance at submitting the 1000, too.

14:36 - rng_58 submits the hard, and lyrically submits the easy! rng_58 will be in the lead if he solves the easy in the remaining 17 minutes. I don’t anticipate any of the 5 “usual strategy” guys to even come close on solving the 1000.

14:35 - the Japanese contestants’ strategic move makes the contest really exciting. Kudos!

14:33 - he resubmits, and opens the 1000. Everybody is working on 1000 except lyrically who’s solving 250. Top 5 are: bmerry, PaulJefferys, ACRush, nika, mikhailOK.

14:32 - mikhailOK still debugging his solution. I guess he wants to make sure he resubmits it just once.

14:30 - all 3 Japanese coders seem to be implementing the solution we described below. [[iwi]] has implemented everything except “-1” case, and is passing some of the examples. lyrically has got all examples except the last one passed, but decided to open the 250 - maybe to switch subjects for a short time. rng_58 has written lots of code that looks correct, too - but I’m not sure how close he is to submitting.

14:25 - it looks like mikhailOK has found the same bug, and is fixing his code now, one more resubmit coming I guess. This might be actually quite important at the challenge phase as two of the guys didn’t resubmit :)

14:22 - mikhailOK also submits and moves into third place. Now 5 coders have two problems submitted and 3 have none. But those 3 might actually still be on a winning strategy, since almost any score on 1000 will be higher than those scores on 500, and 250 is really quick to code.

14:20 - and nika also resubmits and opens the 1000. Now the top 4 are bmerry, PaulJefferys, ACRush, nika. We think that the reason for resubmits might be 1xn testcases since those should be handled separately.

14:19 - PaulJefferys also submits 500 to get into third place, and opens the 1000.

14:18 - ACRush has been testing the 500 for a long time, and finally resubmitted! Meanwhile, bmerry has submitted the 500 as well. The top 3 are: nika, bmerry, ACRush. bmerry and ACRush are reading the hard, nika still hasn’t opened it.

14:12 - the solution for the hard is still quite tedious since one has to deal with “-1” as well.

14:10 - nika is the first to submit the 500! He’s now in the lead. ACRush submits the 500 as well, but score is lower and he’s still in 2nd place. Both guys didn’t open the 1000 yet.

14:07 - so here’s the deal (mostly by Vitaliy): every of the 2^18 ways gives you the following information: we can go from position X to position X+delta for all X in some segment [L, R] (which is derived from the fact we must not go outside the borders). Now, we put all ends of those segments for both halves into one set of events, sort them, and go from left to right. We maintain how many segments are there open now for each delta in each half, and that allows us to quickly find the number of combinations for the current X, for the total running time of 18*2^18 or something similar.

14:03 - I’m surprised that nobody has submitted the medium yet. We must be missing something. The hard seems to be some kind of meet-in-the-middle (we just iterate over all 2^18 ways for each half), but we can’t figure out how to combine the halves yet.

13:55 - one hour to go. In the hard problem, we’re not asked about “permutations” exactly: several cards may go into one slot. The slots are numbered.

13:54 - meanwhile, 5 coders have submitted the easy, in this order: ACRush, nika, bmerry, PaulJefferys, mikhailOK. The 3 Japanese coders are still solving the hard, the rest are solving the medium.

13:46 - the medium problem: you start with a 50x50 grid of digits, and calculate sums of “crosses”: c_ij = sum(a_lm where l equals i or m equals j). You now need to reconstruct the original grid, and return it, or return the number of solutions if there are multiple solutions (or no solution if there are none). This one looks to be obvious as well: if we sum all “crosses” corresponding to one row, we will sum all numbers in that row n times, and all other numbers once. By subtracting two of those, we can find the difference between every two rows, and similarly for columns. Then, we iterate over the sum for the first row and for the sum of the first column. After that, we know the sum in every row and the sum in every column, and then we know all numbers (row + column - cross = number). Since the sum of first row plus sum of first column is the first cross plus a small number, there are only 450*10 cases to check for those two sums, and each case can be checked in 50*50 operations, which should be fast enough.

13:41 - the Japanese coders will now know that 250 is very easy, so their strategy seems to be quite solid.

13:39 - nika submits the easy for 230.88 points.

13:36 - ACRush submits the easy for 240.80

13:34 - the size of the board in the easy is 20x20, there are 20 throws. So I guess one has to calculate the expected probability when there are n throws left and the current difference in scores is m, and then iterate over all possibilities for the throw and choose the one that gives the best winning probability, resulting in a simple DP.

13:34 - in the hard Number of slots is not greater than 10^6, Di are up to 10000. Also there is information “card 1 can be Dn positions right or left to the card n”.

13:32 - the hard problem statement: count the number of card permutations (modulo “some large number”), where you are given the information like “card i+1 can be exactly Di positions right or left to the card i”. There are also special cases: Di = 0 - two cards must be at the same position, Di = -1 - card positions may be arbitrary. Number of cards is not greater than 36.

13:31 - the easy problem statement: you are given a rectangular board of digits, and you throw darts at it. At each throw, you select a 3x3 square and your dart hits each of its cells with probability 1/9. There are two players that throw darts one after another, and the one who scores more wins. In case of a tie, a fair coin is tossed. What is the probability that the second player will win after the given number of throws?

13:30 - all 3 Japanese contestants have opened the hard problem!!! All others start with easy.

13:28 - the introduction is over, 10 seconds to go!

13:25 - contestants are lining up for an introduction, in alphabetical order :)

13:23 - 6 minutes to go, still no loud introduction. Are they going to skip it?

13:20 - here are the results of a prediction contest that a Russian programming contest news website ran (before the semifinals took place): http://158.250.33.215/~ejudge/showvote.cgi?data=tco2011

13:17 - 12 minutes before the start.

13:14 - today, the coverage is provided by Petr, KOTEHOK, marek.cygan and Vitaliy. If you have any questions for us, I guess the best way to ask them would be in the Competition Arena, in the room where all contestants are (“2011 TCO Algorithm - Championship Round”). Contestants won’t see them (and our clever answers), don’t worry!

13:12 - lyrically seems to have just coded an efficient max-flow implementation. PaulJefferys is solving the easy problem from the first semifinal (which is the only practice round available, I guess).

13:08 - 7 out of 8 contestants use C++, and they’re busy writing long lists of #include’s. MikhailOK, being the only Java coder, has nothing to do and spends his time just thinking about nothing. Go Java! Go Russia!

13:02 - waiting for the main event to start. Contestants were just allowed on stage. See http://petr-mitrichev.blogspot.com/2011/09/topcoder-open-2011.html for a small overview of who competes today!

TopCoder Open 2011

2011-09-28T17:32:00.000+04:00

The most prestigious event for individual algorithmic programmers is taking place right now in Hollywood, Florida - it's TopCoder Open 2011 time. I have already been eliminated (twice :)), but that means I will provide live coverage for the finals, where 8 best coders will compete. Here are the participants (in alphabetical order):

	[[iwi]] from Japan, currently ranked 43rd in the world. He's already advanced to the TCO semifinals twice, in 2008 and 2009, but this is the first time he made it to the finals.
	ACRush from China, currently ranked 3rd in the world. He has already been in the TCO finals twice, in 2008 and 2010, but is still to score his first win.
	bmerry from South Africa, currently ranked 4th in the world. He has also been in the TCO finals twice, in 2007 and 2010, but haven't won yet.
	lyrically from Japan, currently ranked 9th in the world. I think it's his first trip to the TCO - and he got through to the finals (the semifinal also happens onsite).
	mikhailOK from Russia, currently ranked 26th in the world. It is also his first trip to the TCO.
	nika from Georgia, currently ranked 7th in the world. He's already been to the TCO semifinals back in 2008, but it's his first time in the finals.
	PaulJefferys from the United Kingdom, currently ranked 19th in the world. He's also been in the TCO finals last year, in 2010.
	rng_58 from Japan, currently ranked 5th in the world, and the current TopCoder Open champion - he won in 2010, and is the only finalist to have won previously. He has never been to the TCO before last year.

Tune in to this blog today at 13:30 TopCoder time (click the link for other timezones) for live coverage, in less than 4 hours!

TCO 2011 Algorithm Semifinal 2 commentary

2011-09-27T20:44:00.037+04:00

14:51 - The results have been announced. ainu7’s 600, Kankuro’s 900 and ACRush’s 250 and 900 failed. [[iwi]], rng_58 and ACRush advance to the finals, unbing, nika, mikhailOK and Kankuro to the wildcard. That's it for this commentary!

14:47 - Kankuro’s 600 has integer overflow. We know nothing about other solutions that might fail.

14:44 - scoreboard after challenge phase:

14:43 - scoreboard before challenge phase:

14:40 - he also tried to challenge Kankuro’s 900, also unsuccessfully. That’s it for the challenge phase!

14:39 - RAD. tried to challenge [[iwi]]’s 900, unsuccessfully.

14:38 - unbing brought down Kankuro’s 600. That moves him into 5th place on preliminary standings!

14:38 - rng_58 and ainu7 stopped reading others’ solutions, other ten contestants are still trying to find some bugs.

14:37 - Let me remind that this blog is actually a team effort :) Petr, KOTEHOK, bmerry and Vitaliy trying to bring you the latest information.

14:36 - R.A.D.’s 250 is still popular, but may be it’s too large to be safely challenged.

14:35 - most of the challenge phase is over, just 4 minutes remaining. It’s just 10 minutes at the onsite rounds. I still expect a few last-second challenges, though.

14:34 - Two contestants are reading Kankuro’s 600, but seems that they do not see a bug there.

14:32 - Four contestants are reading solutions of ACRush. What are they trying to find there?

14:32 - ACRush tries to break ainu7, but unsuccessfully.

14:31 - mikhailOK’s 600 is successfully challenged by ACRush.

14:30 - Contestants like to read 250, 600 and 900 of the others nearly equally. The most popular viewed solutions are Kankuro’s 900 and R.A.D.’s 250.

14:29 - 40 seconds before Challenge phase.

14:28 - ACRush is doing something with a large random case of many numbers. Kankuro has tested his 600 and got a negative number, his solution seems to be wrong. Some contestants are watching history and write test generators.

14:25 - Coding phase has ended. Some people think that 600 must be the most challengeable problem though there are seven sample tests. We’ll see in the few minutes.

14:23 - Kankuro has submitted 900 and now he is second in the scoreboard with all three problems complete. Some other contestants are still testing their solutions, but they seem not to pass the samples.

14:19 - the scoreboard is: ACRush, [[iwi]], Kankuro, mikhailOK, rng_58, nika, ainu7, unbing, LayCurse, pieguy, _Romka_, RAD.

14:18 - ACRush is the first to submit 900 for 551.77, [[iwi]] follows closely after him, but just for 383.96. It is enough to put him into second place, though.

14:13 - nika was one of the first to open 900, but now he has some five-dimensional dynamic programming uniformly filling his screen, seems that it is very hard to debug

14:13 - ainu7 has resubmitted his 600.

14:12 - rng_58 submits the medium. He’s in 4th place after ACRush, Kankuro and mikhailOK.

14:11 - ACRush finally compiled his solution for 900, but it did not pass the first sample

14:09 - RAD. submits the easy. Is there time still left for him to solve another problem? He opens the 600 with 15 minutes to go.

14:07 - ainu7 submits the medium for 305.75 - he still doesn’t have the easy. He opens the hard.

14:06 - finally milkhailOK was the third to submit his 600 scoring 276.88 points

14:04 - mikhailOK has passed large sample cases 5 and 6 in 600. He also has a function “getStupid” in his code which may be used in something like stress-tester.

14:03 - there seems to be not much difference caused by 600/900 instead of 500/1000, as all scores on 600 are low and it seems most likely that all scores on 900, if any, will be higher.

14:02 - mikhailOK is testing 600 and it seems to pass at least some non-trivial cases, may be we can expect submit from him after some time; most of others are still coding something.

13:57 - most of contestants working on 900 have just non-moving flashing cursor in their code, they might be thinking of something; though [[iwi]] is writing something like a testing-code.

13:57 - at this point, I think it should be pretty obvious to the contestants that many 600s and 900s may fail, so accuracy will be the deciding factor. I guess there are two main strategies - make sure you get one absolutely correct and forget about the second, or submit two hoping that at least one is correct :) Not many have the second strategy available, though.

13:54 - Kankuro was the second to submit 600 (337.64 points). He still continued to test it for some time, then finally opened 900.

13:54 - 30 minutes left.

13:53 - ACRush is writing his 900 pretty fast.

13:52 - [[iwi]]’s 900 works on some cases, but on sample case 2 it gives a negative answer.

13:51 - RAD. and ainu7 are the only contestants still to submit anything.

13:50 - it seems like at least three contestants are testing their 600, but it does not work even on small cases.

13:48 - the feeling is that the 600/900 in this round are completely about implementing an intuitively easy solution that is really hard to implement.

13:45 - ACRush submits the 600 after testing it for a very long time!

13:42 - Vitaly has suggested a nice implementation of 900 solution: you can compress coordinates, enumerating them from 1 to 300, make 300x300 matrix, then go from top to bottom, monitoring the current segment on the corresponding y-coordinate, expanding it when there is a point outside its current border of the segment, and shrinking the segment, if there is no point in the whole rectangle lying to the left from the left border of the segment (or to the right from the right border) and completely downside to the current y.

13:36 - but this seems to be fixable if handled carefully. Let’s build the “left border” and “right border”. If they don’t intersect, we’re done. Whenever they intersect, we may choose either path. Let’s try to formalize this :)

13:34 - however, the below solution for 900 has a problem: suppose we have points (0,9),(1,10),(9,0),(10,1). Then “minimal” paths from (1,10) to (10,1) and from (0,9) to (9,0) interfere. The correct solution in this case is to take cells (1,9) and (9,1) and an arbitrary path connecting them.

13:31 - it looks like nika abandoned the 600 and is working on the 900.

13:28 - the last problem doesn’t seem very difficult as well. Let’s consider the topmost point, the leftmost point, the bottommost point and the rightmost point. Then we just need to connect those in the following way: consider going from topmost point to leftmost point. It looks like this:
#
#
###
###
#####
#####
and so on. So we just need to find all points (x,y) such that there’re no other point (x’,y’) such that (x’>=x) and (y’>=y).

13:23 - [[iwi]] went straight from the 250 to the 900. It looks like a variant of convex hull, where the points are discretised. A set is convex if one of the shortest paths between A and B (for any A, B in the set) through the lattice grid is contained within the set. The return value is the area. The constraints on the given coordinates are quite large (~10^9). There are up to 300 input points.

13:20 - there’s lots of corner cases there, though.

13:18 - half of the contestants submitted 250, four of them are opened 600 but did not start coding

13:18 - and chains of odd lengths are basically counted by “layers”. Cells with x>=maxx-dx and y>=maxy-dy have chain of length 1, then chains with (x>=maxx-3*dx, y>=maxy-3*dy, and at least one of x
13:15 - the 600 seems easier than 250. All cells can be split into chains (by connecting (x, y) with (x+dx, y+dy) and (x-dx, y-dy)). For every chain that doesn’t have any coin, the answer is the size of the chain divided by 2 - either 0 or 1 cells in each chain will be unused. For chains that have coins, they are effectively split into smaller chains. So the only thing we need to find out is how many chains of odd length are there.

13:15 - ACRush submits the 250 for 223.21.

13:09 - nearly half of the contestants started coding, nika submitted his solution and gained 239.26 points

13:12 - nika has opened the 600. There is a chessboard (very big - up to 10^9 by 10^9) with some coins on it. You need to find out how many times you can place a coin on (x, y) and another on (x + dx, y + dy) such that you never place a coin on a square which already has a coin. dx and dy are given (also up to 10^9). The initial set of coins has up to 50 coins.

13:10 - column player can win in that situation because at her move, there are more columns than rows, so it’s always possible to choose one that doesn’t spoil the invariant.

13:09 - and question marks don’t add much - since the condition is independent for every row, it’s a pretty simple one to check even in the presence of question marks.

13:09 - nika gets the first submission on the 250.

13:07 - collectively, we’ve invented a solution: the column player wins if in each row, there is at least one cell of her color. The row player wins, if there is at least one row that is all of her color (or, in other words, if it is not true that each row there is either a cell of column player’s color or of the draw color).

13:05 - nika is starting to write solution, the others are still reading the statement

13:04 - matrix is 50x50. People don’t seem to know how to solve this yet.

13:02 - Everybody is starting with the easy problem.

13:01 - the easy problem is: given a NxN matrix with each cell colored with one of 3 colors, two players play the following game: 1st player crosses out a row, then 2nd player crosses out a column, and so on N-1 times until just one cell is left. If that cell is one color, the first player wins, the second color - the second player wins, the third color - a draw. Some of cells are ‘?’, meaning they are of each color with equal probability. What is the probability that each player wins?

12:59 - feel free to ask questions in Arena’s Chat Room 1.

12:58 - Contestants are finally at their positions. Best of luck to them!

12:57 - minus 3 minutes.

12:55 - Looks like there are 250, 600 and 900 point problems.

12:54 - Competitors are standing in the line preparing to be called to the stage. Intro is beginning.

12:49 - During setting up, people write often some well-known algorithms. One of most popular algorithms during this time is min-cost flow. Some people just write templates or solve practice

12:44 - Petr, Vitaliy and KOTEHOK writing this commentary today. bmerry might also offer some insight.

12:38 - People are setting up their workstation and writing solution templates.

Integral bounded knapsack problem solvable in O(knapsack_size*num_of_items)

2011-07-09T13:52:00.000+04:00

The bounded knapsack problem is: you are given n types of items, you have u_i items of i-th type, and each item of i-th type weighs w_i and costs c_i. What is the maximal cost you can get by picking some items weighing at most W in total?

This problem is apparently reasonably popular, and there are many articles about it. However, most of those seem to be interested in approximate solutions or performance on random inputs. But what if we want to treat it as a usual algorithm problem - what is the best possible worst-case running time for solving it?

The best algorithm I could find on the Internet has complexity O(W*n*log(max(u_i)). It goes like this: instead of having u_i items of type i, we create several new types that are multiples of type i, for example items with weight 2*w_i and cost 2*c_i, then the same for 4 and so on, and declare that we have just one item of each type. We create the new types in such a way that the number of new types is logarithmic, and anything that was possible to represent using the old items is also representable using the new items and vice versa. We get a 0-1 knapsack problem with n*log(max(u_i) types which leads to a dynamic programming solution with the above complexity.

However, when this problem was given at a Codeforces contest yesterday, several people came up with a O(W*n) solution for this problem. First, we start with the standard dynamic programming solution: let dp_k,w be the best cost that we can get by packing the total weight of w using the first k item types. Each new type is then handled as follows: dp_k,w=min(dp_k-1,w, dp_{k-1,w-w_k}+c_k, ..., dp_{k-1,w-u_k*w_k}+u_k*c_k). This dynamic programming has O(W*n) states, and each state is processed in O(max(u_i)).

But we can process each state in O(1) amortized time! Let's take a look at the above recurrence. First, we notice that we can separate all values of w into w_k groups, based on the remainder of division on w_k, and those groups can be handled separately. Then, for each group, the problem we need to solve is to find min(a_i, a_i-1+c, a_i-2+2*c, ..., a_i-k+k*c). By setting b_i=a_i-i*c, this expression is transformed into min(b_i+i*c,b_i-1+(i-1)*c+c, ...), which is just i*c+min(b_i, b_i-1, ..., b_i-k). Thus our problem is reduced to finding minimums of groups of k+1 consecutive numbers in a given array.

And this, in turn, is a well-known problem that is solvable in O(size of array) using one of the two methods: we can either maintain a sequence of incremental (from the end) minima for a segment of size k+1 and update it quickly when we shift one position to the right, or we can just separate the entire array into blocks of size k+1, and calculate the prefix and suffix minima for each block - this allows to find the minimum for any block of size k+1 by splitting it into two blocks with precomputed answers.

Is it well-known that bounded knapsack is solvable in O(W*n) worst-case?

ACM ICPC 2011 World Finals - prizes for first solution for each problem

2011-06-05T11:55:00.000+04:00

Did you know that they gave $1500 to the team with the first accepted solution, and $1050 for every other team that solved one of the problems before others in the ACM ICPC 2011 World Finals? You can find all teams that got these prizes at the bottom of the Official Results.

People who went to the World Finals awards ceremony obviously do, but I think this hasn't been mentioned online. What do you think - does this make sense?

Binary search and eps in comparisons

2011-06-02T22:35:00.000+04:00

The usual wisdom about floating-point comparisons inside binary search is to make comparisons exact, to avoid losing precision (as opposed to comparison using some error tolerance denoted as eps). For example this:

for (int step = 0; step < 100; ++step) {
  double middle = (left + right) / 2;
  if (f(middle) > 0) right = middle; else left = middle;
}

is preferable to

for (int step = 0; step < 100; ++step) {
  double middle = (left + right) / 2;
  if (f(middle) > eps) right = middle; else left = middle;
}

when f is a monotonically increasing function, because even with small eps, there's a danger that the corresponding error in the binary search parameter will be much bigger. On the other hand, even if our comparison is incorrect for equal values due to rounding errors, the binary search will still converge correctly since equal values may only appear in one point and everything will be correct in points very close to it.

But all above is true only if f is monotonically increasing! If it is just non-decreasing, and has a plateau, going without eps gets you hugely incorrect results. This bit me today in the hard problem of SRM 508: my failed solution that passes after adding error tolerance to the last comparison in enough() (TopCoder login required).

I guess the lesson is that when trying to be too clever (instead if adding eps to all comparisons), one needs to be extra careful :-)

Reflections on ACM ICPC 2011 World Finals Problems

2011-05-31T22:48:00.000+04:00

I've taken some time to reflect on the World Finals problems - hopefully that will be interesting for you to read. If you were not following the World Finals closely, you should probably skip this post :)

The problems are at http://cm.baylor.edu/digital/icpc2011.pdf, the unofficial solutions from Per at http://www.csc.kth.se/~austrin/icpc/finals2011solutions.pdf.

I've really liked the problemset, so please don't take my words below as criticism - I've just tried to look at the problems from different angles and classify them in different ways, and maybe suggest some improvements for the future.

Problem A - To Add or to Multiply - ad-hoc (number theory?) (by ad-hoc I mean "need creative thinking to solve but no necessary prior algorithm/mathematics knowledge or experience solving similar problems"), most difficulty in corner cases and finding the lexicographically smallest answer.
Problem B - Affine Mess - exhaustive search (do what's described in the problem statement) + solving a system of 2 linear equations, most difficulty in corner cases.
Problem C - Ancient Messages - ad-hoc, out-of-format problem, as there's no precise definition of valid input.
Problem D - Chips Challenge - maximum flow (reduction to flow is the most difficult part).
Problem E - Coffee Central - exhaustive search (do what's described in the problem statement) + the набившая оскомину idea about using inclusion-exclusion for rectangle sums. Most difficulty in finding the lexicographically smallest answer.
Problem F - Machine Works - DP plus incremental convex hull within one quadrant. The key to producing NlogN solution is the somewhat well-known idea about incremental convex hull to find the maximum of a set of linear functions. Most difficulty is inventing this speedup (if not known in advance) and implementing incremental convex hull.
Problem G - Magic Sticks - ad-hoc, geometry. The solution has two main parts - inventing and then proving (or believing) the key mathematical fact about throwing away the longest edge, and solving a sub-problem where you have to maximize the area of the polygon with the given sides. The sub-problem is again quite well-known and was a significant advantage to the teams who saw it before. However, I believe the most difficult part was the longest edge fact. There was also a catch about one edge taking more than Pi angle which many teams forgot to account for.
Problem H - Mining Your Own Business - graph theory, ad-hoc. The most mathematically beautiful problem of the contest in my opinion. The main difficulty is constructing the "if and only if" condition for the set of escape shafts.
Problem I - Mummy Madness - interval trees (or priority queues), ad-hoc. The main difficulty is realizing (a.k.a proving or believing) the problem can be reduced to checking if a square is completely covered by a set of squares. The NlogN solution to that sub-problem is very well-known and should be very easy for top teams.
Problem J - Pyramids - quite straightforward DP (backtracking should also work). I don't see any significant difficulty at all here, but if I were to choose the main difficulty, it would be building the lexicographically largest answer in the DP solution.
Problem K - Trash Removal - a well-known problem. Solvable in NlogN using rotating calipers, but since the constraints were so low, that solution is an overkill. The only difficulty with such small constraints was to realize that the line should be parallel to the line connecting some pair of vertices. The main difficulty is the geometric formulas, but those are very easy as well.

Problem H was really standing out from the problemset, in my view, because it required graph theory thinking but at the same time involved no heavyweight algorithms or implementation difficulties. I would love to see more problems like this, but they are very hard to come up with. Problem C is unusual (so one might argue it gets close to the boundary of teams might reasonably expect) but still good. Problems E, F, I, J, K are "professional" problems - the most difficult part of each lies in a "standard set of tools" that most competitive programmers hone from contest to contest. This is not a negative thing - those ideas form the standard set of tools exactly because they're most useful "building blocks" of various algorithms. Problem K may be too well-known though. Problem G is borderline as it combines a beautiful ad-hoc part with quite difficult algorithm that might be well-known to some teams but not others. Problem D is borderline (but still very good in my opinion) because the "reduce to maximum flow" trickery can also be viewed as a part of "standard set of tools", and thus the problem is quite "professional" too. Problems A, E, J require relatively little thought, and have main difficulty in figuring out the corner cases and careful implementation, which is not exciting, and I'd say 3 such problems is too much (but maybe I'm too subjective after several teams I've supported got buried in those issues).

To spice up the long text, here's my picture with the World Champions:

Please share your thoughts :)

ACM ICPC 2011 World Finals

2011-05-30T16:32:00.074+04:00

Here's my (hopefully) live commentary from the ACM ICPC 2011 World Finals. This post will be updated as the contest goes on.

8:31 - there's a big countdown screen that shows 28 minutes before the start of the contest. The rumor has it that the Peabody ducks will walk on the contest floor before the contestants :)

8:38 - 21 minutes before the contest start, the teams are coming in, right after 5 ducks.

8:43 - 16 minutes before, everyone is seated. I guess it's now up to Bill to entertain everybody.

8:50 - 9 minutes before, Bill is trying hard.

8:53 - to Adrian: I would expect after about 1 hour of the contest. We might try to publish the photos if we get them earlier :)

8:53 - 1 minute before! It looks like they decided to skip some minutes.

8:55 - the contest has started! It looks like there's 11 colored balloons.

8:56 - unlike yesterday, the scoreboard on the big screen is working. Teams are sorted alphabetically for now.

8:58 - no problem statements for spectators yet.

8:59 - no submits yet.

9:02 - live scoreboard from Kattis appears at http://scrool.se/icpc/wf2011/.

9:05 - we got the problem statements from Tatyana Churina!

9:13 - SPbSU and SPbSU ITMO solved K! No other submissions were visible before the scoreboard went down.

9:14 - according to zibada's chat, Perm solved K as well.

9:19 - photos of problem statements are being uploaded to Picasa. Sorry for the poor quality, hopefully it's still readable.

9:22 - 13 teams have solved K, no other submits. Time to look at the problem statements…

9:24 - problem K is classical: find the two parallel lines closest to each other that will fit the given polygon (maybe rotated) between them. It's not hard to see that the line must be parallel to the line connecting some pair of vertices, so you can just try them all. For even faster solution, we should just check adjacent vertices of the convex hull.

9:28 - problem C is quite straightforward as well. You are given 6 pictures of hieroglyphs, and need to write an OCR that will recognize them. The constraints say that the hieroglyphs in input may be distorted by the shape will be "topologically equivalent" to one of the 6 given pictures. The pictures are chosen such that one can just check the number of connected components of the white pixels (kudos to andrewzta for noticing that).

9:30 - meanwhile, there are lots of teams that solved 1 problem. All solved K except Tsinghua, who solved C, and Shanghai, who solved E.

9:33 - problem E is: given at most 500K points on a 1000x1000 grid, and at most 20 queries X, find the X by X square in (x+y, x-y) coordinates that has the most points inside.

9:34 - the constraints are so low that I believe the straightforward solution should pass: using inclusion-exclusion we can find the number of points in each square in O(1), then we can just check 20 million squares.

9:36 - it looks like official problem statements are up at http://cm.baylor.edu/digital/icpc2011.pdf. I hope you've enjoyed my photos in the meantime :)

9:39 - problem J, which several teams have attempted but failed, is: given a number C, represent it as a sum of numbers of form a_i=i*(i+1)*(2i+1)/6, b_i=4*i*(i+1)*(2i+1)/6, c_i=a_(2i+1)-b_i (sums of squares, sums of even squares, sums of odd squares). Each a_i, b_i, c_i may be used at most once. If there are several representations, choose the one with the smallest number of addends. If there are still several ones, pick the lexicographically largest one.

9:43 - meanwhile, three teams have 2 problems: SPbSU and SaratovSU have J and K, Tsinghua has C and K.

9:44 - 6 teams with 2 problems now: NNSU and Hangzhou have E+K, Taurida has J+K.

9:45 - I would expect that simple backtracking (trying all possible choices for the next number in decreasing order, and truncating the search when current best answer is less than remaining sum divided by the maximum possible value for the rest) works for J, since the numbers are quite dense and thus the be split will always be found very quickly.

9:48 - 3 problems solved for Tsinghua, C+J+K.

9:50 - problem A, which is the only remaining problem that has attempts on it, is the following: given two numbers a and m, and two segments [p, q], [r, s], one must create such sequence of operations +a and *m that will transform every number in [p, q] into some number in [r, s].

9:51 - moreover, one should output the program of minimum length, and smallest lexicographically among those with minimum length.

9:59 - here's one idea: even if we add before we multiply, we still add a multiple of a. So in order to check what is the minimal number of steps required to transform a given segment [q, w] to become a segment inside [r, s], we can just iterate over how many times k we multiply, check that there's a multiple k*a of a that, after being added, will move the result inside [r, s], and the number of steps will be the number of multiplications plus the sum of digits in k when written in m-ary system (roughly). So in order to solve this we must solve a sub=problem: given a segment [l, r], what is the number with the smallest sum of digits (in m-ary system) inside that segment? That is a standard problem that is solved by considering the number of digits of that number that coincides with corresponding digits of l (or r).

10:04 - The above solution yields the lexicographically smallest representation as well if implemented carefully. This looks quite tricky to implement, though. KAIST is the only team to solve the problem.

10:06 - The top of the scoreboard is: Saratov, Zheijang, NNSU, Taurida, Tsinghua - all with 3 problems.

10:10 - Problem G is: you are given N segments connected in one row via flexible joints, and you need to assemble one or more polygons in such a way that every segment is a side of at most one polygon and the segments are not allowed to intersect except at endpoints. Your goal is to maximize the total area of the polygons.

10:14 - Tsinghua got 4! A+C+J+K.

10:16 - There are at most 500 segments in problem G. I guess the first question is does it ever make sense to form more than one polygon?

10:19 - Yes, obviously it does. Suppose one middle segment is much, much longer than the others so no polygon can be formed using it. In this case, the segments to the left and to the right of this segment should be treated independently. We can then build similar examples in each part to have the best answer include even more polygons.

10:21 - What doesn't make sense is to have one polygon have non-consecutive set of segments as its sides - we obviously can increase the total area by joining this polygon with the adjacent one then. So it seems that the solution should be: for every [l, r] part of the given sequence of segments, find the best polygon (this is a standard problem). Then, run a standard DP to find the best total area.

10:24 - The only trick I guess is to solve the "standard problem" for so many cases. The standard solution, as Google tells us, is that the optimal polygon with the given sides is a polygon inscribed in a circle, and we can find the radius of the circle by binary search. But that gives a running time of O(n^3*log(precision)) which may be too big.

10:30 - I would expect that it is fast enough, since n^3 is divided by 6 (the number of segments is n^2/2, and the average length of one is n/3). With the super-fast computers, that should be fast enough.

10:32 - Three teams have 4 problems: Zhejiang, Taurida, Tsinghua.

10:48 - problem H is: given a graph, you need to mark the smallest number of its vertices in such a way that after removal of any vertex, there's a path from any vertex to some marked vertex. Unless I'm missing some corner case, this is reasonably straightforward (suggested by Burunduk1): first, we find the tree of biconnected components of the graph, then we choose one vertex in each of the leaves of this tree (in each biconnected component that is a leaf, we must choose a vertex that is not the articulation point that connects this component to the rest of the graph). In case the entire graph is biconnected, we must mark any two different vertices. This is obviously less than the optimal answer since all those marks are required (what happens if we disconnect a leave of the biconnected component tree?), and it's not hard to see they are sufficient.

10:48 - SPbSU, NNSU, Warsaw and Ural also have 4 problems solved.

10:56 - as discussed offline, I expect the winner to solve 8 or 9 problems.

11:02 - problem D: you are given a 40x40 grid of ".", "/" and "C" letters. Your goal is to replace as many "."s by "W"s as possible in such a way that: the total number of "C"s and "W"s in each row and column is at most the given fraction of total number of "C"s and "W"s, and the total number of "C"s and "W"s in the first row is equal to the total number of "C"s and "W"s in the first column, the same for second row and second column, and so on.

11:14 - NNSU has 5.

11:18 - problem F: you are given 100000 machines, each described by the day it appears on (D_i), the price to buy it (P_i), the money you get when you get rid of it (R_i), and the profit it brings on each day (G_i). You may own at most one machine at a time, you can get rid of an old machine and buy a new one in one day, a machine brings profit only on days between the one when you bought it and the one when you got rid of it (exclusive). You can only buy a machine exactly on the day it appears on, and you start with the given amount of money C. What is the maximum possible profit?

11:21 - this actually looks solvable: first, let's start with straightforward N^2 DP: we solve the problem "what is the most money we can earn from the previous machines if we buy k-th machine on the day it appears" by iterating over which machine will we buy before k-th. Then, we will optimize the solution to work in O(N*polylog(N)). More specifically, suppose the previous machine is m-th. Then the maximum profit to get before buying k-th machine is ans[m]-P_m+R_m+G_m*(D_k-D_m-1), and we can only do this if ans[m]+C>=P_m. The second condition doesn't depend on k at all, and the first only depends on D_k. So essentially when choosing the best m for the given k we're choosing the highest among several linear functions of D_k. We can find that quickly, for example, by keeping track of the convex hull of the existing functions.

11:34 - meanwhile, Zhejiang, Tsinghua and Saratov also got 5.

11:36 - and Tsinghua got 6.

11:49 - problem B is: you are given integer coordinates of 3 points before and after the following transformation: first, you rotate the plane such that Ox axis passes through an integer point on the border of [-10,10]x[-10,10] square. Then, you round the coordinates (up in absolute value if the fractional part is 0.5). Then, you multiply all coordinates in each axis by a non-zero integer (different for different axes). And then, you add an integer constant to all coordinates in each axis (different for different axes). You're asked whether there exists such transformation for the 3 given points, and if yes, whether those transformations transform each integer point in the same way. It looks like one can just iterate over all possible rotations, then find scaling and translation numbers based on linear equations, and then check the resulting transformation. The biggest difficulty I guess would be handling corner cases where all points have the same coordinates and suchlike.

11:50 - meanwhile, Zhejiang also got 6 and is in second place.

11:56 - SPbSU solves 6 and moves into second place.

11:58 - problem I is: you are standing in a cell of an infinite plane, and you have 100000 mummies going after you. Each mummy stands in some cell. You make moves in turn: first, you can move to any 8-adjacent cell. Then, each mummy moves to a 8-adjacent cell that is closest to you. You lose if at any point a mummy is in the same cell as you. What is the maximal number of moves you can survive?

12:02 - Moscow solves 5th problem but it's G! Now go for the easy ones! Saratov got 6.

12:32 - had a lunch break. Lots of teams with 6, teams with "standard" set of problems have better penalty time.

12:34 - and Tsinghua solves F. I didn't expect them fixing the problem so quickly.

12:47 - problem I solution together with FedorTsarev: first, let's assume that once the mummy catches us, it follows all our moves. It means that we need to find the largest time X such that we can be in a point distinct from all mummies at time X, and that can be done by binary search. To check a specific X, we believe the following proposition works: we take a 2X+1 times 2X+1 square with center in our position, and check if it's completely covered by 2X+1 times 2X+1 squares centered at mummies'. This relies on assumption that the way the mummies move in the problem statement is "optimal", but this is kind of obvious, since their move always provide strictly optimal distance to us both by x and by y. And checking if a square is covered by other squares can be done in O(NlogN) using the sweeping line method and keeping an interval tree that stores how many times each cell is covered.

12:47 - meanwhile, 1 team has 7 problems and 9 teams have 6 problems.

12:56 - the standings are frozen. The only problem for me to solve is D. I'm going to the contest room to watch the balloons brought to the teams.

13:13 - three teams in the 7/6 group have submitted problems, but none of them seems to have the corresponding balloon, so it looks those were wrong submissions.

13:20 - still no new top teams with non-standard balloon colors. Maybe they've stopped delivering them?..

13:30 - it looks like new balloons are indeed not delivered to top teams at all. Warsaw team were congratulating each other twice, so I assume they have 7.

13:32 - it looks like Moscow got A!

13:43 - no further updates. The only way to figure something out is to look at team's exctited/disappointed reaction.

13:45 - or maybe Warsaw actually has 6?

13:55 - the contest is over! Still no news.

13:59 - Saratov has 7.

14:08 - Taurida has 6.

14:15 - SPbSU, Saratov, Moscow, Nizhny Novgorod, FAU, Donetsk, Ural, Krakow all have 7.

14:17 - Zhejiang has 8! Warsaw and ITMO have 6.

14:20 - Waterloo has 7!

14:21 - Michigan has at least 7!

14:23 - most likely results: Zhejiang, Tsinghua, SpbSU, Nizhny, Saratov, FAU, Donetsk, Krakow, Moscow, Michigan, Ural, Waterloo.

14:29 - no, it's not! Zhejiang - 8, Michigan - 8, Tsinghua, SpbSU, Nizhny, Saratov, FAU, Donetsk, Krakow, Moscow, Ural, Waterloo - all 7.

14:40 - that's it. I'll probably not update this post anymore, unless some interesting comments surface. Thanks for following my blog today!

ACM ICPC 2011 World Finals - pre-contest

2011-05-30T09:16:00.001+04:00

ACM ICPC 2011 World Finals are happening these days in Orlando. Tomorrow, as usual, I will be doing live commentary on the tasks and on the contest itself. Today, about 9 hours before the start of the contest, I write about what happened before the contest - using style borrowed from Mike's notes.

On Friday, we went to see the ocean and the Kennedy Space Center, where most American space launches happen. The space center was very disappointing - it looks like the only reason to go there would be to view an actual launch (and the next launch is in July), that should be very impressive and maybe even educational. What we found there was:

Real-size models of most American rockets, Russian ships and the Shuttle:

Space-themed and not-so-space themed attractions and fountains (really nice in 30C heat):

The ocean is nice and warm, but comes with some jellyfish bites :)

On Saturday, the organizers took us to SeaWorld resort. The resort welcomes you with a traffic jam on the parking entrance:

They started with an IBM history recap given on a stadium where the killer whale show (Shamu) takes place. Not everyone was excited:

Then we were given lots of time to explore SeaWorld, which was quite exciting. The most exciting part was the dolphin show, but I'm yet to download it from the camera, so here goes the still part of SeaWorld:

On Saturday, the Opening Ceremony and two Practice Sessions took place. Here's how the contest area feels:

And here's how the teams look:

Good luck to all teams, and especially to the team in the last picture - and stay tuned for the live commentary tomorrow right in this blog! The contest starts around 9am local time (click the link for other timezones).

Solution to the alternating jumps problem

2011-01-15T12:51:00.000+03:00

Let me remind about the problem: we alternate jumps to the left and to the right, possible jumps to the left are given as set A, possible jumps to the right are given to set B. Is any integer point reachable?

When we first approach this problem, the alternating jumps condition restricts our thinking, so the natural move is to get rid of it. How? Let's pair up the jumps to the left and to the right. Then we have a new set of possible jumps C = {b - a, for b from B and a from A} that consists of all differences between B and A. We can then jump by numbers from C arbitrarily, so the sub-problem that we need to solve is:

Given a set C of integers, which integer points are reachable if we jump by numbers from C starting from 0?

This is where you have to apply the previous knowledge. More specifically, the fact we're interested in is: given a set of integers C = {c₁, c₂, ...}, their greatest common divisor g (the largest positive integer that divides every number in C) is representable as g = q₁c₁ + q₂c₂ + ... where q₁, q₂ and so on are integers.

This fact is about what we need to solve our sub-problem. First, we note that every integer point that is reachable by jumping by numbers from C is divisible by g (as a sum of several numbers divisible by g). What we hope for is that the reverse is true as well: every point divisible by g is reachable.

The above representation of g = q₁c₁ + q₂c₂ + ... almost gives us the strategy to reach point g: each q_i means the number of times we jump by the corresponding amount c_i. The only problem that some q_i may be negative, and we can't do a jump minus one times.

Now the question is: take one number c from C. How do we jump by -c? If we can do that, we can use the above formula to reach point g. Let's consider the case where c is positive. Here's where we need another non-trivial idea: let's check if there's any negative number if C. If not (all numbers in C are non-negative), it's obvious that we can't reach -c (or any other negative number). However, if there's a negative number -d in C, we can reach -c by doing the -d jump c times, then doing the c jump d-1 times: -d*c+c*(d-1)=-c.

In case c is negative, a similar argument shows that if there's a positive number in C, then we can reach -c, otherwise we can't reach any positive number.

Let's summarize the result that we've arrived at. If C has at least one positive number and at least one negative number, then we can reach point g. We can reach point -g in the same manner. But then we can reach any point divisible by g by repeating the sequence!

Having (almost) solved the sub-problem, we return to the main problem. The solutions for the sub-problem correspond to the points that we can reach after an even number of steps. What about points reachable after an odd number of steps?

First, consider the case where C is "bad" - has only non-negative or only non-positive numbers. We know that not all points are reachable via even number of steps. Moreover, we know that a lot of points are not reachable via even number of steps: all positive points or all negative points. But then it's obvious that not all points are reachable via odd number of steps as well: if we'll always be at a non-negative point after an even number of steps, one more step can only bring us this far into the negative half of the line - so all numbers below a certain value (minus maximal element of A) are not reachable, and the answer to the main problem is "NO".

Then, consider the case where C is "good". We know that every number divisible by g is reachable via an even number of steps. What does one more step (subtracting a number from A) change? We can reach every point that has the same remainder of division by g as minus number from A. But what remainders of division by g can numbers from A have?

Since g = gcd(a₁-b₁, a₂-b₁, ...), then a₁-b₁ and a₂-b₁ are divisible by g. But then their difference, which is a₁-b₁-a₂+b₁=a₁-a₂, is divisible by g. Similarly, the difference between any two numbers in A is divisible by g. So all numbers from A have the same remainder x of division by g!

We've finally summarized all numbers that are reachable: those divisible by g and those that have the remainder of g-x of division by g. When does that cover all numbers? When g equals 1, or when g equals 2 and x equals 1. With larger g, some remainders are not covered. With g equal to 2 and x equals 0, odd numbers are not covered.

We're almost there - here's what we have now. When all number from C have the same sign, the answer is "NO". Otherwise, if g is the greatest common divisor of C, then the answer is "YES" if and only if g equals 1 or g equals 2 and a₁ is odd.

The only problem is that C may have too many elements: when A and B have 10000 elements each, C may have as many as 100 million! The last step is to notice that we don't need to find C. All we need to know is:
- does C have a positive number?
- does C have a negative number?
- what is the greatest common divisor of all numbers in C?

The first question (and the second one similarly) is answered easily. C has a positive number if and only if the largest element of B is larger than the smallest element of A.

And the last question can be answered using the trick mentioned above. Consider an arbitrary element of C: a_i-b_j. Since we already know that differences between numbers in A (or numbers in B) are divisible by g, we can represent this number as the sum of three numbers divisible by g: a_i-b_j=(a_i-a₁)+(a₁-b₁)+(b₁-b_j). That allows us to consider the greatest common divisor g₁ of the following set C₁ of numbers: a₁-b₁, a_i-a₁ for all i, and b₁-b_j for all j, and prove that g₁ equals g. This is easy: g divides g₁ since g₁ is the greatest common divisor of numbers that are differences of numbers from C. But g₁ divides g for the same reason: every number in C is a sum of three numbers from C₁! So g₁ equals g, and we can find g as the greatest common divisor of C₁ which has at most 20000 elements.

Phew! This was a long solution, not because it's complicated, but because it has many steps that have to be carefully executed. Each particular step is either obvious or represents a relatively easy mathematical fact. However, in order to successfully walk the entire path and not make any mistake along the way (take a look at the contest results: the problem in question is problem A) you have to be really careful and have a good understanding of where you are and what is left to prove. That's why I said this problem is really about formal reasoning skills.

To spice up the long textual post, here's a picture of our Moscow State University team at the ACM ICPC 2003 World Finals in Beverly Hills (by David Hill, from the official World Finals photo archive):

A nice problem to test formal reasoning skills

2011-01-13T18:00:00.002+03:00

Here's a problem that I think is easy if you're fluent with formal mathematical reasoning (and some facts from mathematics I don't want to reveal now :)), and close to impossible otherwise.

You are given two sets of positive integers: A and B. You start at point 0 on a line, and alternate jumps to the left and to the right, starting with a jump to the left. Whenever you jump to the left, you jump by a number chosen from A. Whenever you jump to the right, you jump by a number chosen from B.

Is any integer point reachable?

Example: A = {1, 5}, B = {2, 4}. To reach point -2, you can jump by -5, then by 4, then by -1, yielding -5+4-1=-2.

Constraints: A and B have at most 10000 elements, numbers in A and B are between 1 and 1000000000 (billion). Note that you can't jump to the left or to the right twice in a row - you have to alternate.

Source: SnarkNews Winter Series 2011, Round 2 (the round is over so it's fine to discuss solutions now).

Codeforces Beta Round 50: how to avoid stupid bugs?

2011-01-11T18:55:00.001+03:00

Today I've solved another Codeforces round, with very disappointing results. That was even more disappointing given the fact that the problems were very nice (and they are always both in Russian and English there - no excuse for you not to participate in the next round on Friday :)), and I was able to see the solutions quickly.

Two of my five solutions failed. The first one, for problem B, had this bug (here's a link to full solution):

036                    if (bx < 0 || bx * by > hblock * wblock || (bx * by == hblock * wblock && bx < hblock)) {

037                        bx = hblock;

038                        by = wblock;

039                    }

Line 36 must have "bx > hblock" instead of "bx < hblock": this is an implementation of the tie-breaker which asks us for minimal value, not maximal value.

The second one, for problem E, had this bug (here's a link to full solution):

067                double rc = Math.min(ra + Math.PI / 2, rb);

...                ...

070                if (rc > rb + EPS) {

071                    ++b;

072                } else {

073                    ++a;

074                }

The condition in line 70 must be "rc > rb - EPS" or "ra + Math.PI / 2 > rb + EPS" instead of "rc > rb + EPS". This code iterates over two sets of segments, and needs to advance one of the pointers based on which segment ends first. I've even had the correct condition with "- EPS" in the beginning, but has found that this would shift pointer b in case of a tie. For some reason, I've decided that it's better to shift a instead to be on the safe side (now I realize it doesn't matter) - but changed the code in such a way that it will always shift pointer a!

What do you think is the best way to find such bugs during the contest or to not make them in the first place? I used to do the latter automatically, it looks like I need to improve in this area.

SnarkNews winter series - 2011

2011-01-10T21:44:00.001+03:00

I'd like to share another screencast: round 1 of SnarkNews winter series - 2011. Here's Torrent (preferable), Direct AVI. The rules of this contest are quite different from TopCoder and one needs to submit ACM-style programs through a web interface instead of using the TopCoder arena.

What is this series? You can find the rules at the "rules of the series" link above. Overall, this is (at least) 13th series of 5-6 contests, each presenting 5-6 problems for 1 hour 20 minutes (usually), with the timeframe to start each contest about a week. The problems are usually not new but are chosen to be unknown to most Russian competitors. The problem statements are often in Russian, so participation is usually limited to Russian speakers. However, if you want to practice your Russian skills, feel free to register and participate as described on the rules page. You've missed Round 1, but the remaining four rounds are still up for grabs.

The problems were on the difficult side of what usually happens in such contests this time, so the remaining four rounds should be easier on average :)

Screencasts: 2010

2011-01-10T00:25:00.004+03:00

As requested, here's an attempt at a richer screencast for SRM 491 - this one also has a side-cam view at myself and my table. I'm afraid it doesn't make the screencast much more interesting, but probably it becomes a bit more funny, and the psychological experiment of working while knowingly being recorded was definitely interesting. Feels a bit like creating the big event atmosphere at home :) Since the file turned out to be 3.2G, the only feasible way to distribute it seems to be via: Torrent.

The highlight of that SRM was the failing min-cost-max-flow solution for the hard problem, which was even one of the intended solutions by the judges. Luckily, there was another greedy solution that worked much more quickly. I went this road, but in the opposite direction: my first solution was greedy, then I wrote a stress test against a stupid solution and found it didn't work, couldn't figure out how to fix it and then came up with the min-cost-max-flow solution which I've resubmitted and which failed systest due to timeout. After the match, the logical question was: why did I choose writing min-cost-max-flow instead of fixing the greedy solution? I think that the answer is that programming contests teach us to look for a 'beautifully fitting' solution. When I saw the reduction to min-cost-max-flow, it looked like something the author of the problem had in mind, and I gave it no second thought.

Here are other screencasts of 2010, just for the record.
SRM 461: Torrent
SRM 476: Torrent
SRM 480: Torrent
SRM 485: Torrent
SRM 486: Torrent

TCO 2010 Finals Hard

2010-10-15T22:20:00.000+04:00

With no better idea of spending some time on the Las Vegas - New York plane, I've decided to try coding the hard problem from the TCO 2010 finals (statement linked). This took me 26 minutes and I got 618 points in the practice room — knowing the solution in advance and using IDEA instead of a simple text editor (rng_58's time in the finals was 48 minutes, for 463 points).

I hope the code with the below explanations can serve as a semi-editorial while we're waiting for the official editorial.

  1: import java.util.*; 
  2:  
  3: public class ColorfulJewelry { 
  4:     static final long MOD = 1000000009; 
  5:     int height; 
  6:     int width; 
  7:     int maxCount; 
  8:     String[] jewels; 
  9:  
 10:     class RectangleSums { 
 11:         int[][] sums; 
 12:  
 13:         public RectangleSums(char ch) { 
 14:             sums = new int[height + 1][width + 1]; 
 15:             for (int r = 0; r < height; ++r) { 
 16:                 int colSum = 0; 
 17:                 for (int c = 0; c < width; ++c) { 
 18:                     if (jewels[r].charAt(c) == ch) 
 19:                         ++colSum; 
 20:                     sums[r + 1][c + 1] = colSum + sums[r][c + 1]; 
 21:                 } 
 22:             } 
 23:         } 
 24:  
 25:         int getSum(int r1, int c1, int r2, int c2) { 
 26:             if (r1 >= r2 || c1 >= c2) 
 27:                 return 0; 
 28:             return get(r2, c2) + get(r1, c1) - get(r1, c2) - get(r2, c1); 
 29:         } 
 30:  
 31:         private int get(int r, int c) { 
 32:             if (r < 0) 
 33:                 r = 0; 
 34:             if (c < 0) 
 35:                 c = 0; 
 36:             if (r > height) 
 37:                 r = height; 
 38:             if (c > width) 
 39:                 c = width; 
 40:             return sums[r][c]; 
 41:         } 
 42:     } 
 43:  
 44:     public int getChains(String[] jewels, int k) { 
 45:         this.jewels = jewels; 
 46:         height = jewels.length; 
 47:         width = jewels[0].length(); 
 48:         RectangleSums[] sums = new RectangleSums[3]; 
 49:         for (int i = 0; i < 3; ++i) 
 50:             sums[i] = new RectangleSums("RGB".charAt(i)); 
 51:         maxCount = height * width; 
 52:         int[][] maxCounts = new int[maxCount + 1][maxCount + 1]; 
 53:         for (int i = 0; i <= maxCount; ++i) 
 54:             Arrays.fill(maxCounts[i], -1); 
 55:         for (int r1 = 0; r1 < 1 || r1 + k <= height; ++r1) { 
 56:             for (int c1 = 0; c1 < 1 || c1 + k <= width; ++c1) { 
 57:                 for (int r2 = r1; r2 < r1 + 1 || r2 + k <= height; ++r2) { 
 58:                     for (int c2 = 0; c2 < 1 || c2 + k <= width; ++c2) { 
 59:                         int[] count = new int[3]; 
 60:                         for (int i = 0; i < 3; ++i) { 
 61:                             count[i] += sums[i].getSum(r1, c1, r1 + k, c1 + k); 
 62:                             count[i] += sums[i].getSum(r2, c2, r2 + k, c2 + k); 
 63:                             count[i] -= sums[i].getSum(Math.max(r1, r2), Math.max(c1, c2), Math.min(r1, r2) + k, Math.min(c1, c2) + k); 
 64:                         } 
 65:                         maxCounts[count[0]][count[1]] = Math.max(maxCounts[count[0]][count[1]], count[2]); 
 66:                     } 
 67:                 } 
 68:             } 
 69:         } 
 70:         for (int r = maxCount; r >= 0; --r) 
 71:             for (int c = maxCount; c >= 0; --c) { 
 72:                 if (r > 0) 
 73:                     maxCounts[r - 1][c] = Math.max(maxCounts[r - 1][c], maxCounts[r][c]); 
 74:                 if (c > 0) 
 75:                     maxCounts[r][c - 1] = Math.max(maxCounts[r][c - 1], maxCounts[r][c]); 
 76:             } 
 77:         prepare(); 
 78:         long res = 0; 
 79:         for (int r = 0; r <= maxCount; ++r) 
 80:             for (int g = 0; g <= maxCount; ++g) 
 81:                 if (maxCounts[r][g] >= 0) { 
 82:                     res = (res + solve(r, g, maxCounts[r][g])) % MOD; 
 83:                 } 
 84:         // Divide by 2
 85:         res = (res * ((MOD + 1) / 2)) % MOD; 
 86:         // Subtract 1
 87:         res = (res + MOD - 1) % MOD; 
 88:         return (int) res; 
 89:     } 
 90:  
 91:     int[][] combinations; 
 92:     int[][] combinationSums; 
 93:  
 94:     private void prepare() { 
 95:         combinations = new int[maxCount + 1][maxCount + 1]; 
 96:         combinations[0][0] = 1; 
 97:         for (int n = 1; n <= maxCount; ++n) { 
 98:             combinations[n][0] = 1; 
 99:             for (int i = 1; i <= maxCount; ++i) 
100:                 combinations[n][i] = (int) (((long) combinations[n - 1][i] + combinations[n - 1][i - 1]) % MOD); 
101:         } 
102:         combinationSums = new int[maxCount + 1][maxCount + 1]; 
103:         for (int rplusg = 0; rplusg <= maxCount; ++rplusg) { 
104:             combinationSums[rplusg][0] = combinations[rplusg][0]; 
105:             for (int maxb = 1; maxb + rplusg <= maxCount; ++maxb) { 
106:                 combinationSums[rplusg][maxb] = (int) (((long) combinationSums[rplusg][maxb - 1] + combinations[rplusg + maxb][maxb]) % MOD); 
107:             } 
108:         } 
109:     } 
110:  
111:     private long solveSimple(int r, int g, int maxB) { 
112:         long simple = combinations[r + g][r]; 
113:         simple *= combinationSums[r + g][maxB]; 
114:         simple %= MOD; 
115:         return simple; 
116:     } 
117:  
118:  
119:     private long solve(int r, int g, int maxB) { 
120:         long simple = solveSimple(r, g, maxB); 
121:         // Now to the symmetric ones
122:         long symmetric = 0; 
123:         if (r % 2 != 0) { 
124:             if (g % 2 != 0) { 
125:                 // This can't be symmetric
126:             } else { 
127:                 symmetric = solveSimple(r / 2, g / 2, maxB / 2); 
128:             } 
129:         } else if (g % 2 != 0) { 
130:             symmetric = solveSimple(r / 2, g / 2, maxB / 2); 
131:         } else { 
132:             // Even number of Bs
133:             symmetric = solveSimple(r / 2, g / 2, maxB / 2); 
134:             if (maxB > 0) { 
135:                 // Odd number of Bs
136:                 symmetric += solveSimple(r / 2, g / 2, (maxB - 1) / 2); 
137:                 symmetric %= MOD; 
138:             } 
139:         } 
140:         return (simple + symmetric) % MOD; 
141:     } 
142: }

The entry point method, getChains, is located in lines 44-89. First, we create 3 RectangleSums objects each tracking one kind of jewel. The object itself, located in lines 10-42, keeps track of sums for each (0,0)-(x,y) rectangle, and that allows it to calculate the sum for an arbitrary rectangle using inclusion-exclusion.

Lines 51-69 are responsible for trying all possible combinations of two squares. Please note the loop boundaries: although the problem statement allowed for the squares to be outside the field, it is not really necessary since we can always use only some of the jewels we get. The only case when this is necessary is when k is larger than the size of the field - that's the reason for the "r1 < 1 ||" clause and similar ones for other loops. We also start r2 from r1, not from 0, to cut the total number of cases to consider in half.

ACRush has told me that his hard has timed out because he lacked the above optimizations, that's why I already had them in my mind. During the actual contest, I guess only extensive testing could lead to being so careful here. The solution runs for 1.4s on the worst case, and there's only one such case in the test data (but I guess any test case with a 44x44 field and k=1 will present this running time).

Lines 61-63 calculate the total counts of each jewel in both rectangles using inclusion-exclusion. Line 65 stores the result in the following manner: for every pair of #R and #G we've seen, we store the maximum #B. Since we can always discard some jewels, the maximum is enough for our purposes.

Lines 70-76 "spread" the maximum towards lower values of #R and #G. By that we calculate the following: what is the maximum number of Bs that can appear on a chain with exactly the given amount of Rs and Gs?

Method prepare() calculates two arrays that I've mentioned in the live coverage and that are later used to quickly count chains: combinations[n][k] is the number of ways to choose k items out of n, and combinationSums[rplusg][maxb] is equal to combinations[rplusg][0] + combinations[rplusg+1][1]+...+combinations[rplusg+maxb][maxb].

Lines 78-83 call method solve() which answers the following question: "how many chains are there with exactly R red jewels, exactly G green jewels, and between 0 and maxB blue jewels?".

"how many" is defined in a strange way, though. In order to calculate the number of chains up to reversal, we need to calculate the total number of chains, then the number of symmetric chains, and then divide all non-symmetric ones by 2, yielding the formula (total-symmetric)/2+symmetric=(total+symmetric)/2. We make solve() return the value of "total+symmetric", and divide by 2 in line 85 of the main method. We also need to subtract 1 in the very end since an empty chain is not allowed.

So how does solve() work? The method solveSimple() is reponsible for counting the total number of chains, forgetting about the symmetry issues. In order to calculate the number of symmetric chains, we use the following observation: a symmetric chain of length n is uniquely defined by its first half. When n is even, the half is n/2 long and each color appears twice less frequently in the half. When n is odd, the half is (n+1)/2 long and each color except the one of the middle jewel appears twice less frequently, while the number of occurrences of the color of the middle jewel is (old+1)/2. The code in lines 129-139 is basically concerned with the color of the middle jewel. When both #R and #G are odd, this means the middle jewel is both red and green, which is impossible. When only one of them is odd, this should be the color of the middle jewel, so the number of blue jewels should be even and we divide maxB by 2 to get the corresponding number for the half-chain. When both of them are even, either there's no middle jewel (line 133), or it is blue (line 136).

That's it! Questions? Comments?

What is TopCoder Mod Dash?

2010-10-15T03:30:00.000+04:00

At this year's TopCoder Open, I've naturally enjoyed watching the algorithm and marathon competitions. However, there was one more which I enjoyed and found very watchable and intense: the Mod Dash competition. So here's a small educational video about what this competition is about:

There's also another video that I've made at the TCO, which is the usual overview of the arena. It is a bit boring, but just in case, here it goes:

TopCoder Open 2010 Algorithm Final Round

2010-10-15T00:15:00.057+04:00

Here will go the comments for Algorithm Final Round of TopCoder Open 2010, the pinnacle of the event.

13:16 - 15 minutes before the start. Today's lineup: ACRush, liympanda, Louty from China, dzhulgakov and Klinck from Ukraine, PaulJefferys from UK, bmerry from South Africa and rng_58 from Japan.

13:18 - ACRush, liympanda, bmerry and PaulJefferys are returning participants of the TCO onsites, while Klinck, dzhulgakov, Louty and rng_58 are here for the first time. Klinck has been participating in TopCoder for 7 years, though, and has almost always been near the top of "Submission accuracy" rating. The effort has finally paid off!

13:23 - watching the screens of dzhulgakov and Klinck today.

13:25 - the introduction has started.

13:29 - 1 minute before the start.

13:34 - the easy problem: you have up to 50 election districts, and the voting happens the following way: in i-th district, there are voters[i] voters and each of them votes for somebody. Then, for each district the candidate who's got the largest number of voters wins. In case of a tie, nobody wins. You are asked about the smallest number X such that when X people vote for your party's candidates, no matter which X people, you're still going to have strictly more than half of all winners.

13:39 - the solution is quite easy and suggested by the examples. In the worst case, in order NOT to win you can get all votes in one half of the districts (the largest ones), and one less the half votes in all other districts. This requires care about ties, and different handling for odd/even number of total districts. Most people will submit something like this, but I expect an eventful challenge phase here.

13:40 - submissions from PaulJefferys, rng_58, dzhulgakov and ACRush. Only rng_58 have opened the medium.

13:41 - syg96 suggests a solution that will probably have less corner cases: iterate over how many district wins, draws and losses are we going to have (in the worst case of not winning). It's quite obvious that wins should go in the largest districts, then draws, then losses. Then just take the maximum over all scenarios where we don't win plus one.

13:42 - the medium problem: what is the smallest area of a square with vertices in lattice points that contains exactly n lattice points inside? n is up to 10^12.

13:44 - a submit on easy from Klinck.

13:44 - suppose the side vector of the square is (x, y). Then the number of lattice points inside is x^2+y^2-2*gcd(x,y)+1, according to the Pick's formula.

13:48 - this should be equal to n. Since we need to minimize the area, we need to minimize gcd(x,y).

13:50 - a lot of numbers are representable as sum of two squares. More precisely, all prime factors of form 4k+3 should have even exponent in the prime factorization.

13:51 - meanwhile, PaulJefferys have resubmitted the easy and liympanda has submitted it.

13:56 - so I would guess the following should work: we iterate over possible value for g=gcd(x,y). When that value is fixed, we get x^2+y^2=n+2*g-1. We substitute x=g*p, y=g*q, then we get p^2+q^2=(n+2*g-1)/(g*g). So we need to check if there's a sum of squares of relatively prime numbers equal to the given number. And for that, we can just do bruteforce since we'll need to check sqrt(n) values for g=1, sqrt(n)/2 values for g=2, and so on, for the total of sqrt(n)*log(n) values. This should run fast enough.

13:56 - dzhulgakov seems to have a working solution in terms of time limit, but it doesn't pass the examples.

13:57 - meanwhile Louty submits the easy, and everyone is working on the medium, including bmerry who didn't submit the easy.

13:58 - dzhulgakov fixes his bug, but still unsure about TL. ACRush has already submitted some time ago.

14:00 - rng_58 submits the medium, too.

14:01 - dzhulgakov speeds up his code from about 1s to about 0.2s, but seems to give WA now. He's looking into STL docs now.

14:03 - rng_58 have opened the hard, dzhulgakov has found his bug (int instead of long long). Now his sol works in 0.2s and seems correct. Going to submit?

14:04 - dzhulgakov submits.

14:06 - the hard problem: you are given a 44x44 rectangle of 'R', 'G' and 'B' characters. You consider all possible ways to take two (possibly intersecting or partially lying outside) kxk squares, then take all of the jewels inside at least one of those squares, then discard some of them and place all the rest in one chain. How many different chains can you get, modulo 10^9+9, if two chains that are reverses from each other are considered equal?

14:11 - the obvious idea for the first step is considering all pairs of two squares, and recording how many Rs, Gs and Bs are there in their union. This can be checked in O(1) for each pair if we precalculate partial sums of upper-left rectangles.

14:11 - meanwhile, liympanda and PaulJefferys also submit the medium.

14:13 - ACRush still didn't open the hard, he's checking his solution for the medium. People watching his screen say he didn't find any bug, he's just checking it very thoroughly. Maybe he knows about a problem but is not sure if it can be triggered by the possible testcases?

14:15 - then what we can do is iterate over possible values of how many Rs and Gs are there going to be in the chain. For each such pair, we calculate the largest amount of Bs possible, and now we need to calculate the number of chains with this many Rs and Gs and at most this number of Bs in O(1).

14:17 - if we forget about "up to reverse" condition, the formula is quite straightforward: ((R+G) choose R) times (1+((R+G+1) choose 1) + ((R+G+2) choose 2)+...+(R+G+B) choose B). How do we find that in O(1)?

14:19 - I guess we can just precalculate that for all values of R+G (which are up to 2*44*44 in total) and B (up to 44*44), that should be fast enough. So the only thing to deal with is "up to reverse" condition.

14:24 - And this is dealt with as usually by finding how many stay the same up to reverse (this means looking at a sequence of length n/2, with probably special casing for the middle cell when n is even), and then dividing all the remaining amount by 2 since all others split into pairs. answer_up_to_reverse=(answer+answer_thats_same_as_reverse)/2. This can also be viewed as the Burnside's lemma application.

14:24 - meanwhile, ACRush has resubmitted the easy which drops him to 5th in the current standings. Everyone has submitted the medium, bmerry still didn't submit the easy. rng_58 is first, dzhulgakov is second.

14:29 - now that we seem to have solutions for all problems, let's just watch what the contestants do.

14:31 - ACRush, rng_58 and bmerry seem to be coding something similar to the above solution. Most others are thinking. dzhulgakov is rechecking his easy solution.

14:33 - or maybe he's not? he has the easy code open, but maybe he's thinking about the hard on paper?

14:37 - some discussion of the easy between the spectators suggest it's quite hard to do it by considering all cases - the solution suggested by syg96 above (and dzhulgakov has implemented something very similar) is indeed the way to go.

14:41 - rng_58 is already testing his hard, not sure if it's the version without "up to reverse" or the final one.

14:42 - rng_58 has a bug in counting the number of Rs, Gs and Bs: x and y swapped in one place.

14:43 - liympanda resubmits the easy as well! This is going to be a hell of a challenge phase.

14:45 - everyone except dzhulgakov and liympanda is working on the hard, but it seems like not many are close enough to submit in 10 minutes.

14:47 - Louty gives up. bmerry, ACRush and rng_58 are all debugging one different example cases. Paul and Klinck are still coding.

14:48 - Klinck gives up as well, tests his medium. Maybe giving up now will actually prove crucial for the challenge phase?

14:49 - or maybe not! rng_58 passes all example cases, tests for TL...

14:51 - and he submits!

14:52 - and ACRush submits, too. He's above but the difference is less than 5 points. I guess challenges WILL be important, just not for everybody :)

14:54 - ACRush still looking at his hard - this is probably a bad idea. Should be working on challenge cases instead. Nobody else submits, the coding is over.

14:56 - PaulJefferys is preparing a large random testcase for ACRush and rng_58's hards. We'll see if those seem to be correct at the very beginning at the challenge phase. That will probably affect the further challenging strategy of everyone.

15:00 - most people went for 250s, bmerry is reading 500s. Paul decided not to blind-challenge the hards.

15:01 - ACRush successfully challenges Louty's solution!

15:02 - and there goes dzhulgakov's easy.

15:04 - the challenge case for both is "10, 10, 5, 4, 1" with the correct answer of 25. The trick here is that one needs to win the first two and draw the FOURTH in the worst case, while dzhulgakov only considered winning some largest ones and drawing some next largest ones.

15:08 - just one minute left, still no challenges on the hards. C'mon, Paul!

15:10 - Paul looked at the hards but decided not to challenge. ACRush got -25 in the final seconds.

15:10 - let's wait for the systests...

15:16 - ACRush seems to be pretty confident in his solutions. His only concern is the doubles he uses in the 500.

15:17 - ACRush has also told me that he didn't test his 1000 at all except the examples, but he doesn't think there'll be any TL issues.

15:18 - I think I will take a break now before the results are announced.

16:00 - rng_58 is the champion! ACRush's hard, Paul's easy and liympanda's medium failed, all others passed.

16:01 - wata is the Marathon champion! chokudai is second, doudouille is third. Go Japan!

16:03 - as expected, Margarita is the Mod Dash champion!

16:05 - and djackmania is the Studio champion! I think that's it for today's live coverage. However, please check this blog later for some videos of the event.

TopCoder Open 2010 Algorithm Wildcard Round

2010-10-14T05:13:00.039+04:00

Here will go the comments for Algorithm Wildcard Round of TopCoder Open 2010.

18:22 - it's very quiet in the arena, since most people who are not competing went to enjoy the fabulous Las Vegas (or just went to their rooms to get some sleep?). Most of algorithm competitors are here, though, even the ones who're not competing.

18:27 - I'm sitting in front of dzhulgakov's and syg96's screens. Hope that those two won't disappoint us, as rng_58 did in the semifinal.

18:30 - go!

18:30 - the easy problem: you start with N distinct numbers, and then can swap two adjacent numbers M times. How many different sequences can you get?

18:31 - N and M are up to 2000.

18:32 - so if a sequence X has Y inversions (pairs of indices such that the numbers at these indices are not in the same order in the original sequence), then we can get it using Y, Y+2, Y+4, ... swaps. The problem is thus reduced to counting sequences which have at most M inversions, and have the same amount of inversions modulo 2. I think this is done via quite simple DP - if you know the first number, you know how many inversions it creates, and then continue with the rest. This should work in O(2000^2).

18:35 - everybody is doing the easy problem, no variability from the contestants this time.

18:37 - PaulJefferys has submitted and then found out that his code TLs on (2000, 2000) :( Thanks Rustyoldman for the pointer!

18:40 - oh, AS1_PML30 has pointed out that my above solutions works in O(2000^3).

18:40 - dzhulgakov submits! And the DP is not so difficult to code in O(2000^2) by noticing that we can use accumulated sums to process each state in O(1).

18:42 - the medium problem: you're given at most 50 cards of form "+2", "*3". You shuffle then randomly, and then lay them down next to "0" to get an expression like "0+1-2*3", which is equal to -5. What is the expected value of this expression?

18:44 - first, we can notice that the order of "+" and "-" cards is not important. We can imagine the problem as starting with one "0" card and several "+X" and "-Y" cards, and then we need to place all "*Z" cards next to one of the starting cards, and the order of doing so for each starting card matters.

18:47 - maybe one can just do DP on the number of remaining cards of each type ("*1", "*2", ..., "*9", "*0")? That should be at most 5^10 states, which is about 10 million, but the transition will be quite slow.

18:54 - or maybe we can rely on the fact that we only need to find the expected value somehow? People seem to be at a loss around here.

18:54 - it turns out it's just me who's at a loss. Let rng_58 explain.

19:00 - still discussing the solution...

19:09 - so we need to calculate the expected value for each additive term, then sum those up. That means we should calculate just one number that depends on the multipliers: the expected multiplier for each additive term. At the simplest, we could iterate over all possible at most 5^10 compositions of a multiplier and average those with appropriate weights (some factorials multiplied and divided :)).

19:11 - bmerry suggests we can do it even faster: let's add multipliers one by one, and keep track of the expected value of the product if we have exactly k multipliers for each k, and the number of ways to get exactly k multipliers. Then this will be just something like O(50^2).

19:13 - another spectator reminder from Rustyoldman: everybody had submitted the easy and everyone is doing the medium... Not anymore! grotmol has opened the hard!

19:15 - here's the hard problem: how many ways are there to select some cells in a H times W rectangle such that no cells in one row are closer than K from each other?

19:16 - and the juicy part is that H, W and K are up to 1 billion!

19:19 - one simple part of solution by Onufry: we can forget about H and just take the answer to the power of H and subtract 1 in the end.

19:21 - another idea is that we need to calculate the number modulo 100003 which is a relatively small prime number.

19:25 - people are thinking about the hard problem. Most contestants are working on the medium, still no submissions. Two have opened the hard.

19:26 - dzulgakov submits the medium! I'm not sure what exactly his solution does, but it separates the additive and multipliers, and does some factorials afterwards :) He passed all examples.

19:32 - four people have submitted the medium now. The communal wisdom suggests that if we fix the number r of rooks in one row, then the number of ways is (W-K*(r-1)) choose r. Where do we go from here?

19:34 - and that's where the small prime number calls into play! In order to calculate a choose b modulo p, we can write both a and b in p-ary system, calculate digit-by-digit "choose" numbers, and multiply them. And to calculate those, we can pre-calculate all factorials modulo p and their inverses.

19:39 - so if the number r is relatively small, say, up to 10 million, we can do this. And when it's more than that, it means K is not more than 100 and thus we can do the usual matrix multiplication to find the number of ways (using recurrence f(n)=f(n-1)+f(n-K)).

19:41 - this solution was brought to you by ploh, Onufry, bmerry and jdmetz :)

19:44 - bmerry suggests we can avoid the matrix multiplication by grouping the r's which are the same modulo p and applying the above theorem about the number of combinations to each of those sums.

19:47 - nobody is writing anything that resembles a solution for the hard. Paul has calculated inverses modulo p, gmark has found the answers for small parameters and is staring at them. Unless we're missing a really simple solution, no hard will be solved in this round.

19:50 - izulin and grotmol are still working on their mediums, all others either do nothing or recheck their solutions.

19:52 - I believe there were no submissions in the past 30 minutes. dzhulgakov, Vasyl, syg96 and PaulJefferys have two problems (in this order), tomek, izulin, gmark and grotmol have one problem (in this order). Each of the groups of four is separated by less than 50 points, so any challenge in the first group brings the challenger to the top (and probably to the finals :)).

19:55 - The coding is over. I wonder what is the best strategy for the challenge phase. The medium has expected values so I bet it's pretty hard to fail the systests if you pass examples. Maybe when all numbers are multipliers, or when there are no multipliers at all? For the easy I can only imagine the tricky case when M is more than N*(N-1)/2.

20:01 - tomek tried the maxtest against gmark.

20:03 - the challenge phase is pretty calm, most people take a long time to read one solution.

20:05 - but just one challenge from syg96 or PaulJefferys can change who goes to the finals!

20:10 - a desperate last second challenge by gmark, and that's it. Waiting for the systests!

20:18 - most people agree that probably no solution will fail. More interestingly, Ivan Metelsky has confirmed that our solution for the hard is the expected one!

20:23 - Vasyl's and syg96's mediums have failed. dzhulgakov and Paul go to the finals! Stay tuned tomorrow for the coverage of the finals.

20:27 - here's the reason for the failure of the mediums: if you add up all additive terms in advance, you pass. But if you first multiply them and then add up many numbers, and when the expected answer is ZERO, but the multipliers are big - you're doomed, since small error relative to the product of the multiplier becomes big absolute error. That's a cool bug to fail to :)

TCO 2010 Algorithm Semifinal 2

2010-10-13T23:47:00.047+04:00

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.

TCO 2010

2010-10-13T23:12:00.001+04:00

The bad news (for me :)) is that I've crashed out of TopCoder Open 2010. Somehow got stuck in the easy problem for most of the contest, then somehow decided to open the hard instead of the medium and didn't manage to solve it in time.

Here's the solution for the hard that I had in mind at the end of the contest:

First, iterate over all possible cutoff scores between 0 and 1000, and over lastCutoff (last person to score exactly cutoff points), between 1 and 25.
For each such pair, calculate two arrays using DP:
- What is the probability that out of first x persons, exactly k will advance (that means, score above cutoff, or equal to cutoff if their number is less than or equal to lastCutoff).
- The same for last x persons.
In calculating those arrays, we make use of the fact that all scores are independent, so the DP is quite straightforward; we need to remember that we've already fixed the score of person lastCutoff to cutoff (but this still has probability of 1/n, not 1).
After we've got those arrays, let's calculate the probability of each person a advancing, and being b-th highest ranked person in the finals. This is quite easy now: we need to multiply the probabilities of:
- b-1 people to advance from the first a-1 persons
- k-b-1 people to advance from the last totalPersons-a persons
- a-th person advancing. Here we need to keep in mind that if a is equal to lastCutoff, this should be the fixed 1/n probability since we're only interested in the case where he scores cutoff points.
And finally we accumulate the above probabilities by semifinal number, to get the answer for the problem.

This has complexity of O(1000*25*(25*25+timeOfInnerDP)). The obvious implementation of the inner DP runs in O(25*25*25), processing each state in O(25) operations. 1000*25^4=400M, so this will probably already run in time (since the number of states is not 25*25 but 25*25/2, and so on), but I have the feeling that since the inner DPs are very similar, we can try to run all of them in such a way that each takes just O(25*25). Ideas?. The inner DP actually runs in O(25*25) since each state is processed in O(1), so the total runtime is good enough. I was so close during the round!

The good news is that I'll now have a lot of free time at the TCO and will do live commentary on all 3 remaining Algorithm rounds: Semifinal 2, Wildcard and Finals. I will post the commentary both here and on the TopCoder blog. Stay tuned :)

Can you kill backtracking?

2010-06-11T21:46:00.000+04:00

Here's a problem that has appeared at a recent contest: We are given a 7 times 7 field where some of the cells have numbers between 0 and 8, inclusive, and all remaining cells have dots. We want to find such allocation of exactly 10 stars to the cells with dots, at most one star per cell, so that each cell with a number has exactly that number of stars in its 8 adjacent cells. Moreover, we will only consider such 7 times 7 fields where such allocation of 10 stars exists and is unique.

Can you create a testcase for this problem that will kill backtracking solutions? It seems pretty hard to do at such small field, but it is possible!

Here are the official rules of this challenge: http://killbacktrack.appspot.com/rules.jsp.
And here's the website where you can test your testcases, which also keeps a scoreboard: http://killbacktrack.appspot.com/.

I've got a pretty good testcase, but I don't want to reveal it yet :) Please tell if there's some problem or possible improvement to the website.

Codeforces

2010-02-26T00:14:00.001+03:00

My friends from Saratov are building a new system for hosting contests and beyond. They aim for everything there to be available both in English and in Russian. Today was its second beta-test, which was a contest under ACM ICPC rules for 2 hours with 3 problems. Results: http://codeforces.com/contest/2/standings. Problems: http://codeforces.com/contest/2.

Problem B is very nice. I scratched my head for a long time before getting it, yet the idea is very simple and beautiful. I won't spoil it yet - I hope you'll enjoy solving it as well :)

Problem C turned out to be a tough implementation problem for me (I solved a system of two quadratic equations on 2 variables by eliminating the squares to get a linear equation, substituting one variable from that linear equation into one of quadratic equations, and solving the result. This required a lot of care about precision issues and corner cases, and took an hour). However, I have a feeling that it is doable by some binary/ternary search. Any ideas?

World Finals Recap

2010-02-23T18:10:00.000+03:00

Here're the comments that I've posted during the ACM ICPC 2010 World Finals in Harbin.

Read more

09:08 - Everyone is still waiting on the spectator balcony, teams
are still kept away from the competition room. Problem statements have just
been distributed to team workstations.

09:20 - Still nothing happens. The competition is more likely to start at 10 than at 9:30.

09:23 - Teams are starting to come in.

09:26 - spectators are cheering all the time as the teams take their seats.

09:32 - all teams are at their workstations.

09:35 - Bill promises to start the contest at 10am sharp.

09:39 - if you have questions for me, please post them at http://forums.topcoder.com/?module=Thread&threadID=664073. I'll check that thread from time to time.

09:43 - they're testing the new procedure for photographing the team with their first baloon and with the first baloon for any particular problem.

09:44 - by the way, is the video stream live yet? Maybe it's unnecessary for me to explain what's going on? Please answer at the forum thread above.

09:54 - I've moved to the watching auditorium so I'm watching the same video stream as everybody on the Internet (hopefully) does now.

09:58 - The contest has started!

10:00 - 11 problems. They promised to get the problems to spectators in several minutes.

10:04 - we got the problems. Hopefully they'll be available on the Internet soon as well.

10:06 - problem C is: given a n times m map, with at most w 1-cell-high horizontal walls, find out the number of cells from which you can't get to the top right corner by moving top and right. The coordinates are up to a million, w is up to a thousand. The solution seems obvious - first you compress the coordinates (find all distinct ones) to get at most 1000 distinct ones, and then do a simple DP.

10:11 - problem E is: given a 20 times 9 field with some cells occupied by rocks, find the longest path from top left corner to bottom right corner that doesn't touch itself. 20 times 9 dimensions point us to DP on subsets or something similar. I believe something like that should work: go through the table row-by-row, and keep which cells in the bottom row are connected to which, and which are not occupied at all. Quite hard to implement correctly, but the algorithm is not very complicated.

10:17 - problem G is: given at most 100 points on a plan with distinct x-coordinates, find the shortest cycle that passes through each point exactly once, goes from the leftmost point always to the right until it reaches the rightmost point, then goes always to the left until it gets back to the leftmost point. Additionally, two points are given such that the the path from left to right contains the first point, and the path from right to left contains the second point. This seems to be a very simple DP: after processing the last k points, and with the first path ending in point a and the second path ending in point b, what is the smallest total length to achieve that? This is O(n^2) states, transitions in O(n). We deal with the two special points by forcing the first path to contain the first one, and the second path contain the second one.

10:23 - problem J is: given a rectangle, is it possible to split it by repeatedly splitting it into two parts along a line parallel to a side into several rectangles with the given areas. Maybe we can solve that by trying to do a DP over (rectangle, part sizes multiset)? Since the area of the rectangle should match the sum of part sizes, it seems that the number of states will be reasonably small.

10:24 - Belarusian State University has solved problem J. Many wrong attempts on other problems.

10:29 - Cornell has solved G. I will probably stop commenting on most submissions since the scoreboard is readily available anyway.

10:33 - Problem D has been solved as well. The statement is: given a tree of castles, you need to capture them all. For each castle, you know how many soldiers you need to capture it, and how many will disappear during the process, and how many you should leave in the castle afterwards. It seems that you should just add up the last two numbers. Additionally, you may traverse each road at most twice, which essentially means you should do a normal tree traversal, and the only freedom you have is to choose the order of visiting the children of each vertex in the tree. So the solution seems to be: first, check all possible poits to start the attack - the root of the tree. Then, for each vertex we calculate the best way to capture the subtree rooted at each of its children, and then figure out the best order to visit that subtrees given the total number of soldiers required to capture each subtree X and the total number of soldiers that must be left in that subtree Y. Figuring out the order seems to be a classical problem after that - we should sort them by something like X-Y :)

10:50 - Problem I. When we split the path into four parts, each part has at most 16 cells, so we can just build all possible paths for each part (there're at most 3^16 of them, and in reality much less since we can't self-intersect, can't go outside the labyrinth and should reach the specific cell - so I hope there'll be just several thousands of those). Then, we group the paths by the set of cells they're visiting. Then, we combine the first part and the second part in all possible ways; then we combine the third and the fourth in all possible ways; then we use meet-in-the-middle to combine the complete path (for each subset covered by first two parts, we check if the complement can be covered by the last two parts).

11:12 - Problem B seems to be mostly about accuracy, as a lot of wrong submissions are showing, and many good teams are struggling with it. Generally, the first step of the solution is to separate narrow bars from large bars. To do that, let's take the smallest bar, and then all bars that are less than 50% larger than it should be narrow, and all others should be wide. After that, we should just check all given conditions carefully, and check that the lengths of the all narrow bars fall withing the specified plus-minus 5% of some number, the same for all wide bars.

11:21 - Problem A seems to be a not very complicated simulation. I expect some teams to attempt it in the first two-three hours. There's not much
I can say about the solution - you should just do what's written in the problem
statement, the constraints are reasonably small.

11:23 - the scoreboard is at Shanghai 4, Stanford and Moscow 3, others 2 and less.

11:31 - ACRush correctly suggests that the answer for problem I should be at most about 10000 (even without the constraints for 3 squares, it's in the millions), so pretty much any backtracking-style solution should work in time.

11:41 - Problem H doesn't have constraints, so it's unclear what is
the expected running time. Generally, the approach for this problem should
probably be the same as for the 2-dimensional case of this problem, which is
to go over the vertices from bottom to top, merging the lakes until they reach a point where the water can pour out of the lake. In 3-D this will require a lot of code, like finding the intersection of a horizional plane with the 3-D triangle, but the logical 'pouring' part should be the same as in 2-D case.

11:47 - ACRush points out that in problem B there's no example on the case where the barcode is reversed, which is mentioned only once in the problem statement and is easy to miss. Maybe that's why the teams are struggling with this problem.

11:56 - Problem F. The first step is to notice that since we need to find the total length, we can solve the problem separately for each triangle. Within each triangle, the countour lines are parallel to each other, so we should find one of them and the distance between them, and then carefully find the total length as the sum of two arithmetic progressions. This seems fairly easy to implement, but one has to be careful with the boundaries. There're at most 10K triangles, so we can afford some processing for each of them.

12:04 - Problem K seems to be straightforward from the algorithmic side as well. We try to place it on each side, and just have to carefully calculate
the position of the center of mass and check for stability. The geometric part
is quite standard 3-D routines (for rotating) and 2-D routines (for checking
that projection of the center of mass is at least 0.2 away from the border of the base). The most complicated part seems to be dealing with various possible 'bases' for the paperweight when the figure is not convex.

12:09 - so that's all for my guesses about each of the problems. It seems that there's no really complicated algorithmic background to any of them, and they mostly require careful implementation. Two of them are 3-D geometry, five of them
are DP, the rest are mostly straightforward but tricky implementations.

12:12 - I'm going for lunch now. Please ask your questions on the TopCoder forum thread I've liked to above :)

13:33 - The contest is going, there seem to be 5 problems that are solved by the top teams, and then there are 4 more problems that are solved by at least one team. The contest can still go to any of the top teams.

13:35 - Regarding competing together with ACRush - yeah, if they make an online contest next year, that should be a good thing to try :)

13:42 - They've finally enabled WiFi for coaches!

13:42 - From the 6 "remaining" problems, I think the ordering from the easiest to the hardest is K-F-A-I-E-H.

13:45 - They said they won't be distributing the balloons in the last hour, so I won't have any insider information to share :(

14:00 - So no more updates on accepted/rejected on the scoreboard. They're going to show the submitted runs, though.

14:03 - They told at the ICPC Live stream that SJTU have submitted their code for problem K on problem H, so it was either a mistake or they wanted to mislead other teams.

14:31 - Moscow State University and Warsaw University teams were happy
when they saw the outcomes of their respective runs, so it seems that they have
7 and 6 solved problems now, respectively.

15:16 - Results: Spb IFMO - 22nd. KTH - 12th. Fudan - 11th. Zhongshan - 10th. SpbSU - 9th. Warsaw - 8th. Saratov - 7th. Tsinghua - 6th. Petrozavodsk - 5th. KNU - 4th. Taiwan - 3rd. MSU - 2nd. SJTU - 1st.

16:23 - I've tried to upload a photo of the final scoreboard, but it turns out it is already available at http://uaimages.com/viewer.php?id=383434bord%201-21%20v2.png.

16:24 - Generally, SJTU obviously are very happy with their results, with many other medalists being disappointed they couldn't get better. For example the Bronze medal SpbSU have the same penalty time as the Silver medal Warsaw.

16:25 - Also, it seems that everyone here believes that Ural SU will also get a bronze medal for their 13th place since they're the only team except the first 12 to solve at least 6 problems.

16:25 - That's pretty much it, I think I won't be posting frequent updates here anymore, but may post some more news if I find them.

16:32 - The Moscow State University was trying to solve problem I as did the SJTU team, and both had a complete solution but failed to debug it. Spb IFMO team tried to solve two problems in the end and couldn't get any of them.

17:22 - The awards ceremony is going on. As Oleg Hristenko has rightly pointed out, we are still to announce some regional champions, and the results of the Russian teams that didn't make it to the first page of standings that was posted on the Internet.

18:00 - ICPC Challenge results: 4th place Saratov SU, 3rd place IME-USP, 2nd place Beijing Jiaotong, 1st place U of Canterbury.

18:24 - Tatiana Churina of Novosibirsk SU together with 6 other coaches (I'm being Russia-centric, I know :) got the Coaches' Award.

18:37 - Belarusian SU receives $1000 for getting the first accepted solution.

18:38 - Moscow SU (F), National U of Taiwan (I), NTU KPI (D), Kiev NU (B), Spb IFMO (C), SJTU (E), U of Wroclaw (K), U Maryland (H), Cornell U (G), Fudan U (A), Belarusian SU (J) are recognized for being the first to solve a particular problem.

18:48 - Africa and Middle East champion - British U in Egypt. Latin America champion - UF Pernambuco. North America champion - Stanford U. South Pacific champion - U of Western Australia.

18:54 - the medals are official! 4 gold + 5 silver (including SpbSU) + 4 bronze (including Ural SU). You know the rest, so I won't be posting the teams winning the medals again :)

19:02 - going to the stage with the Moscow SU team :)

ACM ICPC 2010 World Finals

2010-02-05T01:23:00.000+03:00

I hope to be posting updates on the ACM ICPC 2010 World Finals here if I manage to get an internet connection in the Harbin Engineering University: http://77.41.63.3/icpc2010/finals.html.

A difficult problem ten years later

2009-10-26T21:56:00.003+03:00

Here's another Russian IOI camp problem, this time one of the most difficult problems from the 1999 summer camp. Only one contestant was able to solve it back then. I wasn't. How does it look ten years later? I have testdata in case someone wants to actually write the solution :)

You are given eight pairs of numbers, x1, y1, x2, y2, ..., x8, y8. You need to find eight numbers z1, z2, ..., z8 such that (x1,y1,z1), (x2,y2,z2), ..., (x8,y8,z8) are the coordinates of the vertices of a cube with an integer side length, or to report that such numbers do not exist.