SRM 511

div 2
p500 Zoo
The problem is easier after reading the examples. There is a feasible solution iff we have
2's followed by 1's followed by 0's. Some parts might be missing. Assuming it is k 2's and some nonzero 1's, then it is 2^(k+1).

p1000 FiveHundredEleven
A naive solution is to use to keep track of the state of the same and recursion from initial state. But there are 2^50 sets of cards so need to be more clever.

The first observation is that cards that are masked by bitset are equivalent, so we only need the count of them. Play any one of them is the same as play another.

The second observation is that there is no need to keep track of subsets already used. The reason is that for cards not masked, they must not have been used. So we can find them using bitset. For cards that are masked, we only care about their numbers. So remember the number of cards already used suffices.

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].

no more firefox crash

After install latest cups package for fedora, firefox no longer crashes when attempting to print a webpage. Along the way installed a bunch of debuginfo packages for cups and pulseaudio.

After reading some debugging book, almost attempted to use gdb to figure out what went wrong when trying to print a webpage. Now it was fixed by updating cups.

bash and gentoo

Arguably the best bash tutorial that I have ever seen. Concise but touched very advanced usage. Excellent examples.

http://www.ibm.com/developerworks/library/l-bash3.html

Also Gentoo seems to be worth exploring.

http://www.gentoo.org/doc/en/gentoo-x86-quickinstall.xml

book: how to solve it by computer

How to Solve it by computer.
By R. G. Dromey, 1982

I forgot how I get introduced into this book but this is the book that I wish I could read the first day when I started learn programming. Many fundamental but important techniques and guidelines are introduced via examples, with ingredients taken from almost every area in computer science, algorithm and data structure, formal verification. Very fine details are mentioned. Nowhere else have I seen these things.

One example is on Fibonacci numbers:
f(0) = 1, f(1) = 1, f(n) = f(n-1) + f(n-2)

Everybody knows how to compute the n-th fibo number using a loop running n times, but can you do it in O(log n) time?

I have a terrible memory of this problem because this was used in google codejam 2008 round 1A, and I didn't solve it. Neither can I read other people's solutions because I do not understand the magic numbers they use.

Now there are at least two ways to do it. Both using the idea of fast exponentiation.

1. Matrix representation. (I learned this from Dr. Chrobak in his Advanced Algorithm class).

/        \      /      \   /        \
| f(n)   |      | 1  1 |   | f(n-1) |
| f(n-1) |  =   | 1  0 |   | f(n-2) |
\        /      \     /    \        /

To compute n-th fibo number you just need to fast exponentiate the matrix.

2. Using the identity f(2n) = f(n)^2 + f(n-1)^2.
To derive it, observe this:

f(2n) = f(2n-1) + f(2n-2) = f(1)f(2n-1) + f(0)f(2n-2)
f(2n) = f(2n-2) + f(2n-3) + f(2n-2) = 2f(2n-2) + f(2n-3) = f(2)f(2n-2) + f(1)f(2n-3)
See the pattern?
f(2n) = f(i)f(2n-i) + f(i-1)f(2n-2-(i-1)) (*)
Now take i=n, you have the identity. You can prove (*) by induction.

AMPL the modeling language

Very natural to set up models which deals with large scale optimization problems. Close to algebraic notation.

Students version comes for free but limit is 300 variables and 300 constraints.

[lyan@localhost LPSolver]$ cat dualfit.mod
param k;
var f >= 0;
var d {1..k} >= 0;
var a {1..k} >= 0;
var x {1..k,1..k} >= 0;

maximize Dual: sum {j in 1..k} a[j];
subject to deno: f + sum {j in 1..k} d[j] <= 1;
subject to fac {j in 1..k}: sum {i in j..k} x[i,j] <= f;
subject to maxzero {j in 1..k, i in j..k}: x[i,j] >= a[j] - d[i];
subject to trig {j in 1..k, i in 1..j}: a[j] <= a[i] + d[i] + d[j];

[lyan@localhost LPSolver]$ cat dualfit.dat
param k := 20;

[lyan@localhost LPSolver]$ cat runk.sh
#!/bin/bash
if [ $# != 3 ]
then
echo "Usage: runk "
exit 1;
fi

START=$1
END=$2
OUTFILE=$3
if [ -f $OUTFILE ]
then
rm $OUTFILE
fi

for i in `seq $START $END`
do
echo "param k := $i;" > dualfit.dat
cat dualfit.dat >> $OUTFILE
ampl dualfit.run >> $OUTFILE
done

how to check webpage update time

In the address bar, type
javascript:alert(document.lastModified)