By darkshadows, history, 8 months ago, ,

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.

•
• +33
•

 » 8 months ago, # |   +72 Will the scoreboard of previous round ever be fixed?
•  » » 8 months ago, # ^ |   +2 Oh, I wasn't aware. Let me find out!
•  » » 8 months ago, # ^ |   0 So, the situation is a little nuanced, but it will be fixed, soon.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   +26 I dont believe anyone in google india is capable of doing that. They even can't keep it properly in this round too.
•  » » » 8 months ago, # ^ |   +6 Any updates?
 » 8 months ago, # |   +25 Does anyone from any APAC of this year get interview call?just curious to know.
•  » » 8 months ago, # ^ | ← Rev. 3 →   +13 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?
•  » » » 8 months ago, # ^ |   -16 Yeah some people got
•  » » » » 8 months ago, # ^ |   +15 "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.
•  » » » » » 8 months ago, # ^ |   0 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.
•  » » » » » » 8 months ago, # ^ |   0 What rank did you get approximately? Obviously you want to remain anonymous so not your exact rank but an estimate like top 50, top 100 ...?
•  » » » » » » » 8 months ago, # ^ |   +5 top-5
•  » » » 8 months ago, # ^ |   0 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 :)
•  » » 8 months ago, # ^ |   +1 I'm top 30 in Round E but I have no messages from google(( I'm from Europe (Ukraine), maybe this is the cause.
•  » » » 8 months ago, # ^ |   0 yes ,rounds from D to G were for India.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 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. :/
•  » » » » » 8 months ago, # ^ |   0 please don't expect much from them.even if you are in top 20-30. this time,google hiring is pretty low.
•  » » » » » » 8 months ago, # ^ |   0 Yeah, I have heard the same from others. :/
•  » » » » » » » 8 months ago, # ^ |   0 What was your total time taken to solve all the questions?
•  » » » » » » » » 8 months ago, # ^ |   0 Around 1 hr 15 minutes.
 » 8 months ago, # |   +20 The scoreboard is still broken.
 » 8 months ago, # |   +15 Please at least mention the number of people who solved each problem in the analysis after the contest ends.
 » 8 months ago, # |   0 DP everywhere.
•  » » 8 months ago, # ^ |   0 B can be solved by constructing a Minimum Spanning Tree too.. The answer will be the total cost of the MST
•  » » » 8 months ago, # ^ |   0 Can you explain how?
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +4 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.
•  » » » » 8 months ago, # ^ |   +11 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.
•  » » 8 months ago, # ^ |   +25 How do you solve B using DP?
 » 8 months ago, # | ← Rev. 2 →   -10 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. CodeT = int(raw_input()) for t in range(1, T+1): A, N, P = map(int, raw_input().split()) if A % P == 0: print "Case #%d: %d" % (t, 0) continue result = [] product = A % P while product not in result: result.append(product) product *= A product %= P # result is of size at most P repeat = len(result) # compute N! mod repeat if N >= repeat: ans = 0 else: ans = 1 for i in range(1, N+1): ans = (ans * i) % repeat print "Case #%d: %d" % (t, result[ans-1]) 
•  » » 8 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » 8 months ago, # ^ |   0 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.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +1 Now I see where is the problem.The above statement is only true when gcd(A, P) = 1.
•  » » » » » 8 months ago, # ^ |   0 yes
•  » » » 8 months ago, # ^ |   0 Sorry I did not notice your example just. Let me think for a moment...
•  » » » » 8 months ago, # ^ |   0 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
•  » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 Thanks for your kindly reply! Finally I also got my code accepted: CodeT = int(raw_input()) for t in range(1, T+1): A, N, P = map(int, raw_input().split()) if A % P == 0: print "Case #%d: %d" % (t, 0) continue result = {} product = A while product not in result: result[product] = len(result) product *= A product %= P # result is of size at most P head = result[product] repeat = len(result) - head # compute N! mod repeat def check(): temp = 1 for i in range(1, N+1): temp *= i if temp > head: return True return False if check(): res = 1 for i in range(head + repeat): res *= A res %= P ans = 1 for i in range(1, N+1): ans = (ans * i) % repeat ans = (ans - (head % repeat) + repeat) % repeat for i in range(ans): res *= A res %= P else: temp = 1 for i in range(1, N+1): temp *= i res = 1 for i in range(temp): res *= A res %= P print "Case #%d: %d" % (t, res) 
 » 8 months ago, # |   +4 How to solve problem A , Is that so easy :( I didn't get how to approach that problem.
•  » » 8 months ago, # ^ | ← Rev. 2 →   +7 Just use the idea of an * m = (an)m. So Coderes = a; for(int i = 1; i <= n; ++i){    res = power(res, i, p); }
•  » » » 8 months ago, # ^ |   0 why a^(n * m) % p  =  ( (a^n %p )^m ) %p
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 A^n! = (((A^1)^2)^3)^...^n(A^n!)%p = (((((((A^1)%p)^2)%p)^3)%p)^...^n)%pUse logarithmic exponentiation. I solved it in this way.
•  » » » 8 months ago, # ^ |   0 How to solve C?
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 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
•  » » 8 months ago, # ^ |   0 see this : http://codeforces.com/blog/entry/54036the basic idea is (A^n)%p = (A^(n%f(p) * A^(f(p)) )%p, where f(p) = Euler totient function of p
 » 8 months ago, # |   +3 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) 
 » 8 months ago, # |   -8 Solutions & Explanations have been updated here: http://ckcz123.com/blog/posts/kickstart-2017-round-g/
 » 8 months ago, # | ← Rev. 3 →   0 Although official editorial has been published, I'm still wondering whether we can do better on Problem C (Matrix Cutting).Editorial solution uses O(N^2 * M^2 * (N + M)), or roughly about O(N^5), which is pretty slow if N=40 and T=100. Even if I use a down-top (non-recursive) approach, it's still running quite slow.Does anyone know any better solution?Link to the problem: https://code.google.com/codejam/contest/3254486/dashboard#s=p2&a=2Link to the editorial: https://code.google.com/codejam/contest/3254486/dashboard#s=a&a=2