kostka's blog

Google Kick Start 2021 — round B
By kostka, 4 years ago, In English

Round B starts in less than 24 hours (on April 18th at 23:00 UTC).

Join our online coding competition and tackle fun problems designed by Google engineers! ➡️g.co/kickstart

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

Comments Comments (25)
| Write comment?
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

What an ugly problem set. Extremely easy A, tedious casework in B, find and copy primality test in C (turns out it wasn't actually required lol), only D is good...

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

    I didn't find problem B particularly tedious. Calculated results using a recursive formula (is this DP?). My solution in Ruby — https://pastebin.com/n8AMQu2i What's your code for this problem?

    Except that I initially messed up and forgot to handle the reversed array case. Then tried to implement a simple bruteforce solution, but Ruby code wasn't fast enough. Converted this bruteforce solution to C++ and confirmed that it's accepted for the small data set. Then generated random input data and identified a broken testcase. Wasted more than 1 hour on this debugging. Looks like I need more practice to do it much faster.

    Is Google Kick Start very unpopular? Seems like there were only around 7500 participants (including those who didn't manage to solve any problem).

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

      The main reason for less participation was that most of the participants are from India every time, but as this time for Indian students the time was a bit off, that was 4 in the morning, that's why participation was less.

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

In problem B, can someone explain why the answer isn't 8?

9
5 5 4 5 5 5 4 5 6

we can replace 4th integer with 4 then from second number to the end

5 4 5 4 5 4 5 6

is of length 8 arithmetic subarray

what am I missing? please help

Thanks!

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

    I think you expect the difference between the adjacent elements to be either -1 or +1. But you should pick only one of them. The sign matters :)

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

      :( Oh!, Thanks They should have made the problem statement clear by specifying how they are taking difference...just said the adjacent difference is the same but not specified the order :|

      This problem ruined my day ＞﹏＜

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

        "For example, $$$[9,10], [3,3,3],$$$ and $$$[9,7,5,3]$$$ are arithmetic arrays, while $$$[1,3,3,7], \color{red}{[2,1,2]}, and [1,2,4]$$$ are not."

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

Problem C judge was very weird, it was sometimes giving Sample Failed: MLE for no reason,this problem submissions need to be rejudged. kostka

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

Some people have sort of brute forced in test 3 of C, i.e. they just found the square root of the no and used a linear search to find its nearest primes and then some small casework. Shouldn't that give a TLE due to linear search of primes?

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

    There is a theorem in number theory that says something like the first prime equal or bigger the $$$N$$$ is in the order of $$$N +O(ln(n))$$$, so the search is in order of $$$O(ln(n))$$$, so if you use a fast primality test, this solution should pass

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

    Use bitset

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

    The largest gap between two prime numbers for primes <=10^9 is 282. (According to this).

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

    I think it's perfectly fine to linear search for finding 2-3 nearest primes around $$$\sqrt{Z}$$$ if each number in neighbourhood of $$$\sqrt{Z}$$$ is compared against a list of primes smaller than $$$10^5$$$, to be deemed as prime.

    This list can be generated one time, using sieve of eratosthenes, and it will contain $$$9592$$$ values.

    Time Complexity = $$$\mathcal{O}(gap\cdot|list|)\;$$$ per test case, where $$$gap\sim300,\; |list|\sim10000$$$

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

      For seive of eritothenes, we need to first create a boolean array of that size, right? Z = 10^18

      sqrt(Z) = 10^9

      So, if we need to know if sqrt(Z) is prime or not the list should be of size 10^9. But that will give runtime error.

      How can we check for sqrt(Z) if list is only of size 10^5?

      What am i missing?

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

        You can check if numbers lying in the neighbourhood of $$$\sqrt{Z}\;(\leq10^9)$$$ are prime or not by knowing whether any prime less than $$$10^5$$$ divide them. $$$seive[1...10^5]$$$ is sufficient to generate a list of all such primes which are less than $$$10^5$$$

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

        $$$10^9$$$ is OK if you use a boolean array.

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

          Filling it will take $$$\mathcal{O}(n\log\log n)$$$ time and for $$$n=10^9$$$ it will be significantly slow. It may pass if this is done only once per test set where the time limit is 15 seconds, but it is not the intended solution.

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

            It's $$$\mathcal{O}(n)$$$ time if you use Euler sieve.

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

Good contest, enjoyed it. Just a suggestion in problem B, test cases were weak. My solution was O(n) only, but it had a minor bug, still passed for small test cases and got WA on the large test case.

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

kostka I understand that I'm probably asking too much. But is there any chance for Google Kick Start 2021 round B participants to qualify for the upcoming Google Code Jam 2021 rounds 1B and 1C? Or is waiting a year until the next Google Code Jam 2022 the only possible option right now?

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

I uploaded my screencast of getting 1st place + explanations of my solutions to my YouTube: https://www.youtube.com/watch?v=HVISmqzgIq8

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

Approach for the problem C is easy for me but the implementation was difficult for me As the problem said we need to find the maximum product of the two prime number that should not be greater then z ................................................................................................................. So the answer behind this we first take the sqrt(z) and iterate to the left of sqrt(z) then for the first prime number from the left side consider that as num1 then divide that by z for the second prime number if the product of that second num with previously num1 is greater then z then leave that second number find the left prime number of num1 this is how we do

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

    The problem C was really easy and I feel embarrassed that I didn't even try to read its description during the contest because of wasting too much time on debugging problem B.

    Checking primes in the neighbourhood of sqrt(z) is really fast. And Ruby programming language even supports primality test in the standard library. C++ users had to find some good primality test implementations from the Internet and copy/paste these implementations into their code, which probably ended up being a huge headache for the Google people responsible for plagiarism checks (the round B results are still "In review" right now).

    The only minor pitfall is that the minimal allowed value of z is 6 and its integer square root is only 2. There are no prime numbers on the left side of it and a buggy implementation may fail with a TLE verdict unsuccessfully trying to find primes among negative numbers.

    → Reply