Google Code Jam Qualification Round 2010
May 7, 2010 in Uncategorized
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.
Anonymous said on May 8, 2010
i have tried for an hour but could not solved problem A.
reply me incorrect.
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);
}
please help me…
Anonymous said on May 8, 2010
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);
}
//please help me
Anonymous said on May 8, 2010
question B is just too hard…
still don't have any ideas…
Anonymous said on May 8, 2010
solved it in different approach
if(k==a*(2^n)-1) On
or off
Anonymous said on May 8, 2010
Problem B is hard, I'm working on it
Anonymous said on May 8, 2010
solved it in different approach
if(k==a*(2^n)-1) On
or off
and what is 'a'?
Anonymous said on May 8, 2010
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 …
Anonymous said on May 8, 2010
I had A completed and C timeouted, now stucking in B… OMG I don't wanna lose so SOON
Anonymous said on May 8, 2010
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!
Joan Puigcerver said on May 8, 2010
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!
Anonymous said on May 8, 2010
Me too understand so…
I think to Euler algorithm but first i need for a "bigint" library in c#…
Someone know a free library?
Anonymous said on May 8, 2010
In 3.5 framework:D
1337c0d3r said on May 8, 2010
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?
Anonymous said on May 8, 2010
Anyone figured out what we have to do with the problem B ?
1337c0d3r said on May 8, 2010
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 ?
Anonymous said on May 8, 2010
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 ???
jclin said on May 8, 2010
GCD(t_i + y) not GCD(t_i) for i=0..n
Anonymous said on May 8, 2010
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 ???
Anonymous said on May 8, 2010
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…
Anonymous said on May 8, 2010
test
Anonymous said on May 8, 2010
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
Anonymous said on May 8, 2010
And how do compute the value of k ?
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
Miguel Sánchez said on May 8, 2010
what about gdc(differences_of_t_i)-gdc(t_i)
looks good on the examples but fails somewhere
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
Anonymous said on May 8, 2010
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?
Anonymous said on May 8, 2010
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
Anonymous said on May 8, 2010
For all t_i: All_Factors.add(Factors(t_i + y))
T = max(All_Factors)
Gustavo said on May 8, 2010
^ What is "y" on that formula?
Anonymous said on May 8, 2010
what will be range of y while calculating T?
Anonymous said on May 8, 2010
i gt the aNS FOR B
Anonymous said on May 8, 2010
how did you calculate it?
Anonymous said on May 8, 2010
I want to know in what pattern do I need to check for y while calculating T?
Gustavo said on May 8, 2010
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.
Anonymous said on May 8, 2010
do the same thng as u were dng for n=2
Gustavo said on May 8, 2010
gcd(tiList), already does calculations for the entire list.
Anonymous said on May 8, 2010
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?
Gustavo said on May 8, 2010
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.
L said on May 8, 2010
I get correct by finding T as the gcd of all the pairwise difference
Anonymous said on May 9, 2010
did any one gt the qualification mail
1337c0d3r said on May 9, 2010
No, not yet. Be patient
>> did any one gt the qualification mail
generic cialis said on November 24, 2010
Hello, I do not agree with the previous commentator – not so simple