Google Code Jam 2021 Qualification Round Solutions & Live Commentary
Вставка
- Опубліковано 31 тра 2024
- My screencast and commentary of GCJ 2021 Qualification Round. Problems and leaderboard: codingcompetitions.withgoogle...
0:00 A. Reversort
3:37 C. Reversort Engineering
12:40 B. Moons and umbrellas
17:55 D. Median Sort
1:26:18 E. Cheating Detection
1:55:37 Results, Summary
Coding live streams - / errichto
FAQ - github.com/Errichto/youtube/w...
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
0:00 A - Reversort
3:37 C - Reversort Engineering
12:40 B - Moons and umbrellas
17:55 D - Median Sort
1:26:18 E - Cheating Detection
1:55:37 Results, Summary
Can you tell the resources through which you mastered math for competitive programming.
@@07_akashsudan71 school and math olympiad :|
@@Errichto can you recommend any book for math. I saw you solving a question that had some concept related to group theory and i couldn't find any relevant material related to group theory in any book. I am from india and math taught here at school level is not good. So can please recommend any good material.
I never went through any math book in English.
@Code NCode has a series of videos on number theory ua-cam.com/play/PL2q4fbVm1Ik4liHX78IRslXzUr8z5QxsG.html
@@Errichto thanks man. By the way a big fan of you.
I understand nothing of this but still find it therapeutic to watch for some reason :D
Yes! 😂
Some day
Omg we are the same 😘
Reversort engineering took me hours to solve, he did it inside 10 minutes. Insane.
yeah I also took many hours to solve that one.
Thanks for the video! I personally enjoyed it way more than other videos where you code in like 10 minutes and win the contest. It was great to be able to see how you actually think when you occasionally get stuck :) Hope to see more videos like this in the future!
Impressive as always. Your solution to the CJJC mural problem was so quick and elegant... I'd have to doublecheck and compare it with mine, because I think I wrote at least 3x as much code and made it more complicated than it needed to be...
Good job :)
I feel sorry about your rank Errichto :(, you are one of the best programmer!! And I follow you regularly for programming videos. Keep good work bro, next round 1.
Errichto saying "or maybe i am not good enough to solve this problem"
le me: I am not even qualified to hear this:))
p.s: you are so down to the earth and bmost helpful person of the whole community❤️
Thanks a lot for sharing this. I have been always wondering how these top ranked people solve the problems this fast!
It's really helpful to see you solve the problem, thanks a lot!
All the best for the future Errichto!
PS - Here's to hoping that you might be the one to break tourist's streak by winning this year :)
I'm hoping for that too!
Only legends know it's reuploaded.
Haha. What was the title? Place 6......
@@Manu-wb2uv (6th place) Google Code Jam 2021 Qualification Round Screencast
@@Errichto well you were very close indeed. The DP problem was a little tricky.
@@Manu-wb2uv Started competitive programming because of Kamil and I got that one point correct. (I didn't manage to realize D required log3 and didn't do E at all but still pretty proud)
@@meenameiss good job. That means I'll see you in the next round
I don't know if you covered this in any video, but I'd love if you show us the keyboard shortcuts you use or how you deal with your coding environment in general
theres something about the sound of that keyboard
Hey. Are you gonna do a live stream for the Round 1?
Thanks it helps and motivates a lot..
D can be approached linearly by tenary search for each index from 3, total number of queries used for each case is sum of ceil(log3(x)) where x from 3 to 50 ~ 160
O(N*log3(N)) is not linear.
But yeah, the intended solution was indeed ternary search, which means the logarithm of base 3.
In Problem C, please let me know what function on line 37 is doing? how did you arrive at "c
It's the sum of numbers from pref+1 to N.
@@Errichto Oh, that explains it. But why did you check the sum of suffixes here? also, isn't that n*(n+1)/2 - pref*(pref+1)/2 ?
Sorry if I have misunderstood...
*Google code jam qualifiers exists for 40 minutes
*Le Errichto: Lets do it in 20 minutes or 30 minutes.
It took me 10 hours+ to solve first 3 problems,
3rd problem only passed the test case 1. Was excited enough to get 31 points, just enough to qualify for next round.
I wrote mostly brute force solutions to all 3 problems.
Guess, back to drawing board now.
Glad to see you took atleast 10 mins for problem 3. 😊
At the third problem with the Reverse Sort you just leave me breathless. Where do you get those formulas from ? What's the thought process behind ?
Same dude, I spent hours trying to find some pattern in the output and all. I brute forced the first test for 7 points but the actual solution I still dont understand.
you can derive the soultion of 3rd problem from 1st just think in reverse manner
@@abhishek.rathore Same here dude. I derived the conditions for the IMPOSSIBLE test cases but couldn't figure how to solve for test set 2.
Reverse Sort formula is pretty common in C++ (in Competitive Programming). STL comes in handy in CP.
@@prakash_77 yea same
Thanks Errichto ❤️
You got WA on the last test case of 2nd questions. why is it?
It was a mistake to initialize dp values as 0. My program thinks it's allowed to get score from s[-1] to s[0].
Sir , from where you learned programming ,I know and understand python but not able to create codes and solve problems like these
Why am I getting previous video as private ? Btw nice Round ...Was able to solve 3 :)
Keyboard sounds great, mind sharing the brand and model? Thank you.
it's an old model - Logitech UltraX Premium. You would need to hunt a used one in good shape.
I also qualified this time. See you in round 1A
I have a doubt on the code above it what is the use of it bro please say
I've been following Errichto's brilliance for some time now, and I finally decided to give Geany a try: how do I get it to pick up KDE plasma theme settings? The app stays light even though I can change the editing & terminal windows to a dark mode (downloaded configs from github). Kamil, you're an inspiration!
I think you need to download geany themes seperately.
@@organic2976 thanks. I have dark themes for the editing window, e.g., but I want the entire app to be dark mode windows. Haven't found out how to do that yet, but I believe it's possible.
You need to download the monokai theme.
Read more here github.com/Errichto/youtube/wiki/Linux-&-Geany-Setup
@@Errichto thanks!
What board are you using for writing? I see it's OneNote but there is no official OneNote app on Ubuntu
Ubuntu is just a virtual machine so I can still run OneNote from the main OS, which is Windows.
@@Errichto Oh ok great, makes sense now, thanks!
por fin otras olimpiadas de programacion
I hope you get the first place 🥇
Can you tell me which digital writing pad do you use? And does it help in programming?
You mean a drawing tablet? Something from Wacom. It doesn't help in programming though.
Read more about my hardware here github.com/Errichto/youtube/wiki/FAQ#hardware
Wow live commentary and still getting a high rank ure so cool, meanwhile me getting rank 4600 :(
That median sort was real beast
...
Brother round 1 is also live ??
Excuse me sir, but which company Keyboard do you use?? Tempted to ask this question :D
Logitech keyboard, u can read his FAQ
can you create link for your codes???
These probability problems are beautiful, hope I get good at them. Was able to solve first 4. Also why no future Kamil?
Because the current Kamil was talking while solving problems ;)
There is future Kamil if I past Kamil doesn't talk.
@@Errichto sad to see you fail B though, you had a really good rank before that.
This guy is good at this.
Please upload a beginner's guide.
Really wanted to get into this.
See my "how to start Competitive Programming" video ua-cam.com/video/xAeiXy8-9Y8/v-deo.html
@@Errichto I have already watched that video you uploaded an year ago.
I just wanted you to upload a beginner's guide 2021.
@@Errichto A lot has changed till then.
Unbelievable speed...
can someone explain the prompt....
For median sort I tried to insert every element into the current(sorted) array. I found out the position of the new element using ternary search and just inserted it at that position. Using the median query you can easily determine which third of this array the new element should go to.
dude.i did the sameeee...it was one of the fastest solves i made apart from the no1..xD
Yeah, many people did O(N*log3(N)) with ternary search. I don't think it was expected to use O(N*log2(N)) merge sort with a good constant factor.
@@Errichto yep..even tho I solved it in less time , I got TLE in the hidden test case :'( so your solve was way optimized than mine :))
@@lfepped6474 I got all accepted though
@@shivangtiwari8694 i used cout and cin ..can that be the reason of TLE? i saw on codeforces that people suggest to use scanf and printf for interactive problems
It is unfortunate that you missed the extra in problem B but can you somehow explain how your code did not work? What did you missed?
He initialised last_c and last_j = 0 which is wrong. The simplest counter case is just a string of length 1, “?”. The answer should be 0 but his code will give the answer as minimum of (x, y, 0) which will be wrong if either of x or y is negative. This happens because assuming last_c and last_j to be 0 for empty string is wrong.
#include
using namespace std;
#define int long long
const int INF = 1e18L + 5;
void solve() {
int x, y;
cin >> x >> y;
string s;
cin >> s;
int n = (int) s.length();
if(n == 1) {
cout 0 ? min(pv_j, pv_c + x) : 0);
}
pv_c = cur_c, pv_j = cur_j;
}
cout t;
for (int tt = 1; tt
I have made the necessary changes to the code. Now it passes all the test case.
Or maybe I just wanted to get a nice score of 100 points out of 101 :D
@@Errichto That must be it! Hahaha
Fajny materiał
The codejam problems are worded so overcomplicated. It took me so long just to understand what the questions were asking. I barely slid through qualification round with minimum points.
I guess it's also a skill to read statements fast and skip unnecessary parts.
@@Errichto Actually, it takes time and experience to come with the skills you got. Investing time in them at the beginning of CP journey will come out to be fruitful later.
I thought that there are only 4 problems in Codejam😂. I was counting total and total didn't match with 101 points still I thought that the remaining points are due to some more hidden test cases. Lol. (btw this was my first-time participation. I will be cautious next time)Thanks for letting me know there were total 5 problems😁
Their UI is pretty bad recently, it's easy to miss the last problem :(
Which ide did Errichto used in this vedio?
Hi in one of the videos he said it is geany
thanks a lot😃
You're Most Welcome!!
Can someone tell me which Linux he is using??
Which keyboard brother?
Logitech UltraX Premium
What you missed in problem B for hidden test cases ???
It was a mistake to initialize dp values as 0. My program thinks it's allowed to get score from s[-1] to s[0].
Why does he use scanf and printf in cpp
Problem E was so weird. Never seen something like that on Codeforces or atcoder. The rest of the problems were cool.
It's more common in ICPC and GCJ.
@@Errichto Ok......time to expand my training horizon then.
what kind of sorcery is this !!!🤯🤯
Why don't I see him on the leaderboard
Haha seriously. Just how did you guys get so good at programming (problem solving)
terminals??
Finally
🤘
nice sub indo thans sir!
Sorry! :( Your rank slipped from 7 to 437 because of "Moons and Umbrella". We all support you!
100/101 is still a good score, I think :)
@@Errichto Totally agreed! Best of luck for rest of the competition!
you are genius i am struggling to understand this
import math
import sys
for line in sys.stdin:
line.strip()
n=int(line.strip())
for i in range(1,n+1):
if i % 3==0: and i % 5==0:
print("FizzBuzz")
elif i % 3==0:
print("Fizz")
elif i % 5==0:
print("Buzz")
else:
print(i)
def Books(l):
for j in range(1,10**5):
l=([i,i+1,i+2,i+3,i+4,i+5,i+6,i+7])
print(len(l))
if l[0]==i:
print(l[0])
return bool("True")
else:
return bool("False")
I have qualified in it I am happy hope I will win the code jam title this year 😁😁
nice boi atb!
👍🏻
Theres an algo named Median of 5 medians that should help on the problem
I'm glad you're not my teacher, because I am barely understand what were you talking about.
cool
The first 3 Ques were easy to understand but it was codejam so I was like this couldn`t be this easy. I definitely read it wrong or I am missing something.
Or you're better than you think :)
Very nice Errichto!!! Thanks for sharing your thoughts!
Amazing! :D
It's nice that you got the formula: n * (n + 1) / 2 - 1
for problem C.
I need to learn how to find those ...
Sum of arithmetic series.
Niceeeaaa
Hi teacher
Can you elaborate Q.1 plzz
Which part? That problem just requires direct implementation of whatever is written in the statement.
@@Errichto yes I tried to solve it with that but I wasn't able to pass the test cases
Passbook
Canadian guy finished this in less than an hr jesus
World's greatest programmer, after tourist and me; :D ;)
I will take third place, thanks.
Second!