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 thoughts on “Winning Google Kickstart 2019 round G — screencast with commentary

  1. Like if I should add the third Kamil that is even more from the future. And the mentioned post-contest live stream with results and solution description is here

  2. "If we iterate over multiples of 1, multiples of 2, 3 and so on, the amortized complexity of the total thing is O(nlogn)". So if someone gave those exact inputs for r (r=1, r=2, r=3,…, r=n/2) to your solution it would take time n+n/2+n/3+n/4+ .. . But I don't remember that series converging to O(nlogn), do you have a reference? Obviously it grows very slowly, I used wolframalpha to compute it up to n=10^5 to check. Just curious how to know, though, that this would be O(nlogn). I don't remember learning this in CS classes.

  3. Congrats Errichto. I like you so much since before but I know I don't have even just 0.00000000001% chance on you.😢I'll just love you from far away.
    Take care my king

  4. Tam olarak ne yaptıgını anlamadım ama cok ıyı oldugunu anladım. Umarım zahmet edip bunu cevırırsın google translate ıle . Ilerıde senınle tanısmak ve calısmak ısterım. 🙂 bakalım meraklı bırısı mısın

  5. Dopiero zaczynam w programowanie w liceum ale mam nadzieję że kiedyś to znowu obejrzę i będę zrozumial kod na bieżąco

  6. Hello Errichto, I'm just starting competitive coding using C/C++. I want to know how you are too good in competitive coding, I know most of the competitive coder don't tell his successful mantra's but I'm gald if you tell me little bit about your competitive coding skills.
    Thank you. And
    Congrats Man..

  7. People like this have dedicated a majority of their time to be really good a these problems. It's the same as the SAT. If you practice and practice and practice you'll eventually get it like the back of your hand. It's all about how much time you're willing to put into it.

  8. Anyone here from the United States of America do like 👇🇺🇲🇺🇸🇺🇲🇺🇸🥰💝💌💙❤💙❤💙❤💙 and best music

  9. Am I the only one who is amazed by the fact that this guy cloned himself, just to chill and talk while his clone does the coding

  10. I am Surgical resident I didn’t understood a single word though a saw first 5 minute of video. Lol why youtube recommended me this video. Haha

  11. These questions are out of galaxy and this guy cracks it just like that. I wonder what is something challenging to him.

  12. Hey i found your video by chance, i am an Electrical and Electronics graduate interested to learn some codings. I learn some codings though for different purpose ( such as verilog to program De1-SoC, arduino etc ) and also very basic C. Do you have any suggestion for me where can i start and practice from ( such as what language should i start or even framework )? Thank you

  13. Why do you use C++? How it compares to Python or JavaScript in terms of competitive programming? Maybe you could make a video on it?

  14. I believe the reason they give a story is the same reason a lot of standardized tests do. If we are stressed we tend to cling onto information that may not be necessary. Also logically, it traps those who don’t recheck by giving minutiae (see first problem and where you slipped up). This is especially effective at the beginning of the test or at the end. When we are given added unnecessary information or verbiage at the beginning of a test, exam, competition, etc. we tend to skip over important information because we are excited. When this happens at the end we tend to miss it because we are mentally exhausted (not noticeably per se but we are coming down off the adrenaline of the first question).

    This was a competition not only of your coding and problem solving skill. The story adds the element of examination, precision, and attention to detail.

    Added to this reading the story forces you to slow down and read the actual problem. If given an equation (while still difficult) there’s no need to search for necessary information. I personally prefer to have the information right at my disposal in a test too but thats a secondary reasoning for verbiage in mathematical questioning.

    Hope this might answer your question on why the (still painfully forced) story was implemented in this timed competition.

    Anyway it’s always a pleasure seeing you work! Beautiful work.

  15. To guys who get scared after watching this kind of stuff, please don't look at advanced stuff before mastering the basics. You cannot learn always easily a black belt moves in Jiujitsu without mastering the basics mastering the basics first. A baby takes time to walk and it masters it overtime. Secondly real life programming is more about creative thinking and much easier than competitive programming. You don't need to know many of these stuffs to land a job. Programming is very easy actually, it's far far different from these problems and these problems are called competitive for a reason. So please don't look at all these stuffs if you are just into programming and don't love advanced programming and thirdly just follow the traditional programming learning and you will land a job God willingly. Real life programming is wayyy different than these competitions and much creativie and easier God willingly. Enjoy ❤️

  16. 6:07 . When you talk about stories I think its good idea to force the programist to interpret some situations that happen in a life like creating software for a company where you have to approach a project that is complex becasue thats company processes are very complex

  17. Loved this cast errichto! Even though I got lost a lot in between because of my lack of understanding of some concepts. But still this was quite helpful. Thanks for this.😎

  18. Yeah this is why engineers make the big moneys because they can translate logically sophisticated problems into code this worries me as I am working on my bachelors for csi and they don’t even teach you how to code they just expect you to know how to code like him.

  19. So I guess the algorythm brought us together again?
    PS. I have like zero interest in these videos so.. 😂🤷🏼‍♂️

  20. 4:45 ”You need to unlock your phone”
    I feel you phone, he only notices that bitch named COMPUTER. I’ll give you attention.

  21. Im very interested in these things but in school we just started with java xD (Greenfoot) so i dont understand much lol

Leave a Reply

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