Given a string, find the shortest prefix that is an even palindrome, in linear time.
The problem can be seen as asking for a minimum overlap of S and S^R. Then we can slide S^R to match a prefix of S by using Knuth-Morris-Pratt's algorithm to achieve O(n) time.
Saturday, September 4, 2010
Monday, June 14, 2010
GCJ 10 Round 3 Problem A De-RNG-ed
A problem looks simple but hard to get correct.
1. Observations: for k=1 and k=2, and whether S[0] == S[1]
2. Now the formula becomes clear,
S[0]*A + B = S[1] mod P
S[1]*A + B = S[2] mod P
A = (S[2]-S[1])*(S[1]-S[0])^-1 mod P
B = S[1] - S[0]*A
3. How to compute multiplicative inverse?
3.1 Method 1, extended Euclidean Algorithm. The easiest impl is to use recursion
pair gcd(int a, int p)
{
if (p%a==0) return make_pair(1,0);
pair pp = gcd(p%a,a);
int aa = pp.first; int bb = pp.second;
return make_pair(bb-aa*(p/a) , aa);
}
3.2 Method 2, use the fact that a^p = a mod p for prime p
inverse is then mypow(a,p-2)
int mypow(int a, int d, int p)
{
int ret = 1;
while(d)
{
if (d&1) ret = (ret*a)%p;
a = (a*a)%p;
}
return ret;
}
4. Watch integer overflow. Once it gets to 10^6, square it gets 10^12, which is more than MAX_INT.
5. When round a negative number to 0 to P-1, use a = a%p, if (a < 0) a+=p;
a while loop like while(a < 0) a += p; kills you, the running time goes up from a few seconds to 13 min.
6. Precompute primes using naive sieve.
7. Optional, may use binary search to find first prime to work on, but no significant saving in time. Makes no difference in this problem in terms of time.
1. Observations: for k=1 and k=2, and whether S[0] == S[1]
2. Now the formula becomes clear,
S[0]*A + B = S[1] mod P
S[1]*A + B = S[2] mod P
A = (S[2]-S[1])*(S[1]-S[0])^-1 mod P
B = S[1] - S[0]*A
3. How to compute multiplicative inverse?
3.1 Method 1, extended Euclidean Algorithm. The easiest impl is to use recursion
pair
{
if (p%a==0) return make_pair(1,0);
pair
int aa = pp.first; int bb = pp.second;
return make_pair(bb-aa*(p/a) , aa);
}
3.2 Method 2, use the fact that a^p = a mod p for prime p
inverse is then mypow(a,p-2)
int mypow(int a, int d, int p)
{
int ret = 1;
while(d)
{
if (d&1) ret = (ret*a)%p;
a = (a*a)%p;
}
return ret;
}
4. Watch integer overflow. Once it gets to 10^6, square it gets 10^12, which is more than MAX_INT.
5. When round a negative number to 0 to P-1, use a = a%p, if (a < 0) a+=p;
a while loop like while(a < 0) a += p; kills you, the running time goes up from a few seconds to 13 min.
6. Precompute primes using naive sieve.
7. Optional, may use binary search to find first prime to work on, but no significant saving in time. Makes no difference in this problem in terms of time.
Sunday, June 13, 2010
Chad Fowler, the passionate programmer
A good writing from a developer/manager. All sections are 2-pages long with wisdom in developing a software engineers career. Not technical but offers a lot advice. A worth reading. circa 200 pages.
latex template
Spent much time battling LNCS format, last time I had a manuscript with excessive white space but this time I got very small margin and what is worse, the output pdf seems to be in A4 paper, which means much larger margin at bottom than top. Use pdflatex instead of latex/dvips/ps2pdf solves the second problem, but still, where is the large margin?
After went home, I compared previous draft with the current one line by line. And finally, package fullpage is the culprit. Remove it solves all the problems. This is a small paper submitted to a workshop. Now I have 13 pages instead of 10, and the limit is 12 pages. After happily removed one section of pseudo code, everything fits.
After went home, I compared previous draft with the current one line by line. And finally, package fullpage is the culprit. Remove it solves all the problems. This is a small paper submitted to a workshop. Now I have 13 pages instead of 10, and the limit is 12 pages. After happily removed one section of pseudo code, everything fits.
Saturday, June 12, 2010
GCJ 10 Round 3
As in 2008, I failed in round 2. But I made it closer this year. Almost immediately after the contest of round 2, I figured out problem B, the fifa world cup problem. Solving that one in the first hour would send me to the first 500 to qualify. But I just didn't get it and panicked during the contest. Wasting time recompile and test code that I know a problem exists. Lessons learned: Better make every detail correct on paper and write down as much code as possible on paper before start typing. Anyway, it scores zero if the typed code is incorrect.
Round 3 I have to be a spectator, instead of a contestant. All 4 problems are tough to me. But it is amazing to see how other top coders worked out their last problem with only 1min left. Will think over the problems.
Round 3 I have to be a spectator, instead of a contestant. All 4 problems are tough to me. But it is amazing to see how other top coders worked out their last problem with only 1min left. Will think over the problems.
TCO 10 Qual 3
I didn't register in that round so I missed all 3 qual rounds of this year's TCO. But it doesn't hurt to work on the problems in practice room.
p250: Simple problem asking to calc the right bottom number given the top row and left column. The catch is, "return 0 if the bottom right cannot be determined". But this never happes !
p500: Some music jargons. If you read the problem, you know how to solve it.
p1000: The only interesting problem. Given 1000x1000 board, a robot will execute a program made of U, D, L, R, meaning up,down,left,right by one unit. It starts at position (xpos,ypos), and given the program, it will draw the line by executing the program. The problem asks how many pieces will the line cut the board. topleft is (0,0), bottom right is (1000,1000).
After a while I figured out it is a graph connectivity problem. But to actually implement it there are several challenges. To work out the implicit graph needs careful management of the diff in x,y of the two cells separated by that step of robot move. Finally you need to do a BFS or DFS to count number of connected components. But DFS quickly goes segmentation fault because stack overflow. Note each 1x1 cell is a vertex and there are 10^6 of them. A simple BFS with queue implementation will do it.
p250: Simple problem asking to calc the right bottom number given the top row and left column. The catch is, "return 0 if the bottom right cannot be determined". But this never happes !
p500: Some music jargons. If you read the problem, you know how to solve it.
p1000: The only interesting problem. Given 1000x1000 board, a robot will execute a program made of U, D, L, R, meaning up,down,left,right by one unit. It starts at position (xpos,ypos), and given the program, it will draw the line by executing the program. The problem asks how many pieces will the line cut the board. topleft is (0,0), bottom right is (1000,1000).
After a while I figured out it is a graph connectivity problem. But to actually implement it there are several challenges. To work out the implicit graph needs careful management of the diff in x,y of the two cells separated by that step of robot move. Finally you need to do a BFS or DFS to count number of connected components. But DFS quickly goes segmentation fault because stack overflow. Note each 1x1 cell is a vertex and there are 10^6 of them. A simple BFS with queue implementation will do it.
Monday, May 24, 2010
codejam 2010, round 1
I end up participating all 3 subrounds, and the reason is simple, I didn't qualify the first two subrounds.
round 1A is the perfect time, 6pm PST. I gave up problem A because it is too long, although it turns out anyone solve A in one hour gets to top 1000. problem B is a DP for sure, but for some reason I just can't figure out how insertion works. problem C I had every piece correct, even sensed fibonacci numbers. However my submission for small problem is incorrect, while after the match the same code was determined to be correct!
round 1B is another disaster. Solved only problem A, which is far from enough. problem B is not difficult but I am confused on the way swap is done. Failing problem B and looking at problem C. It is even more interesting. I solved small input but forgot to mod 100003, and made 4 failed attempts! God. After the match the moment I looked at one of the top scorer's solution, I figured out the DP recurrence immediately. As later practice attempts show, getting problem C is still tricky because integer overflow issue. Moreover I forgot to remember previous computation to make it a DP.
round 1C, finally I solved problem A and B. This time my analysis made hits and went as far as to make two correct submissions. problem C is still hard for me, I have solved rectangle version but just didn't recognize the same idea for squares. Also the way remove cells is handled is a bit hard to figure out and I basically gave up after 15min, with about 1hour left. It was 3:30am and I have been working on those codejam problems for two days. Having observed I was ranked around 500, I thought I am safe to advance, so went to sleep.
In a way, google codejam is a very nice programming event. The problem sets and testcases are clever and exhaustive. You also get a chance to read top coders's code for free. The analysis is not easy but you will certainly appreciate it once you figure out what is going on. The difference between programming competition and algorithm textbook is that you have to be able to analyze the problem and realize the constraints. Also, you have to be able to code a DP solution.
round 1A is the perfect time, 6pm PST. I gave up problem A because it is too long, although it turns out anyone solve A in one hour gets to top 1000. problem B is a DP for sure, but for some reason I just can't figure out how insertion works. problem C I had every piece correct, even sensed fibonacci numbers. However my submission for small problem is incorrect, while after the match the same code was determined to be correct!
round 1B is another disaster. Solved only problem A, which is far from enough. problem B is not difficult but I am confused on the way swap is done. Failing problem B and looking at problem C. It is even more interesting. I solved small input but forgot to mod 100003, and made 4 failed attempts! God. After the match the moment I looked at one of the top scorer's solution, I figured out the DP recurrence immediately. As later practice attempts show, getting problem C is still tricky because integer overflow issue. Moreover I forgot to remember previous computation to make it a DP.
round 1C, finally I solved problem A and B. This time my analysis made hits and went as far as to make two correct submissions. problem C is still hard for me, I have solved rectangle version but just didn't recognize the same idea for squares. Also the way remove cells is handled is a bit hard to figure out and I basically gave up after 15min, with about 1hour left. It was 3:30am and I have been working on those codejam problems for two days. Having observed I was ranked around 500, I thought I am safe to advance, so went to sleep.
In a way, google codejam is a very nice programming event. The problem sets and testcases are clever and exhaustive. You also get a chance to read top coders's code for free. The analysis is not easy but you will certainly appreciate it once you figure out what is going on. The difference between programming competition and algorithm textbook is that you have to be able to analyze the problem and realize the constraints. Also, you have to be able to code a DP solution.
Subscribe to:
Posts (Atom)
