## Google Code Jam Qualification Round 2010

May 7, 2010

Google Code Jam has begun and there is still time to compete, so register and start coding now if you have not!

For now, I would like to give some overview on the qualification round.

Problem A: Snapper Chain is solved by most people (3597 people so far), with the number of correct being 79% so far. Problem B: Fair Warning is the most difficult, being solved by only 847 people so far, correct rate being 76%. Problem C: Theme Park is solved by a total of 2370 people so far, with correct rate being 92%.

I would say Problem C is the easiest problem among the three, but only for the small input. The large input is quite tricky and you have to be careful of some traps. (Hint: Do your big(O) analysis before you attempt the large input!). I predict that Problem C: large input is gonna have the lowest correct rate among all.

Although Problem A is the most solved problem, it is a bit tricky as well, as you can see from the correct rate being only 79% (Compared to Problem C: small input – 92%). The problem description is also unnecessary complicated. This problem is easy after you discovered the pattern. Then generalizing it is straight forward from there.

Problem B is the hardest among all. So far I am still stucked on this problem. First of all, the question does take some time to digest. It seems like a Math problem to me, but so far I do not have any idea how to approach this problem. The large input for this problem contains integer up to 10^50, which is quite intimidating.

I would update this blog with tips and solutions to the problems once the qualification round has ended, so stay tune!

Update:
Qualification round has just ended! I hope everybody has a great time solving the problems!

If you scored at least 33 points, congratulations because you are qualified to the next round! The next round starts on May 22, and you’ve got 3 chances to qualify (called Round1A, 1B and 1C). Each round is limited to 2 and a half hours and your rank need to be within the top 1000 in order to qualify for Round 2.

Google is also nice to provide a detailed contest analysis, and solutions for each problems. According to them, this year’s questions are tougher than usual. Problem B: Fair Warning is indeed the toughest question. Besides, it is the first question in Code Jam that uses Big Integer, so be prepared for a good Big Integer library (some language provides it) in the future!

As predicted, Problem C: large input has the lowest correct rate of all (only 40% of the attempts passed the large input). This is why complexity analysis is very important in this situation.

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)

### 42 responses to Google Code Jam Qualification Round 2010

1. i have tried for an hour but could not solved problem A.
my approach is:

scanf("%d",&tc);

for(t=1;t<=tc;t++)
{
scanf("%d %d",&n,&k);
m=2*n;

mm=k%m;

m=m-1;

if(mm==m)
printf("Case #%d: ON\n",t);
else
printf("Case #%d: OFF\n",t);
}

VA:F [1.9.22_1171]
0
2. i have tried problem A for an hour but i could not solved it yet.

my approach is

scanf("%d",&tc);

for(t=1;t<=tc;t++)
{
scanf("%d%d",&n,&k);

m=2*n;

mm=k%m;
m–;

if(mm==m)
printf("Case #%d: ON\n",t);
else
printf("Case #%d: OFF\n",t);
}

VA:F [1.9.22_1171]
0
3. question B is just too hard…
still don't have any ideas…

VA:F [1.9.22_1171]
0
4. solved it in different approach
if(k==a*(2^n)-1) On
or off

VA:F [1.9.22_1171]
0
5. Problem B is hard, I'm working on it

VA:F [1.9.22_1171]
0
6. solved it in different approach
if(k==a*(2^n)-1) On
or off

and what is 'a'?

VA:F [1.9.22_1171]
0
7. a is any positive integer…
like
if n=4 k=47
then
a*(2^n)-1= 3*(2^4)-1=3*16-1=47=k
so it should be on
….
in summary to On the light 'a' should be integer …

VA:F [1.9.22_1171]
0
8. I had A completed and C timeouted, now stucking in B… OMG I don't wanna lose so SOON

VA:F [1.9.22_1171]
0
9. The A is simple, very simple.
The C could be simple for small input, but the startegy for large should be different.(I understand this too late…)
In the B someone understend the constraint for T? I'm not sure that I undersatnd the right thing!

VA:F [1.9.22_1171]
0
10. In B you have to obtain the lowest y which maximizes the GCD(t_i + y) ( T is equal to this GCD). But, how to compute that y? That's a good question which I DON'T KNOWWWW!!! ARgh!

VA:F [1.9.22_1171]
0
11. Me too understand so…
I think to Euler algorithm but first i need for a "bigint" library in c#…
Someone know a free library?

VA:F [1.9.22_1171]
0
12. In 3.5 framework:D

VA:F [1.9.22_1171]
0
13. To: Anonymous,

I really don't think that you need a "Big Int" library for problem B. Rethink your approach.

>> Me too understand so…
>> I think to Euler algorithm but first i need for a "bigint" library in c#…
>> Someone know a free library?

VA:F [1.9.22_1171]
0
14. Anyone figured out what we have to do with the problem B ?

VA:F [1.9.22_1171]
0
15. To: Anonymous,

I think I almost got it, however I still fail the small input. I am still fixing on the issue, but I believe that something related to GCD (Greatest common divisor) is the way to go.

>> Anyone figured out what we have to do with the problem B ?

VA:F [1.9.22_1171]
0
16. Think too that GCD is the way to go, but I can not figure how to use it.

Take the example Google provide: three numbers 26000, 11000 and 6000. The GCD for these 3 numbers is 1000. How can they find after that the result is 4000 ???

VA:F [1.9.22_1171]
0
17. GCD(t_i + y) not GCD(t_i) for i=0..n

VA:F [1.9.22_1171]
0
18. When you add y = 4000 to 26000, 11000 and 6000, they become 30000, 15000 and 10000, GCD of which is 5000. 5000 is the highest GCD obtainable by adding ANY y to the 3 given numbers. So the minimum y (4000) which when added yields 5000 as the GCD is the solution.

I can't figure out how to tell when the GCD is maximum. How can you be sure it won't increase anymore for any higher values of y?

>>Think too that GCD is the way to go, but I can >>not figure how to use it.

>>Take the example Google provide: three >>numbers 26000, 11000 and 6000. The GCD for >>these 3 numbers is 1000. How can they find >>after that the result is 4000 ???

VA:F [1.9.22_1171]
0
19. Solve the first line of the sample test file. But never end with the second line as GCD(1, 10, 11) = GCD(1 + y, 10 + y, 11 + y) for any i…

VA:F [1.9.22_1171]
0
20. test

VA:F [1.9.22_1171]
0
21. The largest possible integer factor T is the largest integer such that for all t_i, t_i = k mod T where k is a constant. Then the required answer is T – k

VA:F [1.9.22_1171]
0
22. And how do compute the value of k ?

VA:F [1.9.22_1171]
0
23. L said on May 8, 2010

well…..no idea, just know that an upper bound of T is "second smallest t_i – 1", because if T is largest than this bound, they never give same k for k mod T

VA:F [1.9.22_1171]
0
24. what about gdc(differences_of_t_i)-gdc(t_i)

looks good on the examples but fails somewhere

VA:F [1.9.22_1171]
0
25. L said on May 8, 2010

For N = 2, the required T is always difference of t_1 and t_2, but not yet have idea how to generalize it to N > 2

VA:F [1.9.22_1171]
0
26. jclin said…

T = max(GCD(all(t_i) + y))

For y==0, T of the example would be 1000.
For y==4, T would be 5000.
For y==40, T would be 50000.
For y==400, T would be 500000.

How is there a solution to this problem?

VA:F [1.9.22_1171]
0
27. Can someone who has successfully submitted a solution please provide his input and output files. My algo seems to work fine on paper and on the sample cases but fails on some test case.

P.S.: Since the test cases change every time, I hope this doesn't count as plagiarism. If it does, sorry! My bad

VA:F [1.9.22_1171]
0
28. For all t_i: All_Factors.add(Factors(t_i + y))
T = max(All_Factors)

VA:F [1.9.22_1171]
0
29. ^ What is "y" on that formula?

VA:F [1.9.22_1171]
0
30. what will be range of y while calculating T?

VA:F [1.9.22_1171]
0
31. i gt the aNS FOR B

VA:F [1.9.22_1171]
0
32. how did you calculate it?

VA:F [1.9.22_1171]
0
33. I want to know in what pattern do I need to check for y while calculating T?

VA:F [1.9.22_1171]
0
34. I'm using something like this:
for n in tiList:

y = gcd(tiList-n) – gcd(tiList)

And then I chose y for the greatest ti. Works for the example, but not for the small set.

VA:F [1.9.22_1171]
0
35. do the same thng as u were dng for n=2

VA:F [1.9.22_1171]
0
36. gcd(tiList), already does calculations for the entire list.

VA:F [1.9.22_1171]
0
37. I dont understand tiList in this formula,
y = gcd(tiList-n) – gcd(tiList)
You mean adding all elements in the list i.e. corresponding to N , all nos. given
what does gcd(tiList-n) do?

VA:F [1.9.22_1171]
0
38. tiList is a list containing all given t_is
tList-n, means I'm subtracting each element of the list by n.
The result lowest given y, is your answer.
I can't find what's wrong with this formula. Because it works on example, but still something wrong for the smallset.

VA:F [1.9.22_1171]
0
39. L said on May 8, 2010

I get correct by finding T as the gcd of all the pairwise difference

VA:F [1.9.22_1171]
0
40. did any one gt the qualification mail

VA:F [1.9.22_1171]
0
41. No, not yet. Be patient

>> did any one gt the qualification mail

VA:F [1.9.22_1171]
0
42. Hello, I do not agree with the previous commentator – not so simple

VA:F [1.9.22_1171]
0