Hello again,
Google's Kick Start 2020 season is here! Kick Start hosts online rounds throughout the year, giving participants the opportunity to test and grow their coding abilities while getting a sample of the programming skills needed for a technical career at Google. Top candidates might be invited for interviews.
We have some exciting updates for 2020:
- We’re removing Hidden Verdict Test Sets. All submissions will receive instant feedback.
- You'll see a fourth problem added to each round.
I invite you to solve some fun and interesting problems on Mar 22 2020, 04:00 UTC.
Dashboard can be accessed here during the contest. Problem analyses will be published after the contest.
Bump; few hours to go.
What does it mean when it says Sample Failed: WA?
Does it mean I got WA on the sample provided?
Problems this time are way easier than previous ones. This round is like 1000 — 1200 — 1600 — 1800 compare to the last one I tried 1200 — 1800 — 2200
How many people scored 100/100?
More than 500 as of now.
Can anyone provide code for last two XD. I need it urgently.
Please Downvote it if you would proivde the code.
my solution
Code 1:
Code 2:
I did my part and downvoted.
Provide a working code if you have
It worked for me ¯_(ツ)_/¯
Especially the second one.
It's short and nice.
I feel the third is hardest, I use dp and get TLE for test 2
in 3rd, u need beinary search. check whether we can make x as our answer. we can make x as our answer only when sum of all (a[i+1] — a[i]) / x , for i = 1 , n — 1 is <= k.
s there any category , you would put this problem to ?
It can also be done by simple greedy, just pick the largest gap, decrease the gap, repeat for k times. O(klogn).
Hey!
I'm not sure that this always works, for example, given a case where the optimal solution involves splitting up some difficulty gap twice (one input gap into thirds), but this solution would first split it into halves and split one half into two quarters.
Here's a case:
Here, the optimal solution would be to use two splits between 1 and 19, making
[1, 7, 13, 19]so the answer is 6. However repeatedly picking the largest gap and splitting it into half, would give you:[1, 19] => split into [1, 10, 19]for the first step,Now the largest gap is
[1, 10](or[10, 19]), which you could split into[1, 5, 10]. This approach gives 9 as the answer (because[10, 19]still hasn't been split), but 6 is possible, as we showed above.Thanks!
No, I meant equally distribute the gap, like fo the first time you visit this gap {1,19} divide it in two parts (thus {1,10,19}) now when you visit the same gap again split it into 3 parts(thus {1,7,13,19}), and so on k times. I implemented it like @Spheniscine 's comment down below.
2nd was def tougher than 1200
Speedforces
send your code with speed right now.
I used _dobby_'s code
I really hope you changed the code, I don't want to get caught in plagiarism.
XDD
Speedstart to be precise.
Why priorityqueue based greedy solution giving WA on large test case of problem 3?
If you are just taking biggest gap and dividing it into two, that won't work. Consider the case:
The optimal solution is 1 4 7 10 with a penalty of 3, but the divide-by-two solution would produce something like 1 5 7 10 with a penalty of 4.
I too wrote the solution using priority queue and got 3 WA. Later used binary search.
I actually used priority queue, but rather than storing only the gap, I store both the initial gap and the number of insertions, and greedily add insertions to the entries with the biggest current gap, i.e. $$$\left\lceil \dfrac {gap_0} {insertions + 1} \right\rceil $$$
yeah i did the same ,Having original value is important
Wow, that's smart way.
Can you kindly post your solution?
https://pastebin.com/mqtmKYpd (Kotlin)
It's slightly different from how I described it, as I store the divisor ($$$s = insertions + 1$$$) instead of the number of insertions directly
Is there a mathematical formula/concept behind that expression? I fail to see why that works.
Each entry represents the gap between a pair of consecutive numbers in the input (so $$$gap_0 = M_{i+1} - M_{i}$$$ for the $$$i$$$th entry). $$$insertions$$$ are the number of new exercises you plan to put within that gap.
So say you plan to put $$$3$$$ insertions between $$$2$$$ and $$$11$$$. It can be seen that it's optimal to space them out as evenly as possible (e.g. 2 4 6 8 11), and the largest gap remaining in that segment is $$$\left\lceil \dfrac {11-2} {3 + 1} \right\rceil = 3$$$.
Ahh, Thanks.
I solved it using the priority queue.
My code.
Ok,thanks.
Got rly lucky and got first :) Screencast: https://youtu.be/uGrBHohIgQY
u r legend.
How to get lucky as often as you and win everything?
seems like the thinking phrase was missing
The only reason why I was able to solve the 4th question was that I had seen this video from your Youtube channel in which you applied dfs on the trie. It's a simple and easy concept but still was very helpful. Thanks!
The "Case #x: y" is the most bullshit thing I have ever seen in my life.
Totally agree
11000 people gave this contest. Never ever in the history of kickstart. what make sudden rise.
2100 something people participated in last year November 2019. Such a huge increase in participation.
Because here in India we are observing Janta curfew an unofficial type of lock down. So all interested Indians participated. even in other parts of the world every one of them are in their home
Corona Effect
Maybe because everyone is at home.
how much u solved? how to solve D.
There is an analysis section, you can check editorial there too. By the way D can be solved using trie, Rolling Hash, or even with segment trees.
ok.
I solved it using Trie, felt most intuitive to me.
yes, i see.
Since we need some information about prefixes and not any arbitrary range, using Trie is best and a lot easier.
Any ideas why this brute force is even passing the larger test cases as well. I mean why am I getting both test cases passed without trie etc.
{
}
How to solve D using segment trees?
See this.
Corona
Besides Corona Effect, I think there's an another reason. The first problem in this Kickstart problem set was ridiculously easy so almost everyone attempted it. Otherwise, many candidates who can't come up with a remotely working solution for the first problem, simply leave the contest, without a single submission.
How to solve Plates (second problem) ?
go for knapsack type dp, pick j th plate from ith stack or leave it.
can u provide your solution please??
…
thank you :)
Using dp.
I really feel stupid not noticing the 4th problem and wasted 50 minutes rejoicing. Anyone else along with me?
How is that even possible?
My page size was such that it did not fit the 4th one. And I did not notice there is an option for other problems. Yeah I feel silly.
I used trie to solve the 4th problem. I personally felt that it's a feasible solution with good efficiency, though unfortunately I got WA in larger test. Is there anyone willing to take a quick look at here for me? I hope I could debug by myself, but I have no idea how to proceed since google is unwilling to release the test set even after the contest (sighed). Would be really appreciated if anyone can help :D
did u take care of space?
I think the space should be fine. Also I got WA instead of MLE.
How much pwople going to round B?
Everyone can participate in all of Kickstart's round. This is no elimination kind of contest.
Oh, ok, thanks)
what is wrong with my greedy approach for C
for every session to be added pick that consecutive (a,b) whose difference is maximum and add a seesion at (a+b)/2+(a+b)%2. and i did it using priority queue 1st test case passed but got WA on other.
Please help.
Testcase for which your code fails is
1
3 2
1 2 10
The answer is 3 (insert 5 and 7) ,but you would get 4
How to solve problem D using trie ?
Code
Will it be the sum of frequency/k or sum of valid frequency(atleast k strings possesssing that prefix). Also, when adding the frequencies, ain't we adding up the undesired frequencies too?
for eg — rain, rainbow, rainy, rat, ra, with k=3 so r->5, ra->5, rai->3, rain->3, ra->2, rat->1, rainb->1, rainy->1...and others.
According to me, we should add (len. of "rain")*(freq. of "rain")/k into our final answer and subtract the this frequency from previous prefixes, ie — (freq. of "rai") -= freq. of "rain" and propagate this difference to the previous prefixes.
BTW, why did you use map and pushing the prefix count and later doing
ans+=map[depth][i]/kinstead of directly doingans+=freq/kin thetraverse()function?Yes you are right it can be written that way as well.
PS- This code is what I wrote during the contest so it may not be as neat as it should be.
I did it both ways(yours and my way) but still getting WA. I'm doing
traversething in the fun() function.Can you check a bit this code?Although, I did the 3rd question(Workout) using binary search, How to do it using priority_queue?
Is there any category , you would put this problem to ?
In problem D why does sorting and then grouping them into size of k and then finding longest common prefix for each group is not working . I wasted my 2 hours on this . Anybody help ?
Consider this test case
By your logic, you will group (AB, AC) and (AC, AD) with sum 2. While the correct answer is 3 by grouping (AB, AD) and (AC, AC).
Thank You so much for the test case .
I tried every cyclic shift after sorting. Is there a counter test for that too? Or my implementation was incorrect ( I got WA xD ) ?
Consider this
In any of your cyclic shifts, you will either have (AB AC) (AC AD) (AE AE) or (AC AC) (AD AE) (AE AB) with sum 4. While the correct answer is 5 by grouping (AB AD) (AC AC) (AE AE).
Thanks a lot.
Hi everyone,
For problem 4, I implemented using Trie and passed the small test but somehow I got MLE for the large test, I spent hours trying to find out. Thank you in advance.
My code:(https://ideone.com/s8IpR6)
You need to free the dynamically allocated memory using
deleteafter each test case.Writing destructor also didn't worked for his code. There may be possibly infinite recusion or loop allocating memory indefinitely.
You're right. The actual issue was in the function
print1(), which was $$$\mathcal{O}(n^2)$$$ in time and memory because it passed the string as parameter. It now ACs even without freeing memory. https://ideone.com/4U0qVMWhy exactly does this work? Can you explain the intuition behind the approach?
Thank you so much.
KickStart 2020, Round A. The limit for N of 10^5 in test set 2 which they specified in problem 1 ("Allocation") is incorrect. I am pretty sure they have a test case in test set 2 with more than 10000 houses.
Why? I was getting RE on test set 2 and I spent about 1 hour trying to find "the bug" in my program, and then finally as a last resort I decided to just extend the size of my arrays to 10^6. And the same code which I already had and which was giving me the RE, it suddenly worked fine (just with the array size changed).
Did anyone else notice this issue in test set 2?
FYI 10^5 != 10000
The ranklist was filled with people who never solved more than 2-3 Problem, but guess what,today they solved a friggin trie problem...On a totally unrelated note someone sent me a picture of people discussing on whatsapp groups, but let's just ignore it :)
Yes, i agree. but how u know they r the same people who never solve > 3 problems. I understand there is a lot of cheating and many knows from where they r from. but what they will gain, they will get crushed if they called for interview. so chill :_)
They will get crushed no doubt, but someone might not get a call because of these people, considering google does not call everyone.
Yes.. u r right. Google should take it seriously.
darkshadows please convey it to google. It happened on large scale today.
Google only contacts the top <100 based on previous competitions, so I doubt you can cheat your way to that high because if you need to ask for sol you probably can't code fast enough and you'd have to copy paste from someone in the top 100, and the people that high in ranking do not want to cheat. So if you're worried about cheaters taking your interview, you nor them is probably getting an interview.
Are you sure about the <100 thing? I had a 2 digit rank last year but wasn't invited. I know a guy who had a 500+ rank but was invited for the interview :-/
No this is not true. My fried had around 370 rank in one ks round. He received call and cracked google too. One with 542 rank also got call. So this is not true.
Are you sure that they didn't applied on Google's Career Page and received call?
Maybe they were contacted regardless of performance on kick start. Like referral or just standard application.
Take 4 people who cooperate and parallelize work by first solving harder problems as a team (if necessary) and then coding on 4 machines in parallel and submitting everything under the same account.
This way you can get result in top-X with zero people who have top-X skill level involved.
B was a really beautiful problem