As an experiment the Educational Codeforces Round 33 will be rated for Div. 2. ×

darkshadows's blog

By darkshadows, history, 5 weeks 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  

»
5 weeks ago, # |
  Vote: I like it +72 Vote: I do not like it

Will the scoreboard of previous round ever be fixed?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

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

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

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +26 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Any updates?

»
5 weeks 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.

  • »
    »
    5 weeks 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?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      Yeah some people got

      • »
        »
        »
        »
        5 weeks 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.

        • »
          »
          »
          »
          »
          5 weeks 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.

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

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

    • »
      »
      »
      5 weeks 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 :)

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yes ,rounds from D to G were for India.

      • »
        »
        »
        »
        4 weeks 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. :/

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

The scoreboard is still broken.

»
5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

DP everywhere.

  • »
    »
    5 weeks 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

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

      Can you explain how?

      • »
        »
        »
        »
        5 weeks 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.

      • »
        »
        »
        »
        5 weeks 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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    How do you solve B using DP?

»
5 weeks 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
  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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.

    • »
      »
      »
      5 weeks 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...

      • »
        »
        »
        »
        5 weeks 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

        • »
          »
          »
          »
          »
          5 weeks 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
»
5 weeks 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.

  • »
    »
    5 weeks 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
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks 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.

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

      How to solve C?

      • »
        »
        »
        »
        5 weeks 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

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

    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

»
5 weeks 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)
»
5 weeks 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/

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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