Solving Google Code Jam Qualification Round 2020 A-D

I try to solve Google Code Jam Qualification Round 2020 problems while explaining my thinking process.
A: 00:45
B: 05:53
C: 12:10 (O(nlogn) solution)
D: 26:38
Unfortunately, my solution to E is too complicated for me to explain :(
If this was helpful, consider liking or subscribing!
Website: williamlin.io/
Instagram: / tmwilliamlin168
Twitter: / tmwilliamlin168

[@S4ND1X]

I feel great because even thought I could only solve A-C, but for all of them I did the exact same thing as you, so It really gives me a boost of confidence to see that my practice is paying off

[@aamnasayyed]

How long do you practice per day?

[@S4ND1X]

@@aamnasayyed Between college and home chores like 3 hours a day

[@dhananjaysonawane1996]

Same here! I solved 2 (almost there with 3rd).

[@aamnasayyed]

@@S4ND1X Great! How long did you continue this routine?

[@GiamSaas]

@@S4ND1X can a boy of 16 yrs old learn this?

[@plusequalminusk4203]

I'm going to be honest, I can't even comprehend what you're trying to do, but I still like watching your videos nonetheless.

[@leonardsmith9085]

I legit thought I was the only one 😂😂😂

[@tamasfeka5026]

i learned some programming on a very basic level but idk what the F hes doing 🤣 it's just good to listen to, like an asmr :D

[@LEEH_1]

Same

[@yournan7249]

@@tamasfeka5026 facts

[@dutchboybmx]

I have no idea what you're doing, but that makes me all the more inspired to learn all I can about math and computer science.

[@josephli2119]

"Which one should I write" Imagine being so massive brain that you have multiple solutions and have to decide which one to use

[@kay8108]

Me reading my coding exercise: ok now how im gonna do this? Lin just completed reading: ok i have an idea....actually i have 2

[@tmwilliamlin168]

Please read the description, I quote the rule (with the link) which says people are allowed to "share information" (which includes both ideas and codes) during the qualification round.

[@kartikbhatia4940]

What is the very meaning of keeping a qualifying marks of 30 marks ? if we are allowed to see online solutions of this contest ? This is against the spirit of Competitive programming merely for likes and subscribers you should not be doing this ! I didn't expect it from you !

[@tmwilliamlin168]

The qualification round was intended for Google to give beginners a chance to learn, that's why Google made it 24 hours, and it was never intended to be a serious contest. There are future rounds in Code Jam which will ensure the competitiveness of the contest. I just wanted to help beginners (perhaps this is their first ever round) who are really trying hard to qualify.

[@rajatchaudhari1228]

@@kartikbhatia4940 Qualification Rounds are basically to promote competitive programming I guess, so its fine to discuss. Else, the rules would have stated that you are not allowed to discuss, and maybe would have organised a qualifier of 2.5 hours to 3 hours.

[@kartikbhatia4940]

@@tmwilliamlin168 Codechef Long challenges also last more than 24 hours but even discussion for them is prohibited it is sad to know that Google allowed discussions during the contest itself ! No hard feelings with you but just amused about How The qualifier round is not a serious one :( ! Looking forward to more of your videos and your nice explanations ! :) Happy Coding !

[@tmwilliamlin168]

I know it might be sad for some people who tried these problems, but isn't it better to get more people involved in CP? Imagine a beginner who realizes that he can't even solve the second question and just forgets about CP entirely before the round even ends, versus if he had seen the solution earlier and thought "Actually, this doesn't seem that hard. With more practice, I can definitely become better at this!".

[@buzy6782]

Watching you solve problems is like an art. I can't seem to look away no matter how hard I try. I need to start learning the basics of cp!

[@jasondolorso]

I love how more explanatory you are now.

[@imdeadshot3632]

well i spent hours to solve first 3 and you did in minute! TEACH ME SENPAI!!!

[@sssssingh]

WoW Your are growing really fast! Congrats!

[@NavrajNat]

You should continue to make videos where you think aloud. It’s really helpful to someone like me whose trying to get better at algorithm problems. It provides such great perspective. Keep up the great videos.

[@dhananjaysonawane1996]

I find this way of learning more helpful than reading editorial! Please make more such videos for codeforces rounds as it has a better question set compared to other OJ's (Leetcode, codechef, etc). Thanks William! :)

[@Avighna]

Yes please!

[@mayankmittal6552]

Doing it this way is far better as one can understand and follow what you are upto. Furthermore many have problems implementing the solution (I knew for D but couldn't implement it), it really helped me watching how you coded the solution.

[@kartaLaLa]

Hands: Yes Eyes: Yes Brain: No

[@alessandrobiaggi2965]

I LOVE YOU ❤️ I participated too with a final score of 75

[@siddusiddhartha171]

could you please make a video on how to setup vim with c++ for CP?

[@beinevitable1797]

kzbin.info/www/bejne/bmq2f5pui5KcnK8 I think this video might help

[@bensonyuan5083]

I solved the scheduling problem by sorting by start time as well! 1) When do we sort by end time when do we sort by start time? 2) Can you point to resources for greedy algo for selecting the maximum number of independent ranges?

[@henry145]

When sort with end time that means u want to join as much activities as possible because the earlier it finish the earlier u can join the other activities. But this question is about overlapping, so the earlier it starts the smaller the risk that will overlap.

[@marwannabileldeep4513]

dude will you make a video for today's atcoder contest ?

[@XSTEVEN722X]

FYI for problem A with sets you can do s.insert(value).second which will return true if the value was successfully added to the set, meaning it wasn’t already in the set. And it will return false if it’s already in the set (a duplicate exists). Also if a duplicate exist you can break from the inner loops and increment the counter.

[@kairatopa9564]

Or maybe after inserting elements into set check if s.size()!= n then count++

[@Chris-qn2io]

Hey William, question why you always increment your i's in your for loop beforehand rather than after?

[@ztrixx3280]

Upload more of these typa explanatory videos...New Sub btw!

[@kamalhm-dev]

Hey William, I see you're not even in Uni yet but your skills are impressive. At what age did you get introduced to CS?

[@abubakaraftab4423]

In the first question instead of checking duplicates we can just check wether the size of set is equal to n or not if it is not then we increment it

[@nuralisadibekov7672]

it's pretty cool font in your text editor)

[@ajourney179]

Hello William Lin, since you have experience of code jam round 1. what is the difficulty of round 1 problems as compared to codeforces division 2.

[@sktechguide7780]

Dude.You are the best.😎 Can you please tell me the keyboard that you use while doing competitive typing?I actually want to buy a keyboard like yours. It seems like a superior one.😅 Thanks in advance.

[@ATGamerHTZ]

You can create a programming course. And maybe use google exercises to teach us. or just take the previous kick start, and make videos teaching how to solve step by step calmly and such. it's just an idea, I would follow all the videos

[@prashantiyer6659]

Hey William can you please do a video on how to practice to become better at CP?

[@29saiharsha]

Thanks for inspiring me man I'm also striving to qualify for ioi

[@TheAceInfinity]

If you read the example interaction, the change actually does happen after the query but before you read the response (which is admittedly confusing at first). This makes the change negligible for the first query since you still receive the bit value AFTER the manipulation. The format and the testing tool kind of messed me up for time though too. I think the bit position direction (MSB or LSB) was a bit ambiguous also which caused me time as well haha. That Sample Interaction was what I should have been reading instead of the textual description of the problem I think.

[@namanagrawal1908]

just subscribed after watching this video.. very inspiring..

[@rajatchaudhari1228]

Eagerly waiting for your tutorial videos!!

[@tmwilliamlin168]

This is kind of the tutorial... I explain my solutions as I solve the problems

[@subhajitmanna305]

@@tmwilliamlin168 Can you please provide why the greedy approach works for the third problem or any resource would be fine! Thanks

[@praharshsingh2095]

Dont fall into the Tutorial Trap.Go the Hard WAY

[@subhajitmanna305]

@@praharshsingh2095 You mean using bipartite concept ?

[@praharshsingh2095]

@@subhajitmanna305 Haha Good One :P

[@r0l3ex20]

When you are typing you are useing "Home row position"?

[@shivrajbhatti1074]

Why is the soln for parenting partnering (3rd Q) in O( NlogN )?? That would mean the assignment loop goes on for logN time, but i dont understand why?? plz help🙌

[@rahmanyt]

though ide doesn't do anything in coding... just to know... which ide do u use?

[@ankitkumarsharma9837]

Why did you confirmed "later starting time"? Why is it needed?

[@karanbobade5266]

Hey william, could you please explain, how C could have been solved using bipartite graph

[@magirescutudor7148]

I solved A-C in around 25 minutes, got a code for D in 30 more minutes, stare at the monitor for around 1 hour to find a mistake, then finding a case where it would WA, but i still don't know how to solve the 2nd subtask of E

[@samarjitdeshmukh4845]

I started practicing last Sunday and was only able to solve the first problem.

[@shashibhushanrajput2461]

Awesome Man

[@cartoons__for__kids_Hindi]

What are these kind of problems known as, where can I start ?

[@marmikpatel9261]

What are the specs of your programming device?

[@parvgour5284]

please make a video on the solution of problem E of code jam 2020...

[@yacinmessaoud186]

Thanks for the effort !

[@animenerd_]

Bro, I was so disheartened because I couldn't even think of an approach to E.. 😂 Now I feel better seeing grandmasters like you think E's not easy..

[@AyushGupta-mm4jg]

ok pritishn

[@animenerd_]

@@AyushGupta-mm4jg lol, i should have changed my profile pic 😂

[@secularph8424]

The second problem I did it by keeping track of number of opening parenthesis and closing it with (currently opened - next number ) How different is my approach with his Anyone pls explain If my question is confusing jus comment i can elaborate

[@vivekmishra4994]

Hi. I used to do CP in Python but during code jam i realized that it is too slow. So I switched to C++ during the contest(also u cannot use Python in ioi). Can u tell me how did you learn cpp (source)and how u got better and better

[@secularph8424]

ioi??

[@vivekmishra4994]

@@secularph8424 international Olympiad of informatics (foe high school students only)

[@secularph8424]

@@vivekmishra4994 ok

[@scoopedcontent]

Are you sure about this? I mean qualification round is still active.

[@tmwilliamlin168]

See the description, I quote the rule which says people can discuss during the qualification round.

[@zoompie6786]

Discuss, not to copy the code..

[@tmwilliamlin168]

Google states it as "sharing information", which includes sharing ideas and code.

[@scoopedcontent]

You're the best jugde for that I just didn't wanted you to get banned. Btw am so in love with this series of yours it is really helpful. Please share something about your journey as well.

[@omarbahgat5568]

@@tmwilliamlin168 Bro how did u customize ur tabs to glow green like that. And can u do a setup video

[@shivangawasthi8750]

Can you please explain when to sort by start time and when by ending. I was trying to solve 3rd by sorting ranges with ending time and i am having hard time.

[@naveenrawat6278]

You can do it by sorting on ending times. The issue most people had was that when both J and C were available, they were assigned jobs in a fixed manner irrespective of who gets free first.

[@MohammadSuleman008]

Why you uploaded this video before the end of contest? Is it not against the rule of code Jam?

[@The001Shubham]

Can you please make a video on how to tackle a DP problem ..

[@PrajwalSSYMCA-qx5yw]

anybody know which software he is using.

[@krsaditofficial]

Hey William, would you recommend me how to start competitive programming i.e resources etc.

[@tmwilliamlin168]

Hopefully I can finish that video within the next 12 hours

[@Mike-mw1fu]

William Lin Which editor do you use ?

[@Jay-wb7hw]

study student vim

[@templetherapy]

can u make a vid on how u learned

[@aaronwang3387]

For D, shouldn’t you also have to have some dummy qry() in findchange() to account for the short circuiting? Otherwise wouldn’t it cause the queries to be misaligned with the changes? Great video btw hahaha

[@tmwilliamlin168]

Yes, I fixed that during the debugging session but I forgot to mention that in the video

[@MasabFarooque]

Panther Tech supports you.

[@ArshadKhan-cb4do]

Whii programming language you use c++

[@SayanDasezioauditore]

Why does sorting by end time not work

[@psychoticgamer6853]

That mechanical keyboard was good

[@kingfisher3791]

Which screen recorder u r using

[@anchalvatre2594]

which font you use

[@adityatrivediii]

Please share your Chrome theme! looks nice

[@harishankerchauhan2826]

Sir please solve the questions of CODEVITA and share that video with explanation.

[@Amit_Kumar_1999]

I sorted the activity with their end time because i thought that it would be related to exchange argument & and got 6 Wrong attempts. Can you point out why sorting by ending time solution fails.

[@subhajitmanna305]

same went for me, got 7 wrong attempts. even I was trying to figure out. Let me know if you find out anything.

[@Amit_Kumar_1999]

@@subhajitmanna305 discuss.codechef.com/t/google-code-jam-2020-problem-3/60303/12

[@Amit_Kumar_1999]

or check out with this test case 1 5 1 4 0 200 50 100 150 300 250 270

[@subhajitmanna305]

@@Amit_Kumar_1999 Thanks here! But I am not to figure out how to proof this greedy approach works here.

[@Amit_Kumar_1999]

@@subhajitmanna305 Proof is the tricky part of greedy solution. As i earlier mentioned that i felt this is related to Exchange Arguments. So i think just check out these. You might get something . Also if you found something mention here or mail me offamitkumar[at]gmail[dot]com

[@Drytube]

Please make a set video of vim with C++.

[@marcuslee678]

Thanks William!

[@marcuslee678]

After watching ur vid, I realize the way I approach Q4 is totally all wrong 😅

[@lw03070]

what am i watching? where am i ? I was watching NHL earlier, and now I am here.

[@user-ir2ie3yv7m]

انت مبدع وعبقري حقيقة,,,,,, البرمجة تصيب الشخص وجع الرس كيف تتغلب الملل ,,كيف تصنع الشغف في حب البرمجة بما انك محترف برمجة؟شكرا لك.

[@97lovechina]

What s his vim font?

[@jaichhabra6849]

help me with q 5

[@adityadhane5917]

Is that vim?

[@ermolaevatania]

how do you hire this person?

[@GibbaBites]

Why do u still use windows at this point?

[@RishabhSharma10225]

WE WANT SOLUTION TO E !!!

[@aw12sdfx]

love you my idol

[@youngchung8730]

When will you be hired to Google? Lol

[@kylexie7579]

waiting for your E dude. Solved A-D in 3hrs but have not idea on E totally...maybe your facecam for solving that problem is okay, no need to explain

[@FoodieKing]

Now see the subscribers tomorrow morning .😁😁.. Subscribers gain krne ki ninja technique

[@alfredoterrero2963]

What’s your github?

[@nikhillondhe5815]

The competition is still on right?

[@tmwilliamlin168]

See the description, I quote the rule which says people can discuss during the qualification round.

[@nikhillondhe5815]

@@tmwilliamlin168 Great! But the link is broken. You added a ':' at the end.

[@tmwilliamlin168]

Thanks for letting me know!

[@xvzf115]

With facecam

[@subhajitmanna305]

awsome!

[@ashutosh6060]

Why did you leave E? Its not codechef challenge problem :D

[@ashutosh6060]

Sorry i didn't watch till end that time. Now i know why E is missing.

[@sajjad.h]

The contest is running... How you can upload solution when contest is running?

[@tmwilliamlin168]

See the description, I quote the rule which says people can discuss during the qualification round.

[@abhishekgautam2693]

@@tmwilliamlin168 I believe that discussion and showing solution code is different. But anyways I'll watch it tomorrow ❤️, thanks

[@tmwilliamlin168]

It's not limited to discussing, Google describes it as "sharing information", which includes all of discussing and showing solution code.

[@akhilgunti7540]

Can you please create a programming course mainly focussing on recurrsions and dynamic programming..btw great work bro..

[@steevecastor6514]

My understanding of recursion is that a function calls itself, until it reaches its base case. for example , if you're trying to find the factorial of an integer you can do: public int factorial(int n){ if(n==1) return 1; // this is the base case, once the function reaches this case it returns 1; // the factorial of 1 is just 1. // if your function does not have a base case the function will loop infinitely until your machine runs out of memory. else return n*factorial(n-1); /*this is the recursive case, the function calls itself until it reaches the base case. For example if n=3, then the factorial of 3 = 3 * factorial(2), the function then needs to find the factorial of 2. What that is is just 2 * factorial(1). and the program knows that the factorial of 1 is just 1. So it multiplies 2*1 and returns it to the function calling it. So now the original function we called has an equation that looks like this --> 3* 2 and this equals to 6 so the factorial of 3 is 6. }

[@steevecastor6514]

hope my explanation helped.

[@nithishkumarsaravanan4251]

Looking cute in Black t-shirt...Lol😂

[@lostlong62]

lol people who say this is cheating, why you click it???

[@yugeshnukala949]

which application you are using to write your codes????

[@chienyo8480]

First query：😢

[@timothygao9442]

bro this man reads so fast

[@artworld8586]

Anybody know which software he is using for coding 🤔🤔🤔

[@vaibhavgupta7429]

what are you drinking..?

[@tusharsrivastava370]

Me after reading the first problem : It's easy On the 2nd : I can do it if I try hard 3rd : God, forgive me for I have sinned

[@cartoons__for__kids_Hindi]

Where do you practice

[@sanskargupta6791]

It's an ongoing contest. Why did you share the solutions??

[@tmwilliamlin168]

See the description, I quote the rule which says people can discuss during the qualification round.

[@kushagrasahni9708]

@@tmwilliamlin168 Bro I don't think that's fair because this way everyone will qualify the round. It'd be better if you remove this now and upload it tomorrow.

[@yashkumar8472]

GOD ...Hi

[@scottchilds6676]

Can you make a program to eliminate corona virus thanks

[@fuadf.7842]

What the f is going on this vid. No idea

[@zulqadaridrishi457]

Achha to Kerala wale malyalam bolte h 😅

[@BrijeshYadav-xu5kj]

competition is still going on

[@tmwilliamlin168]

See the description, I quote the rule which says people can discuss during the qualification round.

[@BrijeshYadav-xu5kj]

@@tmwilliamlin168 Still u should have not uploaded it, i lost motivation to solve question further because now people will just copy paste the code

[@tmwilliamlin168]

Yea, I understand that there are drawbacks, but the purpose of this round is to give beginners a chance to get involved with these competitions and not for actual competition. If the competitiveness is your motivation, then you will have that motivation in future rounds.

[@neel4959]

why do u use windows windows suck