GCJ 2011 round 2

Failed abysmally in this round. First got bitten in problem A, when double should be used instead of int. Spent almost one hour and luckily fixed it. Then got panic and spent considerable time on problem B, never get it to go, although it was only one small bug that failed Bsmall. Looked at C and D but didn't have a clue due to panic.

Almost a week later got calm down and worked on those problem offline.

problem A: given a set of nonintersecting walkways and a limit of t seconds to run at speed R, walk speed is S, speed boost at walkway[i] is w[i]. Calculate minimum time to finish passage length X.

Greedy suffices. First consolidate the length not covered by a walkway, call this part w[0], other walkways are w[1] ... w[n]. Now run as much as possible to cover w[0], w[1], ... and do the rest with walking. The only thing that might catch you is cast to double when doing division.

problem B: given a gird with digits, 500x500, find a max square such that after throw away 4 corners, the mass center is at the square center.

This should ring a bell about a standard trick for finding max square with all 1's in a 0/1 matrix, where you can check a square with size s, bottom right corner (r,c) in O(1) time given squares with size s-1 in (r-1,c-1), (r,c-1), (r-1,c). Similar trick here to get you done in O(1) time for each (x,y),s. 500^3 runs in time limit.

Some implementation issues make the problem nasty. You need to keep track of total mass in a square, the sum of mass vectors from size s-1 needs to be adjusted. And you might want to scale the vectors by 2 so that you can deal with integers only. Choice of coordinate is also critical, the best one seems to be below, then (r,c) becomes (x,y) with x=c+1, y=r+1 for bottom right point of the cell.
------------------------>x
|
|
|
\/y

If all these are not enough, you also have to worry about space issue, as store all x,y,s triples would take 500^3 space and this is too much. The good news is that you need only s-2 and s-1 to compute size s. So it is really 500x500x3.

problem B is difficult to get correct. You have to have all the details on paper before coding.

problem C is surprisingly easy, although the problem statement seems a bit daunting. In retrospect there is a good reason that the bottom segment of top 1000 only solved C.

Basically you need to find out, for each prime < N, the maximum k such that p^k <= N. However N=10^12 and there are roughly 10^11 primes then listing them all would be too slow. Fortunately you care about only primes such that k>=2, so you need only primes <= sqrt(N) = 10^6, which is much more manageable. To find k you can use log(N)/log(p), but then you might worry about precision issue since you have introduced double. And there is a good reason to worry because the problem setter is likely to have this in mind and he/she is trying to set it up to get you. I added an assertion to catch this and the assertion did fail. A simple patch is to multiply p^k until you passed N. For this you need fast exp. And that's all for problem C.

problem D. todo.

Now I got some time to deal with problem D. It was the hardest of the four but not that hard once you see it. First it is easy to see you need to do a BFS to find out the number of planets to conquer. Then you need a shortest path with maximum number of neighbors. This looks a bit weird at first as I do not know a standard graph algorithm to do this and it does not look like a flow problem. After a while you see the BFS giving away some structure. The path has to run down level by level. So to solve D-small you can actually enumerate all paths, it is not much worse than (36/6)^6 < 3^12 = 10^6 so it will be fast. One way to do this is to have an L-ary counter to enumerate the paths and compute neighbors of each path. The neighbor sets can be computed using bitset but needs to be a bit careful as 36 bits calls for long long, and my implementation went awry in several places. The last bug was define neighbor[] as int, but it should be LL.

To solve D-large you need some DP strategy, and the crucial observation is that you never have an edge between two nodes with level difference >= 2. So neighbors of level l-2 are fixed as you are dealing with a level l node, and that's how your recurrence was built. To actually implement it probably take quite a bit work.

Done with D-large. For DP you need to keep track of number of neighbors for paths end up with some edge, so dp[i][j] would keep the count of neighbors (or neighbors+path_nodes) for best path end at edge[i][j]. Then node k with edge[j][k] can use all parent and parent of parent to compute dp[j][k].