darkshadows's blog

Google's Kick Start 2020 Round A
By darkshadows, history, 6 years ago, In English

Hello again,

Google's Kick Start 2020 season is here! Kick Start hosts online rounds throughout the year, giving participants the opportunity to test and grow their coding abilities while getting a sample of the programming skills needed for a technical career at Google. Top candidates might be invited for interviews.

We have some exciting updates for 2020:

  • We’re removing Hidden Verdict Test Sets. All submissions will receive instant feedback.
  • You'll see a fourth problem added to each round.

I invite you to solve some fun and interesting problems on Mar 22 2020, 04:00 UTC.

Dashboard can be accessed here during the contest. Problem analyses will be published after the contest.

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

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

Bump; few hours to go.

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

What does it mean when it says Sample Failed: WA?

Does it mean I got WA on the sample provided?

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

Problems this time are way easier than previous ones. This round is like 1000 — 1200 — 1600 — 1800 compare to the last one I tried 1200 — 1800 — 2200

→ Reply
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it -43 Vote: I do not like it

    How many people scored 100/100?

    → Reply
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it -18 Vote: I do not like it

    I feel the third is hardest, I use dp and get TLE for test 2

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

      in 3rd, u need beinary search. check whether we can make x as our answer. we can make x as our answer only when sum of all (a[i+1] — a[i]) / x , for i = 1 , n — 1 is <= k.

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

      It can also be done by simple greedy, just pick the largest gap, decrease the gap, repeat for k times. O(klogn).

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

        Hey!

        I'm not sure that this always works, for example, given a case where the optimal solution involves splitting up some difficulty gap twice (one input gap into thirds), but this solution would first split it into halves and split one half into two quarters.

        Here's a case:

        N = 2
K = 2
M = [1, 19]

        Here, the optimal solution would be to use two splits between 1 and 19, making [1, 7, 13, 19] so the answer is 6. However repeatedly picking the largest gap and splitting it into half, would give you:

        [1, 19] => split into [1, 10, 19] for the first step,

        Now the largest gap is [1, 10] (or [10, 19]), which you could split into [1, 5, 10]. This approach gives 9 as the answer (because [10, 19] still hasn't been split), but 6 is possible, as we showed above.

        Thanks!

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

          No, I meant equally distribute the gap, like fo the first time you visit this gap {1,19} divide it in two parts (thus {1,10,19}) now when you visit the same gap again split it into 3 parts(thus {1,7,13,19}), and so on k times. I implemented it like @Spheniscine 's comment down below.

          → Reply
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it +18 Vote: I do not like it

    2nd was def tougher than 1200

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

Speedforces

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

Why priorityqueue based greedy solution giving WA on large test case of problem 3?

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

    If you are just taking biggest gap and dividing it into two, that won't work. Consider the case:

    1
2 2
1 10

    The optimal solution is 1 4 7 10 with a penalty of 3, but the divide-by-two solution would produce something like 1 5 7 10 with a penalty of 4.

    → Reply
    • »
      »
      »
      6 years ago, hide # ^ |
       
      Vote: I like it +9 Vote: I do not like it

      I too wrote the solution using priority queue and got 3 WA. Later used binary search.

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

        I actually used priority queue, but rather than storing only the gap, I store both the initial gap and the number of insertions, and greedily add insertions to the entries with the biggest current gap, i.e. $$$\left\lceil \dfrac {gap_0} {insertions + 1} \right\rceil $$$

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

          yeah i did the same ,Having original value is important

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

          Wow, that's smart way.

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

          Can you kindly post your solution?

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

          Is there a mathematical formula/concept behind that expression? I fail to see why that works.

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

            Each entry represents the gap between a pair of consecutive numbers in the input (so $$$gap_0 = M_{i+1} - M_{i}$$$ for the $$$i$$$th entry). $$$insertions$$$ are the number of new exercises you plan to put within that gap.

            So say you plan to put $$$3$$$ insertions between $$$2$$$ and $$$11$$$. It can be seen that it's optimal to space them out as evenly as possible (e.g. 2 4 6 8 11), and the largest gap remaining in that segment is $$$\left\lceil \dfrac {11-2} {3 + 1} \right\rceil = 3$$$.

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

      Ahh, Thanks.

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

    I solved it using the priority queue.

    My code.

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

Got rly lucky and got first :) Screencast: https://youtu.be/uGrBHohIgQY

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

The "Case #x: y" is the most bullshit thing I have ever seen in my life.

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

11000 people gave this contest. Never ever in the history of kickstart. what make sudden rise.

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

How to solve Plates (second problem) ?

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

I really feel stupid not noticing the 4th problem and wasted 50 minutes rejoicing. Anyone else along with me?

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

I used trie to solve the 4th problem. I personally felt that it's a feasible solution with good efficiency, though unfortunately I got WA in larger test. Is there anyone willing to take a quick look at here for me? I hope I could debug by myself, but I have no idea how to proceed since google is unwilling to release the test set even after the contest (sighed). Would be really appreciated if anyone can help :D

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

How much pwople going to round B?

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

what is wrong with my greedy approach for C

for every session to be added pick that consecutive (a,b) whose difference is maximum and add a seesion at (a+b)/2+(a+b)%2. and i did it using priority queue 1st test case passed but got WA on other.

Please help.

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

How to solve problem D using trie ?

→ Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +1 Vote: I do not like it 
    First insert each string in the trie ,then traverse the trie starting from the head node and count the frequency of each prefix in the trie.

    The answer would be the sum of frequency/k for all the prefixes.

    Code

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

      Will it be the sum of frequency/k or sum of valid frequency(atleast k strings possesssing that prefix). Also, when adding the frequencies, ain't we adding up the undesired frequencies too?

      for eg — rain, rainbow, rainy, rat, ra, with k=3 so r->5, ra->5, rai->3, rain->3, ra->2, rat->1, rainb->1, rainy->1...and others.

      According to me, we should add (len. of "rain")*(freq. of "rain")/k into our final answer and subtract the this frequency from previous prefixes, ie — (freq. of "rai") -= freq. of "rain" and propagate this difference to the previous prefixes.

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

      BTW, why did you use map and pushing the prefix count and later doing ans+=map[depth][i]/k instead of directly doing ans+=freq/k in the traverse() function?

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

        Yes you are right it can be written that way as well.

        PS- This code is what I wrote during the contest so it may not be as neat as it should be.

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

          I did it both ways(yours and my way) but still getting WA. I'm doing traverse thing in the fun() function.Can you check a bit this code?

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

Although, I did the 3rd question(Workout) using binary search, How to do it using priority_queue?

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

In problem D why does sorting and then grouping them into size of k and then finding longest common prefix for each group is not working . I wasted my 2 hours on this . Anybody help ?

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

Hi everyone,

For problem 4, I implemented using Trie and passed the small test but somehow I got MLE for the large test, I spent hours trying to find out. Thank you in advance.

My code:(https://ideone.com/s8IpR6)

→ Reply
»
6 years ago, hide # |
← Rev. 2  
Vote: I like it -19 Vote: I do not like it

KickStart 2020, Round A. The limit for N of 10^5 in test set 2 which they specified in problem 1 ("Allocation") is incorrect. I am pretty sure they have a test case in test set 2 with more than 10000 houses.

Why? I was getting RE on test set 2 and I spent about 1 hour trying to find "the bug" in my program, and then finally as a last resort I decided to just extend the size of my arrays to 10^6. And the same code which I already had and which was giving me the RE, it suddenly worked fine (just with the array size changed).

Did anyone else notice this issue in test set 2?

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

The ranklist was filled with people who never solved more than 2-3 Problem, but guess what,today they solved a friggin trie problem...On a totally unrelated note someone sent me a picture of people discussing on whatsapp groups, but let's just ignore it :)

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

    Yes, i agree. but how u know they r the same people who never solve > 3 problems. I understand there is a lot of cheating and many knows from where they r from. but what they will gain, they will get crushed if they called for interview. so chill :_)

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

      They will get crushed no doubt, but someone might not get a call because of these people, considering google does not call everyone.

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

        Yes.. u r right. Google should take it seriously.

        darkshadows please convey it to google. It happened on large scale today.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, hide # ^ |
           
          Vote: I like it +24 Vote: I do not like it

          Google only contacts the top <100 based on previous competitions, so I doubt you can cheat your way to that high because if you need to ask for sol you probably can't code fast enough and you'd have to copy paste from someone in the top 100, and the people that high in ranking do not want to cheat. So if you're worried about cheaters taking your interview, you nor them is probably getting an interview.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, hide # ^ |
             
            Vote: I like it +18 Vote: I do not like it

            Are you sure about the <100 thing? I had a 2 digit rank last year but wasn't invited. I know a guy who had a 500+ rank but was invited for the interview :-/

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, hide # ^ |
               
              Vote: I like it +2 Vote: I do not like it

              No this is not true. My fried had around 370 rank in one ks round. He received call and cracked google too. One with 542 rank also got call. So this is not true.

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

                Are you sure that they didn't applied on Google's Career Page and received call?

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

              Maybe they were contacted regardless of performance on kick start. Like referral or just standard application.

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

            Take 4 people who cooperate and parallelize work by first solving harder problems as a team (if necessary) and then coding on 4 machines in parallel and submitting everything under the same account.

            This way you can get result in top-X with zero people who have top-X skill level involved.

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

B was a really beautiful problem

→ Reply