One Possible Implementation of the Generic Push-Relabel Algorithm

The book said that we can select an applicable operation in O(1) time, and use O(V) and O(1) time for relabel and push operation respectively.

First note that all operations are performed on overflowing vertices other than s or t. We may store all these vertices in a data structure and when that structure becomes empty, the algorithm terminates. When nonempty, pick an arbitrary vertex u from it. If there is some admissible edge (u,v)(that is, (u,v) is in the residual network and h[u]=h[v]+1), a push operation is applicable. Otherwise, a relabel operation is applicable.

So we may wish to maintain a list of admissible edges for every vertex. Every time, either a push or relabel operation may be applicable depending on whether the corresponding list is empty or not. After a push, the only possible influence on these lists is that (u, v) has to be removed from the list corresponding to u after a saturating push. If we simply associate every edge a pointer to the nodes in these lists, the removal can be done in O(1) time. Each edge (u,v) may appear in these lists at most once, for h[u]=h[v]+1 and h[v]=h[u]+1 cannot hold at the same time.

But after a relabel operation on u, some edges (u,v) has to be inserted into the list corresponding to u, and all edges (v,u) appearing in other lists has to be removed. The insertion is simple. But we have to check the lists for every other vertex in order to remove edges ending at u, thus resulting in O(E) time complexity. The solution is to use orthogonal lists. Intuitively, all admissible edges leaving u are on the horizontal line, while those entering u are on the vertical line. Now, the insertion and removal operations take time proportional to the out degrees and in degrees of vertex u. A single operation of both types is now a little bit more complicated, but requires only O(1) time.

Finally, a simple list suffices for the data structure mentioned in the second paragraph. Every time, pick the vertex at the end of that list. Relabel doesn't change the flow of any vertex, so no updates are necessary. After a push from u to v, remove u if it is no longer overflowing and insert v if its flow is 0 previously.

Now, the generic push-relabel algorithm is implemented using a total time of O(V²E).

The Initialization of the Generic Push-Relabel Algorithm

When we apply the generic push-relabel algorithm, we first label s as |V| and t as 0, and all edges starting from s are pushed in as many units of flow as possible, i.e they are saturated. But why these operations are necessary and reasonable is not stated explicitly.

What if we label s and t with different values? The difference between h[s] and h[t], h[s]-h[t], must be no smaller than |V|, for otherwise the statement that there is no path from s to t in the residual network never holds. And when the preflow becomes a flow, it is not necessarily a maximum flow since there may be augmenting paths. If s and t are labeled with greater values other than |V| and 0, the bounds on the number of relabel, saturating push and thus non-saturating push will become higher. Intuitively, there must be redundant relabel operations before extra flows are pushed to t or back to s since h[s] and h[t] become greater, and during that process, extra push operations between vertices other than s and t occur.

Suppose for some neighbor u of s, we initially push less flow into edge (s,u) than c(s,u). Then (s,u) is in the residual network. But h[s]=|V|>=2>h[u]+1=0+1=1, i.e. h is no longer a valid height function.

SRM522 Div1 Level1 250 Problem

Given a board consisting of n(n>=2) cells, each marked with either an 'A' or 'B', Alice and Bob alternatively place coins on some continuous empty cells, with the restriction that at least one cell must be left empty. When there is only one cell left, Alice wins if that cell is marked with 'A' and Bob wins otherwise.

First of all, if at least one end is marked with an 'A', then Alice wins. Without loss of generality, suppose the board is of the form "A??...?"('?' means empty cells marked with 'A' or 'B' arbitrarily). Alice can obtain "ACC...C"('C' means covered by a coin) in one step and win.

Then what if the board is of the form "B??...?B"?
If Alice covered either end with a coin, again without loss of generality, the board becomes "CC...CB" or "CC...C??..?B". Bob wins immediately for the former, by covering all other empty cells except the rightmost 'B' for the latter. So Alice would have to choose "B??...?CC...C??...?B" if she wanted to win.
Now let's consider a simpler situation, "B??...?CC...CB". (I)If it is now Bob's turn, he only needs to cover all the empty cells on the left and wins. (II)If it is now Alice's turn, she has up to four choices. If she choose to cover the rightmost 'B' or either end of the empty cells on the left, Bob can obviously win. Then again she has to choose to make the board of the form "B??...?CC...C??...?CC...CB". If Bob covers all empty cells of the second interval, then we reach the same configuration except that the number of empty cells decreases. So we can prove by induction that no matter whose turn is it, the winner would be Bob if the board is of the form "B??...?CC...CB".
So let's return to "B??...?CC...C??...?B". If the second interval is empty, the it corresponds to (I). Otherwise, Bob could cover all empty cells on the right except the rightmost 'B', and now it corresponds to (II). Either way, Bob wins.

So all we have to do is to check the two cells on both ends.

I code a bit mask DP during the contest. Finding patterns and proving them is still a hard task for me. Need more exercise.

Why recursive languages are NOT closed under homomorphism

Refer to this slide.

First let's consider a much simpler problem, inverse homomorphism, in which w is in L' if and only h(w) is in L. We can just apply h to w and let the TM accepting L run with input h(w). So L' is recursively enumerable(resp. recursive) if L is recursively enumerable(resp. recursive).

Now we'll attack homomorphism, in which w is in L' if and only if for some x, both h(x)=w and x being in L hold.

For recursively enumerable languages, the slide say that we can design an NTM M to take as input w, guess an x such that h(x)=w and simulate M₁ on x(suppose L=L(M₁)). I will give a detailed sketch on how M behaves. It
0)sets l to 1
1)guesses one x of length l
2)if there is such an x invokes M₁ otherwise goes to 4)
3)if M₁ accepts so would M otherwise goes to 4)
4)increases l by 1 and goes back to 1)
So if L is recursively enumerable, so is L'.
And of course we can use a DTM that generates each x in a systematic way.

Now what about recursive languages? Even though L is recursive, the above process may not halt since there may be infinitely many x'es such that h(x)=w but none of these x'es is in L.

At last, I will give an example in which for every w, there are infinitely many x'es such that h(x)=w. Consider the function h: N*N->N in which h(a,b)=a. Of course, {x|h(x)=w}=N for every w in N. And N*N is countable, as is explained in this slide.

P.S Since every TM(either deterministic or nondeterministic) has a corresponding encoding, it is possible to "design" different NTM's(as sub-routine) for different input strings, as is the "break" operation in the discussion of concatenation. Even though potential break positions are infinite, for every specific string they are finite.

P.S This page gives a concrete example for exercise 9.2.6(e).

SRM502 Div1 Level2 500 Problem

We define the relation problem[i]<problem[j] if pointsPerMinute[i]*requiredTime[j]>pointsPerMinute[j]*requiredTime[i]. This is a total order, as is explained in this thread.

If two adjacent problems, say i and i+1, satisfies that problem[i+1]<problem[i]. Then by swapping them, we get a better solution, for doing so doesn't affect the points of all other problems, increases problem[i+1]'s point by pointsPerMinute[i+1]*requiredTime[i] and decreases problem[i]'s point by pointsPerMinute[i]*requiredTime[i+1]. By definition, the former is larger.

Many people figure out at this point that the best solution must be exactly the one satisfying problem[i]<=problem[i+1] for all i in the range [0,n-2], e.g. this post by wywcgs. I used to just believe so after a USACO contest, but now I'm not that convinced. So I do some careful analysis.(I hope for an intuitive explanation.)

Lemma 1. If S is not a sorted sequence, then there must be at least one pair of adjacent elements such that S[i]>S[i+1].
Lemma 2. For every possible sequence S, we can get the sorted sequence by repeatedly swapping adjacent pairs such that S[i]>S[i+1]. We know in linear algebra such adjacent swapping reduces the inversion number by exactly 1.(I'm eagerly looking forward to a more elegant explanation.)
Theorem 3. The sorted sequence is the best solution. This comes directly from the fact that all the swapping operations in Lemma 2 increase the points.

Note that we may not want to include some problems, since their points may become negative. But every time we do decide to include a problem, it must be placed at the end if we consider the problems in order. So the optimal substructure and independent substructure properties are reserved. The recurrence relation becomes obvious as in the classic 0-1 knapsack problem: best[i][j]=max(best[i-1][j], best[i-1][j-requiredTime[i]]+maxPoint[i]-j*pointsPerMinute[i]). Here i means we have so far considered problem [0, i] and j means the last problem gets solved at time j.

P.S. See Petr's perfect code here.

Finding one good chip using less than n pairwise tests: solution to CLRS problem 4-6

Part (b) says that when there are more than half good chips and your goal is to find out ONE of them, you can use divide-and-conquer techniques and floor(n/2) pairwise tests can reduce the problem size to nearly half.

We notice that in a test, when "Good-Good" is reported, the two must be both good or both bad. Otherwise, they cannot be both good. So we'll choose any one from such groups and ignore all other groups.

When the number of chips is even, the situation is quite straightforward.  Consider the extreme condition in which there are (n-1) bad chips and (n+1) good ones. The number of groups in which both two are good must be larger than the groups in which both two are bad. So after the "divide", the property that there are more than half good chips is preserved.

When the number of chips is odd, the problem becomes a little bit intricate. Again consider the extreme condition in which there are n bad chips and (n+1) good ones. We must take out a chip, namely X, and perform pairwise tests for the others. When X is bad, it is OK. But what if X is good? We can easily see that after the "divide", the number of good ones must be no smaller than the number of bad ones no matter what you take out. So when there are odd number of chips after the "divide", we can conclude that the property is actually preserved(Note that if there is exactly 1 left, then it must be good) and we can simply ignore X. Otherwise, we cannot tell whether X is good or bad, but from part (a) we know that when there are equal numbers of good chips and bad chips, we may not be able to distinguish any one as good if all bad chips can conspire. So just keep this unknown chip and proceed further. If the one taken out is good and all bad ones do conspire, at last we know X is in fact good. Otherwise, we will find another good one.

This post gives a more detailed explanation in Chinese.

Finding the second smallest element: solution to CLRS exercise9.1-1

The statement says that this can be achieved using exactly n+ceiling(lg(n))-2 comparisons in the worst case. I thought for a long time but didn't get the right idea.
This post by n1b-algo gives a detailed explanation.
Its main idea is to build a comparison tree and check the elements "knocked out" by the smallest one afterwards. The smallest element is placed at the root, and it beats exactly one element at each level except the root, so there are ceiling(lg(n))-1 elements to check in total, since the binary tree with n leaves at the bottom level and without any other leaves has ceiling(lg(n)) levels excluding the root.