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.

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…

0i 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

0question B is just too hard…

still don't have any ideas…

0solved it in different approach

if(k==a*(2^n)-1) On

or off

0Problem B is hard, I'm working on it

0solved it in different approach

if(k==a*(2^n)-1) On

or off

and what is 'a'?

0a 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 …

0I had A completed and C timeouted, now stucking in B… OMG I don't wanna lose so SOON

0The 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!

0In 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!

0Me too understand so…

I think to Euler algorithm but first i need for a "bigint" library in c#…

Someone know a free library?

0In 3.5 framework:D

0To: 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?

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

0To: 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 ?

0Think 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 ???

0GCD(t_i + y) not GCD(t_i) for i=0..n

0When 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 ???

0Solve 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…

0test

0The 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

0And how do compute the value of k ?

0well…..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

0what about gdc(differences_of_t_i)-gdc(t_i)

looks good on the examples but fails somewhere

0For 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

0jclin 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?

0Can 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 😛

0For all t_i: All_Factors.add(Factors(t_i + y))

T = max(All_Factors)

0^ What is "y" on that formula?

0what will be range of y while calculating T?

0i gt the aNS FOR B

0how did you calculate it?

0I want to know in what pattern do I need to check for y while calculating T?

0I'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.

0do the same thng as u were dng for n=2

0gcd(tiList), already does calculations for the entire list.

0I 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?

0tiList 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.

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

0did any one gt the qualification mail

0No, not yet. Be patient 🙂

>> did any one gt the qualification mail

0Hello, I do not agree with the previous commentator – not so simple

0