http://www.ultimatebootcd.com/
EasyBCD from NeoSmart
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.
Subscribe to:
Posts (Atom)
