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

Автор kostka, 5 лет назад, По-английски

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.

 .

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

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

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

        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.

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

          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.

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

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

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

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

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

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

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

    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?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

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

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

        How does that change anything?

        Can you give a test case where it fails?

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

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

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

            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.

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

              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!

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

when can we submit in practice mode?

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

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

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

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

Quick editorial:

Q1

Spoiler

Q2

Spoiler

Q3 (method 1)

Spoiler

Q3 (method 2)

Spoiler

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

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

      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.

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

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

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

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

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

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!!!

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

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

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

    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.

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

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?

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

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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

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

      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.

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

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