kostka's blog

Google Kick Start 2021 — round G
By kostka, 3 years ago, In English

Whether you’re looking to practice your coding, prepare for an upcoming interview, connect with a global community, or have some fun — Kick Start is here to help! Round G 2021 starts in less than 24 hours on October 16 starting at 12:00 UTC. You will have 3 hours to solve what you can during the round.

Hope to see you in Round G 2021!

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

Comments Comments (35)
| Write comment?
»
3 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Very excited about this one ! Best of luck to everyone.

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

Probably the worse kickstart round in last 2 years in regards to quality. Also idk why, as 2021 has progressed, the quality of kickstart has gone down by the time.

A
B
C
D

A very bad round in regards to quality for me.

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

    A..B..C..Ready to argue, because you are purple while I was only cyan, then saw your comments about D. Yeah! 100% agreed!! Run ASAP!!!

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

What is the intended time complexity for problem C?

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

    $$$ O(N^2) $$$ worked for me

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

      How to do it in O(N^2)?

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

        I used dynamic programming.

        My dp table was of size $$$k+1$$$ where $$$ dp[i] $$$ told the minimum number of trees to get $$$i$$$ number of bananas. Initially $$$dp[0]$$$ was equal to $$$0$$$ and for all other values of 1 through k was equal to $$$INF$$$ . Then I iterated through the input array calculating the sum of continuous subarrays. Once I had the sum of subarrays I calculated about the minimum number of trees required to get k bananas if we consider this subarray. Later I updated the dp table for subarrays that were ending at the $$$i$$$'th indice.

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

    O(n^2) with gp_hash_tables worked for me. tho maps and unordered_map tled

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

why N^2log(N) solutions were not allowed for C.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Because strictly N^2 solutions were allowed limiting other approaches to the same problem
    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    That is not true I got full score with a $$$\mathcal{O}(n^2log n)$$$ algorithm

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

      Oh cool please share it.

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

      My solution was for each $$$K$$$ possible sum I created a set of pairs (pos, val), where pos is the start of the interval and val is the number of trees needed for this case, also I guarrante that I never insert pairs $$$(a, b)$$$, $$$(c, d)$$$ with $$$a<c$$$ and $$$b>d$$$. The idea is going from right to left consider all intervals that start at a given point, let $$$s$$$ be the sum of an interval $$$[l, r]$$$, you search for the first pair on the set corresponding to $$$sum = k-s$$$, such that $$$pos > r$$$ and combine their values.

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

        An idea similar to this TLEd for me :( I used binary search to search for the other interval.

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

          Same. It seems that it will work but some more optimizations were required.

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

    I had an O(n^2) solution but saving the suffix in an unordered_map (I know technically its not O(1)) and it TLE. However, with saving the suffix in a vector, it got accepted. Anyone might know, why the unordered_map suddenly drops drastically in performance? I mean if it were a bit worse I would understand but its off by minutes with unordered_map..I don't understand :(

    Code with unordered_map here:

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

      'k' is 10^6 and you should only need O(K) memory, but when you write it like this, you're really using O(N^2) memory in the worse case (the sums aren't bounded at all and you're adding each one to the hash map), which is 2.5 * 10^7 longs, that's gonna be super slow in a hashmap. Just add "if(possible > 1e6) continue;" and it'll pass.

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

        Good Catch, thank you, I really appreciate your help. I just added it and instead of >3mins it takes 28 seconds (the third test case), whereas with vector it only needs 2.7 seconds. Holy, A huge takeaway for me is, that when possible use vector/arrays.

        Here with unordered_map (28.5 seconds):

        unordered_map

        Here with vector (2.7 seconds):

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

Now Geometry problems are trendy at KickStart.

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

Simple doesn't mean convex, lesson learned.

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

In D, for A=7 and n=5, will it be Impossible ?

Are there any other impossible case for n=5 except A<=4

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

Is it possible to use ternary search on cooridinates on problem B ? I'm not sure if it will work or not.

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

    Yes, ternary search will work.

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

    yup. I did ternary search on x and y seperately.

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

      Can you share your code snippet please

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

    Please explain your solution.

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

I loathe that for B I thought about 1486B - Eastern Exhibition but for some reason stubbornly insisted they couldn't have the same crux.

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

N^2LogN TLEd for C :|

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

    $$$N^2logN$$$ passes for me. Fixed the sum of the first part and the binary search over all other possible intervals with that required sum to make the sum $$$K$$$.


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

Actually, not a very good round.

problem A: Just simulation, no algorithm. and nearly no difference between two test sets.

problem B: Very similar to medians, you can treat x and y coordinates independently. Personally I think this is the best problem of four.

problem C: the problem itself is not bad, and there are different approaches with nearly same estimated computational time. but the time constraints are so disgusting, some solutions can pass but others cannot, and you may be punished when you use slow coding language like python. It should be increased by at least 40 seconds per test case.

problem D: Just a corner cases analysis geometry problem.

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

Hey guys, can you tell me why this solution is not passing the second test for D ? The solution is the same zig zag pattern but when n is odd, I end a triangle horizontally, if it is even i end with a trapezium vertically.

https://ide.geeksforgeeks.org/tXEkt3pA8l

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

    I think that for lines 48, 53, and 54, all your t1.ss and t2.ss should += add instead of ++.

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

Great contest! I feel that the constraints were very manageable, allowing me to fully solve every problem with Python (PyPy3). For question C, I had an O(n^2) solution and used an array to memoise results to reduce overhead.

C

For B I actually used a binary search over the gradients (for when it changes from negative to positive) for x and y. If anyone's interested in seeing all of my Python solutions, just search for YMSeah on the scoreboard.

→ Reply