kostka's blog

Google Kick Start 2019 — round E
By kostka, 5 years ago, In English

I haven't seen any post, so let me announce that the Round E of Google Kick Start 2019 is happening this Sunday (August 25) at 5:00UTC. Get ready and register now at g.co/kickstart.

.

  • Vote: I like it
  • +69
  • Vote: I do not like it

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

Can anyone tell why I am not being able to click the "submit attempt" button even after selecting the language ? Please help.

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

    If the problem still occurs, please ask on the platform, not here.

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

      Yeah I mailed them and they told me few possible solution but alas, nothing helped .

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

        I didn't know what was the problem. However when I logged in from my windows instead of ubuntu, I was able to submit the solutions.

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

          I think it is the clock issue in the laptop. Clock is correctly set for me in windows but it was wrongly set in ubuntu.

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

Even I am not able to click the submit button. What is wrong?

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

    If the problem still occurs, please ask on the platform, not here.

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

Not sure if I like this "Results hidden until end of round".

What am I supposed to do with it. Sit arround and ask myself, "Huh, is it really fast enough?"

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

How to solve code-eat switcher? Is it dp or there is some greedy tricks??

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

    That's how I did it:

    Sort the days in decreasing order of eating units.

    Sort slots by the ratio of coding to eating units.

    Initially, use all slots for 100% eating. Days with more required eating units than that, are 'N' obviously.

    Iterating over the days, while our current number of eating units is higher than needed, in the sorted order of slots, exchange the eating into coding (So that we get the highest possible amount of coding units for the needed number of eating units). If possible coding units are greater than required, it's a 'Y'.

    I got WA on large tests though, not sure if because of precision issues, or maybe my solution is actually wrong, is it?

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

      It turns out its wrong -- If you check the limits its 10^5 points and 10^5 queries.

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

        How does that change anything?

        Can you give a test case where it fails?

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

          You provided an algorithm that is O(N) per query, ie. O(NQ) for the test case. When NQ = 10^10, it fails.

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

            No, its complexity is O(N log N + Q log Q), and if you read carefully, I got WA, not TLE.

            We keep an iterator on the last slot, that is not fully changed from eating to coding units in the order of the best coding to eating ratios. We sweep through the queries in an offline order.

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

              Maybe you have already found the issue, but I think your approach is correct.

              I also got WA on large test set and my problem was an integer overflow at some point in the code. In particular, it was when interpolating the value of coding units for a given value of eating units. After performing this operation using 64-bit integers, I got AC.

              Hope this is useful for you!

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

when can we submit in practice mode?

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

Can someone please help in finding why my nlogn solution given TLE for (hidden test cases)Code-Eat Switcher.

Question: https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050edb/00000000001707b8

Solution: https://ideone.com/awL83T

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

Problem 2 — Bonus: Solve for exactly (Ai, Bi) rather than at least (Ai,Bi).

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

Quick editorial:

Q1

Spoiler

Q2

Spoiler

Q3 (method 1)

Spoiler

Q3 (method 2)

Spoiler

Codes: https://github.com/AWice/cptraining/tree/master/GoogleKickStart

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

    for Question 3 I thought and implemented the same strategy as mentioned by you in method 2 but for the case e1==0 or e1==2 while finding whether K is prime or not I think I got TLE on larger set. What can be the fastest way to find it? Using sieve for every number upto 10^9 will give MLE and even TLE

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

      If e1==0 then it just segmented sieve on [L,R] to find interesting numbers with e1==2 then just precalculate segmented sieve on [L/4,R/4] as done above and use this result.

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

    can we apply Gauss method for solving system of linear equations in question 2 ??

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

    in q2) where you taking the case that a slot could be partioned?aren't you taking entire slots only?

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

Hello, My handle on google kickstart is by the name "FIREBIRD33". The following is my code for the first problem:

from collections import *
def find(a):
    while a!=l[a]:
        l[a]=l[l[a]]
        a=l[a]
    return a
def printgoogle(a,b):
    print("Case #",a+1,": ",b,sep="")
for _ in range(int(input())):
    n,m=[int(i) for i in input().split()]
    l=[i for i in range(n)]
    # print(l)
    for i in range(m):
        x,y=[int(i) for i in input().split()]
        x-=1
        y-=1
        x,y=find(x),find(y)
        if l[x]>l[y]:x,y=y,x
        l[y]=x
    visited=[False for j in range(n)]
    for j in range(n-1,-1,-1):
        # if not visited[j]:
        l[j]=find(j)
            # visited[j]=True
    # print(l)
    cnt=Counter(l)
    tot=0
    totsame=0
    diff=0
    for i in cnt:
        if cnt[i] > 1:
            tot+=cnt[i]-1
    tot+=(len(cnt)-1)*2
    printgoogle(_,tot)

After the contest ended I submitted the same solution from my competitve submissions and it got accepted for both the test subsets.But during the contest only first test subset was passed.Please look into this!!!!! Thanks!!!

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

Hello, I want to raise an issue towards Google's Test sets.I checked the below submitted solution by a user whose HANDLE is "frextrite" . The third code submitted by this user is accepted by Google but when i debugged it with the below test case it showed TLE. Are google's test case strong enough!!!!!

CODE:

#include <bits/stdc++.h>

#define MAX ll(1e5)

using namespace std;

typedef long long ll;

vector primes(1e9+5, true);

void sieveOfErastosthenes() { for(int i = 2; i <= MAX; i++) { if(primes[i]) { for(int p = 2*i; p <= 1e9; p+=i) { primes[p] = false; } } } }

bool solve(ll x) { ll temp = x; int even_fact = 0; while((temp & 1) == 0) { even_fact++; temp /= 2; }

if(temp == 1) {
    return (even_fact-1 <= 2);
}

return (even_fact == 1) || (even_fact == 2 && primes[temp]) || (even_fact == 0 && primes[temp]);

}

int main() { ios_base::sync_with_stdio(false);

int t;
cin >> t;

sieveOfErastosthenes();

for(int c = 1; c <= t; c++) {
    ll l, r;
    cin >> l >> r;

    int count = 0;
    for(ll i = l; i <= r; i++) {
        if(solve(i)) {
            count++;
        }
    }

    cout << "Case #" << c << ": " << count << "\n";
}

return 0;

}

TEST CASE:

1

1000005 1000020

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

    I've never thought of this, but maybe it can pass the test, since it only needs to run one sieve across all test cases.

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

Maybe I am thinking of Code Jam, but didn't the analysis for the round and problems used to be ready very soon after the round?

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

Hi, I'm new to Kick Start. For problem A, I used Kruskal's algorithm to find the cost of minimum spanning tree. I AC the small dataset but I got Runtime Error for large dataset. I have no clue why I got Runtime Error. Could anyone give me a hint? Thanks.

My solution

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

    You don't need Kruskal for this problem just find connected components and there size mst of each component will be n-1 then connect components with components -1 edge of weight 2

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

      Yeah, I realized this better solution from others' comments. But I'm still curious why I got Runtime Error for large dataset even though my solution passed the small dataset.

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

        N is 1e5 for large dataset.You cannot create a array of N * N size.

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

Analysis has been published! You can find the Analysis tab on each problem site.

→ Reply