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.

Will the scoreboard of previous round ever be fixed?

Oh, I wasn't aware. Let me find out!

So, the situation is a little nuanced, but it will be fixed, soon.

I dont believe anyone in google india is capable of doing that. They even can't keep it properly in this round too.

Any updates?

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

just curious to know.

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?Yeah some people got

"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.

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.

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 ...?

top-5

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 :)

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

yes ,rounds from D to G were for India.

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. :/

please don't expect much from them.even if you are in top 20-30. this time,google hiring is pretty low.

Yeah, I have heard the same from others. :/

What was your total time taken to solve all the questions?

Around 1 hr 15 minutes.

The scoreboard is still broken.

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

DP everywhere.

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

Can you explain how?

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.

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.

How do you solve B using DP?

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.

Codethe 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.

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.

Now I see where is the problem.

The above statement is only true when gcd(A, P) = 1.

yes

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

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

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

CodeHow to solve problem A , Is that so easy :(

I didn't get how to approach that problem.

Just use the idea of

a^{n * m}= (a^{n})^{m}. SoCoderes = a;

for(int i = 1; i <= n; ++i){

res = power(res, i, p);

}

why a^(n * m) % p = ( (a^n %p )^m ) %p

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.

How to solve C?

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:

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

https://ideone.com/gmlpjj

see this : http://codeforces.com/blog/entry/54036

the basic idea is (A^n)%p = (A^(n%f(p) * A^(f(p)) )%p, where f(p) = Euler totient function of p

Here is my editorial.

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

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.

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.

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

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=2

Link to the editorial: https://code.google.com/codejam/contest/3254486/dashboard#s=a&a=2