Winning Google Kickstart 2019 round G — screencast with commentary

Winning Google Kickstart 2019 round G — screencast with commentary


Okay, Google kickstart 2019 round G starts in 20 seconds, I set up my environment and my idea for recording is I will turn off the sound even in 10 seconds just to focus on The contest I will try to win, of course, then maybe I will add some commentary after the contest. Wish me good luck Hello Kamil from the future here and we’re starting. The first problem is book reading. I remember that I’ve misread this problem first the statement is that There are pages numbered from 1 to N and some readers… First some pages are torn out they are not there then There are some readers and for every reader we know that he reads only pages that are multiples of some number That is by the way a bit stupid problem kind of forced Readers don’t usually read every tenth page unless it’s torn out that they skip that and I thought that we should print the sum of numbers of pages that we that they read while the statement is You should count them and print the sum of numbers of pages read by all the readers I thought that we print a number for every reader. I wasted like a minute there. I thought those are queries that are kind of independent By the way, it’s already a few days after the contest and I’m now adding some not not live, but Post contest commentary so you wouldn’t be bored just by looking at my code. What do we do? we read R that what multiplies we are interested in and We iterate over R, 2R, 3R and so on till we don’t exceed Until we don’t exceed n if that is not bad So not torn out then we add the answer and that shouldn’t be answer[r]+=i it should be just ++ I didn’t know that By the way, I did a stream after that day, with leetcode and kickstart contests and for the first half an hour of that stream I talked about solutions from kickstart if you want to hear that with drawings A link will be in the description or in the pinned comment It’s the first hour of that stream So, you can there see solutions. Right now, I’m only talking about what happens during that contest not really trying to present the full solution But here the complexity is n*log(n) because if we iterate over multiples of 1, then multiples of 2, 3 and so on the amortized complexity of The total thing is nlog(n) Now, what happens I printed too many numbers a lot of zeros Total zero, now I realized that we need the sum, we don’t print so many things It’s important to remember about Long long in C++ not to get overflow 7, 0, 994 it works. I wasn’t sure here if I can copy/paste the code or whatever I can just Upload it because I emulate Linux system in Windows, which isn’t that easy. In Windows it’s easier for me to record videos Linux is a bit buggy. Let’s say An important ??? for contest is if you want to if you are in hurry Then don’t look at the leaderboard because that’s a waste of time. I submitted the first problem went immediately for the second problem without Even a second wasted. I don’t even wait for the result of that first problem in Google Code Jam Your final time is the maximum of submissions not the sum of solutions My phone again thought that I’m talking to it You shouldn’t waste time on Correcting the first problem waiting for verdict because what matters is the maximum submission, it’s fine if after all three problems I see wrong answer, and then correct it as long as You know, you’re strong psychologically that doesn’t bother you that you don’t know verdict of the first problem you can just move to the second one and This second problem is about XOR numbers so for sure something with bits the numbers are up to 10^5 and this is why you can see in code me iterating over bits from 52 to 0 from 50 to zero would be enough. This is how many bits 10^15 can have I’m not going to now explain the solution. Again, go watch that the first half an hour of that stream What else do we see here interesting Yet again, Codejam tries to always have some story in the problem and here we have the laws of universe can be represented by an array of n non-negative integers the universe is good. And so on I guess I’m writing something on a piece of paper now at the end In twenty minutes the past Kamil will show you what notes he has codejam and kick start in general always tries to have some statement, What is sometimes very stupid because The statement is artificial Here in the problem. The problem is given some sequence figure out this value K such that something is satisfied. I don’t understand why they want so much to have a story like here laws of universe What was that in the previous problem? In the previous problem it was fine, but still very forced. It was obvious that The problem was invented first and only then some story Can they just say? there is You were given the sequence with some numbers removed finding the sum of our multipliers or the number of multipliers of this number. I remember that one of organizers of code Jam talked with us during codejam finals that He doesn’t like in you know platforms like top coder The statements are so stupid like there is somebody who got a Christmas gift he got a sequence and something happens with that sequence. Well, this is just This kickstart thing is not better, I would say. So it’s a choice between having just A formal statement like for this sequence do that versus You know creating some artificial story, of course from time to time, the story can be natural – it’ll very very much fit the problem, but it isn’t always the case Maybe you can argue that Google Code Jam is much bigger more important competition Oh every time I say Google Then my phone turns on, I have Google pixel by the way(flex) So I can say codejam but not Google codejam . I’m looking at my phone to see if it turns on again Okay, what happens in my implementation We don’t want to exceed some value M in the input and then I see that if I can improve something and that possible new value `maybe` still doesn’t exceed M then I use that Otherwise apparently something else Already I think I made a typo already is a hard word to spell puts(“-1”) by the way in C++ prints -1 and adds a newline it’s just a bit faster than print “-1 n” I strongly recommend Not removing pieces of your code if they are no longer necessary during the contest just comment them aside I have a button. I think it’s for me control + e to comment it’s very fast And if it turns out that I need that I don’t need to panic and hit ctrl+z ctrl+z, you know, get back to that version because old result, I need that code debug is my thing that can print variables And here I analyze using that I get too many -1’s And I just didn’t apply the logic correctly, I think it was that first We need to iterate over bits and for every bit say what is the best bit there that will give me small sum in total that shouldn’t exceed M and then I go through bits again and I consider switching bit 0 to 1 and I see if I still don’t exceeded the total sum if I don’t then I do it and when I switch from 0 to 1 instead of then saying that to the sum I add What contribution there is from bit 1, I should say this minus what I already added. If I have answer Let’s say that current sum 50 that included Value 10 that was already counted and now I consider Switching 10 to 12. Then I should just add plus 2. So now you saw me Saying verdict for first problem. If that was incorrect, I would now Try to fix it. Why not? It’s just that waiting for verdict is bad. Here we reading the last problem C. N up to… when N is up to 20 your first thought should be: maybe bit masks, exponential solution complexity O(2^n) I started implementing that because I I’ve misread the statement I was just unlucky in this contest twice It happened. When I’m in hurry, I don’t try to read the full statement I skip the story kind of or at least Rush through it Then it can easily happen that I misunderstand something Two out of three problems is a bad statistic. I was just unlucky Here I thought that they require me just to iterate over bit masks and I knew that something is wrong. That would be too easy But I didn’t understand what is wrong so I started implementing I thought: oh maybe iterative version doesn’t pass so I should go with recursion. What is a bit more complicated but faster Here, it’s O(2^n) instead of O(2^n * n) for iterative approach And I wonder when I… when past Kamil realizes that something is wrong. The actual brute force solution will be O(3^n) Because we have N shifts and for every shift either both can come… I wrote a comment that expresses my thoughts. I didn’t want to turn on the microphone to waste time. I now realized that for every moment of those N moments/shift, either first person girl has a shift or second or both, so there are 3 options and that means O(3^N) but already after when I first time read the problem I knew that or maybe they will require meet in the middle from me. Even more, I will say that even before looking at the constraints I expected N to be around 40. I remember that Oh I guess they will say N is 40 and I should use meet in the middle Then I scroll down, saw N

100 comments

Leave a Reply

Your email address will not be published. Required fields are marked *