emacs

From Emacswiki, GNU Emacs 23 has a built-in key combination:
To change font size
C-x C-+ increase and C-x C-- decrease, very convenient

Sprague Grundy theorem

The theorem is about sum of several nim games. A nim game is a pile of stones and in each turn you can take 1 to n stones. The last one makes a move wins.

One pile is trivial, two pile is not hard, what if you have 3 or more piles?

The nim game is solved by the notion of P-position and N-position. A P-position is a configuration, in this case, the number of stones in each pile, such that the previous player wins. An N-position is a configuration that the next player wins.

1. Terminal position is P-position.

2. If a position can go to a P-position, then it is an N-position.

3. If all next positions are N-position, then it is a P-position.

The Bouton's theorem says that a nim game is a P-position iff the nim sum, that is, the xor of all pile size, is 0. Proof by induction. The terminal configuration (0,0,...0) is a P-position. For a general configuration (x1, x2, ..., xn), if its nim-sum is 0, then any move will lead to a configuration with nim-sum nonzero. If its nim-sum is nonzero, then we show that there is a move to a next configuration with nim-sum zero. The move? if x1 + x2 + ... + xn (here + is xor) is nonzero, then there is a leftmost bit that  has odd number of xi with that position bit = 1. To make the sum zero, we have to remove that 1, and complement the sum of other x_j. This can always be done because the complement is smaller than x_i. It turns out the number of moves is exactly the number of x_i with bit = 1 at that position, and there are an odd number of them.

A generalization of the nim game is a graph game with each node having an edge to its successors. Then the P- and N-position is generalized to a much more powerful concept of Sprague-Grundy function, sg(x), defined as the smallest missing nonnegative integer of the set of sg(y) values, where y is a next configuration of x.

The theorem says that x is a P-position iff sg(x) = 0.

We can check the following:

1. sg(x) = 0 when x is a terminal position.

2. If sg(x) = 0, then any move to next configuration results in sg(y) > 0 (because sg(x) cannot be 0 if any sg(y) is 0)

3. If sg(x) > 0, then there must be a next configuration y such that sg(y) = 0 (otherwise sg(x) will be 0)

Now the sum of graph games.

If x is a nim-game consists of n components, x1, ..., xn

sg(x) = sg(x1) + sg(x2) + ... + sg(xn)

again the + is nim-sum, also known as xor.

Why? The proof is very similar to the previous one.

1. terminal configuration, when x has no move, then none of x1, ... xn has a move, and sg(x) = 0

as well as sg(x1) = ... = sg(xn) = 0

2. Now we go from x1, x2, ... xn to a next configuration.

Let b = sg(x1) + sg(x2) + ... + sg(xn)

we are to show two things

i) no next configuration y can have sg(y) = b

ii) for every nonnegative integer a < b, there exists a move of x_i to y_i such that sg(y) = a

First we prove i). Any x_i will move to y_i and we know that sg(x_i) != sg(y_i). Therefore sg(y_i) + sg(x_1) + ... + sg(x_i-1) + sg(y_i) + sg(x_i+1) + ... + sg(x_n) != b.

Second we show that for any a < b, we have a move for some x_i to y_i such that sg(x_1) + ... + sg(y_i) + ... + sg(x_n) = a. The hard part here is that we can move only one x_i.

Since a < b, then we can find some leftmost bit such that b has 1 and a has 0. Let d = a + b, again nim-sum (xor), If our move changes sg(x_i) to sg(x_i) + d, then the resulting configuration, applying inductive hypothesis, will give us sg(x_1) + ... + sg(x_i) + d + ... + sg(x_n) = b + d = a.

Since b has a left bit with 1 while a has that bit as 0, and b is sum of sg(x_i), then there exists some x_i such that sg(x_i) has 1 at that bit too. Since both d and sg(x_i) has that bit as 1, the sum d + sg(x_i) will have that bit as 0. The reason x_i has its SG value being g(x_i) is that x_i has a move to some y_i such that sg(y_i) = t for every t = 0, ... g(x_i) -1. So we must have a move from x_i to y_i such that sg(y_i) = d + g(x_i). And we are done.

The key in this proof is to keep in mind that the reason x_i has value sg(x_i) implies it has a move to y_i such that sg(y_i) = a for every a < sg(x_i). Also we are looking for a way to reset one bit to zero. The rest is just induction.

The Sprague-Grundy function is very powerful and was able to handle a large range of sum of impartial games.

The above was from the UCLA notes
http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf
and motivated by
http://codeforces.ru/contest/256/problem/C?locale=en

camel water, gas to market, elephant banana problem

This problem is probably of folk lore and has gone under several names and settings, basic structure is this:

You have 3000 bananas and need to transport from A to B, the distance is 1000 units and you have 1 elephant. The elephant has a capacity of 1000 bananas and to move 1 unit, the elephant will consume 1 banana. The question is, what is the maximum banana you can transport from A to B, using that elephant? Notice that the elephant may deposit bananas along the way from A to B at any point, not necessarily integral points, for example, it could deposit 3 bananas at a distance of 100/3 units from point A.

Many of us know the solution, but I haven't seen a proof yet.

First the solution:
while the remaining bananas are more than the capacity, you calculate the next point that the elephant can have a reduced number of trips. In the given instance, you need at least 5 one-way trips to move all bananas by 1 unit of distance. The number of trips will reduce when the remaining bananas drops to 2000, then the elephant needs 3 one-way trips, and when the bananas drop to 1000, the elephant can just carry all of them and move to B.

It is in fact an optimal strategy, but why?

Our goal is to show that any proposed optimal strategy cannot beat our strategy, but there are so many ways to move and a strategy can be an arbitrary combination of any of those moves, as long as you have enough bananas.

First observation: Any optimal strategy has to use all 3000 bananas. This is almost obvious since we can always pad a strategy by inserting some preliminary moves to waste all bananas it left at point A.

Now we need a second assumption. Let p be a point between A and B. We fix a proposed optimal strategy S. We say that an event occurred at point p in strategy S if an elephant ever dropped some bananas at point p or ever turned around at point p. We use p0 to denote the smallest p with an event. Now we assume p0 is at finite distance from A. (I am not sure how to justify this but it seems natural for moving an infinitesimally small distance from A does not make much sense).

OK, since our nearest event occur at p0, we can interpret strategy S as moving all bananas to p0, with a reduced number of bananas, and then follow the other moves. This does not change the ultimate gain of strategy S. Suppose the distance from p0 to B is L1, and the number of bananas remain is B1, it is possible to show that our strategy will leave at least B1 bananas at p0. Since having more bananas cannot hurt, we can recursively reduce the instance from (L, B) to (L1, B1), then to (L2, B2), up to the point that the remain Bk is no more than 1000, and then it is obvious that our strategy is optimal as the elephant should take all bananas and make one move to B. This will be our base case. The (L, B) pairs are strictly decreasing by a finite amount every time, because our assumption, then we have an inductive flavor proof by reducing the instance!

It feels right to me, although a lot more work needs to be done to formalize it and justify all details.

CF 156 div 1

A: Given a sequence of 4000 integers, find the longest sequence with p, p - q,  p, p-q, p, p-q, ...
1 <= a[i] <= 10^6

You need O(n^2) algorithm. If you check all pairs of (i,j) then extend to the rest of the sequence, it is O(n^3). However, if you try to do dp without checking the whole sequence for each (i,j) pair, you need to put a[i] into your state, however the max a[i] can be 10^6 and an array with a[4000][10^6] is too big. The rescue is that you don't have to use the raw a[i] value, you only have 4000 distinct values and you can map them into 1, 2, ..., 4000. That's it.

To map values, an easy way is to use stl map
or you can make a copy of a[] to b[], then sort and unique b[],
then a[i] would be the index of a[i] in b[] using binary search, or stl lower_bound.

The actual dp needs two arrays, next[i][k] and dp[i][k]
next[i][k] is the next pos in i+1..n-1 with value = k
dp[i][k] is the length of best subseq ending at pos=i and prev element is equal to k.

for i=0 to n-1
for k=0 to n-1 // values mapped to 0 .. n-1 since at most n distinct elements
  dp[i][k] = 1

for i=0 to n-1
for j=i+1 to n-1
  if next[i][a[j]] not init, then next[i][a[j]] = j

for i=0 to n-1
for k=0 to n-1
  j = next[i][k]  // look for next stop
  if j is a valid index, then update dp[j][a[i]] with dp[i][k] + 1 if this is a longer subseq

// another dp is to use dp[i][k] as length of best subseq starting at i and with next value = k
for i = n-1 to 0
for j = i+1 to n-1
  dp[i][a[j]] = 2
  nxt = next[j][a[i]]
  if nxt is a valid index
    dp[i][a[j]] = dp[j][nxt] + 1

// this avoids taking max and likely faster