$(document).bind('click', function(e) {
var $clicked = $(e.target);
if (! $clicked.parents().hasClass("staticMenu")){
$(".staticMenu dd ul").hide();
$(".staticMenu dt a").removeClass("selected");
} });
Friday, November 8, 2013
syntax highlight template
syntax highlight
Java generics
Java introduced generics, but then I realized that it does not have the equivalent of typedef as C/C++. So if you have something like
this is tedious and annoying, why do I have to type the same thing twice? In java 7, you can write this
For java 6 and earlier, here is one solution, which seems to be the approach of google guava library as well.
http://www.ibm.com/developerworks/library/j-jtp02216/
public class Util {
static Map newHashMap() {
return new HashMap();
}
}
Here is a small test file
Map<String, Future<MyLongClass>> mp = new HashMap<String, Future<MyLongClass>>();this is tedious and annoying, why do I have to type the same thing twice? In java 7, you can write this
Map<String, Future<MyLongClass>> mp = new HashMap<>();For java 6 and earlier, here is one solution, which seems to be the approach of google guava library as well.
http://www.ibm.com/developerworks/library/j-jtp02216/
public class Util {
static
return new HashMap
}
}
Here is a small test file
// UtilTest.java
import java.util.HashMap;
import java.util.Map;
public class UtilTest {
public static void main(String[] args) {
Pair<Integer, String> p1 = new Pair<>(1, "apple");
Pair<Integer, String> p2 = new Pair<>(2, "pair");
boolean same = Util.<Integer, String>compare(p1, p2);
System.out.println(same);
Map<String, String> hashMap = Util.newHashMap();
hashMap.put("key", "value");
for (Map.Entry<String, String> entry : hashMap.entrySet()) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}
}
}
Sunday, August 25, 2013
Saturday, June 22, 2013
a nim-like game
Two players, starting with one pile of n stones. The players take turns. In one move, the current player can pick any pile of stones and split into 2 or 3 new piles with each new pile having at least 1 stone. The player cannot make a move loses. Given n, can you determine the winner, assuming both play optimally?
The answer is deceptively simple, so spend at least one day before you look at the solution below.
Solution:
n = 1, first player loses
n >= 2, if n is even, then the first player can split into two equal piles and mimic the second players move, so the first player wins.
else n is odd, but then the first player can split into 1, k, k, assuming n = 2*k +1. Then the first player can again mimic the second players moves. So the first player wins as well.
In summary, the first player wins for all n >= 2. Simple, huh?
The answer is deceptively simple, so spend at least one day before you look at the solution below.
Solution:
n = 1, first player loses
n >= 2, if n is even, then the first player can split into two equal piles and mimic the second players move, so the first player wins.
else n is odd, but then the first player can split into 1, k, k, assuming n = 2*k +1. Then the first player can again mimic the second players moves. So the first player wins as well.
In summary, the first player wins for all n >= 2. Simple, huh?
Monday, May 13, 2013
GCJ round 1C
This round is full of frustration and nervousness and fear that I cannot advance, and I did not. The plan clearly writes, be patient and focus on the problems. But everything goes chaos when I found myself stuck in problem 1 large.
A. a simple problem but requires some care in implementation. To count the number of pairs, you need to keep track of segments with exactly n consonants and then you can start from prevStart+1 to p1, inclusive, and end with p2 to len-1, inclusive, [p1..p2] marks the current segment of n consonants.
I had an extremely ugly code with lots of if/else and while/for inside of each other. Surprisingly the code is actually correct. But I lost my confidence while waiting for it to finish running large input, and thought I had an infinite loop somewhere. After the contest, I ran the code again and found it takes only 1m24s to finish. On the other hand I have to acknowledge that a properly implemented simpler code runs only a fraction of a second.
B. I figured out the small even when panicking, and so do over 1500 other contestants. For small you can advance to X and Y at increment of 1, by taking -k, then +(k+1) until done.
The large is rather daunting, as you need to finish with minimum number of moves, and algorithms with DP or shortest path do not seem to be viable. You need an EXPLICIT strategy. I hate this as this problem gave those who have seen it before an unfair advantage. This problem falls into the category that when you see it the first time, it takes extreme ingenuity to figure out the strategy, then coding is as simple as write a single for loop.
I think I was close, but not enough to finish.
First you know that sign does not matter, you can assume X and Y being non-negative, and you only need to flip the move accordingly.
Next you try to simplify the problem a bit. What if you have only one number, say X, instead of two numbers, how do you move to get X? One then sees that you can do 1, 2, 3, ..., k such that S[k-1] < X and S[k] >= X. Now if S[k] = X, then you are done. Otherwise S[k] > X. In this case we know we need to flip at least one number in 1, 2, ..., k-1 to make the sum equal X. However there is a catch. Flipping a number j to -j will change S[k] to S[k] - 2*j, in other words, flipping sign can never change the parity of S[k]. So we need S[k] to agree with X in parity, if not we need to get one more number k+1 so that S[k+1] agrees in parity with X.
Now consider two cases:
Case 1: S[k-1] < X and S[k] > X, and S[k] and X agree with parity. Then we can show that (S[k] - X) / 2 <= k. Notice that S[k] - X is even in this case. Simple algebra tells us that this is the same as S[k] <= X + 2k, which is S[k-1] <= X +k, and that obviously holds as we have S[k-1] < X.
Case 2: S[k-1] < X and S[k] > X and S[k] and X disagree with parity. Then we need (S[k+1] - X) / 2 <= k+1 so we can flip the sign of the number j = (S[k+1] - X) / 2. This turns out to be S[k] <= X+k+1, which is S[k-1] <= X+1, and obviously this holds.
Given above, we have actually figured out a way to make X, using minimum number of moves. Now how do we generalize to two numbers, X and Y?
Behold, the trick is.....
NOTHING. You heard it right, nothing, just like the response when Pau, the Panda asks for the secret ingredient. We use the same strategy for two numbers, X and Y.
Well, not quite, but it is close to the truth. Take a step back, and consider what is the necessary number of moves to get X and Y. If we can get X and Y, then we should be able to get |X| + |Y|, just combine the moves into 1 dimension. OK, so now what is necessary to get |X| + |Y|. Our previous discussion tells us that we need k moves such that S[k-1] < |X| + |Y| and S[k] >= |X| + |Y|. In case S[k] and |X| + |Y| disagree in parity, we need one more move, that is k+1. Clearly it is necessary, but why is it sufficient, or rather, is i actually sufficient? The problem setter is clever enough that he/she does not want those who can make only this far to pass, so he/she is asking for the actual moves instead of merely the number of moves, which I would have guessed by going this far.
Now why this k or k+1 moves is sufficient, and what is a strategy and did achieve X and Y simultaneously? There are many false starts for possible proofs, because some claims that one tries to make is simply false. Let's run an example to see what is going on. To make things easier we actually start from X, Y and decrease them to zero. The strategy? Always bring down the larger of the two, of course you take the one with larger abs value.
Let X = 3 and Y = 6, the above tells us that we need at least 1,2,3,4,5 moves.
X Y
1,2,3,4,5 3 6
1,2,3,4 3 1
1,2,3 1 1
1,2 2 1
1 0 1
0 0
OK, so you see it, and some conjectures, or false claims could be dismissed. The X and Y may not going down all the time, they might even go up temporarily. And X and Y could be both smaller than k, the next available move (although you can use move from 1 to k, it seems more reasonable to use move = k). However both X and Y did arrive at 0. Then what is the invariant in the iterations to make this final state eventually achieved?
The claim: at every iteration, S[k] >= |X| + |Y| and S[k] agree in parity with |X| + |Y|.
The corollary: X and Y must go down to 0 eventually, since k will go down to 0.
Proof of the claim: In the beginning it is true, so we have base case covered. After one move, w.l.o.g. we may assume X >= 0 and Y >= 0, and X >= Y. Now our move will update (X,Y) to (X-k, Y). We have two cases:
Case 1: X-k >= 0, then we have X-k, Y as the new X and Y, and our S[k] becomes S[k-1], both X+Y and S[k] decrease by exactly k, so our claim X + Y <= S[k] and agree with parity holds.
Case 2: X-k < 0, in this case we need to show k - X + Y <= S[k-1] and they agree in parity. The parity part is easy, as X + Y and X - Y have same parity with S[k], which is S[k-1] + k, as is S[k-1] - k. Now we show the inequality. We have two subcases.
Subcase 1: S[k-1] < X + Y <= S[k] and X + Y agree in parity with S[k]. Then we need to show k - X + Y <= S[k-1], which is k + Y <= S[k-1] + X. Since X >= Y, for any k >= 3 we know this inequality is true. If k = 2, then we know X + Y <= S[2] = 1+2, then X and Y is either 1,1 or 1,2, both are easy to deal with. Similarly we can deal with k = 1.
Subcase 2: S[k-2] < X + Y <= S[k-1] and X + Y disagree in parity with S[k-1], then our move is (k - X, Y) and we need k - X + Y <= S[k-1]. This is almost the same as Subcase 1.
Whew! We have actually proved that the strategy actually works.
Now the take-home message, in graph theory book, there is an acronym:
The Obvious Necessary Condition Is Also Sufficient, that is TONCIAS.
A. a simple problem but requires some care in implementation. To count the number of pairs, you need to keep track of segments with exactly n consonants and then you can start from prevStart+1 to p1, inclusive, and end with p2 to len-1, inclusive, [p1..p2] marks the current segment of n consonants.
I had an extremely ugly code with lots of if/else and while/for inside of each other. Surprisingly the code is actually correct. But I lost my confidence while waiting for it to finish running large input, and thought I had an infinite loop somewhere. After the contest, I ran the code again and found it takes only 1m24s to finish. On the other hand I have to acknowledge that a properly implemented simpler code runs only a fraction of a second.
B. I figured out the small even when panicking, and so do over 1500 other contestants. For small you can advance to X and Y at increment of 1, by taking -k, then +(k+1) until done.
The large is rather daunting, as you need to finish with minimum number of moves, and algorithms with DP or shortest path do not seem to be viable. You need an EXPLICIT strategy. I hate this as this problem gave those who have seen it before an unfair advantage. This problem falls into the category that when you see it the first time, it takes extreme ingenuity to figure out the strategy, then coding is as simple as write a single for loop.
I think I was close, but not enough to finish.
First you know that sign does not matter, you can assume X and Y being non-negative, and you only need to flip the move accordingly.
Next you try to simplify the problem a bit. What if you have only one number, say X, instead of two numbers, how do you move to get X? One then sees that you can do 1, 2, 3, ..., k such that S[k-1] < X and S[k] >= X. Now if S[k] = X, then you are done. Otherwise S[k] > X. In this case we know we need to flip at least one number in 1, 2, ..., k-1 to make the sum equal X. However there is a catch. Flipping a number j to -j will change S[k] to S[k] - 2*j, in other words, flipping sign can never change the parity of S[k]. So we need S[k] to agree with X in parity, if not we need to get one more number k+1 so that S[k+1] agrees in parity with X.
Now consider two cases:
Case 1: S[k-1] < X and S[k] > X, and S[k] and X agree with parity. Then we can show that (S[k] - X) / 2 <= k. Notice that S[k] - X is even in this case. Simple algebra tells us that this is the same as S[k] <= X + 2k, which is S[k-1] <= X +k, and that obviously holds as we have S[k-1] < X.
Case 2: S[k-1] < X and S[k] > X and S[k] and X disagree with parity. Then we need (S[k+1] - X) / 2 <= k+1 so we can flip the sign of the number j = (S[k+1] - X) / 2. This turns out to be S[k] <= X+k+1, which is S[k-1] <= X+1, and obviously this holds.
Given above, we have actually figured out a way to make X, using minimum number of moves. Now how do we generalize to two numbers, X and Y?
Behold, the trick is.....
NOTHING. You heard it right, nothing, just like the response when Pau, the Panda asks for the secret ingredient. We use the same strategy for two numbers, X and Y.
Well, not quite, but it is close to the truth. Take a step back, and consider what is the necessary number of moves to get X and Y. If we can get X and Y, then we should be able to get |X| + |Y|, just combine the moves into 1 dimension. OK, so now what is necessary to get |X| + |Y|. Our previous discussion tells us that we need k moves such that S[k-1] < |X| + |Y| and S[k] >= |X| + |Y|. In case S[k] and |X| + |Y| disagree in parity, we need one more move, that is k+1. Clearly it is necessary, but why is it sufficient, or rather, is i actually sufficient? The problem setter is clever enough that he/she does not want those who can make only this far to pass, so he/she is asking for the actual moves instead of merely the number of moves, which I would have guessed by going this far.
Now why this k or k+1 moves is sufficient, and what is a strategy and did achieve X and Y simultaneously? There are many false starts for possible proofs, because some claims that one tries to make is simply false. Let's run an example to see what is going on. To make things easier we actually start from X, Y and decrease them to zero. The strategy? Always bring down the larger of the two, of course you take the one with larger abs value.
Let X = 3 and Y = 6, the above tells us that we need at least 1,2,3,4,5 moves.
X Y
1,2,3,4,5 3 6
1,2,3,4 3 1
1,2,3 1 1
1,2 2 1
1 0 1
0 0
OK, so you see it, and some conjectures, or false claims could be dismissed. The X and Y may not going down all the time, they might even go up temporarily. And X and Y could be both smaller than k, the next available move (although you can use move from 1 to k, it seems more reasonable to use move = k). However both X and Y did arrive at 0. Then what is the invariant in the iterations to make this final state eventually achieved?
The claim: at every iteration, S[k] >= |X| + |Y| and S[k] agree in parity with |X| + |Y|.
The corollary: X and Y must go down to 0 eventually, since k will go down to 0.
Proof of the claim: In the beginning it is true, so we have base case covered. After one move, w.l.o.g. we may assume X >= 0 and Y >= 0, and X >= Y. Now our move will update (X,Y) to (X-k, Y). We have two cases:
Case 1: X-k >= 0, then we have X-k, Y as the new X and Y, and our S[k] becomes S[k-1], both X+Y and S[k] decrease by exactly k, so our claim X + Y <= S[k] and agree with parity holds.
Case 2: X-k < 0, in this case we need to show k - X + Y <= S[k-1] and they agree in parity. The parity part is easy, as X + Y and X - Y have same parity with S[k], which is S[k-1] + k, as is S[k-1] - k. Now we show the inequality. We have two subcases.
Subcase 1: S[k-1] < X + Y <= S[k] and X + Y agree in parity with S[k]. Then we need to show k - X + Y <= S[k-1], which is k + Y <= S[k-1] + X. Since X >= Y, for any k >= 3 we know this inequality is true. If k = 2, then we know X + Y <= S[2] = 1+2, then X and Y is either 1,1 or 1,2, both are easy to deal with. Similarly we can deal with k = 1.
Subcase 2: S[k-2] < X + Y <= S[k-1] and X + Y disagree in parity with S[k-1], then our move is (k - X, Y) and we need k - X + Y <= S[k-1]. This is almost the same as Subcase 1.
Whew! We have actually proved that the strategy actually works.
Now the take-home message, in graph theory book, there is an acronym:
The Obvious Necessary Condition Is Also Sufficient, that is TONCIAS.
Monday, May 6, 2013
GCJ round 1B
A. Notice that you always take a prefix after sorting.
B. Draw N= 1 to 7, then you see a pattern. The answer is always 1/2^k
C. DP, although many topcoders use trie.
dp[n][p] is min cost to split S[1..n] into words such that the last mismatch occurs at n-p. So p = 1, 2, 3, 4, 5 (for 5 and above, they are the same)
dp[0][5] = 0
for i = 1 to n
for w = 0 to dict.size()-1
cut dict[w] from the end of S[0..i-1]
for the transition to be valid, the word dict[w] itself must have mismatch dist >= 5 as required, and we need previous dp[i-len][prev] be dist=5 or more away
One important implementation detail: Since there are 5*10^5 words and n is 4000, using vector for dict is 10 times slower than using char[][], which means a difference of 15min vs 1.5 min
B. Draw N= 1 to 7, then you see a pattern. The answer is always 1/2^k
C. DP, although many topcoders use trie.
dp[n][p] is min cost to split S[1..n] into words such that the last mismatch occurs at n-p. So p = 1, 2, 3, 4, 5 (for 5 and above, they are the same)
dp[0][5] = 0
for i = 1 to n
for w = 0 to dict.size()-1
cut dict[w] from the end of S[0..i-1]
for the transition to be valid, the word dict[w] itself must have mismatch dist >= 5 as required, and we need previous dp[i-len][prev] be dist=5 or more away
One important implementation detail: Since there are 5*10^5 words and n is 4000, using vector
Thursday, May 2, 2013
TC SRM 578 div1
p250, very similar to a previous tc 250 problem. The first step is to identify components, that is, nodes with L1 distance <= dist with 'v'. Then we have the count of each component. Let odd and even be the number of components with odd and even number of nodes, to get an overall even count, we must choose an even number of odd components and any number of even components.
An analytical solution is 2^even * (2^odd / 2), because binomial sum is even, and (n choose 0) + (n choose 2) + ... + (n choose 2k) = (n choose 1) + (n choose 3) + (n choose 5) + ... + (n choose 2k+1)
A dp approach is to use dp[n][0] and dp[n][1] denote the number of sets with component 1 to n, and [0] if sum is even and [1] if sum is odd. Then the empty set is dp[0][0] = 1, and dp[0][1] = 0
The recurrence is
let components be numbered 1, 2, ..., n
if (cnt[i] is odd) dp[i][0] = (dp[i-1][0] + dp[i-1][1])
dp[i][1] = (dp[i-1][0] + dp[i-1][1])
because we can use the odd component to make odd become even, and not use it leaves the sum odd.
if (cnt[i] is even) then dp[i][0] = dp[i-1][0] * 2, since use cnt[i] or not leaves even as even, and dp[i][1] = dp[i-1][1] * 2 for the same reason.
Some contestant even implemented choose[n][r] and do the actual summation.
One catch, we need to return dp[n][0] - 1. And since we are doing mod 10^9+7, we need to be a bit careful. If dp[n][0] = 0 MOD 10^9+7, then we would return -1 which is bad. Fortunately for me and many contestants with ignorance, since the real answer is 2^k, the mod will never return 0. So we are saved. What a relieve.
p500, I got almost everything, but still could not finish. The dp solution is
dp[l][r] counts number of ways to place wolves with last two at l and r.
dp[0][0] indicates no wolves.
dp[0][l] indicates only one wolf at location[l], which is 1-based.
dp[l][r] = sum of p = 0 to l-1, dp[p][l] such that [p,r] is not contained in any of the L[i], R[i] intervals. Notice that we need to shift the L[i], R[i] value to the right by 1 to make it 1-based.
An analytical solution is 2^even * (2^odd / 2), because binomial sum is even, and (n choose 0) + (n choose 2) + ... + (n choose 2k) = (n choose 1) + (n choose 3) + (n choose 5) + ... + (n choose 2k+1)
A dp approach is to use dp[n][0] and dp[n][1] denote the number of sets with component 1 to n, and [0] if sum is even and [1] if sum is odd. Then the empty set is dp[0][0] = 1, and dp[0][1] = 0
The recurrence is
let components be numbered 1, 2, ..., n
if (cnt[i] is odd) dp[i][0] = (dp[i-1][0] + dp[i-1][1])
dp[i][1] = (dp[i-1][0] + dp[i-1][1])
because we can use the odd component to make odd become even, and not use it leaves the sum odd.
if (cnt[i] is even) then dp[i][0] = dp[i-1][0] * 2, since use cnt[i] or not leaves even as even, and dp[i][1] = dp[i-1][1] * 2 for the same reason.
Some contestant even implemented choose[n][r] and do the actual summation.
One catch, we need to return dp[n][0] - 1. And since we are doing mod 10^9+7, we need to be a bit careful. If dp[n][0] = 0 MOD 10^9+7, then we would return -1 which is bad. Fortunately for me and many contestants with ignorance, since the real answer is 2^k, the mod will never return 0. So we are saved. What a relieve.
p500, I got almost everything, but still could not finish. The dp solution is
dp[l][r] counts number of ways to place wolves with last two at l and r.
dp[0][0] indicates no wolves.
dp[0][l] indicates only one wolf at location[l], which is 1-based.
dp[l][r] = sum of p = 0 to l-1, dp[p][l] such that [p,r] is not contained in any of the L[i], R[i] intervals. Notice that we need to shift the L[i], R[i] value to the right by 1 to make it 1-based.
Friday, April 26, 2013
SRM 577 div2
I solved all 3, and placed 7th in div2.
p1000 is worth some thoughts. Given an int arr[] with 50 elements, each no more than 10^5, find number of elements to insert so that no two adjacent numbers have gcd > 1 when sorted.
First attempt: is one insertion always enough?
The problem setter is friendly and give case 1 showing the claim is false.
Second attempt: is two insertion always enough?
The answer is yes, and here is why. (UPDATE, apparently the proof is very difficult and I do not know one, although you can write a program to check the claim for the range of numbers, 1 to 10^5)
Let a and b be two adjacent numbers, and first we run all numbers from a+1 to b-1 to see if one of them is coprime with both a and b, if yes we are done and need to insert only one element. Otherwise we claim that a+1 and b-1 suffices to make a, a+1, b-1, b adjacent coprime. Note that since gcd(a,b) > 1, we must have b-a >= 2, and since no number from a+1 to b-1 is coprime with both a and b, we actually have a+1 < b-1.
Now comes the proof that a, a+1, b-1, b are adjacent coprime.
Since we know that every number from a+1 to b-1 have some gcd > 1 with either a or b. We can group them according to this:
class b shares gcd > 1 with b and class a shares gcd > 1 with a, and every number from a+1 to b-1 must fall into one of the two classes. Note also that gcd(a, a+1) = 1, as is gcd(b, b-1) = 1
class b: a+1, b-2, ...
class a: b-1, a+2, ...
Not finished, but checking all a,b=1 to 10^4 works with a+1, b-1
The intended solution, according to mystic, is also cryptic. The observation is that if B - A is at least 504 = 72 * 6, then you can find one prime between A and B and B is not divisible by that prime. This is based on the observation that for numbers less than 10^5, prime gaps are no more than 72. Then you can work on the case B < A + 504 and this is much more manageable.
p1000 is worth some thoughts. Given an int arr[] with 50 elements, each no more than 10^5, find number of elements to insert so that no two adjacent numbers have gcd > 1 when sorted.
First attempt: is one insertion always enough?
The problem setter is friendly and give case 1 showing the claim is false.
Second attempt: is two insertion always enough?
The answer is yes, and here is why. (UPDATE, apparently the proof is very difficult and I do not know one, although you can write a program to check the claim for the range of numbers, 1 to 10^5)
Let a and b be two adjacent numbers, and first we run all numbers from a+1 to b-1 to see if one of them is coprime with both a and b, if yes we are done and need to insert only one element. Otherwise we claim that a+1 and b-1 suffices to make a, a+1, b-1, b adjacent coprime. Note that since gcd(a,b) > 1, we must have b-a >= 2, and since no number from a+1 to b-1 is coprime with both a and b, we actually have a+1 < b-1.
Now comes the proof that a, a+1, b-1, b are adjacent coprime.
Since we know that every number from a+1 to b-1 have some gcd > 1 with either a or b. We can group them according to this:
class b shares gcd > 1 with b and class a shares gcd > 1 with a, and every number from a+1 to b-1 must fall into one of the two classes. Note also that gcd(a, a+1) = 1, as is gcd(b, b-1) = 1
class b: a+1, b-2, ...
class a: b-1, a+2, ...
Not finished, but checking all a,b=1 to 10^4 works with a+1, b-1
The intended solution, according to mystic, is also cryptic. The observation is that if B - A is at least 504 = 72 * 6, then you can find one prime between A and B and B is not divisible by that prime. This is based on the observation that for numbers less than 10^5, prime gaps are no more than 72. Then you can work on the case B < A + 504 and this is much more manageable.
Sunday, April 7, 2013
SRM 575 div 1
250, had some idea but could not finish. Submitted an obviously faulty version.
The problem is a game, given integer C, in each move you can subtract d from C such that d is a divisor of C and 1 < d < C. The player cannot make a move loses.
To start, make a table for C = 1 to 16, and this gives some idea.
if C is 2^k, then 2 is LOSE, 4 is WIN, 8 is LOSE, 16 is WIN. So a guess is that 2^k is LOSE if k is odd and is WIN if k is even.
and all odd numbers are LOSE, 1, 3, 5, 7, ...
and other numbers, 2^k * l for odd l > 1 are WIN.
If you have gone this far, an induction proof is all you need, and that's easy.
if C is 2^k, for even k you can make a move to 2^(k-1) which is an odd power of 2 and a LOSE, so you must be in WIN. For odd k we need to show every move leads to WIN. You possible moves are 2^l for some l >= 1, and C - 2^l = 2^k - 2^l = 2^l (2^(k-l) - 1), so it is of the form 2^l * odd, and that is a WIN.
if C is odd, then we need to show every move leads to WIN. An odd C can only have odd divisor d and d must be greater than 1, less than C. so C - d is even, and since d also divides C - d, the number C - d must be of the form 2^l * odd, and hence a WIN.
if C is 2^l * odd for l >= 1, then we need to find a move to LOSE. And that was easy. Let C = 2^l * d, for some odd d, then C - d = 2^l * d - d = d * (2^l - 1). The product of two odd numbers must be odd, and odd is LOSE.
We are now complete in the induction proof.
The problem is a game, given integer C, in each move you can subtract d from C such that d is a divisor of C and 1 < d < C. The player cannot make a move loses.
To start, make a table for C = 1 to 16, and this gives some idea.
if C is 2^k, then 2 is LOSE, 4 is WIN, 8 is LOSE, 16 is WIN. So a guess is that 2^k is LOSE if k is odd and is WIN if k is even.
and all odd numbers are LOSE, 1, 3, 5, 7, ...
and other numbers, 2^k * l for odd l > 1 are WIN.
If you have gone this far, an induction proof is all you need, and that's easy.
if C is 2^k, for even k you can make a move to 2^(k-1) which is an odd power of 2 and a LOSE, so you must be in WIN. For odd k we need to show every move leads to WIN. You possible moves are 2^l for some l >= 1, and C - 2^l = 2^k - 2^l = 2^l (2^(k-l) - 1), so it is of the form 2^l * odd, and that is a WIN.
if C is odd, then we need to show every move leads to WIN. An odd C can only have odd divisor d and d must be greater than 1, less than C. so C - d is even, and since d also divides C - d, the number C - d must be of the form 2^l * odd, and hence a WIN.
if C is 2^l * odd for l >= 1, then we need to find a move to LOSE. And that was easy. Let C = 2^l * d, for some odd d, then C - d = 2^l * d - d = d * (2^l - 1). The product of two odd numbers must be odd, and odd is LOSE.
We are now complete in the induction proof.
Wednesday, April 3, 2013
SRM 572 div1
250, find pos that must be equal, this is an equivalence relation. Group by the equivalence then exclude the max occurred letter. (did not see it until reading petr's solution)
500, the length n is only 9, but brute force cannot work as we have 10^9 numbers to check, each need to go through 50 guesses. It appears that if n is smaller, say 4 or 5, then we can work out by brute force. How do we do that?
Reading tourist and petr's solution, and the editorial, it finally makes sense. Let's consider one guess, we can cut a number with 9 digits to left with 4 digits and right with 5 digits. Then we try all 0 to 99999 to count the number of bull. If left bull and right bull add up to the right bull, then the left guess and right guess makes a valid guess. Now we have a number of guesses.
What happens if we try 0 to 9999 for left and 0 to 99999 for right. And we record the signature of each try on left in a map, a signature is essentially the bull for each guess in the input, a vector of int with 50 elements. And we also record the signature of each try on the right, put in a second map. Each map entry has the signature as key, and number of tries with the signature as value.
Now we can iterate through the first map, for each entry, we can compute its complement key in the second map and look for matches.
In the end, we can count how many valid numbers with bulls matching all the input guesses. And it is trivial to respond 0, 1 or 2 for the problem.
Code here:
// from 0 to 9999, try left
// from 0 to 99999, try right
//
// map count of tries to key = bull
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
map< vector<int>, int > cnt_left, cnt_right, val_left, val_right;
class EllysBulls
{
public:
string getNumber(vector <string> guesses, vector <int> bulls)
{
int len = guesses[0].size();
int g = guesses.size();
int lim, l1, l2;
lim = 1; l1 = len / 2; l2 = len - l1;
for (int i = 0; i < l1; ++i) lim *= 10; cout << lim << endl;
for (int i = 0; i < lim; ++i) {
vector<int> vec;
for (int k = 0; k < g; ++k) {
int val = i;
int bull = 0;
for (int p = l1-1; p >= 0; --p) {
if (guesses[k][p] - '0' == val % 10) bull++;
val /= 10;
}
vec.push_back(bull);
}
val_left[vec] = i;
cnt_left[vec]++;
}
lim = 1;
for (int i = 0; i < l2; ++i) lim *= 10; cout << lim << endl;
for (int i = 0; i < lim; ++i) {
vector<int> vec;
for (int k = 0; k < g; ++k) {
int val = i;
int bull = 0;
for (int p = l2-1; p >= 0; --p) {
if (guesses[k][p+l1] - '0' == val % 10) bull++;
val /= 10;
}
vec.push_back(bull);
}
val_right[vec] = i;
cnt_right[vec]++;
}
// from right search left
int ans_left = 0, ans_right = 0;
int ans = 0;
for (int i = 0; i < lim; ++i) {
vector<int> vec, other;
for (int k = 0; k < g; ++k) {
int val = i;
int bull = 0;
for (int p = l2-1; p >= 0; --p) {
if (guesses[k][p+l1] - '0' == val % 10) bull++;
val /= 10;
}
vec.push_back(bull);
}
bool good = true;
for (int k = 0; k < g; ++k) {
int entry = bulls[k] - vec[k];
if (entry < 0) { good = false; break; }
other.push_back(entry);
}
if (!good) continue;
if (cnt_left.count(other)) {
ans_right = i; ans_left = val_left[other];
ans += cnt_left[other] * cnt_right[vec];
if (ans >= 2) break;
}
}
if (ans == 0) return "Liar";
if (ans >= 2) return "Ambiguity";
string str;
for (int p = 0; p < l2; ++p) {
str += char(ans_right % 10 + '0');
ans_right /= 10;
}
for (int p = 0; p < l1; ++p) {
str += char(ans_left % 10 + '0');
ans_left /= 10;
}
for (int p = 0, q = str.length()-1; p < q; ++p, --q) {
char t = str[p]; str[p] = str[q]; str[q] = t;
}
return str;
}
};
p1000, seems very similar to the div2 500 problem, since same letter goes through same transformation, we only need to consider distinct letters and there are only 26 of them. Each pair can use either forward or backward transformation and we have 2^26 = 10^7 to deal with. And does that solve a div1 hard?
500, the length n is only 9, but brute force cannot work as we have 10^9 numbers to check, each need to go through 50 guesses. It appears that if n is smaller, say 4 or 5, then we can work out by brute force. How do we do that?
Reading tourist and petr's solution, and the editorial, it finally makes sense. Let's consider one guess, we can cut a number with 9 digits to left with 4 digits and right with 5 digits. Then we try all 0 to 99999 to count the number of bull. If left bull and right bull add up to the right bull, then the left guess and right guess makes a valid guess. Now we have a number of guesses.
What happens if we try 0 to 9999 for left and 0 to 99999 for right. And we record the signature of each try on left in a map, a signature is essentially the bull for each guess in the input, a vector of int with 50 elements. And we also record the signature of each try on the right, put in a second map. Each map entry has the signature as key, and number of tries with the signature as value.
Now we can iterate through the first map, for each entry, we can compute its complement key in the second map and look for matches.
In the end, we can count how many valid numbers with bulls matching all the input guesses. And it is trivial to respond 0, 1 or 2 for the problem.
Code here:
// from 0 to 9999, try left
// from 0 to 99999, try right
//
// map count of tries to key = bull
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
map< vector<int>, int > cnt_left, cnt_right, val_left, val_right;
class EllysBulls
{
public:
string getNumber(vector <string> guesses, vector <int> bulls)
{
int len = guesses[0].size();
int g = guesses.size();
int lim, l1, l2;
lim = 1; l1 = len / 2; l2 = len - l1;
for (int i = 0; i < l1; ++i) lim *= 10; cout << lim << endl;
for (int i = 0; i < lim; ++i) {
vector<int> vec;
for (int k = 0; k < g; ++k) {
int val = i;
int bull = 0;
for (int p = l1-1; p >= 0; --p) {
if (guesses[k][p] - '0' == val % 10) bull++;
val /= 10;
}
vec.push_back(bull);
}
val_left[vec] = i;
cnt_left[vec]++;
}
lim = 1;
for (int i = 0; i < l2; ++i) lim *= 10; cout << lim << endl;
for (int i = 0; i < lim; ++i) {
vector<int> vec;
for (int k = 0; k < g; ++k) {
int val = i;
int bull = 0;
for (int p = l2-1; p >= 0; --p) {
if (guesses[k][p+l1] - '0' == val % 10) bull++;
val /= 10;
}
vec.push_back(bull);
}
val_right[vec] = i;
cnt_right[vec]++;
}
// from right search left
int ans_left = 0, ans_right = 0;
int ans = 0;
for (int i = 0; i < lim; ++i) {
vector<int> vec, other;
for (int k = 0; k < g; ++k) {
int val = i;
int bull = 0;
for (int p = l2-1; p >= 0; --p) {
if (guesses[k][p+l1] - '0' == val % 10) bull++;
val /= 10;
}
vec.push_back(bull);
}
bool good = true;
for (int k = 0; k < g; ++k) {
int entry = bulls[k] - vec[k];
if (entry < 0) { good = false; break; }
other.push_back(entry);
}
if (!good) continue;
if (cnt_left.count(other)) {
ans_right = i; ans_left = val_left[other];
ans += cnt_left[other] * cnt_right[vec];
if (ans >= 2) break;
}
}
if (ans == 0) return "Liar";
if (ans >= 2) return "Ambiguity";
string str;
for (int p = 0; p < l2; ++p) {
str += char(ans_right % 10 + '0');
ans_right /= 10;
}
for (int p = 0; p < l1; ++p) {
str += char(ans_left % 10 + '0');
ans_left /= 10;
}
for (int p = 0, q = str.length()-1; p < q; ++p, --q) {
char t = str[p]; str[p] = str[q]; str[q] = t;
}
return str;
}
};
p1000, seems very similar to the div2 500 problem, since same letter goes through same transformation, we only need to consider distinct letters and there are only 26 of them. Each pair can use either forward or backward transformation and we have 2^26 = 10^7 to deal with. And does that solve a div1 hard?
Monday, April 1, 2013
SRM 572 div2
p500
// check feasibility
// for two intervals opposite, if overlap, then dead
// suppose no two opposite intervals overlap, then they are independent
// we can work with two sets, one forward and one backward
// For same direction set, if one interval is fully contained in another, then dead
// if not, then there is a ways to do the transformation
// select the farthest one (closest to the goal) and move to the goal
#include <string>
using namespace std;
class NextOrPrev
{
public:
bool check(int a, int b, int c, int d)
{
int a1, b1, c1, d1;
a1 = min(a,b); b1 = max(a,b);
c1 = min(c,d); d1 = max(c,d);
if ((a-b) * (c-d) <= 0) {
// opposite direction
if (c1 <= a1 && a1 <= d1) return false;
if (c1 <= b1 && b1 <= d1) return false;
if (a1 <= c1 && c1 <= b1) return false;
if (a1 <= d1 && d1 <= b1) return false;
} else {
if (c1 <= a1 && a1 <= d1 && c1 <= b1 && b1 <= d1) return false;
if (a1 <= c1 && c1 <= b1 && a1 <= d1 && d1 <= b1) return false;
}
return true;
}
// because no wrap around, there is only one way from transform one char to another char
int getMinimum(int nextCost, int prevCost, string start, string goal)
{
int n = start.length();
int cost = 0;
for (int i = 0; i < n; ++i) {
int cur;
if (start[i] > goal[i]) cur = prevCost * (start[i] - goal[i]);
else cur = nextCost * (goal[i] - start[i]);
cost += cur;
}
// check impossible
// if opposite directions, then cannot overlap
// if same direction, cannot fully contain
bool good = true;
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
{
if (!check(start[i], goal[i], start[j], goal[j])) {
good = false; goto done;
}
}
done:
if (good) return cost;
else return -1;
}
};
p1000
// for each K = 1 to M
// count number of ways to have sum = N with K elements
//
// it appears that the sequence is unordered, which makes counting rather difficult
// however we can impose an ordering, since each element has distinct S[i] % M
// we can count all sequences with mod M ordered increasingly, then the ans is obtained
// by multiplying by K factorial
//
// Now our job is to count number of sequence of K elements with mod M ordered increasingly
// if N is small, then we can use dp to count dp[sum][x][l] for number of sequences with
// total = sum and use only mod M from 0 to x-1, with exactly l elements
// however N is huge, 10^18, so we need to work with N mod M somehow
//
// look at a valid sequence
// S[1] + S[2] + ... + S[K] = N
// this is true if and only if
// sum of (S[i] % M) = N % M + S / M where S = sum of S[i]
// and
// sum of (S[i] / M) = N / M - S / M
//
// if we write S[i] = Q[i] * M + R[i]
// then
// sum of R[i] = N % M + R / M where R = sum of R[i]
// and
// sum of Q[i] = N / M - R / M
//
// if we have the R[i]'s, all we need is to find Q[i]'s to complete this equation
//
// Let dp[sum][x][l] be the number of ways to get total = sum, using mod M from 0 to x-1 (at most x-1)
// with exactly l elements,
// then for a given K, we look for adding up dp[sum][M][K] for which sum % M = N % M
// moreover, we need to multiply such dp[sum][M][K] by (Q + K-1 choose K-1) for Q = N/M - sum/M
// notice that K is at most 50 so the combination number can be computed efficiently
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int MOD = (int)(1e9+7);
int dp[1300][55][55];
int fact[55], invfact[55];
class DistinctRemainders
{
public:
void refadd(int &a, int b)
{
a += b;
if (a >= MOD) a -= MOD;
}
int mult(int a, int b)
{
return (long long)a * b % MOD;
}
int gcd(long long a, long long b) // use long long even though only one of them can be long long
{
if (b == 0) return a;
return gcd(b, a % b);
}
int choose(long long a, int b) // compute (Q + K-1 choose K-1), K is at most 50, although Q can be 10^18
{
int ans = 1;
vector<int> v;
for (int i=1; i<=b; ++i) v.push_back(i);
for (int i = 0; i < b; ++i) {
long long k = a - i;
for (int j = 0; j < b; ++j) {
int g = gcd(k, v[j]);
if (g > 1) { k /= g; v[j] /= g; } // careful, forgot to divide v[j] earlier
}
ans = (long long)ans * (k % MOD) % MOD; // watch integer overflow, must reduce k by MOD
}
for (int j = 0; j < b; ++j) { if (v[j] > 1) cout << a << ' ' << b << endl;
assert(v[j] == 1);
}
//for (int i = 0; i < b; ++i) ans = mult(ans, (a-i)%MOD);
//ans = mult(ans, invfact[b]);
return ans;
}
int fastexp(int a, int b)
{
int ans = 1;
int base = a;
while (b) {
if (b&1) ans = mult(ans, base);
base = mult(base, base);
b /= 2;
}
return ans;
}
int inv(int a)
{
return fastexp(a, MOD-2);
}
void init(int n) // n is at most 50 in this problem
{
fact[0] = 1;
for (int i=1; i<=n; ++i)
fact[i] = mult(fact[i-1], i);
for (int i=0; i<=n; ++i)
invfact[i] = inv(fact[i]);
}
int howMany(long long N, int M)
{
if (M == 1) return 1; // careful, M = 1 is special
init(M);
int ans = 0;
for (int K = 1; K <= M; ++K) {
//for (int sum = N%M; sum < M*M/2; sum += M)
//for (int x = 0; x <= M; ++x)
//for (int l = 0; l <= K; ++l)
//dp[sum][x][l] = 0;
dp[0][0][0] = 1; // dp[sum][x][l] is number of increasing seq with total = sum using max <= x-1 with exactly l elements
for (int sum = 0; sum < M*M/2; ++sum)
for (int x = 0; x <= M; ++x)
for (int l = 0; l <= K; ++l)
{
if (sum + x + l == 0) continue;
dp[sum][x][l] = 0;
if (x > 0) dp[sum][x][l] += dp[sum][x-1][l];
if (sum >= x-1 && x > 0 && l > 0) dp[sum][x][l] += dp[sum - (x-1)][x-1][l-1];
if (dp[sum][x][l] >= MOD) dp[sum][x][l] -= MOD;
}
//cout << K << endl;
int cur = 0;
for (int sum = 0; sum < M*M/2 && sum <= N; ++sum) // careful, sum can only be up to N
if (sum % M == N % M) {
//for (int x = 0; x <= M; ++x) {
int tmp = dp[sum][M][K]; //cout << sum << ' ' << x << ' ' << K << ' ' << tmp << endl;
long long Q = N / M - sum / M;
assert(Q >= 0); // careful, without check sum <= N, Q might be < 0 here
tmp = mult(tmp, choose(Q + K-1, K-1));
refadd(cur, tmp);
//}
}
refadd(ans, mult(cur, fact[K]));
}
return ans;
}
};
// now it TLE, the dp I wrote is too slow, 50^6 is not acceptable in TC
// still fail, for N=14, M=7, ans is 643
// my return is 6403, how come? sum needs to be <= N
// check feasibility
// for two intervals opposite, if overlap, then dead
// suppose no two opposite intervals overlap, then they are independent
// we can work with two sets, one forward and one backward
// For same direction set, if one interval is fully contained in another, then dead
// if not, then there is a ways to do the transformation
// select the farthest one (closest to the goal) and move to the goal
#include <string>
using namespace std;
class NextOrPrev
{
public:
bool check(int a, int b, int c, int d)
{
int a1, b1, c1, d1;
a1 = min(a,b); b1 = max(a,b);
c1 = min(c,d); d1 = max(c,d);
if ((a-b) * (c-d) <= 0) {
// opposite direction
if (c1 <= a1 && a1 <= d1) return false;
if (c1 <= b1 && b1 <= d1) return false;
if (a1 <= c1 && c1 <= b1) return false;
if (a1 <= d1 && d1 <= b1) return false;
} else {
if (c1 <= a1 && a1 <= d1 && c1 <= b1 && b1 <= d1) return false;
if (a1 <= c1 && c1 <= b1 && a1 <= d1 && d1 <= b1) return false;
}
return true;
}
// because no wrap around, there is only one way from transform one char to another char
int getMinimum(int nextCost, int prevCost, string start, string goal)
{
int n = start.length();
int cost = 0;
for (int i = 0; i < n; ++i) {
int cur;
if (start[i] > goal[i]) cur = prevCost * (start[i] - goal[i]);
else cur = nextCost * (goal[i] - start[i]);
cost += cur;
}
// check impossible
// if opposite directions, then cannot overlap
// if same direction, cannot fully contain
bool good = true;
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
{
if (!check(start[i], goal[i], start[j], goal[j])) {
good = false; goto done;
}
}
done:
if (good) return cost;
else return -1;
}
};
p1000
// for each K = 1 to M
// count number of ways to have sum = N with K elements
//
// it appears that the sequence is unordered, which makes counting rather difficult
// however we can impose an ordering, since each element has distinct S[i] % M
// we can count all sequences with mod M ordered increasingly, then the ans is obtained
// by multiplying by K factorial
//
// Now our job is to count number of sequence of K elements with mod M ordered increasingly
// if N is small, then we can use dp to count dp[sum][x][l] for number of sequences with
// total = sum and use only mod M from 0 to x-1, with exactly l elements
// however N is huge, 10^18, so we need to work with N mod M somehow
//
// look at a valid sequence
// S[1] + S[2] + ... + S[K] = N
// this is true if and only if
// sum of (S[i] % M) = N % M + S / M where S = sum of S[i]
// and
// sum of (S[i] / M) = N / M - S / M
//
// if we write S[i] = Q[i] * M + R[i]
// then
// sum of R[i] = N % M + R / M where R = sum of R[i]
// and
// sum of Q[i] = N / M - R / M
//
// if we have the R[i]'s, all we need is to find Q[i]'s to complete this equation
//
// Let dp[sum][x][l] be the number of ways to get total = sum, using mod M from 0 to x-1 (at most x-1)
// with exactly l elements,
// then for a given K, we look for adding up dp[sum][M][K] for which sum % M = N % M
// moreover, we need to multiply such dp[sum][M][K] by (Q + K-1 choose K-1) for Q = N/M - sum/M
// notice that K is at most 50 so the combination number can be computed efficiently
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int MOD = (int)(1e9+7);
int dp[1300][55][55];
int fact[55], invfact[55];
class DistinctRemainders
{
public:
void refadd(int &a, int b)
{
a += b;
if (a >= MOD) a -= MOD;
}
int mult(int a, int b)
{
return (long long)a * b % MOD;
}
int gcd(long long a, long long b) // use long long even though only one of them can be long long
{
if (b == 0) return a;
return gcd(b, a % b);
}
int choose(long long a, int b) // compute (Q + K-1 choose K-1), K is at most 50, although Q can be 10^18
{
int ans = 1;
vector<int> v;
for (int i=1; i<=b; ++i) v.push_back(i);
for (int i = 0; i < b; ++i) {
long long k = a - i;
for (int j = 0; j < b; ++j) {
int g = gcd(k, v[j]);
if (g > 1) { k /= g; v[j] /= g; } // careful, forgot to divide v[j] earlier
}
ans = (long long)ans * (k % MOD) % MOD; // watch integer overflow, must reduce k by MOD
}
for (int j = 0; j < b; ++j) { if (v[j] > 1) cout << a << ' ' << b << endl;
assert(v[j] == 1);
}
//for (int i = 0; i < b; ++i) ans = mult(ans, (a-i)%MOD);
//ans = mult(ans, invfact[b]);
return ans;
}
int fastexp(int a, int b)
{
int ans = 1;
int base = a;
while (b) {
if (b&1) ans = mult(ans, base);
base = mult(base, base);
b /= 2;
}
return ans;
}
int inv(int a)
{
return fastexp(a, MOD-2);
}
void init(int n) // n is at most 50 in this problem
{
fact[0] = 1;
for (int i=1; i<=n; ++i)
fact[i] = mult(fact[i-1], i);
for (int i=0; i<=n; ++i)
invfact[i] = inv(fact[i]);
}
int howMany(long long N, int M)
{
if (M == 1) return 1; // careful, M = 1 is special
init(M);
int ans = 0;
for (int K = 1; K <= M; ++K) {
//for (int sum = N%M; sum < M*M/2; sum += M)
//for (int x = 0; x <= M; ++x)
//for (int l = 0; l <= K; ++l)
//dp[sum][x][l] = 0;
dp[0][0][0] = 1; // dp[sum][x][l] is number of increasing seq with total = sum using max <= x-1 with exactly l elements
for (int sum = 0; sum < M*M/2; ++sum)
for (int x = 0; x <= M; ++x)
for (int l = 0; l <= K; ++l)
{
if (sum + x + l == 0) continue;
dp[sum][x][l] = 0;
if (x > 0) dp[sum][x][l] += dp[sum][x-1][l];
if (sum >= x-1 && x > 0 && l > 0) dp[sum][x][l] += dp[sum - (x-1)][x-1][l-1];
if (dp[sum][x][l] >= MOD) dp[sum][x][l] -= MOD;
}
//cout << K << endl;
int cur = 0;
for (int sum = 0; sum < M*M/2 && sum <= N; ++sum) // careful, sum can only be up to N
if (sum % M == N % M) {
//for (int x = 0; x <= M; ++x) {
int tmp = dp[sum][M][K]; //cout << sum << ' ' << x << ' ' << K << ' ' << tmp << endl;
long long Q = N / M - sum / M;
assert(Q >= 0); // careful, without check sum <= N, Q might be < 0 here
tmp = mult(tmp, choose(Q + K-1, K-1));
refadd(cur, tmp);
//}
}
refadd(ans, mult(cur, fact[K]));
}
return ans;
}
};
// now it TLE, the dp I wrote is too slow, 50^6 is not acceptable in TC
// still fail, for N=14, M=7, ans is 643
// my return is 6403, how come? sum needs to be <= N
Tuesday, March 26, 2013
SRM 574 div 1
275: A comb game problem, a straightforward approach is to use dp with memorization. A state is (a, b, turn, move)
bool check(int a, int b, int turn, int move)
// turn = 0 for Manao, 1 for the opponent, move is at most 1000
// a and b has only (10 choose 2) choices, so total number of states
// is around 100 * 100 * 2 * 1000 = 10^7
base case, or terminal states:
1. move = 1000, then, if turn = 1, return true, else return false, because Manao loses
2. a = b, then if turn = 0, return true, else return false, because Manao wins
Other cases:
1. reverse a
2. a div 10
3. reverse b
4. b div 10
call check(anew, bnew, 1-turn, 1+move)
if any of them is false, that means next player loses, then return true
else all of them are true, then this position is a lose position, return false
The solution is by calling check(A, B, 0, 1)
450:
The problem statement is the same as p1000 in div2, however now N can be as large as 18. Does backtrack still work? Should not be because the return type is long long, and one testcase clearly have ans more than 10^9, so an algorithm computes ans by increment of 1 will definitely TLE. How to count faster?
// this is like TSP problem, so think about O(2^n * n) algorithm
// given a prefix with last, we want to extend the prefix by node = next
// In this problem we need to know whether prefix intersects (last, next)
// so it appears we need to know the actual prefix, not only the mask of all
// nodes in prefix, but then the algorithm would be n factorial which is too slow!
//
// Now comes the observation: we only need to know the subset of nodes in prefix,
// to determine intersection, their order does not matter. Let S be the set of nodes
// in prefix, then S contains a pair (a, b) that intersects (last, next) if and only
// if S contains nodes both inside and outside the range of (a, b), regardless of
// how nodes in S are ordered. Because we only need to know whether S crosses
// (last, next) or not, this check is enough.
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;
long long dp[1<<18][20]; // careful, dp[1<<20][20] for long long will mem limit exceeded, SIGKILL
class PolygonTraversal
{
public:
bool inrange(int a, int b, int val)
{
assert(a < b && a != val && b != val);
return a < val && val < b;
}
bool cross(int a, int b, const vector<int> &vec)
{
bool inside, outside;
inside = outside = false;
for (int i = 0; i < vec.size(); ++i) {
int k = vec[i];
if (inrange(a, b, k)) inside = true;
else outside = true;
}
return inside && outside;
}
long long count(int N, vector <int> points)
{
for (int i = 0; i < points.size(); ++i) points[i]--;
int start = 0;
for (int i = 0; i < points.size(); ++i) start |= 1 << points[i];
dp[start][points.back()] = 1;
for (int mask = 0; mask < (1 << N); ++mask) if ((mask & start) == start) { // mask contains start
for (int last = 0; last < N; ++last) if (mask & 1 << last) { // mask has last
vector<int> prefix;
for (int i = 0; i < N; ++i) if ((mask & 1 << i) && i != last)
prefix.push_back(i);
for (int next = 0; next < N; ++next) if (!(mask & 1 << next)) { // next is not in mask
int a, b;
a = min(last, next); b = max(last, next);
if (cross(a, b, prefix)) {
dp[mask | 1<<next][next] += dp[mask][last];
}
}
}
}
long long ans = 0;
for (int last = 0; last < N; ++last) if (last != points[0]) {
vector<int> vec;
for (int i = 0; i < N; ++i) if (i != points[0] && i != last) vec.push_back(i);
int a, b;
a = min(points[0], last); b = max(points[0], last);
if (cross(a, b, vec))
ans += dp[(1<<N) - 1][last];
}
return ans;
} // end of method
}; // end of class
1000:Not read yet.
Conclusion: Had I been competing in div1, I should have p250, but no handle on 450 and 1000.
bool check(int a, int b, int turn, int move)
// turn = 0 for Manao, 1 for the opponent, move is at most 1000
// a and b has only (10 choose 2) choices, so total number of states
// is around 100 * 100 * 2 * 1000 = 10^7
base case, or terminal states:
1. move = 1000, then, if turn = 1, return true, else return false, because Manao loses
2. a = b, then if turn = 0, return true, else return false, because Manao wins
Other cases:
1. reverse a
2. a div 10
3. reverse b
4. b div 10
call check(anew, bnew, 1-turn, 1+move)
if any of them is false, that means next player loses, then return true
else all of them are true, then this position is a lose position, return false
The solution is by calling check(A, B, 0, 1)
450:
The problem statement is the same as p1000 in div2, however now N can be as large as 18. Does backtrack still work? Should not be because the return type is long long, and one testcase clearly have ans more than 10^9, so an algorithm computes ans by increment of 1 will definitely TLE. How to count faster?
// this is like TSP problem, so think about O(2^n * n) algorithm
// given a prefix with last, we want to extend the prefix by node = next
// In this problem we need to know whether prefix intersects (last, next)
// so it appears we need to know the actual prefix, not only the mask of all
// nodes in prefix, but then the algorithm would be n factorial which is too slow!
//
// Now comes the observation: we only need to know the subset of nodes in prefix,
// to determine intersection, their order does not matter. Let S be the set of nodes
// in prefix, then S contains a pair (a, b) that intersects (last, next) if and only
// if S contains nodes both inside and outside the range of (a, b), regardless of
// how nodes in S are ordered. Because we only need to know whether S crosses
// (last, next) or not, this check is enough.
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;
long long dp[1<<18][20]; // careful, dp[1<<20][20] for long long will mem limit exceeded, SIGKILL
class PolygonTraversal
{
public:
bool inrange(int a, int b, int val)
{
assert(a < b && a != val && b != val);
return a < val && val < b;
}
bool cross(int a, int b, const vector<int> &vec)
{
bool inside, outside;
inside = outside = false;
for (int i = 0; i < vec.size(); ++i) {
int k = vec[i];
if (inrange(a, b, k)) inside = true;
else outside = true;
}
return inside && outside;
}
long long count(int N, vector <int> points)
{
for (int i = 0; i < points.size(); ++i) points[i]--;
int start = 0;
for (int i = 0; i < points.size(); ++i) start |= 1 << points[i];
dp[start][points.back()] = 1;
for (int mask = 0; mask < (1 << N); ++mask) if ((mask & start) == start) { // mask contains start
for (int last = 0; last < N; ++last) if (mask & 1 << last) { // mask has last
vector<int> prefix;
for (int i = 0; i < N; ++i) if ((mask & 1 << i) && i != last)
prefix.push_back(i);
for (int next = 0; next < N; ++next) if (!(mask & 1 << next)) { // next is not in mask
int a, b;
a = min(last, next); b = max(last, next);
if (cross(a, b, prefix)) {
dp[mask | 1<<next][next] += dp[mask][last];
}
}
}
}
long long ans = 0;
for (int last = 0; last < N; ++last) if (last != points[0]) {
vector<int> vec;
for (int i = 0; i < N; ++i) if (i != points[0] && i != last) vec.push_back(i);
int a, b;
a = min(points[0], last); b = max(points[0], last);
if (cross(a, b, vec))
ans += dp[(1<<N) - 1][last];
}
return ans;
} // end of method
}; // end of class
1000:Not read yet.
Conclusion: Had I been competing in div1, I should have p250, but no handle on 450 and 1000.
Monday, March 25, 2013
SRM 574 div 2
This time I was downgraded to div2 and was having an easier time. The good news is that I got back to div1 with a rank of 80 in div2.
Summary: got 250 and 500 without much effort, but was not able to finish 1000, a simple backtrack problem after 60 minutes!
250, count for 'A' to 'Z', then print.
500, I use bfs since the number of nodes is bounded by n^2, the string for each node is substr(i,j) and we have forward and backward, for a total of n^2 possible strings. Another solution is to notice that the optimal solution is to cut a prefix and a suffix and possibly reverse, so you can try to find B in A or Areverse, and count the cost. Notice you get a better cost if B is a prefix of A since you can save a reverse cost of 1. Notice also that you never need to do more than 1 reverse.
1000, the constraint N is so small, N=13, and each sequence must end after all N nodes were present. You know we start with at least 2 nodes, so the remaining sequence is at most 11 factorial, which is about 10^8. The only tricky part is to check whether two pairs (i1,j1) and (i2,j2) intersect. Assume i1 < j1 and all i1,j1,i2,j2 are distinct. Then they intersect iff i2 is in range(i1,j1) and j2 is not, or vice versa. The solution is a dfs with backtracking. Each node maintains current neighbor, which goes from 1 to N. In each move we either extend the search path by one more node, or hit the end, in this case if (last, first) intersects some other pair, then we get one more solution. the remaining case is a nodes exhausted all its neighbors 1 to N. In this case and the dead end case we backtrack by popping from the end of the path. We stop when we try to pop the original points. One invariant that helps is to init neighbor to 0, then in each iteration we start with prev neighbor + 1, this guarantees we skip the previous neighbor.
Alternative solution, notice that each feasible solution is a sequence of points followed by a permutation of the remaining elements. And we can generate all such permutations, only 13 - 3 = 10 factorial of them. One catch is that when points have size 2, this case we immediately return 0. In TC server, 11 factorial will TLE.
Code below:
class PolygonTraversal2
{
public:
bool inrange(int lo, int hi, int val)
{
assert(lo < hi);
return (lo < val && val < hi);
}
bool intersect(int a, int b, int c, int d)
{
int x, y;
x = min(a, b); y = max(a, b);
bool ans1 = inrange(x, y, c) && !inrange(x, y, d);
bool ans2 = !inrange(x, y, c) && inrange(x, y, d);
return ans1 || ans2;
}
bool cross(int a, int b, vector list) {
for (int i = 0; i+1 < list.size(); ++i) {
if (intersect(a, b, list[i], list[i+1]))
return true;
}
return false;
}
int count(int N, vector points)
{
int ans = 0;
if (points.size() < 3) return 0;
// generate all permutations, only 13-2=11 factorial
vector rem;
for (int i = 1; i <= N; ++i) {
bool used = false;
for (int j = 0; j < points.size(); ++j)
if (points[j] == i) { used = true; break; }
if (!used) rem.push_back(i);
}
sort(rem.begin(), rem.end());
do {
bool good = true;
vector prefix = points; prefix.pop_back();
for (int i = 0; i <= rem.size(); ++i) {
int prev, curr;
if (i == 0) { prev = points.back(); curr = rem[i]; }
else if (i == rem.size()) { prev = rem.back(); curr = points[0]; }
else { prev = rem[i-1]; curr = rem[i]; }
if (!cross(prev, curr, prefix)) { good = false; break; }
prefix.push_back(prev);
if (prefix.size() >= N-1) prefix.erase(prefix.begin());
}
//cout << good << endl;
if (good) { ans++; }
} while (next_permutation(rem.begin(), rem.end()));
return ans;
}
};
Conclusion: I think I am done with div2 problems for this SRM. I guess those red coders are seeing div1 problems as the way I am seeing div2 problems...
Summary: got 250 and 500 without much effort, but was not able to finish 1000, a simple backtrack problem after 60 minutes!
250, count for 'A' to 'Z', then print.
500, I use bfs since the number of nodes is bounded by n^2, the string for each node is substr(i,j) and we have forward and backward, for a total of n^2 possible strings. Another solution is to notice that the optimal solution is to cut a prefix and a suffix and possibly reverse, so you can try to find B in A or Areverse, and count the cost. Notice you get a better cost if B is a prefix of A since you can save a reverse cost of 1. Notice also that you never need to do more than 1 reverse.
1000, the constraint N is so small, N=13, and each sequence must end after all N nodes were present. You know we start with at least 2 nodes, so the remaining sequence is at most 11 factorial, which is about 10^8. The only tricky part is to check whether two pairs (i1,j1) and (i2,j2) intersect. Assume i1 < j1 and all i1,j1,i2,j2 are distinct. Then they intersect iff i2 is in range(i1,j1) and j2 is not, or vice versa. The solution is a dfs with backtracking. Each node maintains current neighbor, which goes from 1 to N. In each move we either extend the search path by one more node, or hit the end, in this case if (last, first) intersects some other pair, then we get one more solution. the remaining case is a nodes exhausted all its neighbors 1 to N. In this case and the dead end case we backtrack by popping from the end of the path. We stop when we try to pop the original points. One invariant that helps is to init neighbor to 0, then in each iteration we start with prev neighbor + 1, this guarantees we skip the previous neighbor.
Alternative solution, notice that each feasible solution is a sequence of points followed by a permutation of the remaining elements. And we can generate all such permutations, only 13 - 3 = 10 factorial of them. One catch is that when points have size 2, this case we immediately return 0. In TC server, 11 factorial will TLE.
Code below:
class PolygonTraversal2
{
public:
bool inrange(int lo, int hi, int val)
{
assert(lo < hi);
return (lo < val && val < hi);
}
bool intersect(int a, int b, int c, int d)
{
int x, y;
x = min(a, b); y = max(a, b);
bool ans1 = inrange(x, y, c) && !inrange(x, y, d);
bool ans2 = !inrange(x, y, c) && inrange(x, y, d);
return ans1 || ans2;
}
bool cross(int a, int b, vector
for (int i = 0; i+1 < list.size(); ++i) {
if (intersect(a, b, list[i], list[i+1]))
return true;
}
return false;
}
int count(int N, vector
{
int ans = 0;
if (points.size() < 3) return 0;
// generate all permutations, only 13-2=11 factorial
vector
for (int i = 1; i <= N; ++i) {
bool used = false;
for (int j = 0; j < points.size(); ++j)
if (points[j] == i) { used = true; break; }
if (!used) rem.push_back(i);
}
sort(rem.begin(), rem.end());
do {
bool good = true;
vector
for (int i = 0; i <= rem.size(); ++i) {
int prev, curr;
if (i == 0) { prev = points.back(); curr = rem[i]; }
else if (i == rem.size()) { prev = rem.back(); curr = points[0]; }
else { prev = rem[i-1]; curr = rem[i]; }
if (!cross(prev, curr, prefix)) { good = false; break; }
prefix.push_back(prev);
if (prefix.size() >= N-1) prefix.erase(prefix.begin());
}
//cout << good << endl;
if (good) { ans++; }
} while (next_permutation(rem.begin(), rem.end()));
return ans;
}
};
Monday, March 18, 2013
CF 174
A: each operation, update sum and remember extra at the last element. When pop, add extra[last] to extra[last-1].
B: notice that we only have (pos, hop) states, where pos = 1 to n, hop = 0 or 1, meaning whether next is x + a[x] or x - a[x]. We can assume we start at pos > 1, because (x, y) is (1, 0) to begin with and the first move is necessarily pos=1 and hop = 0, after that since a[1] = 1 to n-1, so next pos must be greater than 1. So the start state is some (pos, hop=1) with pos >= 2. And it is not hard to see that if we ever have the same (pos, hop) appearing again, then it is a loop. Otherwise either we end at some (pos, hop) and next move get to pos out of bounds, that is, pos > n or pos <= 0. This will stop the sequence. The only remaining case is when pos = 1. Then if hop = 1, we know that next move is x - a[x], where we have x = 1 and a[1] >= 1, so next move must have pos <= 0, and the sequence will stop. The other case is that hop = 0, then we have next move is x + a[x] for x = 1. This will get us to next pos = 1 + a[1]. However, the only way we can get to this pos = 1 + a[1] is by starting at (x, y) = (1, 0) and when a[1] is set to the number such that pos = 1 + a[1], so we started at x=1 and val = a[1], and after some steps we are at x=1 again, and the next pos must be 1 + a[1], so we must have a loop (**this part is not clear as I would like to**).
We have covered all cases and it is clear that we only need to do dfs for n*2 states, the graph has 2n nodes and 2n edges, given n = 10^5, it runs in time limit.
Friday, March 15, 2013
TC 573
Summary: failed 250 and that's it. Finally down to div 2.
250: Given an array of int, a[n], find max number of triples such that value(triple) > target.
value(triple) is min + max.
Solution: easy to see that if we sort a[n], then two pointers left and right going towards each other. Move left++ while left + right <= target. The pitfall is when we have left and right but there are only two elements remaining.
450: Given a graph with 50 nodes, each node has altitude[i]. edge[i][j] = 'Y' or 'N'. Find a path from 0 to N-1 such that each node has altitude[i] changed to b[i] and node[k-1] has height >= node[k] in path. Cost is sum of abs(altitude[i] - b[i]).
The hardest part is to figure out that optimal path only need b[i] to be one of a[0] .. a[N-1]
Then it is a shortest path problem with state being (pos, alt) meaning node[pos] is taking altitute[alt]
Could use either Dijkstra or Bellman-Ford.
Here is a sketch of proof:
// claim: there is an opt path uses a[i] altitude only
// proof: given an opt path, convert into a path uses a[i] only
// first break the path into blocks with each block using a[k] < b[i] < a[k+1]
// then what happens inside block does not affect outside
// for each block, we can shift the whole thing towards + or -, until one node hits some a[i]
// then we effectively break the block into several blocks and we recurse
// in the end we have an optimal path with each node takes some a[i] altitude only, and in
// every step we never increase the path cost.
//
// then the problem becomes a shortest path problem with vertex (i, j) indicating node[i] is having altitude a[j]
p850: this is wcao's solution
// this is a math problem // // 1. if we consider x[i] + y[i] for i = 0 to n-1, // then the only way for i and j to meet is to // have x[i] + y[i] with the same parity as x[j] + y[j] // because in every step, both change their parity // so first check if all x[i] + y[i] must have same parity // and ans is 0 if not // // 2. now we count the number of ways the wolves can meet // first notice that the x and y are independent, we can // count the number of ways x values meet and y values meet // then just multiply them // consider the minval and maxval of x, call it v // then minval = v[n-1] - M and maxval = v[0] + M // assuming v[0] .. v[n-1] are sorted // // there is a catch here, some wolf might have both odd parity for // x and y, while some might have both even parity for x and y // // solution by wcao: since x[i] + y[i] and x[i] - y[i] uniquely determine // x[i] and y[i], we can work on these two quantities instead, then both // have same parity as M // // now we count for each val from minval to maxval // for a given v[i], how many ways it can make to val // let there be a count of a +1 and a count of b -1 // then a + b = M for M rounds // a - b = val // so the number of ways is (M choose a) which is (M choose (M+val)/2) // notice that val must have the same parity with M to have nonzero result // // although I looked at wcao's solution, when implement it myself, // integer overflow everywhere #include#include #include using namespace std; typedef long long int64; const int MOD = (int)(1e9+7); int fact[100000+5]; int invfact[100000+5]; class WolfPack { public: int fastpow(int a, int b) { int ans = 1; int base = a; while (b) { if (b&1) ans = (int64)ans * base % MOD; base = (int64)base * base % MOD; b /= 2; } return ans; } int inv(int a) { return fastpow(a, MOD-2); } int comb(int n, int k) { int deno = (int64)invfact[k] * invfact[n-k] % MOD; //cout << "deno " << deno << ' ' << inv(deno) << ' ' << fact[k] << ' ' << fact[n-k] << endl; int ans = (int64)fact[n] * deno % MOD; //cout << "comb " << n << ' ' << k << ' ' << ans << endl; return ans; } void init() { fact[0] = 1; for (int i=1; i<100005; ++i) fact[i] = (int64)fact[i-1] * i % MOD; //for (int i=0; i < 10; ++i) cout << fact[i] << endl; for (int i=0; i<100005; ++i) invfact[i] = inv(fact[i]); } int calc(vector v, int m) { sort(v.begin(), v.end()); int minval, maxval; int n = v.size(); int64 ans = 0; for (int i = 1; i < n; ++i) if ((v[i] & 1) != (v[0] & 1)) { return 0; } minval = v[n-1] - m; maxval = v[0] + m; for (int val = minval; val <= maxval; val += 2) // val and m must be same parity { int tmp = 1; for (int i = 0; i < n; ++i) { int diff = abs(val - v[i]); tmp = (int64)tmp * comb(m, (m - diff)/2) % MOD; //cout << tmp << ' ' << val << ' ' << i << ' ' << v[i] << ' ' << diff << endl; } //ans = ((int64)ans + tmp) % MOD; ans += tmp; if (ans >= MOD) ans -= MOD; } return ans; } int calc(vector x, vector y, int m) { int n = x.size(); init(); vector a(n), b(n); for (int i = 0; i < n; ++i) { a[i] = x[i] + y[i]; b[i] = x[i] - y[i]; } return (int64)calc(a, m) * calc(b, m) % MOD; } };
Tuesday, March 12, 2013
CF 172
A: a geometry problem but difficult to implement nonetheless.
B: For each item a[i], if it serves as the second maximum element in the range, then the only choice for first maximum element would be the first one to the left that is larger, or the first one to the right that is larger. Now this looks very similar to the maximum rectangle problem in which you need the first smaller to the left and the first smaller to the right. For problem B you maintain a stack with decreasing elements and a[i] kills the top of stack until the top of stack is larger than a[i], then you push a[i] into stack. Every time you pop an item, called curr out of stack, update ans with curr xor st.top() and curr xor a[i], the one that caused curr to pop. Time complexity O(n)
C: This one is tricky when you look at the problem. If it is a list instead of a tree, then it is easy, because after removing some element, you get a shorter list. However for trees you can have potentially a larger number of different trees when a subtree gets pruned from the input tree.
Now look at it differently and consider each node individually. What is the chance of a node get selected in a step and hence contribute 1 to the final cost. Things happen in other places do not matter, and the only thing that matters is whether some nodes in the path from this node to the root gets selected or not, and since we select each remaining node with equal probability, the only way a node can get selected is to get selected before any of its ancestor, and the probability is 1/depth[i] for node a[i], and this probability remains the same until one node in the path from a[i] to root a[1] gets selected and then we are done with a[i]. So the expected total number of steps is:
sum over i=1 to n, 1/depth[i]
This is reminiscent of the analysis in randomized quicksort when you need to find the probability that two items get 1 comparison or never compared. You get 1 comparison if one of them gets chosen as pivot before any other item in between becomes a pivot, in which case the two items will enter separate partition and never compared.
B: For each item a[i], if it serves as the second maximum element in the range, then the only choice for first maximum element would be the first one to the left that is larger, or the first one to the right that is larger. Now this looks very similar to the maximum rectangle problem in which you need the first smaller to the left and the first smaller to the right. For problem B you maintain a stack with decreasing elements and a[i] kills the top of stack until the top of stack is larger than a[i], then you push a[i] into stack. Every time you pop an item, called curr out of stack, update ans with curr xor st.top() and curr xor a[i], the one that caused curr to pop. Time complexity O(n)
C: This one is tricky when you look at the problem. If it is a list instead of a tree, then it is easy, because after removing some element, you get a shorter list. However for trees you can have potentially a larger number of different trees when a subtree gets pruned from the input tree.
Now look at it differently and consider each node individually. What is the chance of a node get selected in a step and hence contribute 1 to the final cost. Things happen in other places do not matter, and the only thing that matters is whether some nodes in the path from this node to the root gets selected or not, and since we select each remaining node with equal probability, the only way a node can get selected is to get selected before any of its ancestor, and the probability is 1/depth[i] for node a[i], and this probability remains the same until one node in the path from a[i] to root a[1] gets selected and then we are done with a[i]. So the expected total number of steps is:
sum over i=1 to n, 1/depth[i]
This is reminiscent of the analysis in randomized quicksort when you need to find the probability that two items get 1 comparison or never compared. You get 1 comparison if one of them gets chosen as pivot before any other item in between becomes a pivot, in which case the two items will enter separate partition and never compared.
Thursday, March 7, 2013
mesos build on Ubuntu 12.04 LTE
Hey Flo, run configure with --disable-perftools.
./bootstrap
mkdir build
../configure --with-webui --with-included-zookeeper
make
make check
# I correctly guess that the error below is due to running without sudo :)
[ FAILED ] 19 tests, listed below:
[ FAILED ] CgroupsIsolationTest.ROOT_CGROUPS_BalloonFramework
[ FAILED ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Enabled
[ FAILED ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Subsystems
[ FAILED ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Mounted
[ FAILED ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Get
[ FAILED ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_NestedCgroups
[ FAILED ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Tasks
[ FAILED ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Read
[ FAILED ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Write
[ FAILED ] CgroupsAnyHierarchyWithCpuMemoryTest.ROOT_CGROUPS_Busy
[ FAILED ] CgroupsAnyHierarchyWithCpuMemoryTest.ROOT_CGROUPS_SubsystemsHierarchy
[ FAILED ] CgroupsAnyHierarchyWithCpuMemoryTest.ROOT_CGROUPS_MountedSubsystems
[ FAILED ] CgroupsAnyHierarchyWithCpuMemoryTest.ROOT_CGROUPS_CreateRemove
[ FAILED ] CgroupsAnyHierarchyWithCpuMemoryTest.ROOT_CGROUPS_Listen
[ FAILED ] CgroupsNoHierarchyTest.ROOT_CGROUPS_MountUnmountHierarchy
[ FAILED ] CgroupsAnyHierarchyWithCpuAcctMemoryTest.ROOT_CGROUPS_Stat
[ FAILED ] CgroupsAnyHierarchyWithCpuMemoryFreezerTest.ROOT_CGROUPS_Freeze
[ FAILED ] CgroupsAnyHierarchyWithCpuMemoryFreezerTest.ROOT_CGROUPS_Kill
[ FAILED ] CgroupsAnyHierarchyWithCpuMemoryFreezerTest.ROOT_CGROUPS_Destroy
./bootstrap
mkdir build
../configure --with-webui --with-included-zookeeper
make
make check
# I correctly guess that the error below is due to running without sudo :)
[ FAILED ] 19 tests, listed below:
[ FAILED ] CgroupsIsolationTest.ROOT_CGROUPS_BalloonFramework
[ FAILED ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Enabled
[ FAILED ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Subsystems
[ FAILED ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Mounted
[ FAILED ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Get
[ FAILED ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_NestedCgroups
[ FAILED ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Tasks
[ FAILED ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Read
[ FAILED ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Write
[ FAILED ] CgroupsAnyHierarchyWithCpuMemoryTest.ROOT_CGROUPS_Busy
[ FAILED ] CgroupsAnyHierarchyWithCpuMemoryTest.ROOT_CGROUPS_SubsystemsHierarchy
[ FAILED ] CgroupsAnyHierarchyWithCpuMemoryTest.ROOT_CGROUPS_MountedSubsystems
[ FAILED ] CgroupsAnyHierarchyWithCpuMemoryTest.ROOT_CGROUPS_CreateRemove
[ FAILED ] CgroupsAnyHierarchyWithCpuMemoryTest.ROOT_CGROUPS_Listen
[ FAILED ] CgroupsNoHierarchyTest.ROOT_CGROUPS_MountUnmountHierarchy
[ FAILED ] CgroupsAnyHierarchyWithCpuAcctMemoryTest.ROOT_CGROUPS_Stat
[ FAILED ] CgroupsAnyHierarchyWithCpuMemoryFreezerTest.ROOT_CGROUPS_Freeze
[ FAILED ] CgroupsAnyHierarchyWithCpuMemoryFreezerTest.ROOT_CGROUPS_Kill
[ FAILED ] CgroupsAnyHierarchyWithCpuMemoryFreezerTest.ROOT_CGROUPS_Destroy
Saturday, March 2, 2013
TCO 13 round 1B
This could have been my first ever successful submission to 500 and 1000, although I did not take the competition for other work. Anyway this round seems easier than most div1 SRM. Here are my solution:
250: sort and add a[0], a[n-1], then a[1], a[n-2], and keep track of min and max.
500: try all 2^15 possible moves for rows, then you have a fixed choice for col moves.
1000: two strings would match if and only if break them down to pairs of letters, a[0] with a[1], and a[2] with a[3], ... and the pairs match (either a[2*i] to b[2*j] and a[2*i+1] to b[2*j+1], or a[2*i] to b[2*j+1] and a[2*i+1] to b[2*j])
And you only need to find one word, then iterate through the rest to find a match, cross both. Repeat until no more word can be matched.
250: sort and add a[0], a[n-1], then a[1], a[n-2], and keep track of min and max.
500: try all 2^15 possible moves for rows, then you have a fixed choice for col moves.
1000: two strings would match if and only if break them down to pairs of letters, a[0] with a[1], and a[2] with a[3], ... and the pairs match (either a[2*i] to b[2*j] and a[2*i+1] to b[2*j+1], or a[2*i] to b[2*j+1] and a[2*i+1] to b[2*j])
And you only need to find one word, then iterate through the rest to find a match, cross both. Repeat until no more word can be matched.
Friday, February 22, 2013
TC 571
p250 given a prefix and try next digit from 0 to 9, stop if current number is over n.
vector ans;
void rec(string pre, long long prod, int n)
{
if (prod > n) return;
ans.push_back(pre);
for (ch = '0'; ch <= '9'; ++ch)
rec(pre+ch, prod*10+ch-'0', n);
}
p500 need to find weighted maximum clique, yes, find max clique for n=50. The solution uses backtracking and it builds maximum clique containing a particular vertex from 1 to n, for each center, use dfs to explore next vertex to expand. This runs within time limit.
Some implementation tip: use bitmask to remember vertices in clique already, since 50 fits in 64 bits.
vector
void rec(string pre, long long prod, int n)
{
if (prod > n) return;
ans.push_back(pre);
for (ch = '0'; ch <= '9'; ++ch)
rec(pre+ch, prod*10+ch-'0', n);
}
p500 need to find weighted maximum clique, yes, find max clique for n=50. The solution uses backtracking and it builds maximum clique containing a particular vertex from 1 to n, for each center, use dfs to explore next vertex to expand. This runs within time limit.
Some implementation tip: use bitmask to remember vertices in clique already, since 50 fits in 64 bits.
Wednesday, February 20, 2013
CF 168
A. among a[i] and k*a[i] you can have only one of them. If we sort all numbers, then it is always better to choose a[i] since a[i]*k potentially will conflict with a higher number. Some inductive argument will prove this claim. Then it takes only one scan of the sorted array and remember the banned numbers in a c++ stl set. One catch is to use 64 bit integer as k can be 10^9.
B. interesting problem. No solution yet. Here are some observations:
1. There is always a solution. Why? You can first solve a subproblem with only n-1 nodes, and then that subtree is all zero, now you have only one node with nonzero value and it is easy to see how to do the rest.
2. Order of operations do not matter. Actually, if you fix the set of operations, any permutation of ordering give you same end result.
3. Given 2, then at least one leaf node needs to be considered at most once.
B. interesting problem. No solution yet. Here are some observations:
1. There is always a solution. Why? You can first solve a subproblem with only n-1 nodes, and then that subtree is all zero, now you have only one node with nonzero value and it is easy to see how to do the rest.
2. Order of operations do not matter. Actually, if you fix the set of operations, any permutation of ordering give you same end result.
3. Given 2, then at least one leaf node needs to be considered at most once.
facebook hackercup round 3
When it is down to top 100, the competition is tough, as is the problem.
A. given a matrix of conflict M[10][10], M[i][j] = 1 if i and j conflict. Find count of valid numbers with length K or less. K can be 10^18. A number is valid if any two conflicting digits have two other digits between them.
I don't have a solution but here is some idea.
Let C[L][first][second] be the count of numbers with length at most L and first digit and second digit, both first and second could be zero.
Then C[L][first][second] = sum of C[L-1][second][d] for d = 0 to 9, and first does not conflict with d. (We already know that second does not conflict with d or C[L-1][second][d] is zero)
This is a linear recurrence and since L could be 10^18, this hints to a solution using fast exponentiation. It would be an easy problem if we need only one digit separation, now it is two digits.
Update: watashi's solution, you can map [first][second], a 2d vector into 1d by using a*n+b as coordinator, then the rest is just like a linear recurrence with two dimensions, L, and pair of first and second. Everybody knows fastpow can do this.
A. given a matrix of conflict M[10][10], M[i][j] = 1 if i and j conflict. Find count of valid numbers with length K or less. K can be 10^18. A number is valid if any two conflicting digits have two other digits between them.
I don't have a solution but here is some idea.
Let C[L][first][second] be the count of numbers with length at most L and first digit and second digit, both first and second could be zero.
Then C[L][first][second] = sum of C[L-1][second][d] for d = 0 to 9, and first does not conflict with d. (We already know that second does not conflict with d or C[L-1][second][d] is zero)
This is a linear recurrence and since L could be 10^18, this hints to a solution using fast exponentiation. It would be an easy problem if we need only one digit separation, now it is two digits.
Update: watashi's solution, you can map [first][second], a 2d vector into 1d by using a*n+b as coordinator, then the rest is just like a linear recurrence with two dimensions, L, and pair of first and second. Everybody knows fastpow can do this.
Subscribe to:
Posts (Atom)
