Gumnami's blog

Google Kick Start Round C 2020
By Gumnami, history, 5 years ago, In English

The Round C of Google Kick Start 2020 is scheduled on May 17 2020, 11:00 UTC.
Kick Start is an online coding competition hosted by Google throughout the year. Registrations is also open throughout the year.

Let's discuss the problems here once the contest is over! Happy Coding :)
PS. This contest is more helpful for beginners since the problems are more or less easy.

The dashboard can be accessed from here

  • Vote: I like it
  • -26
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someOne explain me Question Stable Wall?i didn't even get the Question?

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

    same here..lol..

    join all same letter and u can see the shape.

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

      Ya till then i get it.but after that how is stable walls defined?

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

        u are given a wall of (RxC) ..

        U have to tell in which order ... u can build if possible else -1

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

    Lets say W[i][j] is the letter at row i and column j. Now you can say that, W[i][j] depends upon W[i+1][j] (the brick just below it) If both are not the same then you can add the dependency of W[i][j] -> W[i+1][j].

    Now you have a directed graph where each edge A->B shows that A depends upon B. Thus you must place A after B. If there is a cycle in this graph then its impossible to build the wall.

    Otherwise, you can do topological sorting and reverse the order finally to get the answer.

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

2nd question

my sol : https://ideone.com/kDYhav

i dont know why its giving WA....please help...

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

how to solve pefect subarray prblm???????????/ please help

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

    First create an "offset array" of integers $$$C$$$ indexed over $$$[-a_{max} \cdot n, a_{max} \cdot n]$$$, where $$$a_{max} = 100$$$. This can either be manually done with a normal array of size $$$2n \cdot a_{max} + 1$$$ and adding an offset to every array access, or with a helper object / struct. Initialize all $$$C[i] := 0$$$.

    You now want to iterate through $$$a$$$, accumulating the prefix sum into the variable $$$p$$$ that starts with $$$0$$$. First do $$$C[p] \text{++}$$$, then do $$$p \text{ += } a_i$$$. Now for $$$j$$$ counting from $$$0$$$ upward, do $$$ans \text{ += } C[p - j^2]$$$, stopping when $$$p - j^2$$$ is too low. This works because $$$C$$$ stores a count of the prefix sums you have previously seen.

    The key here is identifying what "too low" means. You can stop when $$$p - j^2 < -a_{max} \cdot n$$$ (cause otherwise it would be outside $$$C$$$'s indices!). This gives a runtime complexity of $$$O(n \sqrt {a_{max} \cdot n})$$$. Note that this is a fairly large number for the max case in test set 2, around $$$3 \cdot 10^8$$$, so it may not pass in slower languages or implementations.

    You can't really improve the worst-case complexity, but you can cut it by a constant factor, which can be useful for "edge" complexities like this problem. The best optimization I found so far is to keep the minimum prefix sum seen, and stop when $$$p - j^2$$$ is below it. This not only cuts the search space for the worst case by a significant constant factor, but also improves the average case to $$$O(n\sqrt{\log n \cdot a_{max}})$$$, since the minimum and maximum prefix sum has an expected absolute value of $$$O(\log n\cdot a_{max})$$$ in random cases.

    This type of optimization is particularly useful for Google's competition formats, as there are no hacks and your program is fed one large file consisting of many test cases, and they're likely to not be all worst-case/near-worst-case and contain some randomly-generated cases. Overall you can expect the total runtime to be somewhere between the average case and the worst case.

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

      can we use map funtion in place of offest array"C"??

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

        Theoretically, yes. Practically, due to the already-high runtime complexity of this problem, it's kinda sketchy; you might be able to make it work in faster languages, but I can't guarantee it

        → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Here is my solution to the problem stable wall. Here you have to do topological sorting for a graph formed by characters of blocks. To check if the wall is stable or not you can check if there is any cycle in graph or not.
https://ideone.com/rHxaJa

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

here is my solution( in Python 3) for problem Candies i am using segment tree to solve it, but still i m getting TLE even for 1st subset can anyone please tell me where i am going wrong. my soltuion is giving correct ans for tc.

from math import ceil, log2; 
 
def getMid(s, e) : 
    return s + (e -s) // 2;  

def getSumUtil(st, ss, se, qs, qe, si) :  # to get sum from range l to r inclusive

    if (qs <= ss and qe >= se) : 
        return st[si];
    if (se < qs or ss > qe) : 
        return 0;  
    mid = getMid(ss, se);  
      
    return getSumUtil(st, ss, mid, qs, qe, 2 * si + 1) + getSumUtil(st, mid + 1, se, qs, qe, 2 * si + 2);  

def updateValueUtil(st, ss, se, i, diff, si) :  
  
 
    if (i < ss or i > se) : 
        return;  
    st[si] = st[si] + diff;  
      
    if (se != ss) : 
      
        mid = getMid(ss, se);  
        updateValueUtil(st, ss, mid, i,  
                        diff, 2 * si + 1);  
        updateValueUtil(st, mid + 1, se, i,  
                         diff, 2 * si + 2);  
   
def constructSTUtil(arr, ss, se, st, si) :  
  
    if (ss == se) : 
      
        st[si] = arr[ss];  
        return arr[ss];  
      
    mid = getMid(ss, se);  
      
    st[si] = constructSTUtil(arr, ss, mid, st, si * 2 + 1) + constructSTUtil(arr, mid + 1, se, st, si * 2 + 2);  
      
    return st[si];  
  
def constructST(arr, n) :   # to construct segment tree
    x = (int)(ceil(log2(n)));   
    max_size = 2 * (int)(2**x) - 1; 
      
    st = [0] * max_size;   
    constructSTUtil(arr, 0, n - 1, st, 0);   
    return st;  
  

def solve():  
    n,q=map(int,input().split())
    ls=list(map(int,input().split()))
    n = len(ls); 
    sm=[0 for i in range(n+1)]
    arsm=[0 for i in range(n+1)]
    n+=1
    for i in range(1,n):
        if i%2:
            sm[i]=-ls[i-1]
            arsm[i]=-ls[i-1]*i
        else:
            sm[i]=ls[i-1]
            arsm[i]=ls[i-1]*i
    
        
    stsm = constructST(sm, n)
    starsm=constructST(arsm, n)
    ans=0
    for _ in range(q):
        qt,l,r=input().split()
        l=int(l)
        r=int(r)
        if qt=="U":
            diff=r-ls[l-1]
            ls[l-1]=r
            
            if l%2:
                diff=-diff
            updateValueUtil(stsm, 0, n - 1, l, diff, 0)
            updateValueUtil(starsm, 0, n - 1, l, diff*l, 0)
            
        else:
            temp=(getSumUtil(starsm, 0, n-1, l, r, 0) - (l-1)*getSumUtil(stsm, 0, n-1, l, r, 0))
            if l%2:temp=-temp
            ans+=temp
    return ans
    
for tc in range(1,int(input())+1):
    res=solve()
    print("Case #%d:"%tc,res)
→ Reply