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.
No comments:
Post a Comment