darkshadows's blog

Google Code Jam Kickstart 2018 Round F
By darkshadows, 6 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, Sept 30, 2018 19:00 UTC.

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

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

Comments Comments (15)
| Write comment?
»
6 years ago, # |
  Vote: I like it +27 Vote: I do not like it

What kind of rank can get the attention of a recruiter? Can anyone please share?

Thanks in advance.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +49 Vote: I do not like it

    5th place is not enough from my experience (Kickstart Round C 2018)

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

      This is actually quite interesting. I've heard from people getting interviews with a rank as high as 350, so something tells me that it isn't rank itself that they use to offer interviews. Maybe your region/country would make a difference?

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

      I got 3rd place in Kickstart Round C. Back then, I was really really hyped because I thought I would get an email or something from Google. No contact whatsoever :(

      → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    27th place was enough for SWE interviews in 2016. (It was APAC and not Kickstart then)

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

Analysis is published. https://codejam.withgoogle.com/codejam/contest/3314486/dashboard#s=a

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

    Hey is Google hiring interns on the basis of today's kickstart

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

Hey, I tried problem-B's large dataset case but had doubt even in the analysis (here), can anyone help?

When f(v) has no food assigned its says to give any food to v but if(l(f(v))>l(v)) and d(v)>d(f(v)) then there may be case that f(f(v)) has already a food assigned(say F1) and thus if assign F1(which means F2 to v) average distance will more compared to when we assign F2 to f(v)(which means F1 to v).

So how can we count the minimum average distance cases is this way?

P.S.: If there is any other method please enlighten :)

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

    Hi, your can solve it in this way.

    Sort the roads by distance in increasing order. Initialize graph with no road with V nodes. From lowest distance to highest connect on initialized graph if one of endpoints have not connected before to any other node(i.e. no neighbor). By doing this our graph converged N disconnected trees, where answer is 2^N. (there is special case when zero road is included.). We can color connected tree with two color(Fruit and vegetable as color), such that every neighbor is different color, in two way. This lead to 2^N. Also note that each node is connected to at least one other node.

    Why this way of connecting is minimum? When we connect we use the roads which are the smallest distance roads for one of its endpoints.

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

      Can it also be said that the required answer is equal to the number of different MST of the given graph?

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

        No, in MST makes tree where each node is reachable from any node. But in this case it is possible to use less than V-1 roads to connect, such as second example.

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

      @bayram Thanks, this is quite an inspiring way of solving!

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

      Please explain the special case when road length is zero.

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

        Say there are 3 vertices, 3, 4 and 5 and edge weight connecting 3 and 4 is 0, and say edge weight is 10 for edge connecting 3 and 5. Suppose, the nearest neighbour to 5 is 3, i.e at distance of 10. Hence, we can assign any of the labels either fruit or vegetable to vertex 5, since in this case labels of 3 and 4 will be opposite and 5 is at same distance with 3 as well as 4. That's it.

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

        Suppose you have a graph after connecting some roads and suppose road A to B is zero distance. First of all A's and B's color should be different. If we make them same then it will not be minimum.

        Any node(except A and B) which is directly connected to A or B does not necessarily chose according to A's or B's color, because if it reaches to A then it can also reach to B and vice versa. So we can think each them as disconnected tree where there is two ways to color. For example.
        9 8
        1 2 6
        3 4 0
        5 6 7
        3 5 1
        4 6 2
        5 7 3
        7 8 4
        6 9 5

        We make new graph which includes all roads except (5,6) with distance 7. Only nodes 5 and 6 have roads which connects to 3 or 4. So we can think that [5,7,8] and [6,9] as new disconnected tree. As a result N will be change by -1 + 2 + 1.
        -1 for tree which includes zero road.
        +2 for newly disconnect trees.
        +1 for coloring endpoints of zero road. (A is vegetable, B is fruit and vice versa).

        In short, we should count roads which connects to zero road endpoints in our new graph and add that number to N.

        → Reply