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)

ipe: the diagram kit for latex

Ipe is a nice kit for drawing diagrams for latex. It exports both as eps and pdf. You can then includegraphics to get the diagram. The nice thing is that it allows you to use latex command to write math symbols and formulae.

Installation for Debian/ubuntu is straightforward, a couple of apt-get. However if you do not have root previlige and you are using Redhat system, here is what you can do:

fontconfig: http://www.fontconfig.org/release
Install the latest version, I use 2.8.0 and installed to /opt

Qt: http://get.qt.nokia.com/qt/source/qt-everywhere-opensource-src-4.6.3.tar.gz
in projects.pro, add a line
LIBS += /opt
so that qt will find your fontconfig before hits the old one in /usr/
compile Qt take a while.

LUA: put in /opt as well.

Here is my change for config.mak under ipe/src
LUA_CFLAGS ?= -I/opt/include
LUA_LIBS ?= -L/opt/lib -llua
QT_CFLAGS ?= $(shell pkg-config --cflags QtGui QtCore)
QT_LIBS ?= $(shell pkg-config --libs QtGui QtCore)

MOC ?= moc

there might be build errors when you type 'make'. Just go to the source file and comment out offending lines, or enable some lines that says 'Alternative'

Finally, the ipe script to run ipe, the PIEANCIENTPDFTEX is necessary if your pdflatex is older than 1.4

$ cat ~/bin/ipe
============================
#!/bin/bash
export LD_LIBRARY_PATH="/opt/lib:/opt/ipe7/lib:$LD_LIBRARY_PATH"
export IPEANCIENTPDFTEX=1
/opt/ipe7/bin/ipe $* &
============================

palindrome

Given a string, find the shortest prefix that is an even palindrome, in linear time.

The problem can be seen as asking for a minimum overlap of S and S^R. Then we can slide S^R to match a prefix of S by using Knuth-Morris-Pratt's algorithm to achieve O(n) time.

GCJ 10 Round 3 Problem A De-RNG-ed

A problem looks simple but hard to get correct.

1. Observations: for k=1 and k=2, and whether S[0] == S[1]

2. Now the formula becomes clear,

S[0]*A + B = S[1] mod P
S[1]*A + B = S[2] mod P

A = (S[2]-S[1])*(S[1]-S[0])^-1 mod P
B = S[1] - S[0]*A

3. How to compute multiplicative inverse?
3.1 Method 1, extended Euclidean Algorithm. The easiest impl is to use recursion

pair gcd(int a, int p)
{
if (p%a==0) return make_pair(1,0);
pair pp = gcd(p%a,a);
int aa = pp.first; int bb = pp.second;
return make_pair(bb-aa*(p/a) , aa);
}

3.2 Method 2, use the fact that a^p = a mod p for prime p
inverse is then mypow(a,p-2)
int mypow(int a, int d, int p)
{
int ret = 1;
while(d)
{
if (d&1) ret = (ret*a)%p;
a = (a*a)%p;
}
return ret;
}

4. Watch integer overflow. Once it gets to 10^6, square it gets 10^12, which is more than MAX_INT.

5. When round a negative number to 0 to P-1, use a = a%p, if (a < 0) a+=p;
a while loop like while(a < 0) a += p; kills you, the running time goes up from a few seconds to 13 min.

6. Precompute primes using naive sieve.

7. Optional, may use binary search to find first prime to work on, but no significant saving in time. Makes no difference in this problem in terms of time.