### kostka's blog

By kostka, 6 weeks ago,

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!

• +62

 » 6 weeks ago, # |   +2 Good luck to everyone!
 » 6 weeks ago, # | ← Rev. 2 →   -15 Can you postpone your contest?
•  » » 6 weeks ago, # ^ |   +14 There's a gap of a whole 25 minutes, why do you want it to be postponed?
•  » » » 6 weeks ago, # ^ |   0 As if I would seriously ask that, obviously I was memeing 1-gon
 » 6 weeks ago, # |   +3 Thanks for the pypy3 :)
 » 6 weeks ago, # | ← Rev. 2 →   +20 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.
•  » » 5 weeks ago, # ^ |   0 Hi, Sorry for being ignorant but Is Google available in China? I thought they are banned in China.
 » 6 weeks ago, # |   0 Is it me or the last two problems were harder than usual ?
•  » » 6 weeks ago, # ^ |   +12 last problem was easier than usual , according to me.
 » 6 weeks ago, # |   +3 Could someone pls post a clean code for C (star trap) ? I am not good at geometry.
•  » » 6 weeks ago, # ^ |   -18 The analysis section is open now. You can read the editorial.Also after the contest you can view anyone's solutions.
•  » » 6 weeks ago, # ^ |   +5 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.
•  » » 6 weeks ago, # ^ |   +30 Here's my contest submission codeI 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).
•  » » » 6 weeks ago, # ^ |   0 Thabkyou Yours is a much lesser loc solution. Great.
•  » » 6 weeks ago, # ^ |   +5 Some edge cases that tripped my solution.  x oo oo   o o o x o 
 » 6 weeks ago, # |   0 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.
•  » » 6 weeks ago, # ^ |   0 Can you explain you approach ( for the first half) for D! I read the editorial and yet not able to understand it.
•  » » » 6 weeks ago, # ^ |   +2 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 Code C++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]; int curr = 0; for (int i = 0; i < n; i++) { if (mask & (1 << i)) { curr += a[i]; } } if (curr == k) { // cout << src << " " << mask << " " << curr << " " << 1 << endl; return dp[src][mask] = 1; } if (curr > k) { // cout << src << " " << mask << " " << curr << " " << 0 << endl; return dp[src][mask] = 0; } int res = 0; set vis; for (int i = 0; i < n; i++) { if (mask & (1 << i)) { for (auto it : adjlist[i]) { if ((mask & (1 << it)) == 0 && curr >= entry[it].F && curr <= entry[it].S && (vis.find(it) == vis.end())) { vis.insert(it); // cout << src << " " << mask << " " << curr << "->" << it << endl; res += solve(it, mask | (1 << it)); } } } } // cout << src << " " << mask << " " << curr << " " << res << endl; return dp[src][mask] = res; }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 KStest() { cin >> n; in(m); cin >> k; memset(dp, -1, sizeof(dp)); for (int i = 0; i < n; i++) { adjlist[i].clear(); } for (int i = 0; i < n; i++) { cin >> entry[i].F >> entry[i].S; cin >> a[i]; } for (int i = 0; i < m; i++) { in(u); in(v); adjlist[u].pb(v); adjlist[v].pb(u); } int ans = 0; for (int i = 0; i < n; i++) { ans += solve(i, (1 << i)); } KScout << ans << endl; } return 0; }
 » 6 weeks ago, # |   0 I forgot to check if the submask was connected in my dp for problem D and yet passed test set 1.
 » 6 weeks ago, # |   0 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.
•  » » 6 weeks ago, # ^ |   +6 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 scriptdef testcase(n) abort "n must be divisible by 4" unless n % 4 == 0 puts n blue_x, blue_y = 1000, 1000 (n / 4).times do |i| puts "#{blue_x + 1 + i} #{blue_y}" puts "#{blue_x - 1 - i} #{blue_y}" puts "#{blue_x} #{blue_y + 1 + i}" puts "#{blue_x} #{blue_y - 1 - i}" end puts "#{blue_x} #{blue_y}" end t = 100 puts t 10.times { testcase(300) } 90.times { testcase(60) } 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.
 » 6 weeks ago, # | ← Rev. 2 →   +3 can someone share solution using multiset in problem B ?
•  » » 6 weeks ago, # ^ |   0
•  » » 6 weeks ago, # ^ |   +5
 » 6 weeks ago, # |   0 Was that open for everyone?? , or only who cleared the previous rounds were eligible for this Round??
•  » » 6 weeks ago, # ^ |   +3 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.
•  » » » 5 weeks ago, # ^ |   0 Thanks , I was not aware of this information.
 » 6 weeks ago, # | ← Rev. 2 →   0
 » 6 weeks ago, # | ← Rev. 12 →   0 Congratulations to all the winners. Benq Egor.Lifar Maksim1744 neal tmwilliamlin168 MarcosK Heltion rama_pang xiaowuc1 molamola.
•  » » 6 weeks ago, # ^ | ← Rev. 8 →   0 Sorry for "Egor.Lifar" and "molamola." 😅. I don't know how to tag their names because I think it has something to do with the point "." in their handles.
 » 6 weeks ago, # |   +13 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.