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!

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

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.

AA — just simulate

BB — you know this is something related to medians, then you try 95708430734 things regarding median, then you literally guess that you should put all boundaries (of horizontal/vertical type at once) in a single vector and sort it and use median and hope it works and you get AC

CC — you know this is something related to 4sum-ish thing. You notice the very weird constraints and just try to submit with different things like map/unordered_map/gp_hash_table and see that they tle and suddenly see one of them work.

DD — you see this is geometry, you close you machine and run as fast as you can.

A very bad round in regards to quality for me.

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!!!

What is the intended time complexity for problem C?

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

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

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.

Spoilerfor(int tc=1;tc<=t;tc++) { cout << "Case #" << tc << ": " ;

}

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

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

Because strictly N^2 solutions were allowed limiting other approaches to the same problemThat is not true I got full score with a $$$\mathcal{O}(n^2log n)$$$ algorithm

Oh cool please share it.

My solutionMy 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.

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

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

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

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_mapHere with vector (2.7 seconds):

vectorNow Geometry problems are trendy at KickStart.

Simple doesn't mean convex, lesson learned.

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

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

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

Yes, ternary search will work.

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

Can you share your code snippet please

codePlease explain your solution.

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

N^2LogN TLEd for C :|

$$$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 referenceActually, 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.

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

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

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.

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