Блог пользователя Gumnami

Google Kick Start Round C 2020
Автор Gumnami, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • -26
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    same here..lol..

    join all same letter and u can see the shape.

    → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

2nd question

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

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 18   Проголосовать: нравится +8 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        → Ответить
»
4 года назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)
→ Ответить