Google Code Jam Qualification Round 2010

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

» Participate in Google Code Jam Now!

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: 4.0/5 (1 vote cast)
Google Code Jam Qualification Round 2010, 4.0 out of 5 based on 1 rating

42 thoughts on “Google Code Jam Qualification Round 2010

  1. Anonymous

    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…

    VA:F [1.9.22_1171]
    0
  2. Anonymous

    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

    VA:F [1.9.22_1171]
    0
  3. Anonymous

    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
  4. Anonymous

    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
  5. Joan Puigcerver

    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
  6. Anonymous

    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
  7. 1337c0d3r

    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
  8. 1337c0d3r

    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
  9. Anonymous

    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
  10. Anonymous

    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
  11. Anonymous

    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
  12. Anonymous

    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
  13. L

    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
  14. Miguel Sánchez

    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
  15. L

    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
  16. Anonymous

    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
  17. Anonymous

    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
  18. Gustavo

    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
  19. Anonymous

    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
  20. Gustavo

    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

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*