kostka's blog

By kostka, 4 weeks ago, In English,

Round G of Google Kick Start 2019 will start this Saturday (October 19) at 13:30UTC.

Get ready and register now at g.co/kickstart.

 .

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

»
4 weeks ago, # |
  Vote: I like it -31 Vote: I do not like it

ok.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

When I reach the last page of registration process (where there are "About you" and "Rules" sections), and press "Register" button, it does nothing but remaining at the same page.

What do you think?, is it a general problem, or just for me (and my friend from the same country, Syria, and we use a vpn connection to enter this site)?.

Thanks in advance.

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

    I had a similar problem when I tried logging in to the website using Firefox. Opening it on Chromium solved the issue.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Clashes with the Atcoder round.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Can you please elaborate on this approach? During Contest I realised that 3^N can be optimised 2^N via SOS DP but i Couldn't come up with approach. It would be great if you could share your approach.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 3   Vote: I like it +8 Vote: I do not like it

        Let dpA[mask] be sum of A's happiness for shifts represented by mask. Then for every mask such that dpA[mask] >= H, we need to compute F[mask1], where mask1 is obtained from mask by flipping its bits, and F[mask1] is the number of supersets of mask1 whose sums on B are >= H. This is equivalent to find all the subsets of mask whose sums on B are <= totalB - H.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    meet in midddle and ordered set will also work fine......

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Although SOS DP solution seems to be better, but I used Meet in the Middle Technique to solve this problem.

    The approach was to solve for both the halves of the array recursively by brute force O(3^(n/2)) and store all the possible pairs of total happiness values for A and B for both the halves separately and sort them according to any one of the person. I did it for A.

    Now, how to compute the number of possible pairs from second halves ??

    Suppose (x,y) is the first pair for (A,B), you need to find the number of pairs from the second halves (X,Y) such that x+X >= h and y+Y >= h;

    So basically find the number of pairs (X,Y) such that (X>=(h-x),Y>=(h-y)). At this stage, I first did coordinate-compression to limit the values. (Think Why)

    To calculate the number of pairs, I made a classical segment tree and accordingly kept on updating it by visiting the pair in first half in the sorted order.

    Complexity -> O(3^(n/2)*lg(3^(n/2))

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

      At least in terms of time complexity, Meet in the Middle is better.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you please tell, how do you use segmentation tree.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve (b)the equation?

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

anyone with rank 150-200 got a call from a google recruiter in this year rounds ??

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Seems like there's no way getting a call from a recruiter without being in top ~20-30 (if possible). Not even sure whether recruiters even look at Kickstart standings.

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

      I have seen many cases where people got call even without participating in Kickstart.

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

        I mean if you want to get a call from Google recruiter as a result of your performance in Kickstart. Yeah, sure there are many cases of call without involving Kickstart

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

          Thankyou so much for the information, will work hard to get a better rank. Btw, how can we get a call from recruiters through ways other than Kickstart. If you know anything related to it can you share !!

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Hey man I know many getting call. Even after a rank of 213 in Kickstart ayushghd got a call from Google.

      May be see this video and your doubts will be clear. Link

      And also you should try connecting to recruiters or someone working in Google and knows cp so that (s)he can give you a referral.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Hey CMaster,i got a call for onsites at Google office

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I did SOS DP on 3rd Question but I am getting the wrong answer can anyone point out what am I doing wrong here. Solution

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You havent understood the question correctly. Either this or your logic is wrong. It says that atleast one of them has to work everyday,ie, both can also work on any day.

    See the spoiler if needed. (Based on explanation by @tuananh238)

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In Book Reading my code gave wrong answer for Test Set 2. When I replaced the ans variable datatype to long long int from int it got AC.

But according to me int should also work the maximum value of answer will be 1166750. Can anybody help me finding error in my code.

Code
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider the case:

    1
    100000 0 100000
    1 1 1 1 1 1 1 1 1 1 1 1 ... 1 1 1 1 (100000 times)
    
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohk, you are right. Thanks for the help.

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

        I myself felt so bad about the same mistake too.I was done with all 3 in 1.5 hrs, but after the system test results were out, i realized i shouldn't have been greedy taking int type(to avoid any possible TLE)....

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with the 2nd question? I just cannot figure out whats wrong in my approach:-

1.Find total sum

2.Find count of set bits in n numbers at each bit place.

3.Subtract the values (those bits where count(1s) >= count(0s) say ith bit has this property. then subtract (2*count(1s) — n)*(1<<i) )

4.Now add the values (those bits where count(0s)>counts(1s)) — starting from msb

5.Keep updating the value of k

Here's my code

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

    You have an overflow in your code. Just use numbers with 51 bits only(bn=50 in your code instead of 55) and your code will pass.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone help me with 3rd problem? I want to know what's wrong with my solution. I used meet in the middle algorithm and then used merge sort tree. I got TLE with bigger cases. Code

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the logic for the second problem-The Equation? I did not understand the analysis. I mean why we did what we did. If someone could explain in simple terms it would be really great along with the intuition behind it if possible.

»
4 weeks ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

Hey, this is my first time participating in Google's Kickstart. I know my code is probably inefficient but it works beautifully on my local IDE (IntelliJ). However, when I upload it to the kickstart website, it gives me a runtime error. Can someone please help me? TY :D

(This is for Round G, Question A)

Here is the code: http://txt.do/1kcfs

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

    Look at their FAQ, you may have to name the main class Solution.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey guys. Stuck on the 3rd question with the following logic: Meet in the middle and then using trie to count no. of numbers less than the needed value.

I think the logic is right but just not able to figure out the bug. Code is well written and self explanatory. Here's my code.

Please help

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is my solution for the 2nd problem — The Equation. But, I'm getting WA.

My logic : I am looping over every bit of each no. and if the majority of the no.s have current bit equal to 1 then K has that bit set else K has that bit unset.

This way it gives the minimum K that satisfies the condition <=m. But, now we have to maximise this value of K.

For this, I iterate over the bits of K and if any bit is unset(ie-0), then I make it 1(set it) and check if this changed K satisfies the condition or not. If yes, then I update this K permanently, otherwise I move forward to check other unset bits.

I request someone to point out the glitch in the code or in the logic. Kindly help.

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Screencast of me winning the round: https://youtu.be/bc3DpNRZ0lk.

(sorry for posting it so late)