kostka's blog

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 F 2021 starts in less than 24 hours on September 18 starting at 17:00 UTC. You will have 3 hours to solve what you can during the round.

We are excited to announce we are now supporting PyPy3 and updated compilers and interpreters for several languages. You can find more information in the Platform section of the FAQ.

Hope to see you in Round F 2021!

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Good luck to everyone!

»
3 years ago, # |
Rev. 2   Vote: I like it -15 Vote: I do not like it

Can you postpone your contest?

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

Thanks for the pypy3 :)

»
3 years ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

So excited! It's the first time I get a perfect score and rank 102 (currently) in this contest.

I remember the first time I take part in kick start, in the round E of 2020, I only solved one problem and ranked 3868. Efforts have been made, and progress have been made.

Since I am applying for Google Software engineer developer this year, hope this contest can help me get an interview.

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

Is it me or the last two problems were harder than usual ?

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

    last problem was easier than usual , according to me.

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

Could someone pls post a clean code for C (star trap) ? I am not good at geometry.

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

    The analysis section is open now. You can read the editorial.

    Also after the contest you can view anyone's solutions.

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

    Here is my successful code.

    It's a similar idea to the editorial, with the following difference: when handling quadrilaterals, I place all points into equivalence classes by the gradient formed when joined to the blue star. In all classes where there are >= 2 stars, and they are on different 'sides' of the blue star (found by checking the signs of the x differences and y differences, I take the pair closest on either side and treat these as a 'candidate pair'. This candidate pair now forms 2 non-adjacent vertices of a potential quadrilateral (since we know that the blue star sits on the intersection of the lines formed by 2 such pairs). I then iterate over all pairs of 'candidate pairs', which gives me all combinations of 4 vertices.

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

    Here's my contest submission code

    I used a different idea then the analysis. I viewed the stars as vertices of a graph. I placed an edge from white star x to white star y, if the blue star was to the right of the line through x and y (I did this with a cross product check). The edges have weight equal to the distance between star x and y. If we find a cycle in this graph, it means we went completely around around the blue star, thus we made a polygon. So in this graph we have to find the minimum weight cycle. This can be done with Floyd-Warshall in O(n^3).

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

    Some edge cases that tripped my solution.

      x
    oo
    oo
    
     o 
    o o  x
     o
    
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wasted a lot of time on C trying to solve it by Jarvis March algorithm. I was completely incorrect with that.

Luckily I managed to solve D, got a half decent score.

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

    Can you explain you approach ( for the first half) for D! I read the editorial and yet not able to understand it.

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

      It is an obvious Bitmask DP problem.

      STATE

      We define the state as -> (mask,node) Where the mask has the ith bit set if that particular node's shield has been broken. We need to maintain the node variable along with the mask which means that this particular mask was the last node whose shield's was broken.

      TRANSITIONS

      We are traversing the graph in a connected fashion, so at any instant we can break the shield of a previously unvisited node if it is connected to any visited node and l <= pot <=R. Luckily we can traverse the entire adjacency list for this as it fits in the Time Constraints. Just make sure you don't count a particular transition multiple times(use a set to keep a track of that).

      BASE CASES

      If points > k return 0. If points == k return 1.

      My Code

      C++
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I forgot to check if the submask was connected in my dp for problem D and yet passed test set 1.

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

My solution for C has time complexity $$$O(N^4)$$$ but still it passes. Maybe because of optimizations.

I think the worst case for this is around $$$(\frac{N}{4})^4$$$ operations so that's why, but I'm not sure.

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

    My solution for C also has time complexity $$$O(N^4)$$$ and I also was very surprised that it passed. I think that it may be hacked by the following testcase:

    Ruby script

    Basically place the blue star at x=1000 y=1000. So that it is in the center of a cross spanning 75 points up, 75 points down, 75 points left and 75 points right.

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

can someone share solution using multiset in problem B ?

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

Was that open for everyone?? , or only who cleared the previous rounds were eligible for this Round??

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

    kick start is unlike code jam, and each contest is independent. Everyone can register and participate, you don't need to do well in the previous round.

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

Anybody solved C with shortest path algorithm? I think it will be applicable even if we need to enclose a set of stars, rather than one.