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!

Good luck to everyone!

Can you postpone your contest?

There's a gap of a whole 25 minutes, why do you want it to be postponed?

As if I would seriously ask that, obviously I was memeing Monogon

Thanks for the pypy3 :)

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.

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

last problem was easier than usual , according to me.

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

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

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

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.

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).

Thabkyou Yours is a much lesser loc solution. Great.

Some edge cases that tripped my solution.

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.

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

It is an obvious Bitmask DP problem.

STATEWe 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.

TRANSITIONSWe 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 CASESIf points > k return 0. If points == k return 1.

My CodeC++int dp[16][(1 << 16)];

vector adjlist[20];

vector entry(20);

vector a(20);

int k, n;

int solve(int src, int mask) { if (dp[src][mask] != -1) return dp[src][mask];

}

int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); // #ifndef ONLINE_JUDGE // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); // #endif

}

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

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.

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 scriptBasically 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.

can someone share solution using multiset in problem B ?

Video explaining the multiset approach for problem 2

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

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.

Video Editorial for Problem 1, Video Editorial for Problem 2, Video Editorial for Problem 4

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.