jonathanirvings's blog

Google Code Jam Kickstart 2018 Round G
By jonathanirvings, history, 5 years ago, In English

Throughout the year, Google Code Jam hosts online Kickstart rounds to give participants the opportunity to develop their coding skills, get acquainted with Code Jam’s competition arena, and get a glimpse into the programming skills needed for a technical career at Google.

Each Kickstart round gives participants 3 hours to solve challenging, algorithmic problems developed by Google engineers. Participating is a fun way to grow your coding skills—and potentially explore opportunities at Google.

Inviting you to solve some fun and interesting problems on Sunday, Oct 21, 2018 13:00 UTC (24 hours from now).

Dashboard can be accessed here during the contest. Problem analysis will be published soon after the contest.

  • Vote: I like it
  • +40
  • Vote: I do not like it

Comments Comments (18)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

BUMPing this. Contest starts in about half an hour :)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    jonathanirvings what the top that you will invite to google?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Unfortunately I can't say for sure. It depends on everything happening during the contest (e.g., score distribution).

      Whatever the cutoff is, I wish everybody luck and see you on top of the leaderboard. :)

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

The boring preprocessing of the problem 2 killed all the fun. :/

By the way, how to solve it for large? Does binary search work for the small?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 20   Vote: I like it 0 Vote: I do not like it

    Due to our input size limit policy, unfortunately we need to "compress" every big input problems using pseudorandoms.

    You can check the analysis of this contest, including the analysis for problem B here.

    → Reply
»
5 years ago, # |
← Rev. 37   Vote: I like it +9 Vote: I do not like it

Thanks to everyone who participated in Google Code Jam Kickstart Round G today.

Analysis is available here.

Congratulations to the top placers, and special congratulation to Reyna to finish the contest in 1h22m and winning it.

There will be only one more Google Code Jam Kickstart round left this year. Round H will be held on November 18, 5am UTC. See you in Round H :)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you all for the cool contest!

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I see in analysis of C that precomputation takes N*M*2^traps. But I think it can be reduced if we compress the graph initially i.e we remove the traps and find connected components and treat each component as a vertex. We can reduce complexity to trap*trap*2^trap. Do you think I missed something?

    → Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I got Rank 47. Any hope for me of getting a call for recruitment from Google ?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Although the contest is already over, unfortunately I still can't say for sure. Contacting the contestants for recruitment is the responsibility of our recruiters, and I believe they are working on it now.

    Please be patient and stay tuned. Thank you for your understanding.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think it also depends on the participants ratio...

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry Bro, But i had a rank of 100 in round A and 26 in round B and both the rounds had Good participation. However No call Came yet. So its very unclear what they see for the procedure. However mine would be an internship opportunity so this might not be applicable to you.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Even I meant for the internship bro :)

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And most probably Round A and Round B were not applicable for recruitment in India, either for fulltime or internship or both.

      Consider "What is the recommended schedule for participants?" link

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        arjitkansal please reply to this comment if you get a call in future from google. All the best!!

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        As far as i know, they see your whole graph for all the Kickstart contests(confirmed by a friend who got intern at google via campus and asked the HR regarding it). Anyways, try getting a referral if you can(much safer).

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not getting how to convert the compressed scores back to actual values. Can anyone elaborate the last line in problem B's analysis — "However, note that the answer is not exactly x, since we compressed the scores earlier. The exact details of the implementation are left as an exercise."

→ Reply