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.

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.

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.

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.