darkshadows's blog

Google APAC Kickstart 2017 Round G
By darkshadows, history, 7 years ago, In English

Throughout the year, Code Jam hosts online Kickstart rounds to give students 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.

Inviting you to solve some fun and interesting problems with Professor Shekhu and Akki this Sunday(hopefully in your timezone as well!) Oct 22 05:00 UTC – 08:00 UTC.

You'll find the link to contest dashboard at https://code.google.com/codejam/kickstart/ on the day of the contest. Also, we'll try to publish analysis as early as possible.

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

Comments Comments (43)
| Write comment?
»
7 years ago, # |
  Vote: I like it +72 Vote: I do not like it

Will the scoreboard of previous round ever be fixed?

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

Does anyone from any APAC of this year get interview call?

just curious to know.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +13 Vote: I do not like it

    I am also a little bit curious, with previous contest's scoreboard not fixed, can darkshadows kindly tell if any of the top scorers of Kickstart (Round D, E, F) held specially for Asia region (including India) were called this time?

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

      Yeah some people got

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

        "some people" is a little vague. Do they make the selected candidates sign some kind of non disclosure which doesn't allows them to disclose their selection for interviews? if anyone can share some names please do.

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

          No for your question and i said "some people got" because i got the call myself and what will you achieve by knowing the names of other peoples too?

          my prev comment got downvoted ,it seems those[who downvoted] are unable to digest their failure in getting shortlisted.

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

      I don't have this specific info handy and the decision is up to recruiters, and is affected by various factors(head count etc.). Personally, I won't worry too much about this at the moment, and focus on getting a good score in upcoming rounds :)

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

    I'm top 30 in Round E but I have no messages from google(( I'm from Europe (Ukraine), maybe this is the cause.

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

      yes ,rounds from D to G were for India.

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

        I wish they fix the scoreboard soon. I am guessing that I am under top 20-30 — which is my best performance so far. Hoping that at least this time I will get a call. :/

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

The scoreboard is still broken.

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

Please at least mention the number of people who solved each problem in the analysis after the contest ends.

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

DP everywhere.

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

    B can be solved by constructing a Minimum Spanning Tree too.. The answer will be the total cost of the MST

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

      Can you explain how?

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

        For all pairs of cards (i, j) precompute the minimum addition to be performed. This can be thought of as a graph, where all cards are connected to all other cards, and the cost of the edge is the minimum addition.

        Now if we find the MST, you can choose any node as the root, and then perform the given operation(choosing 2 cards and removing 1) from the leaves to the top. In the end, the root will be the card left.

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

        Consider a complete graph with N nodes numbered 1, 2, ..., N where ith card denotes the ith node. Weight of edge between node i and j is min(r[i]^b[j], b[i]^r[j]). From this graph, you need to select N — 1 edges. Try to get the intuition that the selected edges must never have a cycle.

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

    How do you solve B using DP?

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

Can anyone tell me why the following code for Problem A is wrong?

The idea is to first find the repeated length r of A^n mod P,

then find the value of N! mod r.

Then the result will be A^r mod P.

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

    the problem is suppose repeated length is "C". and it repeats after first "X" terms and Q=n!. then answer is (Q-X)%C=((Q%C-X%C)%C). In your notion (r=C) . You forgot to take into account X. example a=2 mod=12 then a^0=1,a^1=2,a^2=4,a^3=8,a^4=4,hence X=2,C=2.

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

      Thank you for your reply!

      I also considered this condition at the first time. But then I realize that:

      If A^m mod P == A^n mod P, then A^{m-1} mod P == A^{n-1} mod P. So that X must be 0.

      What is the flaw in the above mentioned statement? Thanks again.

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

      Sorry I did not notice your example just. Let me think for a moment...

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

        I have submitted using similar idea you can see my code link. Though there exist a very simple answer of that question. see this code. this rajat's code

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

          Thanks for your kindly reply! Finally I also got my code accepted:

          Code
          → Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve problem A , Is that so easy :(
I didn't get how to approach that problem.

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

    Just use the idea of an * m = (an)m. So

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

    A^n! = (((A^1)^2)^3)^...^n
    (A^n!)%p = (((((((A^1)%p)^2)%p)^3)%p)^...^n)%p

    Use logarithmic exponentiation. I solved it in this way.

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

      How to solve C?

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

        I solved C using dp.

        I will describe what I did. There are probably many optimizations over what I did, but it ran in time, so I didn't try further.

        Find answer for all ranges [i, j] for all rows and columns.
        And then combine them to find answer for a matrix with top left corner (x1, y1) and right bottom corner (x2, y2). That can be found by:

        maxim = 0;
for (i = x2; i > x1; i--)
    maxim = max(maxim, ans[x1][y1][i-1][y2]+ans[i][y1][x2][y2]);
for (i = y2; i > y1; i--)
    maxim = max(maxim, ans[x1][y1][x2][i-1]+ans[x1][i][x2][y2]);
ans[x1][y1][x2][y2] = maxim + minim; //minim = minimum value in the submatrix

        Answer will be ans[1][1][n][m].

        https://ideone.com/gmlpjj

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

Here is my editorial.

Problem 1. A^(N!) = (...(((A^1)^2)^3)...)^N

def solve(A, N, P):
    for e in xrange(1, 1 + N):
        A = pow(A, e, P)
    return A

Problem 2. Draw an edge (i, j) if on some card i is paired with some card j. There are N-1 unique edges. We want the lowest sum of edges such that we form one connected component with the edges — this is just an MST.

class DSU:
    #details omitted
    
def solve(N, A, B):
    cards = zip(A, B)
    edges = [(min(c[0] ^ d[1], c[1] ^ d[0]), i, j)
             for i, c in enumerate(cards)
             for j, d in enumerate(cards) if i < j]
    edges.sort()
    dsu = DSU(N)
    return sum(dsu.union(i, j) and cost
               for cost, i, j in edges)

Problem 3. Let dp(r1, c1, r2, c2) be the answer for the submatrix with those corners. For each of the (r2-r1) + (c2-c1) cuts, calculate the answer recursively. It depends on being able to query the minimum value that occurs in r1, c1, r2, c2.

def solve(A, R, C):
    def lookup_min(r1, c1, r2, c2):
        #details omitted
    
    @memoize
    def dp(r1, c1, r2, c2):
        if r1 == r2 and c1 == c2: return 0
        ans = None
        for r in xrange(r1, r2):
            ans = max(ans, dp(r1, c1, r, c2) + dp(r+1, c1, r2, c2))
        for c in xrange(c1, c2):
            ans = max(ans, dp(r1, c1, r2, c) + dp(r1, c+1, r2, c2))
        return ans + lookup_min(r1, c1, r2, c2)
    
    return dp(0, 0, R-1, C-1)
→ Reply
»
7 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Solutions & Explanations have been updated here: http://ckcz123.com/blog/posts/kickstart-2017-round-g/

→ Reply