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
Sunday, December 30, 2012
Friday, December 21, 2012
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
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
Wednesday, December 19, 2012
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.
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.
Tuesday, December 18, 2012
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
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
Friday, November 16, 2012
Friday, October 19, 2012
Wednesday, October 17, 2012
degree sequence
Given a sequence of n numbers, d1 <= d2 <= d3 <= ... <= dn
find a graph with such degree or assert that it is not a valid sequence.
The hakimi algorithm constructs such a graph recursively. It finds a graph for
d2-1, d3-1, ... dk-1, d_k+1, ... d_n where k = d1 + 1, then add d1 to the graph connecting to each of d2 to d_k.
Obviously the degree sequence thus constructed is a valid graph, but why if the algorithm fails to find a graph, then no such graph exists.
The theorem shows that d_i sequence is a degree sequence iff the c_i sequence by removing d1 and subtract 1 from each of d2 to d_k is a degree sequence.
Sufficiency is easy, since we just add d1 to the c_i graph.
To see necessity, we first consider an easy case, when the d_i graph has d1 connected to d2 up to d_k and none beyond that. What if this is not true, then we can swap in some d_j with j > k with d_i for i in [2,k] while keeping all d_i intact. First because node 1 has deg = d1, it must have a neighbor beyond d_k, call it x, and in [2..k] there is a node that is not adjacent to d1, call it y. Now y has degree at least d1, and it is not connected to node[1], so y must have 2 or more neighbors in [k+1..n]. As a result there exists some node z != x such that (y,z) is an edge and we also have (1,x) is an edge. Then we swap the two edges by set (1,y) (x,z) to edges and remove (1,x), (y,z) from E. This does not change the d_i sequence yet we have one more neighbor of node[1] in [2..k]. So we will eventually have all node[1]'s neighbor in [2..k] and we are back to the easy case.
find a graph with such degree or assert that it is not a valid sequence.
The hakimi algorithm constructs such a graph recursively. It finds a graph for
d2-1, d3-1, ... dk-1, d_k+1, ... d_n where k = d1 + 1, then add d1 to the graph connecting to each of d2 to d_k.
Obviously the degree sequence thus constructed is a valid graph, but why if the algorithm fails to find a graph, then no such graph exists.
The theorem shows that d_i sequence is a degree sequence iff the c_i sequence by removing d1 and subtract 1 from each of d2 to d_k is a degree sequence.
Sufficiency is easy, since we just add d1 to the c_i graph.
To see necessity, we first consider an easy case, when the d_i graph has d1 connected to d2 up to d_k and none beyond that. What if this is not true, then we can swap in some d_j with j > k with d_i for i in [2,k] while keeping all d_i intact. First because node 1 has deg = d1, it must have a neighbor beyond d_k, call it x, and in [2..k] there is a node that is not adjacent to d1, call it y. Now y has degree at least d1, and it is not connected to node[1], so y must have 2 or more neighbors in [k+1..n]. As a result there exists some node z != x such that (y,z) is an edge and we also have (1,x) is an edge. Then we swap the two edges by set (1,y) (x,z) to edges and remove (1,x), (y,z) from E. This does not change the d_i sequence yet we have one more neighbor of node[1] in [2..k]. So we will eventually have all node[1]'s neighbor in [2..k] and we are back to the easy case.
Tuesday, October 16, 2012
CF 145 div2
For some time I thought I could do div1 A and B, and in div2 I can usually finish everything except E. Now I am in a situation that I can do only A,B for div2. Haven't been in timed competition for a while.
Last night was CF145 with ICPC rule. It started at midnight so I was tired from the beginning. Finished 4 out of 8, although the top scorer finished all 8 within 1.5h. The contest length was 3.5h. I spent 2.5h then do not see how to solve the rest.
B,C,D,E were simple problems that you just need to implement the right thing.
A, F, G, H I finished today.
A: You want to place students into desks such that the two sharing a desk cannot have id +1 or -1, and they cannot be RL. This was easy, just pair i, i+n/2. Another way would be i, i+2. If we have RL, we change it to LR.
F: DP. try to paint each block left to right, for each one, try R or G and keep track of current cost.
G: If you work out n=2, 4, 8, there is a pattern.
H: Merge the block of zero and one, then check the number of blocks in the merged sequence. The number of flips is the number of blocks, or minus one if the bottom is zero already.
Last night was CF145 with ICPC rule. It started at midnight so I was tired from the beginning. Finished 4 out of 8, although the top scorer finished all 8 within 1.5h. The contest length was 3.5h. I spent 2.5h then do not see how to solve the rest.
B,C,D,E were simple problems that you just need to implement the right thing.
A, F, G, H I finished today.
A: You want to place students into desks such that the two sharing a desk cannot have id +1 or -1, and they cannot be RL. This was easy, just pair i, i+n/2. Another way would be i, i+2. If we have RL, we change it to LR.
F: DP. try to paint each block left to right, for each one, try R or G and keep track of current cost.
G: If you work out n=2, 4, 8, there is a pattern.
H: Merge the block of zero and one, then check the number of blocks in the merged sequence. The number of flips is the number of blocks, or minus one if the bottom is zero already.
Friday, October 12, 2012
windows 7 update installation
After acquired a lenovo T430, I got 32 Windows 7 updates ready to install. Then followed by several frustrated rounds of download, install, restart, fail to configure, revert.
To be safe on other issues, I even wiped out the linux partition and restored boot loader to windows loader. Still...
The solution that works for me was from answers.microsoft.com
KB2647753 needs to be manually downloaded and installed, then use windows update to automate the other updates.
Although the error code says updates need to write to certain system files and one suggestion by microsoft is to restart without starting some start-up programs. That approach did not work for me.
Finally I got all updates installed. The thing is, even if you do not care your system's security or stability, windows is so friendly that it will keep remind you every 4 hours, which is annoying.
To be safe on other issues, I even wiped out the linux partition and restored boot loader to windows loader. Still...
The solution that works for me was from answers.microsoft.com
KB2647753 needs to be manually downloaded and installed, then use windows update to automate the other updates.
Although the error code says updates need to write to certain system files and one suggestion by microsoft is to restart without starting some start-up programs. That approach did not work for me.
Finally I got all updates installed. The thing is, even if you do not care your system's security or stability, windows is so friendly that it will keep remind you every 4 hours, which is annoying.
Thursday, October 4, 2012
a problem about deque, double ended queue
The easier version:
A sequence of push with 1, 2, 3, ..., N is done, each push could be either push_back or push_front. Given the resulting sequence of numbers, can you find a sequence of push ops that generates such a sequence?
Solution: Obviously N can only be the first or the last in the resulting sequence and you can recurse from there.
Slightly harder version:
You have push_front, push_back and pop_front, can some sequence of (1, 2, ..., N) be realized?
Solution: Consider the time you push in N, either front or back. This is the last push, and the rest have to be pop_back. Now if you push N in front, then N must be popped last, so N must appear last in the display sequence. The other case is that you push N back, then all you have are pops and you can only pop_back, so N must be push_back, then immediately pop_back.
Case 1: N is push_front, then it must be the last item in the sequence is N. So we can work with the rest 1,...,N-1 now.
Case 2: N is push_back, then it must be the next op is pop_back, as there are no more push. And the item got popped must be N. Now consider N-1, if N-1 is a push_front, then N-1 must appear in the end of the sequence removing N, else N-1 is push_back and it must then be popped back immediately. In that case N-1 must be to the left of N.
Now we are almost there. Look at the sequence, locate N. From the pos where N appears, to the end, it must be increasing, because they are all push_front. (if not they will appear to the left of N) , then they got pop_back.
Then we locate N-1, if it is to the right of N, then it must be the last. Else it is to the left of N, then the sequence from N-1 to the right, excluding N, must be increasing, for the same reason.
The algorithm:
mark[0..N-1] = 0
last = N (the pos where N could occur if it is push_front, hence popped last)
pos = N
for i = N down to 1 {
if (s[--last] == i) then { mark[last] = 1; }
else while (--pos >= 0) { if (s[pos] == i) break; } // implicitly skipped mark[pos] = 1
if (pos < 0) break;
else mark[pos] = 1;
}
// All pos from 0 to N-1 must have been marked for a feasible sequence
assert( all mark[0..N-1] are 1);
The harder version:
In addition to push, you now have pop, and there are four operations: push_back, push_front, pop_back, pop_front. The push still follows the order of 1, 2, 3, ..., N as the numbers they push, although each could either be push_back or push_front. The pops will interleave the pushes and in the end all numbers pushed will get popped. So you get a sequence which is a permutation of 1,...,N. The question asks you to reconstruct an op sequence to realize the output of the pops.
It seems for all N<=4, any permutation can be realized. For N=5, seems 5 1 3 2 4 cannot be realized. The reason?
When 5 is popped, all 1, 2, 3, 4 have already in the deque, the only thing that can happen afterwards are pops, no push any more. 5 is either the first or the last, w.l.o.g. we can assume it is first. Then 1 is either second or last, suppose it is second, then there is nothing in between 1 and 5, so 2, 3, 4 are to the right of 1. Then we can only have 1, 2, 3, 4, but no pop can give 1, 3, 2, 4. The case that 1 is last is similar, you have 4 3 2 1 and cannot give 1 3 2 4 either.
I think I have some idea about the algorithm now.
First the output of N marks the end of push, and the rest have to be pop. To be a valid pop cluster, the cluster has to have min element as its left or right edge, and the rest recurse. Before that, we have seen a sequence of output smaller than N, and the first one must be a left or right element, the next one, if larger, can be adjacent to it predecessor, else it is smaller and has to take an opposite edge. Along this line, we somehow could reconstruct a sequence by ignoring all pops, and this might help us find the pushes, then the pops.
A sequence of push with 1, 2, 3, ..., N is done, each push could be either push_back or push_front. Given the resulting sequence of numbers, can you find a sequence of push ops that generates such a sequence?
Solution: Obviously N can only be the first or the last in the resulting sequence and you can recurse from there.
Slightly harder version:
You have push_front, push_back and pop_front, can some sequence of (1, 2, ..., N) be realized?
Solution: Consider the time you push in N, either front or back. This is the last push, and the rest have to be pop_back. Now if you push N in front, then N must be popped last, so N must appear last in the display sequence. The other case is that you push N back, then all you have are pops and you can only pop_back, so N must be push_back, then immediately pop_back.
Case 1: N is push_front, then it must be the last item in the sequence is N. So we can work with the rest 1,...,N-1 now.
Case 2: N is push_back, then it must be the next op is pop_back, as there are no more push. And the item got popped must be N. Now consider N-1, if N-1 is a push_front, then N-1 must appear in the end of the sequence removing N, else N-1 is push_back and it must then be popped back immediately. In that case N-1 must be to the left of N.
Now we are almost there. Look at the sequence, locate N. From the pos where N appears, to the end, it must be increasing, because they are all push_front. (if not they will appear to the left of N) , then they got pop_back.
Then we locate N-1, if it is to the right of N, then it must be the last. Else it is to the left of N, then the sequence from N-1 to the right, excluding N, must be increasing, for the same reason.
The algorithm:
mark[0..N-1] = 0
last = N (the pos where N could occur if it is push_front, hence popped last)
pos = N
for i = N down to 1 {
if (s[--last] == i) then { mark[last] = 1; }
else while (--pos >= 0) { if (s[pos] == i) break; } // implicitly skipped mark[pos] = 1
if (pos < 0) break;
else mark[pos] = 1;
}
// All pos from 0 to N-1 must have been marked for a feasible sequence
assert( all mark[0..N-1] are 1);
The harder version:
In addition to push, you now have pop, and there are four operations: push_back, push_front, pop_back, pop_front. The push still follows the order of 1, 2, 3, ..., N as the numbers they push, although each could either be push_back or push_front. The pops will interleave the pushes and in the end all numbers pushed will get popped. So you get a sequence which is a permutation of 1,...,N. The question asks you to reconstruct an op sequence to realize the output of the pops.
It seems for all N<=4, any permutation can be realized. For N=5, seems 5 1 3 2 4 cannot be realized. The reason?
When 5 is popped, all 1, 2, 3, 4 have already in the deque, the only thing that can happen afterwards are pops, no push any more. 5 is either the first or the last, w.l.o.g. we can assume it is first. Then 1 is either second or last, suppose it is second, then there is nothing in between 1 and 5, so 2, 3, 4 are to the right of 1. Then we can only have 1, 2, 3, 4, but no pop can give 1, 3, 2, 4. The case that 1 is last is similar, you have 4 3 2 1 and cannot give 1 3 2 4 either.
I think I have some idea about the algorithm now.
First the output of N marks the end of push, and the rest have to be pop. To be a valid pop cluster, the cluster has to have min element as its left or right edge, and the rest recurse. Before that, we have seen a sequence of output smaller than N, and the first one must be a left or right element, the next one, if larger, can be adjacent to it predecessor, else it is smaller and has to take an opposite edge. Along this line, we somehow could reconstruct a sequence by ignoring all pops, and this might help us find the pushes, then the pops.
Thursday, September 27, 2012
leetcode
An online judge to practise interview problems. Most of them are nontrivial.
In one of the problems I need to use dp to remember vector >
so I end up having some awkward thing like vector
Using typedef saves a few key strokes, but what is a good way to write such things?
In one of the problems I need to use dp to remember vector
so I end up having some awkward thing like vector
Using typedef saves a few key strokes, but what is a good way to write such things?
Monday, September 24, 2012
github notes
If you want read/write access to repo, use ssh link.
To clone a project:
To clone a project:
cd ~/.ssh && ssh-keygencat id_rsa.pub | xclip git clone
git init
git remote add some_name_in_remote.git git add filesgit push
git branch
Sunday, September 23, 2012
codechef September short
| Carvans | CARVANS | 1093 | 39 |
| Coal Scam | COALSCAM | 138 | 24.35 |
| Prime Permutations | PPERM | 155 | 19.58 |
| Pizza Tossing | PTOSS | 12 | 14.81 |
| Recipe Reconstruction | RRECIPE | 769 | 35.21 |
Carvans: keep track of the slowest car before you.
Coal Scam: Two phase of Kruskal's, the key is to prove that ties can be broken arbitrarily. For implementation, since M is only 20000, even the O(n) union-find implementation will work. For quick union-find, either union by size or union by rank is fast. I had another terrible mistake for not noticing nodes are given as 0 to N-1, while I thought it was 1 to N. This caused id[0] not to get reinitialized between testcases.
Prime Permutation: To count, notice that after you placed 1 to N-1, inserting N to anywhere does not affect whether the first N-1 numbers are in a valid position or not, since their rank does not change. So you only need to place N at 1 or a prime position. My mistake is only calculate cnt[] to 5000000-1, and got a WA.
Recipe Reconstruction: since it has to be palindrome, you can match char by char from both ends. The tricky part is that 10000000+9 = 23 * 434783 which is NOT a prime. So you need Chinese Remainder's Theorem (CRT) to calculate the mod.
Side note: to verify my solution after seeing editorial for PPerm, I wrote a bash for loop to write 1 to 5000000 to a file. This takes about 6m30s. Running the c++ code read in the file and do all the calculations and write to another file takes less than 2s.
Tuesday, September 18, 2012
Vertex Cover in bipartite graph
Vertex cover reduces to matching and flow when the input is a bipartite graph.
First the unweighted case, that is, we want the minimum cardinality vertex cover.
Konig's theorem says size(VC) = size(M) where VC is a minimum vertex cover and M is a maximum matching.
Quick proof: The direction M >= VC is easy since at least one of the two endpoints in M has to appear in VC. The other direction, M <= VC is proved by providing an algorithm that constructs VC from M.
Suppose we have a matching M now. We have a simple observation, if v in L is matched to w in R, then at most one of v and w can have an unmatched neighbor, otherwise we can augment. A stronger version is that an alternating path start with an unmatched vertex must end at a matched vertex.
The algorithm: start from every unmatched vertex on the left L, do dfs/bfs to reach other vertices in L and R. Let L1 and R1 be set of matched vertices. From L to R we use E-M, from R to L we use M. Let the hit vertices in L be L0 and those in R be R0, the answer is L1-L0 + R0. Intuitively we need all v in R0 to cover all unmatched vertices in L, as well as v in L0. Given the observation we had before, no vertex in L0 can have an edge with an unmatched vertex in R. So edges involving all unmatched vertices in R is covered by L1-L0. Edges involving R1-R0 are covered by L1-L0 because none of them is reachable from L0 when we do dfs. Edges involving R0 are covered by R0 of course. That way we have covered all edges with endpoints in R, namely unmatched vertices, R0 and R1-R0.
The weighted version involves a reduction to min-cut. The graph is constructed by adding s and t, s has edge w(e) = w(v) for each v in L, and each v in R has an edge to t with w(e) = w(v). Each edge from v1 in L to v2 in R has inf capacity. Now a mincut is a min VC.
First observe that a trivial cut is to have s by itself and the weight is finite. So a mincut cannot have an inf edge. Suppose we have a VC = L1 + R1, then our cut is s + L - L1 + R1. The cost of VC is w(L1) + w(R1) and the cost of cut is also w(L1) + w(R1). Conversely, if we have a cut with finite capacity, let the cut assign L1 to s, where L1 is a subset of L, then all vertices in R, call it R1, with an inf edge with L1 must also belong to s. Hence we have L-L1 + R1 being a vertex cover with the same weight.
The algorithm is thus solving the mincut problem with max-flow-min-cut algorithm, then those reachable from s in R and those not reachable from s in L form VC.
First the unweighted case, that is, we want the minimum cardinality vertex cover.
Konig's theorem says size(VC) = size(M) where VC is a minimum vertex cover and M is a maximum matching.
Quick proof: The direction M >= VC is easy since at least one of the two endpoints in M has to appear in VC. The other direction, M <= VC is proved by providing an algorithm that constructs VC from M.
Suppose we have a matching M now. We have a simple observation, if v in L is matched to w in R, then at most one of v and w can have an unmatched neighbor, otherwise we can augment. A stronger version is that an alternating path start with an unmatched vertex must end at a matched vertex.
The algorithm: start from every unmatched vertex on the left L, do dfs/bfs to reach other vertices in L and R. Let L1 and R1 be set of matched vertices. From L to R we use E-M, from R to L we use M. Let the hit vertices in L be L0 and those in R be R0, the answer is L1-L0 + R0. Intuitively we need all v in R0 to cover all unmatched vertices in L, as well as v in L0. Given the observation we had before, no vertex in L0 can have an edge with an unmatched vertex in R. So edges involving all unmatched vertices in R is covered by L1-L0. Edges involving R1-R0 are covered by L1-L0 because none of them is reachable from L0 when we do dfs. Edges involving R0 are covered by R0 of course. That way we have covered all edges with endpoints in R, namely unmatched vertices, R0 and R1-R0.
The weighted version involves a reduction to min-cut. The graph is constructed by adding s and t, s has edge w(e) = w(v) for each v in L, and each v in R has an edge to t with w(e) = w(v). Each edge from v1 in L to v2 in R has inf capacity. Now a mincut is a min VC.
First observe that a trivial cut is to have s by itself and the weight is finite. So a mincut cannot have an inf edge. Suppose we have a VC = L1 + R1, then our cut is s + L - L1 + R1. The cost of VC is w(L1) + w(R1) and the cost of cut is also w(L1) + w(R1). Conversely, if we have a cut with finite capacity, let the cut assign L1 to s, where L1 is a subset of L, then all vertices in R, call it R1, with an inf edge with L1 must also belong to s. Hence we have L-L1 + R1 being a vertex cover with the same weight.
The algorithm is thus solving the mincut problem with max-flow-min-cut algorithm, then those reachable from s in R and those not reachable from s in L form VC.
Friday, September 14, 2012
Software engineering principles
Things I learned from google, or some google engineer.
Look for sound design and code readability (this is more than small things like indentation, but the overall structure)
Do not compromise quality.
Look for sound design and code readability (this is more than small things like indentation, but the overall structure)
Do not compromise quality.
Thursday, September 13, 2012
SRM 556 another setback
First I am not very careful indeed.
p250 is easy, just recognize that you need to explore all possible states
dp[n][val], n is at most 50 and val is at most 1023
each (k, v) can lead to at most n new states.
For some reason I thought you only need dp[n], and the challenge follows.
p500 is not hard either. This is one of the few p500 problems that I got the idea pretty quickly. The reason I was not able to finish is:
1. I wrote too much python recently and keep using string str = "" + a[i] + tmp;
C++ does not understand what I am doing.
2. I didn't spend enough time to figure out the base case and my dp implementation is rather messy.
Given over 60min on p500 and I still could not get close enough to a working implementation. Quite disappointed with myself.
One more note, if you get SIGKILL in tc arena, you are using too much memory. string dp[55][55][55][55]; is too much, for example.
p250 is easy, just recognize that you need to explore all possible states
dp[n][val], n is at most 50 and val is at most 1023
each (k, v) can lead to at most n new states.
For some reason I thought you only need dp[n], and the challenge follows.
p500 is not hard either. This is one of the few p500 problems that I got the idea pretty quickly. The reason I was not able to finish is:
1. I wrote too much python recently and keep using string str = "" + a[i] + tmp;
C++ does not understand what I am doing.
2. I didn't spend enough time to figure out the base case and my dp implementation is rather messy.
Given over 60min on p500 and I still could not get close enough to a working implementation. Quite disappointed with myself.
One more note, if you get SIGKILL in tc arena, you are using too much memory. string dp[55][55][55][55]; is too much, for example.
Friday, September 7, 2012
Thursday, September 6, 2012
two problems about RSA
1. Given e, d and N, can you find p and q?
2. if alice send the same message M to three different people, that is, if you have M^e1, M^e2 and M^e3, and N1, N2, N3, can you recover M?
problem 1 involves deep number theory.
problem 2 can be solved using chinese remainder's theorem, assuming N1, N2 and N3 are relatively prime.
2. if alice send the same message M to three different people, that is, if you have M^e1, M^e2 and M^e3, and N1, N2, N3, can you recover M?
problem 1 involves deep number theory.
problem 2 can be solved using chinese remainder's theorem, assuming N1, N2 and N3 are relatively prime.
Friday, August 24, 2012
preorder, postorder and reconstruct tree
An interesting problem from mitbbs.com, jobhunting, posted by geniusxyz
The problem is, given two lists, pre and post, representing the preorder and postorder traversal of a general tree, each node in the list is struct {int val; bool is_leaf; }. Reconstruct the tree.
It seems rather difficult and took me a full day.
Some picture always helps, draw a tree and do preorder and postorder to see how nodes are listed.
Observation: we can partition the tree into vertex-disjoint paths, each path starts at some node and ends with a leaf. The pre list gives exactly the paths, each path terminated by a leaf.
Now our job is to attach the paths to the right subtree root, and this follows from post list.
Let's start with attaching the second list to the first list.
Let ptr be the pointer to some node in the first list, init to the leaf. In post list we have ptr matched to the first leaf in post[] in the beginning. Now as long as we have not hit the next leaf in post[], we advance postptr (pointer to post[]) and move ptr to its parent. When we stop, the parent of ptr is where we attach the second list to the first. Why? because we now run into another leaf and the parent of ptr is an ancestor of that leaf, so it must also be a parent of the second list. (a more rigorous argument is needed here). Repeat until we attached all lists to the first list.
Picture-wise, the tree starts with a linear list, which is the first list, then the second list was attached and the frontier consists of the second list and the common sublist that is the ancestor of both the first and second list. We move the frontier as we attach new lists and update ptr in that frontier.
ZhangBZ replied in the same post with very elegant code.
The problem is, given two lists, pre and post, representing the preorder and postorder traversal of a general tree, each node in the list is struct {int val; bool is_leaf; }. Reconstruct the tree.
It seems rather difficult and took me a full day.
Some picture always helps, draw a tree and do preorder and postorder to see how nodes are listed.
Observation: we can partition the tree into vertex-disjoint paths, each path starts at some node and ends with a leaf. The pre list gives exactly the paths, each path terminated by a leaf.
Now our job is to attach the paths to the right subtree root, and this follows from post list.
Let's start with attaching the second list to the first list.
Let ptr be the pointer to some node in the first list, init to the leaf. In post list we have ptr matched to the first leaf in post[] in the beginning. Now as long as we have not hit the next leaf in post[], we advance postptr (pointer to post[]) and move ptr to its parent. When we stop, the parent of ptr is where we attach the second list to the first. Why? because we now run into another leaf and the parent of ptr is an ancestor of that leaf, so it must also be a parent of the second list. (a more rigorous argument is needed here). Repeat until we attached all lists to the first list.
Picture-wise, the tree starts with a linear list, which is the first list, then the second list was attached and the frontier consists of the second list and the common sublist that is the ancestor of both the first and second list. We move the frontier as we attach new lists and update ptr in that frontier.
ZhangBZ replied in the same post with very elegant code.
Wednesday, August 22, 2012
SRM 553
p250: 0 is special, so eval with program[pos] set to 0, where pos is the -1.
then you can eval with -1 there. If it comes out equal wanted, then you return 1, since 0 did not work and the next smallest number is 1.
Otherwise you got a number different from wanted. You know that if target can make eval to wanted, then use -1 instead of target you get wanted - target - 1, so target = wanted - ans -1, where ans is the eval result when you leave -1 unchanged. However there is a catch, the eval returned value may not use -1 at all. To trace whether -1 has been hit or not turns out a bit tricky. pieguy has an elegant solution, use 1 and 2 to replace -1 and eval them, if the two ans come out different, then you know -1 has been hit. My offline solution is to do one more eval starting from program[pos]=-1, then check stack size = 1. There are other solutions which remembers whether the current value in stack has -1 built in or not.
p500, the solution must be a decreasing rows of B matched with an increasing rows of W, this will lead to a dp solution. One more observation, since each cell is either B or W, it must be start with topleft an all B or all W row echelon form.
then you can eval with -1 there. If it comes out equal wanted, then you return 1, since 0 did not work and the next smallest number is 1.
Otherwise you got a number different from wanted. You know that if target can make eval to wanted, then use -1 instead of target you get wanted - target - 1, so target = wanted - ans -1, where ans is the eval result when you leave -1 unchanged. However there is a catch, the eval returned value may not use -1 at all. To trace whether -1 has been hit or not turns out a bit tricky. pieguy has an elegant solution, use 1 and 2 to replace -1 and eval them, if the two ans come out different, then you know -1 has been hit. My offline solution is to do one more eval starting from program[pos]=-1, then check stack size = 1. There are other solutions which remembers whether the current value in stack has -1 built in or not.
p500, the solution must be a decreasing rows of B matched with an increasing rows of W, this will lead to a dp solution. One more observation, since each cell is either B or W, it must be start with topleft an all B or all W row echelon form.
Thursday, August 16, 2012
SRM 552
As usual I only know how to do the 250 problem, and I failed that one.
p250, given three numbers R, G, B, and another number N, you lay out a triangle such that no two neighboring balls share same color. The problem asks how many triangles with N layers you can make.
It is easy to see that you need
N R G B
-------------
1 0 0 0
2 1 1 1
3 2 2 2
4 4 3 3
5 5 5 5
6 7 7 7
Enough pattern, so to make one triangle of N layers you need sum of 1 to N balls, which is N(N+1)/2. For N=3k or 3k+2 this number is a multiple of 3 so you need the same number of three colors, and the answer is simply B/(S/3), where R>=G>=B and S = N(N+1)/2.
The tricky case is N=3k+1, then S = 3k' + 1. Now you need to distribute balls to make max number of triangles. Let us image that the optimal answer is m triangles, then you need at least m*((S-1)/3) for each color, and whatever remain can be any color, as long as the remaining balls are at least m. So the answer is min of (R+G+B)/S and B/(S/3). The special case is N=1, where you return R+G+B. An easier way to visualize this is that you grow three equal columns for each color, then what has been cut off from each color are the remaining balls you have, those balls are equivalent and can be distributed to any triangle you want to make.
The problem setter is more evil than this to introduce a few integer overflow even for long long, if you use * instead of /
p500
notice that the two rectangles r1 and r2, can be separated by a horizontal or vertical divider. Try all possible dividers and within each region, brute-force on all possible r1, and of all possible r2 respectively. We have no more than 30 horizontal divider and same for vertical ones. To try all possible r1, just run (x1,y1) and (x2,y2). This is no more than 30*30*30*30 < 10^6. The implementation demands extreme care. Draw a picture to get the indices correct. Also check when there is no solution, you need to return -1. This is different from the case when there is zero flowers.
p1000
p250, given three numbers R, G, B, and another number N, you lay out a triangle such that no two neighboring balls share same color. The problem asks how many triangles with N layers you can make.
It is easy to see that you need
N R G B
-------------
1 0 0 0
2 1 1 1
3 2 2 2
4 4 3 3
5 5 5 5
6 7 7 7
Enough pattern, so to make one triangle of N layers you need sum of 1 to N balls, which is N(N+1)/2. For N=3k or 3k+2 this number is a multiple of 3 so you need the same number of three colors, and the answer is simply B/(S/3), where R>=G>=B and S = N(N+1)/2.
The tricky case is N=3k+1, then S = 3k' + 1. Now you need to distribute balls to make max number of triangles. Let us image that the optimal answer is m triangles, then you need at least m*((S-1)/3) for each color, and whatever remain can be any color, as long as the remaining balls are at least m. So the answer is min of (R+G+B)/S and B/(S/3). The special case is N=1, where you return R+G+B. An easier way to visualize this is that you grow three equal columns for each color, then what has been cut off from each color are the remaining balls you have, those balls are equivalent and can be distributed to any triangle you want to make.
The problem setter is more evil than this to introduce a few integer overflow even for long long, if you use * instead of /
p500
notice that the two rectangles r1 and r2, can be separated by a horizontal or vertical divider. Try all possible dividers and within each region, brute-force on all possible r1, and of all possible r2 respectively. We have no more than 30 horizontal divider and same for vertical ones. To try all possible r1, just run (x1,y1) and (x2,y2). This is no more than 30*30*30*30 < 10^6. The implementation demands extreme care. Draw a picture to get the indices correct. Also check when there is no solution, you need to return -1. This is different from the case when there is zero flowers.
p1000
Saturday, August 11, 2012
evernote code sprint
a bit disappointing codesprint.
all 4 problems are typical 15min interview problems and the testcases are probably not strong.
Most coders would finish within an hour and being rank 1 the first time didn't make me feel anything close to accomplishment.
all 4 problems are typical 15min interview problems and the testcases are probably not strong.
Most coders would finish within an hour and being rank 1 the first time didn't make me feel anything close to accomplishment.
codechef aug12
Other problems:
why my segment tree got WA?
some 10^8 solution got TLE, which is strange.
block game: why I didn't realize it is the stable marriage problem, and my idea is very close on the last day?
Just found a very stupid bug in my code, I am implementing exactly the algorithm but confused in two indexing arrays. Easily ACed after that.
OK, now I can describe my approach. The problem looks a bit confusing, and in fact the statement has to be rewritten to clean up some ambiguity. Quite a few coders got AC before rewritten and I guess they are good at guessing what the problem setter has in mind because great coders think alike. The confusion mostly comes from the intent that the setter is trying to hide the trick in the problem. Or he does not want people to realize what the constraint really meant. shangjingbo is a top coder, that is no question, just the way the problem was phrased make me a bit disappointed, although I did read the problem correctly. Another evil part of the statement was that you output -1 if there is no solution. In fact, this can never happen, as the existence of a solution can be proved.
Let's read the problem first. Each boy visits each house at a different time, also a house can never have two boys at the same time. Now we need to find a mapping from boys to houses, such that after boy B locked at house H, nobody can visit house H later. The implication is that, for any boy, they cannot visit H, and any house on his schedule after H. For example, if a boy B1 visits H1, H2, ..., Hn in order of time, and H = H3. then after another boy B2 was locked to H3, boy B1 can only visit H1 and H2, houses from H3 to Hn are not available to B1 now.
At this point, it is clear that we can simulate the game. Let all boys pick up their first choice of house in their schedule. As long as there is a conflict, that is, a house is shared by two or more boys, we find such a house, then find the boy in that house with minimum time. This boy must be able to visit that house before all conflicting boys, so we move this boy to his next house. In the end, if we end up in a state that all boys get a different house, then we have a solution, otherwise there is no solution.
Now we show that there is always a solution. The reason is, the only case when there is no solution is that a boy was moved beyond his last, the n-th house. But this can happen only after all the n houses were taken. Since a boy can take only one house, the other n-1 boys cannot take all n houses. So there is always a solution.
Clearly if our algorithm stops, then it finds a solution. On the other hand, if there is a solution, then the algorithm always finds one. Intuitively it is clear, but I do not have a good proof than the one based on stable marriage problem. A high level argument is that we started with all boys take their first choice and keep them as happy as possible, any time we were forced to move a boy, we move the boy that has to do so, because it is the one that is able to visit the house before its peers hence was able to advance to its next choice.
Lessons learned:
In the final output code, I should wrote myindex[i] instead of location[i]. Two ways could possibly avoid this mistak:
1. do not use location[i] as global, then it will not be visible in the final output code part.
2. keep some note of key data structure, or be careful and take note of variable renaming.
3. have a proof of what I am trying to do, as I am not convinced about my algorithm which is a bad thing.
machine gun: I know it is bipartite matching, just my hopcroft-karp implementation keeps getting TLE. The author (ktuan) and tester (laycurse) use the same Hopcroft-Karp algorithm but they must be running within 15s limit. Also ACrush's code runs within 8s. I heard severkplus mentioned that other people have graphs twice as big as his yet they had a better max-flow implementation and passed, while his failed.
Actually there is one simple but crucial observation, the graph has 4 disconnected components, based on parity of cell index, (odd, odd), (odd, even), (even, odd), (even, even), they cannot be connected. So we are dealing with 4 graphs each with size (700/2)^2 < 130000. This will run in time.
stunning difference:
laycurse solution runs 300x300 all F graph in 0.02s
my solution runs the same graph in 23s
A stupid bug, when running multiple testcases,forgot to initialize globals, in particular, ans is not reset so it accumulates previous counts!
optimizations:
1. the graph is of 4 parts based on (odd/even, odd/even) also essential
2. each component is bipartite with (x+4, y+2) vs (x+2, y+2) also essential
3. when reset visited[][], only reset those entries that you actually set, this requires remember all nodes visited in the current DFS augment
4. map (i,j) into N1++, N2++, this one is essential
5. use +1, -1 to find neighbors, eliminate +2 then /2
6. check bounds with if expr instead of inbound() call, there are too many calls
why my segment tree got WA?
some 10^8 solution got TLE, which is strange.
block game: why I didn't realize it is the stable marriage problem, and my idea is very close on the last day?
Just found a very stupid bug in my code, I am implementing exactly the algorithm but confused in two indexing arrays. Easily ACed after that.
OK, now I can describe my approach. The problem looks a bit confusing, and in fact the statement has to be rewritten to clean up some ambiguity. Quite a few coders got AC before rewritten and I guess they are good at guessing what the problem setter has in mind because great coders think alike. The confusion mostly comes from the intent that the setter is trying to hide the trick in the problem. Or he does not want people to realize what the constraint really meant. shangjingbo is a top coder, that is no question, just the way the problem was phrased make me a bit disappointed, although I did read the problem correctly. Another evil part of the statement was that you output -1 if there is no solution. In fact, this can never happen, as the existence of a solution can be proved.
Let's read the problem first. Each boy visits each house at a different time, also a house can never have two boys at the same time. Now we need to find a mapping from boys to houses, such that after boy B locked at house H, nobody can visit house H later. The implication is that, for any boy, they cannot visit H, and any house on his schedule after H. For example, if a boy B1 visits H1, H2, ..., Hn in order of time, and H = H3. then after another boy B2 was locked to H3, boy B1 can only visit H1 and H2, houses from H3 to Hn are not available to B1 now.
At this point, it is clear that we can simulate the game. Let all boys pick up their first choice of house in their schedule. As long as there is a conflict, that is, a house is shared by two or more boys, we find such a house, then find the boy in that house with minimum time. This boy must be able to visit that house before all conflicting boys, so we move this boy to his next house. In the end, if we end up in a state that all boys get a different house, then we have a solution, otherwise there is no solution.
Now we show that there is always a solution. The reason is, the only case when there is no solution is that a boy was moved beyond his last, the n-th house. But this can happen only after all the n houses were taken. Since a boy can take only one house, the other n-1 boys cannot take all n houses. So there is always a solution.
Clearly if our algorithm stops, then it finds a solution. On the other hand, if there is a solution, then the algorithm always finds one. Intuitively it is clear, but I do not have a good proof than the one based on stable marriage problem. A high level argument is that we started with all boys take their first choice and keep them as happy as possible, any time we were forced to move a boy, we move the boy that has to do so, because it is the one that is able to visit the house before its peers hence was able to advance to its next choice.
Lessons learned:
In the final output code, I should wrote myindex[i] instead of location[i]. Two ways could possibly avoid this mistak:
1. do not use location[i] as global, then it will not be visible in the final output code part.
2. keep some note of key data structure, or be careful and take note of variable renaming.
3. have a proof of what I am trying to do, as I am not convinced about my algorithm which is a bad thing.
machine gun: I know it is bipartite matching, just my hopcroft-karp implementation keeps getting TLE. The author (ktuan) and tester (laycurse) use the same Hopcroft-Karp algorithm but they must be running within 15s limit. Also ACrush's code runs within 8s. I heard severkplus mentioned that other people have graphs twice as big as his yet they had a better max-flow implementation and passed, while his failed.
Actually there is one simple but crucial observation, the graph has 4 disconnected components, based on parity of cell index, (odd, odd), (odd, even), (even, odd), (even, even), they cannot be connected. So we are dealing with 4 graphs each with size (700/2)^2 < 130000. This will run in time.
stunning difference:
laycurse solution runs 300x300 all F graph in 0.02s
my solution runs the same graph in 23s
A stupid bug, when running multiple testcases,forgot to initialize globals, in particular, ans is not reset so it accumulates previous counts!
optimizations:
1. the graph is of 4 parts based on (odd/even, odd/even) also essential
2. each component is bipartite with (x+4, y+2) vs (x+2, y+2) also essential
3. when reset visited[][], only reset those entries that you actually set, this requires remember all nodes visited in the current DFS augment
4. map (i,j) into N1++, N2++, this one is essential
5. use +1, -1 to find neighbors, eliminate +2 then /2
6. check bounds with if expr instead of inbound() call, there are too many calls
Saturday, August 4, 2012
SRM 551
p250.
You know the optimal solution has to fix one pos unchanged. So try to fix each of the 0 to n-1 pos. For a fixed pos, search left and right to get the nearest same color letter until run out of maxSwap.
It took me a while to figure it out and my coding is rather slow.
p500.
A relatively easy 500 problem, observe that many people got 400+ points. However I could not find an algorithm during contest. This solution is due to liympanda.
We are to find how many 'Y' we need to remove to force a path from 0 to n-1. Generalize a bit, we need to find ans[0] to ans[n-1] where ans[i] is the min op to get from 0 to i. This leads to a DP + BFS solution.
First ans[0] = 0
Then we need to repeat at most n times.
In each iteration, we find min ans[i] such that i has not been used before, that is use[i] = 0
Then we use i to update all next such that color[i][next] is 'Y' and ans[next] can be improved. Notice that we also need to add an extra = k-1 if next is the k-th neighbor of i.
This is a bit like Dijkstra, each time we pull out the best node with min dist from src, then we use that to update dist of all other nodes. In the end we have dist of all nodes.
You know the optimal solution has to fix one pos unchanged. So try to fix each of the 0 to n-1 pos. For a fixed pos, search left and right to get the nearest same color letter until run out of maxSwap.
It took me a while to figure it out and my coding is rather slow.
p500.
A relatively easy 500 problem, observe that many people got 400+ points. However I could not find an algorithm during contest. This solution is due to liympanda.
We are to find how many 'Y' we need to remove to force a path from 0 to n-1. Generalize a bit, we need to find ans[0] to ans[n-1] where ans[i] is the min op to get from 0 to i. This leads to a DP + BFS solution.
First ans[0] = 0
Then we need to repeat at most n times.
In each iteration, we find min ans[i] such that i has not been used before, that is use[i] = 0
Then we use i to update all next such that color[i][next] is 'Y' and ans[next] can be improved. Notice that we also need to add an extra = k-1 if next is the k-th neighbor of i.
This is a bit like Dijkstra, each time we pull out the best node with min dist from src, then we use that to update dist of all other nodes. In the end we have dist of all nodes.
Tuesday, July 31, 2012
CF 131
problem set 213
A. you have to start at some machine, then you keep finishing deg=0 job until exhausted. Now it only makes sense to go to machine curr+1 as going to the other one cost=2, while you can go to cost=1 then go for another cost=1. All remaining jobs have deg = deg-1 if some of its predecessor finished. Now the only question is which machine do you start? Since there are only 3 machines, the solution is easy, try to start from each of them, the best of the 3 start is your answer.
A. you have to start at some machine, then you keep finishing deg=0 job until exhausted. Now it only makes sense to go to machine curr+1 as going to the other one cost=2, while you can go to cost=1 then go for another cost=1. All remaining jobs have deg = deg-1 if some of its predecessor finished. Now the only question is which machine do you start? Since there are only 3 machines, the solution is easy, try to start from each of them, the best of the 3 start is your answer.
Wednesday, July 25, 2012
gcj round 3
A. Linearity of expectation and greedy.
B. scared by the picture.
C. I only have some idea before reading solution:
First you can binary search from 1 to M.
Second thing is to find how many delivers you need (this is ternary search but I do not know how)
Third thing is that each delivery is identical, you just find cheapest item that can last i days for i=1 to K, say a delivery can last K days. This can be done in O(N log N) using binary search.
D.
B. scared by the picture.
C. I only have some idea before reading solution:
First you can binary search from 1 to M.
Second thing is to find how many delivers you need (this is ternary search but I do not know how)
Third thing is that each delivery is identical, you just find cheapest item that can last i days for i=1 to K, say a delivery can last K days. This can be done in O(N log N) using binary search.
D.
Saturday, July 21, 2012
The Hungarian algorithm: Kuhn-Munkres theorem
The Kuhn-Munkres theorem:
Given a bipartite graph with w(e) on edges, find a matching with maximum weight.
Simplified assumption, let the graph be bipartite complete, missing edges can be taken as w(e)=0.
Then we can assume optimal matching is perfect, that is, if |L|=|R|=n, then the matching M is of size n. the reason is that we can always add some edge if not perfect, and a complete bipartite graph must have a perfect matching.
Now we look for a feasible labeling on vertex, called slack, s(v), such that
s(x) + s(y) >= w(e) for e=(x,y). This ensures that sum of all s(v) is an upper bound on opt matching. Now we seek a feasible labeling and a perfect matching on the admissible edge graph, an edge is admissible if s(x) + s(y) = w(e). This prefect matching is necessarily optimal.
The algorithm starts with a feasible labeling, each v in L has s(v)=w(e), each v in R has s(v)=0, and an empty matching M.
Now find a free vertex in L, call it x0, we then look for a way to extend the matching by one more edge.
If x0 leads to an alternating path in E(admissible), then we augment. Otherwise we end up with a subset L' and R' such that L' is contained by R'. We then lower s(v) in L' and increase s(v) in R'. This keeps edges admissible if they are admissible before, and it will give us at least one more admissible edge to augment the matching.
Time complexity is O(|V|^3).
Variantions:
- The above algorithm assumes all w(e)>=0, what if we are given some w(e) <0?
Simply replace those w(e) by 0. The reason is that if those w(e) were not chosen in the solution, then we are good. If they do get included in the solution, they can only beat edges with w(e)=0, then we are fine as well since we can simply throw away the w(e) <0 that we get in the solution.
- How about finding minimum weight perfect matching?
We can use some large integer Z and replace each w(e) with Z - w(e). Now we look for maximum matching instead. Since the solution has to be a perfect matching, flip sign of w(e) does not change the optimal solution, although its value needs to be restored.
- Implementation
nodes: X = 0,1,...,N-1,
Y=N,...,2*N-1
slack[i]=0 for each i in Y
slack[j]= max w(i, j) among all i in Y
mate[i]=-1 for i in Y
mate[j]=-1 for j in X
ans=0
for i = 0 to N-1
if mate[i]==-1 // i not matched yet
clear vis[]
while (update = augment(i) is false)
// update slack[]
delta = inf
for each j in X that vis[j] is true
for each i in Y that vis[i] is false
checkmin(delta, w(i,j) - s[j] - s[i]) // how much s[j] can decrease,
//notice that s[i] is not changed in this update
for each j in X that vis[j] is true: slack[j] -= delta
for each i in Y that vis[i] is true: slakc[i] +=delta
clear vis[]
// after enough update, i must reach all j in X, so an augment has to occur
ans++ // each augment increase matching size by 1
function augment(vertex s): return true if augment
if (vis[s]) return false;
vis[s] = true;
for each neighbor z of s // only edges with w(e) = slack[x] + slack[y] eligible
if (mate[z]==-1):
then mate[z] = s, mate[s]=z, return true
if (augment(mate[z]) is true):
then mate[z]=s, mate[s]=z, return true
return false
Observation: once a vertex is matched, it stays matched
Given a bipartite graph with w(e) on edges, find a matching with maximum weight.
Simplified assumption, let the graph be bipartite complete, missing edges can be taken as w(e)=0.
Then we can assume optimal matching is perfect, that is, if |L|=|R|=n, then the matching M is of size n. the reason is that we can always add some edge if not perfect, and a complete bipartite graph must have a perfect matching.
Now we look for a feasible labeling on vertex, called slack, s(v), such that
s(x) + s(y) >= w(e) for e=(x,y). This ensures that sum of all s(v) is an upper bound on opt matching. Now we seek a feasible labeling and a perfect matching on the admissible edge graph, an edge is admissible if s(x) + s(y) = w(e). This prefect matching is necessarily optimal.
The algorithm starts with a feasible labeling, each v in L has s(v)=w(e), each v in R has s(v)=0, and an empty matching M.
Now find a free vertex in L, call it x0, we then look for a way to extend the matching by one more edge.
If x0 leads to an alternating path in E(admissible), then we augment. Otherwise we end up with a subset L' and R' such that L' is contained by R'. We then lower s(v) in L' and increase s(v) in R'. This keeps edges admissible if they are admissible before, and it will give us at least one more admissible edge to augment the matching.
Time complexity is O(|V|^3).
Variantions:
- The above algorithm assumes all w(e)>=0, what if we are given some w(e) <0?
Simply replace those w(e) by 0. The reason is that if those w(e) were not chosen in the solution, then we are good. If they do get included in the solution, they can only beat edges with w(e)=0, then we are fine as well since we can simply throw away the w(e) <0 that we get in the solution.
- How about finding minimum weight perfect matching?
We can use some large integer Z and replace each w(e) with Z - w(e). Now we look for maximum matching instead. Since the solution has to be a perfect matching, flip sign of w(e) does not change the optimal solution, although its value needs to be restored.
- Implementation
nodes: X = 0,1,...,N-1,
Y=N,...,2*N-1
slack[i]=0 for each i in Y
slack[j]= max w(i, j) among all i in Y
mate[i]=-1 for i in Y
mate[j]=-1 for j in X
ans=0
for i = 0 to N-1
if mate[i]==-1 // i not matched yet
clear vis[]
while (update = augment(i) is false)
// update slack[]
delta = inf
for each j in X that vis[j] is true
for each i in Y that vis[i] is false
checkmin(delta, w(i,j) - s[j] - s[i]) // how much s[j] can decrease,
//notice that s[i] is not changed in this update
for each j in X that vis[j] is true: slack[j] -= delta
for each i in Y that vis[i] is true: slakc[i] +=delta
clear vis[]
// after enough update, i must reach all j in X, so an augment has to occur
ans++ // each augment increase matching size by 1
function augment(vertex s): return true if augment
if (vis[s]) return false;
vis[s] = true;
for each neighbor z of s // only edges with w(e) = slack[x] + slack[y] eligible
if (mate[z]==-1):
then mate[z] = s, mate[s]=z, return true
if (augment(mate[z]) is true):
then mate[z]=s, mate[s]=z, return true
return false
Observation: once a vertex is matched, it stays matched
SRM 550
Solved p250 with 161pt. My idea is to simulate the move of robot and then cut the minimum board.
p500 is still too hard for me, it takes a thorough analysis of the game. Coding itself is trivial. I am not good at that.
p1000 is a DP but with N up to 10^9, you need to be good at compressing states.
The result is not too bad for me as many people failed their solution. I am now only 50pt away from getting yellow.
p500 is still too hard for me, it takes a thorough analysis of the game. Coding itself is trivial. I am not good at that.
p1000 is a DP but with N up to 10^9, you need to be good at compressing states.
The result is not too bad for me as many people failed their solution. I am now only 50pt away from getting yellow.
n queen problem
Today interviewstreet gave a problem that to find one solution to place N queen in NxN board. In addition, a queen is allowed a knight's move.
I wrote a simple backtrack solution which solves N=32, N=35 is doable but takes maybe 30min.
There are solution for the original N queen problem solves N with time O(N^2). Given there are solution solves N up to 10^4, the solution should be applicable to this modified problem as well.
I wrote a simple backtrack solution which solves N=32, N=35 is doable but takes maybe 30min.
There are solution for the original N queen problem solves N with time O(N^2). Given there are solution solves N up to 10^4, the solution should be applicable to this modified problem as well.
Thursday, July 12, 2012
Copy only text
A simple solution when you want only the text from a webpage or some document, everything else like style or tags, you don't care.
cat >/dev/null
then paste your text here and copy to the destination. This works only on a unix/linux terminal, though.
Maybe not related, but format c++ code, you can use a tool called astyle.
cat >/dev/null
then paste your text here and copy to the destination. This works only on a unix/linux terminal, though.
Maybe not related, but format c++ code, you can use a tool called astyle.
Aho–Corasick_string_matching_algorithm
codechef July Challenge: Favorite Number problem.
The algorithm finds all matching positions that matches one or more in the given set of patterns.
It implements a finite state automaton. States are 0, 1, 2, ....
goto(s, a) = s' move from state s to s', when input is letter a
fail(s, a) = s' move from state s to s', when input letter a does not match any next state
output(s) = { set of strings in pattern }
When do matching text to patterns, just walk through the trie and follow fail link when necessary, similar to Knuth-Morris-Pratt.
First we show how to use the finite state machine to process text
state = 0
for each ch in text
while goto(state, ch) == fail do, state = fail(state) // must stop at state = 0
state = goto(state, ch)
if output(state) not empty, then emit output(state)
Now we show how to construct the functions.
goto() is easy, for each keywords y[i] , i=1..k (we have k keywords)
state = 0
for each ch in y[i]
if goto(state, ch) == fail, then goto(state, ch) = cntstate++
else do nothing
append y[i] to output[state]
fail() function is constructed using a BFS on the graph. We first do depth=1 nodes, which have parent as state=0, then do it with increasing depth.
queue = empty
state = 0
// do depth=1
for each next_state of state, fail(next_state) = state, enqueue(next_state)
// do depth=d using d-1
while queue not empty do
r = queue.pop()
for each symbol ch
if goto(r, ch) = s != fail, then // s is at depth=d with parent=r
enqueue(s)
state = fail(r)
while goto(state, ch) == fail, do state = fail(state)
fail(s) = state
output(s).append(output(state))
The algorithm finds all matching positions that matches one or more in the given set of patterns.
It implements a finite state automaton. States are 0, 1, 2, ....
goto(s, a) = s' move from state s to s', when input is letter a
fail(s, a) = s' move from state s to s', when input letter a does not match any next state
output(s) = { set of strings in pattern }
When do matching text to patterns, just walk through the trie and follow fail link when necessary, similar to Knuth-Morris-Pratt.
First we show how to use the finite state machine to process text
state = 0
for each ch in text
while goto(state, ch) == fail do, state = fail(state) // must stop at state = 0
state = goto(state, ch)
if output(state) not empty, then emit output(state)
Now we show how to construct the functions.
goto() is easy, for each keywords y[i] , i=1..k (we have k keywords)
state = 0
for each ch in y[i]
if goto(state, ch) == fail, then goto(state, ch) = cntstate++
else do nothing
append y[i] to output[state]
fail() function is constructed using a BFS on the graph. We first do depth=1 nodes, which have parent as state=0, then do it with increasing depth.
queue = empty
state = 0
// do depth=1
for each next_state of state, fail(next_state) = state, enqueue(next_state)
// do depth=d using d-1
while queue not empty do
r = queue.pop()
for each symbol ch
if goto(r, ch) = s != fail, then // s is at depth=d with parent=r
enqueue(s)
state = fail(r)
while goto(state, ch) == fail, do state = fail(state)
fail(s) = state
output(s).append(output(state))
Saturday, July 7, 2012
interviewstreet oxygencloud
Two hard problems.
Problem 1: one person game: given 8x8 grid, with each cell having a number, find a path in the grid with maximum sum. The path cannot contain zero cell.
I wrote a brute force dfs solution, which passed case 1 and 3 by sheer luck. This 20 points was also the only points I earned. Now we know the starting position has to be nonzero. A cell can go up, down, left, right, 4 neighbors. Still no idea for a solution.
Problem 2: data center. Given integer n, find the number of possible labeled spanning forest with root, 1 2, 1 2 3, 1 2 3 4, ..., 1 2 ... n. MOD = 10^9+7
Two people solved it. I don't have any idea. Looks a tough counting problem.
UPDATE:
Solution for problem 2 from chhung6.
The idea is DP with knowledge of Cayley's formula. The number of labeled rooted tree with n nodes is n^(n-2)
Let dp[N][M] be number of forests with N servers and M clients,
then N=1 we use Cayley's formula.
N=2, we can use K clients to server 1 and M-K clients to server 2, and there are (M choose K) ways to split the M clients.
In general,
dp[N][M] = sum_K=0^M mult((M choose K), dp[N-1][K], (M-K+1)^(M-K+1-2))
be careful when M-K+1=1, then (M-K+1-2) is -1.
Now that we have dp[N][M], the answer is sum_K=2 to n: dp[K][n-K]
since n could be as large as 10^9, you know you need a closed form. Then the natural step is to google the first a few terms. However, there is a catch.
Search the first a few terms of ans[2, 3, 4, 5, 6] did not return anything useful. In fact, my search in google or oeis did not return anything.
Then the next step is to search sum_K=1 to n: dp[K][n-K], note the start index is from 1 now. This gives a closed form formula in oeis,
A058128 a(1)=1, a(n)=(n^n-n)/(n-1)^2 for n >= 2.
1, 2, 6, 28, 195, 1866, 22876, 342392, 6053445, 123456790,
our answer is simply a(n) - number of spanning trees with n nodes (that is, with only 1 server)
Problem 1: one person game: given 8x8 grid, with each cell having a number, find a path in the grid with maximum sum. The path cannot contain zero cell.
I wrote a brute force dfs solution, which passed case 1 and 3 by sheer luck. This 20 points was also the only points I earned. Now we know the starting position has to be nonzero. A cell can go up, down, left, right, 4 neighbors. Still no idea for a solution.
Problem 2: data center. Given integer n, find the number of possible labeled spanning forest with root, 1 2, 1 2 3, 1 2 3 4, ..., 1 2 ... n. MOD = 10^9+7
Two people solved it. I don't have any idea. Looks a tough counting problem.
UPDATE:
Solution for problem 2 from chhung6.
The idea is DP with knowledge of Cayley's formula. The number of labeled rooted tree with n nodes is n^(n-2)
Let dp[N][M] be number of forests with N servers and M clients,
then N=1 we use Cayley's formula.
N=2, we can use K clients to server 1 and M-K clients to server 2, and there are (M choose K) ways to split the M clients.
In general,
dp[N][M] = sum_K=0^M mult((M choose K), dp[N-1][K], (M-K+1)^(M-K+1-2))
be careful when M-K+1=1, then (M-K+1-2) is -1.
Now that we have dp[N][M], the answer is sum_K=2 to n: dp[K][n-K]
since n could be as large as 10^9, you know you need a closed form. Then the natural step is to google the first a few terms. However, there is a catch.
Search the first a few terms of ans[2, 3, 4, 5, 6] did not return anything useful. In fact, my search in google or oeis did not return anything.
Then the next step is to search sum_K=1 to n: dp[K][n-K], note the start index is from 1 now. This gives a closed form formula in oeis,
A058128 a(1)=1, a(n)=(n^n-n)/(n-1)^2 for n >= 2.
1, 2, 6, 28, 195, 1866, 22876, 342392, 6053445, 123456790,
our answer is simply a(n) - number of spanning trees with n nodes (that is, with only 1 server)
Saturday, June 23, 2012
reach interviewstreet
a summer game puzzle, basically given a board with char, ask for a route of knights moves without intersecting itself. The concatenated string is the address of interviewstreet mountain view office.
After several failed attempts, about a dozen, with hand, I have to write a program to do it. DFS with intersection checking. Finally got accepted. Now wondering what are the mysterious gifts they claimed to give away.
After several failed attempts, about a dozen, with hand, I have to write a program to do it. DFS with intersection checking. Finally got accepted. Now wondering what are the mysterious gifts they claimed to give away.
Sunday, June 17, 2012
mihai patrascu passed away at 29
A star in theoretical computer science, made fundamental contribution to data structure and lower bounds, passed away this year at age of 29.
Wednesday, June 13, 2012
achilles tendor rupture
A non-technical one. This happens when I was playing badminton, then a pop. Had surgery two days later and now in splint. The full recovery takes 6 months, so I have to be patient. All activities are kept at minimal level, including programming competition.
a graph exercise
From Dasgupta's Algorithms book.
Given an undirected graph, find a subgraph such that each vertex has at least 5 neighbors and at least 5 non-neighbors.
This is a simple problem but it took me an afternoon to figure out the algorithm.
Disclaimer: my solution may not be the most efficient, nor does it represents a consent from the authors for being correct.
The whole idea is about degree. Let deg(v) be the degree of vertex v in current graph. We know that in the final graph, all deg(v) must be
5 <= deg(v) <= n-6
the >=5 is obvious, the n-6 upper bound comes from the need to have 5 non-neighbors.
A simple observation is that if the input graph G has all vertex v with deg(v) within bound, then we are done. Otherwise there is at least one vertex violating the bound. To convert any graph G into a graph with only valid vertex (deg within bounds), we repeat the two operations until done:
1. Remove all vertex v with deg(v) <=4, until no such vertex available.
2. Remove all vertex v with deg(v) >=n-5, until no such vertex available.
op 1 is obvious, if v has deg<=4, then it can never have deg>=5 if we remove other vertices.
op 2 is for a similar reason, if a vertex has deg>=n-5, that implies it has less than 5 non-neighbors. Because we only remove vertex, removing other vertex cannot make v have more non-neighbors. So we have to remove v from the graph to make all vertices valid.
For complexity, we do at most |V| iterations, each iteration takes O(|V|+|E|) time to count deg for each vertex, for a total of (|V|^2 + |V||E|)
Given an undirected graph, find a subgraph such that each vertex has at least 5 neighbors and at least 5 non-neighbors.
This is a simple problem but it took me an afternoon to figure out the algorithm.
Disclaimer: my solution may not be the most efficient, nor does it represents a consent from the authors for being correct.
The whole idea is about degree. Let deg(v) be the degree of vertex v in current graph. We know that in the final graph, all deg(v) must be
5 <= deg(v) <= n-6
the >=5 is obvious, the n-6 upper bound comes from the need to have 5 non-neighbors.
A simple observation is that if the input graph G has all vertex v with deg(v) within bound, then we are done. Otherwise there is at least one vertex violating the bound. To convert any graph G into a graph with only valid vertex (deg within bounds), we repeat the two operations until done:
1. Remove all vertex v with deg(v) <=4, until no such vertex available.
2. Remove all vertex v with deg(v) >=n-5, until no such vertex available.
op 1 is obvious, if v has deg<=4, then it can never have deg>=5 if we remove other vertices.
op 2 is for a similar reason, if a vertex has deg>=n-5, that implies it has less than 5 non-neighbors. Because we only remove vertex, removing other vertex cannot make v have more non-neighbors. So we have to remove v from the graph to make all vertices valid.
For complexity, we do at most |V| iterations, each iteration takes O(|V|+|E|) time to count deg for each vertex, for a total of (|V|^2 + |V||E|)
Monday, June 4, 2012
children and candy problem
N children in a circle, each with some number of candies in hand, a_1,a_2,...,a_n. There is also a basket with unlimited candies.
In each round, each child gives half of his candies to the next child, if a_i is odd, he/she gets one more from the basket to make it even. The process terminates if all children have equal number of candies in hand.
The problem is: Will the process terminate?
Intuitively the answer is yes. But the proof ?
I used to have a better proof but I forgot. Here is the one I have now.
Proof by induction on max-min. Base case is diff=max-min=0, and the process stops without any round. For inductive step, notice that max of all children never increases after a round, while there is at least one min gets killed in one round.
Consider a_i which is min and a_i-1 is strictly larger than min. Then after a round, a_i will be strictly larger than min and a_i-1 stays strictly larger than min, regardless of what a_i-2 is, even if it is min. Therefore after no more than n rounds we killed all min. That is min now increased by at least 2. Applying the inductive hypothesis, we conclude that the process will terminate with max-min = 0
In each round, each child gives half of his candies to the next child, if a_i is odd, he/she gets one more from the basket to make it even. The process terminates if all children have equal number of candies in hand.
The problem is: Will the process terminate?
Intuitively the answer is yes. But the proof ?
I used to have a better proof but I forgot. Here is the one I have now.
Proof by induction on max-min. Base case is diff=max-min=0, and the process stops without any round. For inductive step, notice that max of all children never increases after a round, while there is at least one min gets killed in one round.
Consider a_i which is min and a_i-1 is strictly larger than min. Then after a round, a_i will be strictly larger than min and a_i-1 stays strictly larger than min, regardless of what a_i-2 is, even if it is min. Therefore after no more than n rounds we killed all min. That is min now increased by at least 2. Applying the inductive hypothesis, we conclude that the process will terminate with max-min = 0
Saturday, June 2, 2012
TCO 2C
My last round in TCO, and finally I got one problem correct.
p300 looks doable by just brute-force all possible choices. However search from 1 to 9999 might be too slow. A minute of thinking makes you realize that you only need to try all possible out-edge weight +1,0,-1, and that's all. The rest is just implementation which took me about 40min.
p500 and p900 all look doable, at least I understand the problem statement. The problem is, how to do it fast? Need to read the editorial, I guess.
In terms of difficulty, 2C is easier than 2A and 2B, at least it seems to me. There are quite some people finishing all 3. I have yet to make my first successful p500 submission.
p300 looks doable by just brute-force all possible choices. However search from 1 to 9999 might be too slow. A minute of thinking makes you realize that you only need to try all possible out-edge weight +1,0,-1, and that's all. The rest is just implementation which took me about 40min.
p500 and p900 all look doable, at least I understand the problem statement. The problem is, how to do it fast? Need to read the editorial, I guess.
In terms of difficulty, 2C is easier than 2A and 2B, at least it seems to me. There are quite some people finishing all 3. I have yet to make my first successful p500 submission.
interviewstreet elastic
https://elastic.interviewstreet.com/challenges/dashboard/#problems
The problems look accessible, but I only managed the last one with 50pt. It is DFS by the way.
Problem A: how to do it fast?
The problems look accessible, but I only managed the last one with 50pt. It is DFS by the way.
Problem A: how to do it fast?
Sunday, May 20, 2012
TC SRM 541
Another bad performance, failed 250 and get a score of 0.
One thing to learn:
When you need to do 1<
long long val=1;
while(val < cap) val<<=1;
One thing to learn:
When you need to do 1<
long long val=1;
while(val < cap) val<<=1;
Friday, May 18, 2012
codechef may12, problem MEDIAN
After 10 submissions, multiple WA and TLE, finally got problem MEDIAN in codechef may12 challenge accepted.
The problem is: given a sequence of 0 and 1, with at least one 1, and n<=30, find minimum number of steps to make them all 1. In each step you can choose a subarray with #1 >= #0 and flip all 0 to 1.
OK, you know n<=30 so you can represent all states with bitmap which fits into int. Then you do BFS search to start from initial configuration and look for (1<<30)-1. The hard part, at least to me, is to implement each transition in O(n) time. A naive approach is to try all possible subarray, there are O(n^2) of them, and add them to the queue. This will TLE for sure as it gets you a lot more useless states. An improvement is by observing that if a feasible interval, meaning #1>=#0, is included in another feasible interval, then there is no point try that subinterval. This gives O(n) next state instead of O(n^2). However, if you insist on finding feasible interval starting from each pos=0..n-1, it still takes O(n) time for each pos and you need O(n^2) time to find them. Maybe there is a way to do it in linear time, but I do not know how.
My idea is based on the observation: start at p1=0, then look for the rightmost p2 such that diff=#1 - #0 is minimized. Once we found p2, we check diff. If diff <0, then we know we are done, add next state into queue and update its dist. If diff ==0, then we can try p2=p2+1 in next iteration to look for a new p2. Otherwise diff > 0, then we move p1 to the right and stop when diff=0. If we end up with diff >0, that means there is no feasible interval within [p1..n-1], and we stop. Otherwise we have diff=0 so we record this interval, and in next iteration we will start with p2=p2+1. Clearly it is O(n) time and we have at most O(n) next state.
Now we prove the case diff>0 implies no feasible interval can appear within [p1..n-1]. Since diff >0, we know that either all [p1..p2] are 0, or p2 must be 1, otherwise we can take p2=p2-1 and we get a smaller diff. But if p2 is 1, then when we move p1 to p2, we have to have a feasible interval because p2 itself is a feasible interval. Therefore all [p1..p2] are 0. However, for a feasible interval to exist within p1..n-1, we have to have some 1 in this interval, then include this pos into [p1..p2] will give a smaller diff, which is a contradiction. Therefore we have a somewhat surprising result, if we fail to find a feasible interval between p1..n-1, then all p1..n-1 must be 0.
Implementation notes:
1. I forgot to clear map between testcases.
2. I was using a[i] instead of the a[i] value from bitmap conf.
3. To run all cases, the standard way is:
int ncase; cin >> ncase;
while(ncase--)
solve();
The problem is: given a sequence of 0 and 1, with at least one 1, and n<=30, find minimum number of steps to make them all 1. In each step you can choose a subarray with #1 >= #0 and flip all 0 to 1.
OK, you know n<=30 so you can represent all states with bitmap which fits into int. Then you do BFS search to start from initial configuration and look for (1<<30)-1. The hard part, at least to me, is to implement each transition in O(n) time. A naive approach is to try all possible subarray, there are O(n^2) of them, and add them to the queue. This will TLE for sure as it gets you a lot more useless states. An improvement is by observing that if a feasible interval, meaning #1>=#0, is included in another feasible interval, then there is no point try that subinterval. This gives O(n) next state instead of O(n^2). However, if you insist on finding feasible interval starting from each pos=0..n-1, it still takes O(n) time for each pos and you need O(n^2) time to find them. Maybe there is a way to do it in linear time, but I do not know how.
My idea is based on the observation: start at p1=0, then look for the rightmost p2 such that diff=#1 - #0 is minimized. Once we found p2, we check diff. If diff <0, then we know we are done, add next state into queue and update its dist. If diff ==0, then we can try p2=p2+1 in next iteration to look for a new p2. Otherwise diff > 0, then we move p1 to the right and stop when diff=0. If we end up with diff >0, that means there is no feasible interval within [p1..n-1], and we stop. Otherwise we have diff=0 so we record this interval, and in next iteration we will start with p2=p2+1. Clearly it is O(n) time and we have at most O(n) next state.
Now we prove the case diff>0 implies no feasible interval can appear within [p1..n-1]. Since diff >0, we know that either all [p1..p2] are 0, or p2 must be 1, otherwise we can take p2=p2-1 and we get a smaller diff. But if p2 is 1, then when we move p1 to p2, we have to have a feasible interval because p2 itself is a feasible interval. Therefore all [p1..p2] are 0. However, for a feasible interval to exist within p1..n-1, we have to have some 1 in this interval, then include this pos into [p1..p2] will give a smaller diff, which is a contradiction. Therefore we have a somewhat surprising result, if we fail to find a feasible interval between p1..n-1, then all p1..n-1 must be 0.
Implementation notes:
1. I forgot to clear map between testcases.
2. I was using a[i] instead of the a[i] value from bitmap conf.
3. To run all cases, the standard way is:
int ncase; cin >> ncase;
while(ncase--)
solve();
| User | Mem | Time | Lang | |
|---|---|---|---|---|
| bb_1 | 1.6M | 0.00 | C | View Solution |
| adge1 | 2.8M | 0.01 | C++ 4.3.2 | View Solution |
| lantimilan | 2.8M | 0.02 | C++ 4.3.2 | View Solution |
Tuesday, May 15, 2012
classics revisited
There are always something new to things that you thought you already know, and google codejam just proved it.
round 1B, problem C, you are given exactly 500 positive integers, each no more than 10^12, find two subsets with equal sum.
round 1C, problem C, you are given two lists, list A has a sequence of of toys, and list B has a sequence of of boxes. You try to pack as many boxes with toys. Each toy can only be put into a box of same type. And the two lists have to go in order, each time you either fit a toy into a box, or discard a toy, or discard a box. Constraints: cnt is at most 10^12, type is no more than 100, list A and B has length no more than 100.
The round 1B problem looks like the NP-hard problem subset sum and it seems impossible to deal with 500 items with value as large as 10^12. The well-known solutions either enumerates all 2^n subsets or build a table with dp[n][sum]. Neither of them works here. However, read the constraints again. It says EXACTLY 500 items, why didn't it say at most 500? Why having more items helps?
OK, you know that each item is no more than 10^12, so you do not have many different sums, in fact, no more than 500*10^12=500*10^14. On the other hand you have 2^500 = 10^150 different subsets which is way bigger.
The solution builds on all 6-element subsets. The number of sums is no more than 6*10^12, and the number of sets is 500^6 = 10^16, so you have a good chance to hit two subsets with same sum if you pick two random subsets. And the algorithm simply shuffle the input integers, and keep enumerating 6-element subsets until you have two subsets with equal sum. The time limit is 8min which is more than enough. My naive implementation runs in 4min.
The round 1C problem is about longest common subsequence, or LCS, except that the two lists are a bit long, could be 100*10^12 items, and the usual dp approach just won't work. However you can observe the special arrangement of this problem and tweak the algorithm a bit. The recurrence looks like this:
dp[i][j] = max(dp[i][j-1], dp[i-1][j], dp[i-1][j-1] + 1)
And the last case applies only when type at a[i] matches type at b[j]. In this problem, if type of a[i] and b[j] mismatch, then we do the same since the optimal solution end at a[i],b[j] has to discard either a[i] or b[j]. However, if they do agree on type, then we have to run this particular type from i to some prior position x, and run from j to some prior position y, so we update dp[i][j] by dp[x][y] + min(count of type in a[x+1..i], count of type in b[y+1..j]) and the count can be obtained by maintaining a prefix sum.
And that was it. The large case runs in 20s.
round 1B, problem C, you are given exactly 500 positive integers, each no more than 10^12, find two subsets with equal sum.
round 1C, problem C, you are given two lists, list A has a sequence of
The round 1B problem looks like the NP-hard problem subset sum and it seems impossible to deal with 500 items with value as large as 10^12. The well-known solutions either enumerates all 2^n subsets or build a table with dp[n][sum]. Neither of them works here. However, read the constraints again. It says EXACTLY 500 items, why didn't it say at most 500? Why having more items helps?
OK, you know that each item is no more than 10^12, so you do not have many different sums, in fact, no more than 500*10^12=500*10^14. On the other hand you have 2^500 = 10^150 different subsets which is way bigger.
The solution builds on all 6-element subsets. The number of sums is no more than 6*10^12, and the number of sets is 500^6 = 10^16, so you have a good chance to hit two subsets with same sum if you pick two random subsets. And the algorithm simply shuffle the input integers, and keep enumerating 6-element subsets until you have two subsets with equal sum. The time limit is 8min which is more than enough. My naive implementation runs in 4min.
The round 1C problem is about longest common subsequence, or LCS, except that the two lists are a bit long, could be 100*10^12 items, and the usual dp approach just won't work. However you can observe the special arrangement of this problem and tweak the algorithm a bit. The recurrence looks like this:
dp[i][j] = max(dp[i][j-1], dp[i-1][j], dp[i-1][j-1] + 1)
And the last case applies only when type at a[i] matches type at b[j]. In this problem, if type of a[i] and b[j] mismatch, then we do the same since the optimal solution end at a[i],b[j] has to discard either a[i] or b[j]. However, if they do agree on type, then we have to run this particular type from i to some prior position x, and run from j to some prior position y, so we update dp[i][j] by dp[x][y] + min(count of type in a[x+1..i], count of type in b[y+1..j]) and the count can be obtained by maintaining a prefix sum.
And that was it. The large case runs in 20s.
Saturday, May 12, 2012
TCO 2B
Much easier than 2A, although I end up with -25.
p250, just keep the known ones in a set and do the processing.
you can use max in the known,
or use some prefix of unknown and the rest maxKnown,
or use several copies of all unknown and prefix + maxKnown.
My bug? I wrote
for(int k=1; k<=N && r>0; ++k, r-=k, ans++)
But in r-=k I need the k value before ++.
A hard lesson that cost my p250.
p500, the game is completely determined by move[0]. After deciding the partition of move[0] numbers, the rest is just a dp to pick best subset. The implementation is nontrivial and I need maybe 15min more to complete.
p250, just keep the known ones in a set
you can use max in the known,
or use some prefix of unknown and the rest maxKnown,
or use several copies of all unknown and prefix + maxKnown.
My bug? I wrote
for(int k=1; k<=N && r>0; ++k, r-=k, ans++)
But in r-=k I need the k value before ++.
A hard lesson that cost my p250.
p500, the game is completely determined by move[0]. After deciding the partition of move[0] numbers, the rest is just a dp to pick best subset. The implementation is nontrivial and I need maybe 15min more to complete.
Saturday, May 5, 2012
CodeSprint TwitchTV
This is an interview street codesprint challenge and I started really late, sometime around 3pm and the contest is between 12-4pm. Luckily I got the second one fairly quick, and then realized that the first one is bipartite matching. The third one is Floyd-Warshall with greedy. I don't know about 4th one. It surprised me a bit to see my bipartitie matching code passed in the first submission, after checked the trivial test case.
Travel: the only problem I do not have a solution.
UPDATE: Apparently it is Bellman-Ford (I don't know why I keep calling this one Boyer-Moore, which is for string matching), the dynamic programming shortest path algorithm. The only tricky point is that you need to pay toll, so let node[i] be the gold you have at i, then the update step from i to j is
node[j] = max(node[j], (node[i]-edge[i][j]+s[j]) /2)
The problem statement is not very clear on this. Here node[i] is the max gold you can have at node i. Also note that you cannot have unbounded gold at any node as max among all node[i], let it be node[k], will not improve once passed its own s[k] so the updating process cannot continue indefinitely.
Arrangement: the problem is about finding hamitonian path and with N=1000 there is no hope to solve it exactly. And that is why the problem says it is an approximate problem. I didn't have time to implement some backtrack solution but it would be interesting to try some heuristics. Given 3 more hours, I could have done better.
Anyway I am happy with my score and interesting enough, why this particular company cares so much about graph algorithms.
Update: I finished a naive dfs backtrack solution to the last problem, Arrangement, which asks for a Hamitonian path given a graph. Surprisingly, it got Accepted.
The score board and my rank
Travel: the only problem I do not have a solution.
UPDATE: Apparently it is Bellman-Ford (I don't know why I keep calling this one Boyer-Moore, which is for string matching), the dynamic programming shortest path algorithm. The only tricky point is that you need to pay toll, so let node[i] be the gold you have at i, then the update step from i to j is
node[j] = max(node[j], (node[i]-edge[i][j]+s[j]) /2)
The problem statement is not very clear on this. Here node[i] is the max gold you can have at node i. Also note that you cannot have unbounded gold at any node as max among all node[i], let it be node[k], will not improve once passed its own s[k] so the updating process cannot continue indefinitely.
Arrangement: the problem is about finding hamitonian path and with N=1000 there is no hope to solve it exactly. And that is why the problem says it is an approximate problem. I didn't have time to implement some backtrack solution but it would be interesting to try some heuristics. Given 3 more hours, I could have done better.
Anyway I am happy with my score and interesting enough, why this particular company cares so much about graph algorithms.
Update: I finished a naive dfs backtrack solution to the last problem, Arrangement, which asks for a Hamitonian path given a graph. Surprisingly, it got Accepted.
The score board and my rank
| Rank | Hacker | Country | Score | Submissions | Solved |
|---|---|---|---|---|---|
| 31 | lantimilan | USA | 300.00 | 4 | 3 |
| Name | Points | Status | Statistics  |
|||
|---|---|---|---|---|---|---|
| Super Bomb | 100 | 
|
40/580 | |||
| Matching | 100 |
|
43/630 | |||
| Centre of Mass | 100 |
|
47/297 | |||
| Travel | 100 | 
|
29/63 | |||
| Arrangement | 100 |
|
14/271 |
Codeforces Round #118 (Div. 2)
This one has some easy problems and I got lucky in google problem D, and no one solved E. My highest rank in div2, and got a huge boost in rating.
Candidate Master lantimilan
Li Yan, Riverside, CA, United States (USA)
Online
-
Contest rating:
1735
| 10 |
lantimilan
|
4194 | 492 00:04 | 924 00:19 | 1290 00:35 | 1488 01:04 |
Friday, May 4, 2012
AM-GM inequality
In today's codeforces match, there is a problem ask for x,y,z such that
x+y+z = S for a given S
to maximize x^a * y^b * z^c
peter50216 points out AM-GM inequality applies to this problem.
for a, b, c > 0
S = x+y+z = a*x/a + b*y/b + c*z/c >= ((x/a)^a * (y/b)^b * (z/c)^c)^(1/abc)
and equality holds when x/a = y/b = z/c = (x+y+z)/(a+b+c)
x+y+z = S for a given S
to maximize x^a * y^b * z^c
peter50216 points out AM-GM inequality applies to this problem.
for a, b, c > 0
S = x+y+z = a*x/a + b*y/b + c*z/c >= ((x/a)^a * (y/b)^b * (z/c)^c)^(1/abc)
and equality holds when x/a = y/b = z/c = (x+y+z)/(a+b+c)
Thursday, May 3, 2012
bash if
The if constructs in bash is a convenient tool if you know how to use it
conditions are inside [ ], which is equivalent to test command
== and related are for strings
-gt -ne for numeric comparison
-a -o for and or
if [ -f /var/log/message ]; then echo "message exists"; fi
[ "$(whoami)" != 'root' ] && (echo you are using non-privileged account; exit 1)
test "$(whoami)" != 'root' && (echo you are using non-privileged account; exit 1)
conditions are inside [ ], which is equivalent to test command
== and related are for strings
-gt -ne for numeric comparison
-a -o for and or
if [ -f /var/log/message ]; then echo "message exists"; fi
[ "$(whoami)" != 'root' ] && (echo you are using non-privileged account; exit 1)
test "$(whoami)" != 'root' && (echo you are using non-privileged account; exit 1)
Wednesday, May 2, 2012
A silly RSA implementation
A while ago I had a homework to implement RSA and each letter is raised to the e-th power where e is the public key, modulo N=pq. Decryption is by raise each integer in cipher text C to the d-th power where d is the secret key. The problem? Since we have only 256 ascii characters and if each char is mapped to a distinct integer, then you do NOT need e or d or whatever key to decrypt, you only need a mapping from char to integer.
One remedy approach is to group adjacent char into blocks so you will need a mapping of 256^10 = 2^80 if you group letters in block of 10, and this is much harder to keep a mapping.
One remedy approach is to group adjacent char into blocks so you will need a mapping of 256^10 = 2^80 if you group letters in block of 10, and this is much harder to keep a mapping.
Strongly Connected Components
The Tarjan's algorithm does two passes of DFS, and I keep forgetting the algorithm. Now that I have to look it up again, here are some intuitions.
SCC for directed graph.
Let us begin with a DFS tree. You know that if you can reach your ancestor, then both of you are in the same component. To check if some node y is your ancestor, and you are x, then dfsbegin[y] < dfsbegin[x] and dfsfinish[y] < dfsfinish[x], that is, you start later and finish early, then whoever has an interval covers your interval is your ancestor.
Now consider a node y, we know that y can reach x for every x that is its descendant. If we start from x and there is a path to y, then we can assign x to y. However we do not want to start from every x as it is too slow. Now comes the reverse edge trick. A path from x to y is equivalent to a path from y to x if we reverse every edge in the graph. If we do that, every tree edge and forward edge become back edge, and the previous back edge becomes either tree edge or forward edge but that does not bother us since they are not involved in finding components. The annoying edge is cross edge, which must go from right to left in the original graph, now they have to go from left to right after reverse. Then we can finish components on the right before work on the left so we will detect a node already assigned to a different component when hitting a cross edge. One way to achieve this is to process nodes with decreasing order of dfsfinish[x].
SCC for directed graph.
Let us begin with a DFS tree. You know that if you can reach your ancestor, then both of you are in the same component. To check if some node y is your ancestor, and you are x, then dfsbegin[y] < dfsbegin[x] and dfsfinish[y] < dfsfinish[x], that is, you start later and finish early, then whoever has an interval covers your interval is your ancestor.
Now consider a node y, we know that y can reach x for every x that is its descendant. If we start from x and there is a path to y, then we can assign x to y. However we do not want to start from every x as it is too slow. Now comes the reverse edge trick. A path from x to y is equivalent to a path from y to x if we reverse every edge in the graph. If we do that, every tree edge and forward edge become back edge, and the previous back edge becomes either tree edge or forward edge but that does not bother us since they are not involved in finding components. The annoying edge is cross edge, which must go from right to left in the original graph, now they have to go from left to right after reverse. Then we can finish components on the right before work on the left so we will detect a node already assigned to a different component when hitting a cross edge. One way to achieve this is to process nodes with decreasing order of dfsfinish[x].
Thursday, April 26, 2012
On Binary Search
Recently failed a quixey challenge on binary search and went over the Knuth v3, although the notes below are from some code I have seen before.
Everybody knows binary search, but not good enough to write a perfect one.
Here the problem asks for something similar to c++ stl lower_bound
Given a[0..n-1] with a[0]<= a[1] <=... <= a[n-1], and int x, return pos such that if we insert x at pos, the order of a[] is preserved, that is, pos is such that
a[0]<= a[1] <=... <= a[pos-1] <= x < a[pos] <= ... <= a[n-1]
The version presented below has the invariants:
Everybody knows binary search, but not good enough to write a perfect one.
Here the problem asks for something similar to c++ stl lower_bound
Given a[0..n-1] with a[0]<= a[1] <=... <= a[n-1], and int x, return pos such that if we insert x at pos, the order of a[] is preserved, that is, pos is such that
a[0]<= a[1] <=... <= a[pos-1] <= x < a[pos] <= ... <= a[n-1]
The version presented below has the invariants:
- 1. m is a valid index, that is, 0 <= m < n
- 2. each iteration, either l or u gets updated.
- 3. a[l] < x and a[u] <= x. This is done by using phantom element a[-1] and a[n]
- 4. Inside loop, l < m < n
- 5. Outside loop, l+1=u
binsearch(a[0..n-1], int x) // returns first pos such that a[pos]>=x
l=-1, u=n
while l+1 < u m = (l+u)/2 if (a[m]
CF 182
The number is different from the actual round number, but refers to the final problem set index.
A: Shortest Path, Dijkstra.
B: easy, just add a fixed offset and you get the answer.
C: you are given an array of n int, n=10^5, and a number k, a number len, you are to compute the maximum sum (sum of int, then take abs of the sum), with the condition that you can flip at most k int in the current window of size=len. It is a typical problem with 1D array and sliding fixed-length window. You can query min in current window in O(n) time. But this problem is a bit different. This kind of problem is about what you need to remember in the past elements.
This solution is from watashi's code. When you are dealing with current window, you know you can flip signs of k numbers, and they must be same sign, all + or all -, so you need only the best k positives, and the best k negatives. But how do you update that information as the window slides to the right. Well, you need to drop one element x=a[pos-len] and you have one more element y=a[pos]. So if x is in top k, then x needs to be removed, after that you may need to put back the best one in remaining elements in a[pos-len+1] to a[pos-1] into top k. Now check y, if y can make into top k, then send y into top k, as a result the min in top k will get kicked out and you put it to the reserve. With that you can maintain a BST with count of appearance in each element. A multiset or a map comes in handy.
D: compute the number of factors between two strings, s1 and s2, with length up to 10^5. My approach is fairly complicated and I am a bit surprised to see it get AC. Basically I compute a gcd of s1 and s2, then get all factors of that gcd. To do a gcd in strings, assume s1 is longer. then keep taking s2 from s1 until it is no longer possible. Then the remaining s1, if still longer than s2, you know gcd is empty string. Otherwise let swap s1, s2 and keep going. To get all factors of gcd, simply try all factors of gcd.length() and this could take 10^5 * sqrt(10^5) = 10^7 which is fast enough, since n has at most O(sqrt(n)) factors. Actually this number is an over-estimate, as I tested numbers up to 10^7, the max is only about 500.
E: combinatorial counting and needs a DP solution. The problem statement is wrong but there are 200+ people got AC. It seems they can read the problem setter's mind to see what solution is intended. Actually that's exactly what you need to have when dealing with a DP problem.
A: Shortest Path, Dijkstra.
B: easy, just add a fixed offset and you get the answer.
C: you are given an array of n int, n=10^5, and a number k, a number len, you are to compute the maximum sum (sum of int, then take abs of the sum), with the condition that you can flip at most k int in the current window of size=len. It is a typical problem with 1D array and sliding fixed-length window. You can query min in current window in O(n) time. But this problem is a bit different. This kind of problem is about what you need to remember in the past elements.
This solution is from watashi's code. When you are dealing with current window, you know you can flip signs of k numbers, and they must be same sign, all + or all -, so you need only the best k positives, and the best k negatives. But how do you update that information as the window slides to the right. Well, you need to drop one element x=a[pos-len] and you have one more element y=a[pos]. So if x is in top k, then x needs to be removed, after that you may need to put back the best one in remaining elements in a[pos-len+1] to a[pos-1] into top k. Now check y, if y can make into top k, then send y into top k, as a result the min in top k will get kicked out and you put it to the reserve. With that you can maintain a BST with count of appearance in each element. A multiset or a map comes in handy.
D: compute the number of factors between two strings, s1 and s2, with length up to 10^5. My approach is fairly complicated and I am a bit surprised to see it get AC. Basically I compute a gcd of s1 and s2, then get all factors of that gcd. To do a gcd in strings, assume s1 is longer. then keep taking s2 from s1 until it is no longer possible. Then the remaining s1, if still longer than s2, you know gcd is empty string. Otherwise let swap s1, s2 and keep going. To get all factors of gcd, simply try all factors of gcd.length() and this could take 10^5 * sqrt(10^5) = 10^7 which is fast enough, since n has at most O(sqrt(n)) factors. Actually this number is an over-estimate, as I tested numbers up to 10^7, the max is only about 500.
E: combinatorial counting and needs a DP solution. The problem statement is wrong but there are 200+ people got AC. It seems they can read the problem setter's mind to see what solution is intended. Actually that's exactly what you need to have when dealing with a DP problem.
Monday, April 23, 2012
TC SRM 541
p250: 50 ants move in grid, when two or more meet at same point, they disappear. each move at speed 1, and no two start at same position. The problem asks for number of ants remaining. Coordinates are from -1000 to 1000.
The only problem I know how to solve, basically after some limit, if two ants still not meet, they will never meet. So just iterate some fixed number of steps. The question is, what is the limit?
Since ants could meet at half way of an integer position, you need to multiply all coordinately by 2 so that they all meet in integer position. The limit is then (1000 - (-1000))/0.5 = 4000, to be safe you can use 4010 or 5000.
exod40 uses a different check, if (ox[i],oy[i]), (ox[j],oy[j) becomes (ox[j],oy[j]) (ox[i],oy[i]), that is, if two ants swap position, then they have to meet. the converse is true as well. so you can check that instead of multiply coordidates by 2.
The only problem I know how to solve, basically after some limit, if two ants still not meet, they will never meet. So just iterate some fixed number of steps. The question is, what is the limit?
Since ants could meet at half way of an integer position, you need to multiply all coordinately by 2 so that they all meet in integer position. The limit is then (1000 - (-1000))/0.5 = 4000, to be safe you can use 4010 or 5000.
exod40 uses a different check, if (ox[i],oy[i]), (ox[j],oy[j) becomes (ox[j],oy[j]) (ox[i],oy[i]), that is, if two ants swap position, then they have to meet. the converse is true as well. so you can check that instead of multiply coordidates by 2.
Sunday, April 15, 2012
vim line wrap or line break
When editing text files, you might want vi/vim to insert line break automatically.
:set textwidth=60
To format a paragraph, move cursor anywhere inside the paragraph, type gqip or gqap
:set textwidth=60
To format a paragraph, move cursor anywhere inside the paragraph, type gqip or gqap
Thursday, April 12, 2012
all about bibtex and style
BibTeX and bibliography styles
http://amath.colorado.edu/documentation/LaTeX/reference/faq/bibstyles.html
http://en.wikibooks.org/wiki/LaTeX/Packages/Installing_Extra_Packages
Something called biblatex, in experiment
http://amath.colorado.edu/documentation/LaTeX/reference/faq/bibstyles.html
http://en.wikibooks.org/wiki/LaTeX/Packages/Installing_Extra_Packages
Something called biblatex, in experiment
Wednesday, April 4, 2012
TCO qual 1A
Got a bit lucky and qualified in round 1A.
p250, easy if you see 2 counts are enough to win. An edge case is when there is only 1 player.
p500, if you see prime factoring, you got the problem. I am just slow in implementing it.
p1000, easy in algorithm but hard in implementation. Has some connection with 2SAT but you do not need that knowledge. I had the right algorithm but took two days to finalize the details of implementation. Guess my recursion/dfs implementation skills are terrible.
Here is my solution (offline)
p250, easy if you see 2 counts are enough to win. An edge case is when there is only 1 player.
p500, if you see prime factoring, you got the problem. I am just slow in implementing it.
p1000, easy in algorithm but hard in implementation. Has some connection with 2SAT but you do not need that knowledge. I had the right algorithm but took two days to finalize the details of implementation. Guess my recursion/dfs implementation skills are terrible.
Here is my solution (offline)
#include <vector>
#include <string>
#include <iostream>
using namespace std;
#define MAX 1000
#define sz(a) int(a.size())
int bulb[60][5], state[60], tmp[60];
string initial;
vector<string> switches;
class EllysLights {
public:
int getMinimum(string _initial, vector <string> _switches);
};
bool dfs(int j, int st)
{
tmp[j]=st;
// check all bulbs
for(int i=0; i<sz(initial); ++i) if (switches[j][i]=='Y') {
int next;
if (bulb[i][1]<0) { // bulb has one switch
if (st == 0 && initial[i]=='N') {}
else if (st == 1 && initial[i]=='Y') {}
else return false;
}
else { // bulb has two switch
next = bulb[i][0]; if (next==j) next = bulb[i][1];
int target;
if (initial[i]=='N') target = st;
else target = 1-st;
if (tmp[next]>=0) { // hit a visited switch
if (tmp[next]!=target) return false;
}
else {
if (!dfs(next, target)) return false;
}
}
}
return true;
}
int check(int j, int st)
{
memset(tmp, -1, sizeof tmp);
int ans=0;
if (dfs(j, st)) {
for(int k=0; k<sz(switches); ++k)
ans += (tmp[k]==1);
return ans;
}
return MAX;
}
int EllysLights::getMinimum(string _initial, vector <string> _switches)
{
int ans=0;
initial=_initial; switches=_switches;
memset(state, -1, sizeof state);
// construct bulb
memset(bulb, -1, sizeof bulb);
for(int i=0; i<sz(initial); ++i) {
int c=0;
for(int j=0; j<sz(switches); ++j) {
if (switches[j][i]=='Y') bulb[i][c++]=j;
}
}
for(int i=0; i<sz(initial); ++i) {
if (bulb[i][0]<0 && initial[i]=='Y') return -1;
}
for(int j=0; j<sz(switches); ++j) if (state[j]<0) {
int aa, bb;
aa = check(j, 0); for(int k=0; k<sz(switches); ++k) if (tmp[k]>=0) state[k]=tmp[k];
bb = check(j, 1);
if (bb < aa) {
for(int k=0; k<sz(switches); ++k) if (tmp[k]>=0) state[k]=tmp[k];
}
ans += min(aa, bb);
// cout << "switch " << j << ' ' << state[j] << ' ' << ans << endl;
}
if (ans <= sz(switches))
return ans;
else
return -1;
}
Tuesday, April 3, 2012
a probability problem
A robot enters a room with a large number of coins on the floor. It flips a coin if it is head, and toss a coin if it is tail. The problem asks what is the ratio of head to tail after sufficiently long time.
solution:
since we only need the ratio we might as well assume head=1-t and tail=t to begin with.
Then we work out a few iterations to see the pattern
(1-t, t)
(t/2, 1-t/2)
(1/2-t/4, 1/2+t/4)
(1/4+t/8, 3/4-t/8)
(3/8-t/16, 5/8+t/16)
(5/16+t/32, 11/16-t/32)
This should give enough evidence that whatever t you start with, the end ratio does not depend on t.
And to compute the final ratio, we can drop t and go through a few more calculations.
(21/64, 43/64)
(43/128, 1-43/128)
Now it is much clear that the sequence converges to some number. And what is the fixed point?
Let (x, 1-x) be a fixed point, one more iteration will make it 1/2*(1-x) and 1-1/2*(1-x)
Then we have x = 1/2*(1-x) and solve x=1/3, it satisfies the other equation as well. It is almost obvious that if you start with (1/3, 2/3) you next iteration must be 2/3*1/2=1/3 and 1-1/3=2/3, where you start with.
So the answer is 1 to 2.
One more problem,
you have 50 shoe laces so there are 100 ends. You randomly tie two ends until you finish tying all 100 ends. What is the expected number of cycles?
Solution:
First we work out small examples:
n=1 ans=1
n=2 ans=1+1/3, with prob=1/3 the first lace will tie at both ends so we have 2 cycles, with prob=2/3, we have 1 cycle.
Now try to generalize. Treat each end as a vertex and the lace and the tying as edges, we have each vertex having deg=2, so they form a collection of disjoint cycles. Therefore we have a one-to-one mapping from cycles in n=k-1 to n=k, assuming the k-th lace does not have its two ends tied together. In this case we have expectation = E[n=k-1], and the other case is that we have one extra cycle, that part = 1/(2*k-1) * 1,
So the answer is
1 + 1/3 + 1/5 + 1/7 + ... + 1/(2*n-1)
solution:
since we only need the ratio we might as well assume head=1-t and tail=t to begin with.
Then we work out a few iterations to see the pattern
(1-t, t)
(t/2, 1-t/2)
(1/2-t/4, 1/2+t/4)
(1/4+t/8, 3/4-t/8)
(3/8-t/16, 5/8+t/16)
(5/16+t/32, 11/16-t/32)
This should give enough evidence that whatever t you start with, the end ratio does not depend on t.
And to compute the final ratio, we can drop t and go through a few more calculations.
(21/64, 43/64)
(43/128, 1-43/128)
Now it is much clear that the sequence converges to some number. And what is the fixed point?
Let (x, 1-x) be a fixed point, one more iteration will make it 1/2*(1-x) and 1-1/2*(1-x)
Then we have x = 1/2*(1-x) and solve x=1/3, it satisfies the other equation as well. It is almost obvious that if you start with (1/3, 2/3) you next iteration must be 2/3*1/2=1/3 and 1-1/3=2/3, where you start with.
So the answer is 1 to 2.
One more problem,
you have 50 shoe laces so there are 100 ends. You randomly tie two ends until you finish tying all 100 ends. What is the expected number of cycles?
Solution:
First we work out small examples:
n=1 ans=1
n=2 ans=1+1/3, with prob=1/3 the first lace will tie at both ends so we have 2 cycles, with prob=2/3, we have 1 cycle.
Now try to generalize. Treat each end as a vertex and the lace and the tying as edges, we have each vertex having deg=2, so they form a collection of disjoint cycles. Therefore we have a one-to-one mapping from cycles in n=k-1 to n=k, assuming the k-th lace does not have its two ends tied together. In this case we have expectation = E[n=k-1], and the other case is that we have one extra cycle, that part = 1/(2*k-1) * 1,
So the answer is
1 + 1/3 + 1/5 + 1/7 + ... + 1/(2*n-1)
Sunday, March 25, 2012
SRM 537 div2 clear
p925, find prerequisite chain and compute each element individually.
ans = sum of each a[i]
ans for a[i] = 1.0/length of prerequisite chain, if loop, then 0.0
ans = sum of each a[i]
ans for a[i] = 1.0/length of prerequisite chain, if loop, then 0.0
Monday, March 19, 2012
latex save/squeeze spacing
http://www.eng.cam.ac.uk/help/tpl/textprocessing/squeeze.html
algorithm environment
http://en.wikibooks.org/wiki/LaTeX/Algorithms_and_Pseudocode#The_algorithm_environment
display math
http://www.math.uiuc.edu/~hildebr/tex/displays.html
algorithm environment
http://en.wikibooks.org/wiki/LaTeX/Algorithms_and_Pseudocode#The_algorithm_environment
display math
http://www.math.uiuc.edu/~hildebr/tex/displays.html
Saturday, March 17, 2012
notes on linked list
Things that are simple and easy for arrays might get messy in linked list and debugging is harder.
Some tips:
1. know the primitives
delete after prev: prev->next = prev->next->next
if you need prev->next, save the pointer.
it is usually simpler to have a dummy node so you always have a valid prev pointer.
insert p after prev: p->next = prev->next; prev->next = p;
2. maintain a tail pointer if necessary
for(p=head; p->next != NULL; p=p->next) ;
tail = p; // since p->next is NULL after loop terminates, p is tail now
when recursion, consider returning both head and tail pointer, otherwise you might have to walk through the list one more time to reach tail pointer.
3. have a conceptual picture
when doing things like reverse list, sort list, split into odd even, it is usually easier to have separate heads of lists, and you remove nodes from the input list, and grow lists in the output list.
an example is sorting, say selection sort.
you keep removing max node from input list, and insert into head of output list.
4. check NULL whenever you want to dereference using ->
5. do initialization properly, if you need to get min node or max node, initialize the minval and ptr2minval with the first node.
6. draw a picture to help with the links.
7. walk the list with two pointers make the code simpler, an example is mergesort when you need to split the list into two halves.
for(p1=head, p2=head->next; p2!=NULL && p2->next!=NULL; p1=p1->next, p2=p2->next->next) ;
p2 = p1->next; p1->next = NULL; p1=head;
it is easy to show that when length is even, then we cut after pos=(n/2)-1 with length n/2 in each half,
when length is odd, the first half ends at pos=(n-1)/2 with length=(n+1)/2
since p1 always walks floor((n-1)/2) steps.
and for mergesort, the merge step ends with appending p1 or p2 to output list and it is simply tail->next = p1 or p2
Some tips:
1. know the primitives
delete after prev: prev->next = prev->next->next
if you need prev->next, save the pointer.
it is usually simpler to have a dummy node so you always have a valid prev pointer.
insert p after prev: p->next = prev->next; prev->next = p;
2. maintain a tail pointer if necessary
for(p=head; p->next != NULL; p=p->next) ;
tail = p; // since p->next is NULL after loop terminates, p is tail now
when recursion, consider returning both head and tail pointer, otherwise you might have to walk through the list one more time to reach tail pointer.
3. have a conceptual picture
when doing things like reverse list, sort list, split into odd even, it is usually easier to have separate heads of lists, and you remove nodes from the input list, and grow lists in the output list.
an example is sorting, say selection sort.
you keep removing max node from input list, and insert into head of output list.
4. check NULL whenever you want to dereference using ->
5. do initialization properly, if you need to get min node or max node, initialize the minval and ptr2minval with the first node.
6. draw a picture to help with the links.
7. walk the list with two pointers make the code simpler, an example is mergesort when you need to split the list into two halves.
for(p1=head, p2=head->next; p2!=NULL && p2->next!=NULL; p1=p1->next, p2=p2->next->next) ;
p2 = p1->next; p1->next = NULL; p1=head;
it is easy to show that when length is even, then we cut after pos=(n/2)-1 with length n/2 in each half,
when length is odd, the first half ends at pos=(n-1)/2 with length=(n+1)/2
since p1 always walks floor((n-1)/2) steps.
and for mergesort, the merge step ends with appending p1 or p2 to output list and it is simply tail->next = p1 or p2
SRM 537
This SRM has cash award so it attracted a lot coders. I have to wake up at 6:00am and register myself.
p275 is easy. Given A, B positive integer, and X positive integer, count number of positive Y != X such that (X,Y) can generate all linear combination of (A,B), and we only accept A*a + B*b for a,b>=0. If there are infinitely many Y, return -1.
First it is easy to see when -1 occur. Only when X divides both A and B, then we do not need Y at all. Easy check, A % X == 0 && B % X ==0. I ended up coding a gcd, which is a bit overkill.
Then we need to enumerate all possible Y's since A, B and X are all small, at most 200. Notice that for Y to be valid, (X,Y) has to be able to generate A and B, and if that is true, then (X,Y) can generate all integers representable by (A,B). For this purpose Y cannot be bigger than max(A,B) so we only try Y=1 to max(A,B). For each Y, we check whether both A and B are representable.
ans=0;
for Y=1 to max(A,B)
aok = bok = false;
for(a=0; a*X <= A; ++a)
if ((A-a*X) % Y == 0) // A is good
aok = true;
for(b=0; b*X <= B; ++b)
if ((B-b*X) % Y == 0) // B is good
bok=true;
if (aok && bok)
ans++;
return ans;
p500 is a DP problem, and everybody knows that. The problem is:
given ducks[N] which are ducks in room 0 to N-1, with N at most 50.
there are two spells, spellOne[i] makes ducks[i] turn into ducks[i] xor spellOne[i]
spellTwo[i] will move ducks[i] into ducks[spellTwo[i]] and it is a permutation.
In each day spellOne and spellTwo occur with prob=0.5. After K days, with K at most 50, what is the expected number of ducks in room[0].
We all know linearity of expectation, but we cannot really apply xor to doubles. Now what?
The trick is to consider each bit of an integer separately, as ducks[i] is at most 10^9, so 30 bits suffices. We know the operation of xor if we have only one bit.
Now we have a DP[k][i][b] means probability of ducks in room[i] being 1 after k days, when only bit b is considered. And the transition is
DP[k][i][b] +=
// spellOne
if spellOne[i] is one at bit[b]
0.5 * (1.0 - DP[k-1][i][b])
else
0.5 * DP[k-1][i][b]
// spellTwo
DP[k][spellTwo[i]][b] += 0.5 * DP[k-1][i][b]
In the end we combine all bits
for b=0 to 30-1
ans += (1<<b) * DP[K][0][b]
return ans;
p1000, asks for longest circular dominos and I did not quite understand the problem, the solution is mincost flow, though.
Got a rating boost by solving p250, boosted from 1332 to 1409.
p275 is easy. Given A, B positive integer, and X positive integer, count number of positive Y != X such that (X,Y) can generate all linear combination of (A,B), and we only accept A*a + B*b for a,b>=0. If there are infinitely many Y, return -1.
First it is easy to see when -1 occur. Only when X divides both A and B, then we do not need Y at all. Easy check, A % X == 0 && B % X ==0. I ended up coding a gcd, which is a bit overkill.
Then we need to enumerate all possible Y's since A, B and X are all small, at most 200. Notice that for Y to be valid, (X,Y) has to be able to generate A and B, and if that is true, then (X,Y) can generate all integers representable by (A,B). For this purpose Y cannot be bigger than max(A,B) so we only try Y=1 to max(A,B). For each Y, we check whether both A and B are representable.
ans=0;
for Y=1 to max(A,B)
aok = bok = false;
for(a=0; a*X <= A; ++a)
if ((A-a*X) % Y == 0) // A is good
aok = true;
for(b=0; b*X <= B; ++b)
if ((B-b*X) % Y == 0) // B is good
bok=true;
if (aok && bok)
ans++;
return ans;
p500 is a DP problem, and everybody knows that. The problem is:
given ducks[N] which are ducks in room 0 to N-1, with N at most 50.
there are two spells, spellOne[i] makes ducks[i] turn into ducks[i] xor spellOne[i]
spellTwo[i] will move ducks[i] into ducks[spellTwo[i]] and it is a permutation.
In each day spellOne and spellTwo occur with prob=0.5. After K days, with K at most 50, what is the expected number of ducks in room[0].
We all know linearity of expectation, but we cannot really apply xor to doubles. Now what?
The trick is to consider each bit of an integer separately, as ducks[i] is at most 10^9, so 30 bits suffices. We know the operation of xor if we have only one bit.
Now we have a DP[k][i][b] means probability of ducks in room[i] being 1 after k days, when only bit b is considered. And the transition is
DP[k][i][b] +=
// spellOne
if spellOne[i] is one at bit[b]
0.5 * (1.0 - DP[k-1][i][b])
else
0.5 * DP[k-1][i][b]
// spellTwo
DP[k][spellTwo[i]][b] += 0.5 * DP[k-1][i][b]
In the end we combine all bits
for b=0 to 30-1
ans += (1<<b) * DP[K][0][b]
return ans;
p1000, asks for longest circular dominos and I did not quite understand the problem, the solution is mincost flow, though.
Got a rating boost by solving p250, boosted from 1332 to 1409.
Thursday, March 15, 2012
bst to doubly linked list
// =========================================================
//
// Filename: bst2list.cpp
//
// Description: convert a bst to a linked list
//
// Version: 1.0
// Created: 03/15/2012 10:21:02 PM
// Revision: none
// Compiler: g++
//
// Author: LI YAN (lyan), lyan@cs.ucr.edu
// Company: U of California Riverside
// Copyright: Copyright (c) 03/15/2012, LI YAN
//
// =========================================================
#include <cstdio>
using namespace std;
struct node {
int val;
node *left, *right; // for bst, it is lchild and rchild, for doubly linked list, it is prev and succ
};
node* bst2list(node *root)
{
if (root==NULL) return NULL;
node *subleft = bst2list(root->left);
node *subright = bst2list(root->right);
root->left = root->right = root;
node *head, *tail, *ltail, *rtail;
head=root;
if (subleft) {
ltail = subleft->left; tail=head->left;
ltail->right = head; head->left = ltail;
subleft->left = tail; tail->right = subleft;
head = subleft;
}
if (subright) {
tail=head->left; rtail = subright->left;
tail->right = subright; subright->left = tail;
head->left = rtail; rtail->right = head;
}
return head;
}
void print(node *root)
{
if (root==NULL) return;
print(root->left);
printf(" %d", root->val);
print(root->right);
}
void printlist(node *head)
{
if (head==NULL) return;
node *p=head;
do {
printf("%d ", p->val);
p=p->right;
} while (p!=head);
}
int main()
{
node a[100];
for(int i=0; i<10; ++i) {
if (2*i+1<10) a[i].left=&a[2*i+1];
else a[i].left = NULL;
if (2*i+2<10) a[i].right=&a[2*i+2];
else a[i].right = NULL;
}
// expected: true
int v[] = { 500, 200, 800, 100, 300, 600, 900, 50, 150, 280};
// expected: false
//int v[] = { 500, 200, 800, 100, 300, 600, 900, 50, 150, 350};
for(int i=0; i<10; ++i) {
a[i].val = v[i];
}
node *root=&a[0];
puts("input");
print(root); putchar('\n');
puts("convert to list");
node *head=bst2list(root);
printlist(head); putchar('\n');
}
check binary tree being binary search tree
// =========================================================
//
// Filename: bstcheck.cpp
//
// Description: check whether a binary tree is a binary search tree (BST)
//
// Version: 1.0
// Created: 03/15/2012 10:14:03 PM
// Revision: none
// Compiler: g++
//
// Author: LI YAN (lyan), lyan@cs.ucr.edu
// Company: U of California Riverside
// Copyright: Copyright (c) 03/15/2012, LI YAN
//
// =========================================================
#include <cstdio>
using namespace std;
struct node {
int val;
node *left, *right;
};
// check left, check right
// also need min and max of this subtree
//
bool checkbst(node *root, int &vmin, int &vmax)
{
if (root==NULL) return true;
int a1, b1, a2, b2;
vmin=vmax=root->val;
if (root->left != NULL) {
bool bleft = checkbst(root->left, a1, b1);
if (!bleft) return false;
if (b1>root->val) return false;
vmin = a1;
}
if (root->right != NULL) {
bool bright = checkbst(root->right, a2, b2);
if (!bright) return false;
if (a2<root->val) return false;
vmax = b2;
}
return true;
}
void print(node *root)
{
if (root==NULL) return;
print(root->left);
printf(" %d", root->val);
print(root->right);
}
int main()
{
node a[100];
for(int i=0; i<10; ++i) {
if (2*i+1<10) a[i].left=&a[2*i+1];
else a[i].left = NULL;
if (2*i+2<10) a[i].right=&a[2*i+2];
else a[i].right = NULL;
}
// expected: true
int v[] = { 500, 200, 800, 100, 300, 600, 900, 50, 150, 280};
// expected: false
//int v[] = { 500, 200, 800, 100, 300, 600, 900, 50, 150, 350};
for(int i=0; i<10; ++i) {
a[i].val = v[i];
}
node *root=&a[0];
int x, y;
print(root); putchar('\n');
bool c = checkbst(root, x, y);
if (c) puts("true");
else puts("false");
}
list flatten
// listflatten.cpp
//
#include <cctype>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <utility>
using namespace std;
const char lparen = '(';
const char rparen = ')';
struct node {
bool atomp;
int val;
struct node *sub;
struct node *next;
};
struct node *
parse(char *str)
{
if (!*str) return NULL;
char *p = str;
while(isspace(*p))
{
p++;
}
assert(*p == lparen);
char *q;
int lcnt = 1;
for(q=p+1; ; q++)
{
if (*q == rparen)
lcnt--;
else if (*q == lparen)
lcnt++;
if (lcnt == 0)
break;
}
assert(*q == rparen);
*q = '\0';
struct node *newnode = (struct node*)malloc(sizeof(struct node));
for(p++; isspace(*p); p++)
;
int val = 0;
bool atomp = false;
if (isdigit(*p))
{
atomp = true;
while(isdigit(*p))
{
val = val * 10 + *p-'0';
p++;
}
}
newnode->atomp = atomp;
newnode->val = val;
newnode->sub = parse(p);
newnode->next = parse(q+1);
return newnode;
}
typedef pair<struct node*, struct node*> pnn;
pnn flatten(struct node *head)
{
pnn ret; ret.first=ret.second=NULL;
if (!head) return ret;
pnn subpair = flatten(head->sub);
pnn nextpair = flatten(head->next);
head->sub=head->next=NULL;
struct node dummy;
struct node *subhead = subpair.first;
struct node *subtail = subpair.second;
struct node *nexthead = nextpair.first;
struct node *nexttail = nextpair.second;
struct node *tail = &dummy;
// set up new head
if (head->atomp) { tail->next=head; tail = tail->next; }
if (subhead) { tail->next = subhead; tail = subtail; }
if (nexthead) { tail->next = nexthead; tail = nexttail; }
if (tail==&dummy) { ret.first=ret.second=NULL; }
else { ret.first=dummy.next; ret.second=tail; }
return ret;
}
void print(struct node *head)
{
if (!head) return;
cout << "( ";
if (head->atomp)
cout << head->val << " ";
print(head->sub);
cout << ") ";
print(head->next);
}
int main()
{
char list[] = "(1 (21 (339) ()))(410)(()(123))";
//char list[] = "(1(3 ()))(2)";
//char list[] = "(())";
struct node *head = parse(list);
print(head);
cout << endl;
cout << "flatten list\n";
head = flatten(head).first;
print(head);
cout << endl;
}
swap odd even position in linked list
#include <cassert>
#include <cstdio>
using namespace std;
struct node
{
int val;
node* next;
};
node* swap(node *head)
{
node dummy;
node *prev, *curr, *u, *tmp;
if (head==NULL) return head;
prev=&dummy;
for(curr=head; curr!=NULL && curr->next!=NULL; ) {
u = curr->next;
tmp = u->next;
prev->next = u;
u->next = curr;
prev = curr;
curr = tmp;
}
prev->next = curr;
return dummy.next;
}
void print(const node *head)
{
for(const node *p=head; p; p=p->next)
printf("%d ", p->val);
putchar('\n');
}
int main()
{
const int N=101;
node v[N];
for(int i=0; i<N; ++i) {
v[i].val=10*i;
if (i<N-1) v[i].next=&v[i+1];
else v[i].next=0;
}
node *head=&v[0];
puts("input");
print(head);
head = swap(head);
puts("swap even odd");
print(head);
}
Subscribe to:
Posts (Atom)
