Intro to Competitive Programming
Ғылым және технология
Most interesting video ever created. I don't know what I mispronounced but I definitely mispronounced something. Also Junferno's face is not in this video as much due to him falling into a state of anguish mid-recording (he was busy).
Patreon: / junferno
Twitter: / junferno
Join the Discord: / discord
Secondary Discord invite if vanity invite expires: / discord
Check out my other stuff on GitHub: github.com/kevinjycui
Corrections:
- [Visual error at 6:02] "Ultrecht" should be Utrecht
- [Visual error at 10:32] Shortest path from A to C should be ADC, yielding a distance of 1+7=8, making the total distance from A to C to E: 8+12=20
Footnotes:
- Other prominent online judges similar to Codeforces/DMOJ include AtCoder, Leetcode (mostly technical interview-type questions), Codechef, and TopCoder. CSES is an online judge focused on a single problemset. Advent of Code is a Christmas-themed daily programming challenge run annually in December in which only the output of the test cases has to be submitted as opposed to the solution code. Google Foobar is a "secret" Google programming challenge meant to be a recruiting technique targeted towards Google Search users who use keywords related to coding.
- The technical term for a "network of nodes" is a "graph". Algorithms dealing with such graphs are categorised as graph theory algorithms. Nodes are connected by "edges" which may or may not have "weights". A directed graph is a graph in which the edges only go one way. An acyclic graph is a graph which contains no cycles.
- A queue is different from a list in that it is not indexable, but rather just serves the element at the top when polled. A priority queue serves the element with the highest priority (usually implemented with heap). It does not actually "sort itself" but the elements will come out "sorted". The queue is sometimes referred to as "a list" in this video. This is meant to mean a "sequence of elements" and not the "list" data structure that exists in some languages.
- The preferred language for most competitive programming is C++, though other languages are also used. Java, for example, is often used alongside a rewrite of the input reader class, as the built-in Scanner is too slow.
References: "For the absence of a bibliography I offer neither explanation nor apology." -- Edsger W. Dijkstra
Photos courtesy of Wikimedia Commons, GeeksForGeeks, DMOJ
DMOJ: dmoj.ca/
Codeforces: codeforces.com/
Single Source Shortest Path: dmoj.ca/problem/sssp
VM7WC '15 #4 Gold - Chain Rule: dmoj.ca/problem/vmss7wc15c4p3
Music tracklist:
• The Complete Junferno ...
Community Captions:
Portuguese (Brazil) - Guilherme BR
Пікірлер: 871
Corrections: - [Visual error at 6:02] "Ultrecht" should be Utrecht - [Visual error at 10:32] Shortest path from A to C should be ADC, yielding a distance of 1+7=8, making the total distance from A to C to E: 8+12=20
@Ammar813
Жыл бұрын
Oh yeah i have probably noticed
@chamberofhope
Жыл бұрын
Honestly to most people (me) half of the video sounds like radio noise only changing when you randomly mention some stupid joke that makes me spit my drink so I don't think you have to be that worried.
@peatral
Жыл бұрын
Also: A Priority Queue is not a list that sorts itself, it is a queue that always returns the element with the highest priority next (usually the lowest value in a list of numbers). As a matter of fact, PQs usually get implemented using a Min-Heap (which, by keeping the heap invariant true, has always the lowest element as its root). Important to understand is that a PQ is not a list but a queue (a First-In-First-Out data structure which makes it impossible to do index calls) and is not (fully) sorted but only gives back the element with the highest priority / lowest value. Of course you can easily implement it by sorting a list once an element has been added but that is usually not how it is done because the computational overhead it generates for the little (to no - in a PQ we don't care about any other element than the next) benefit it gives us. Operating on a large dataset this can significantly affect the performance. You based your explanation on your implementation and while the implementation of course works the explanation of a PQ is wrong. Just something I wanted to mention but other than that, nice video as always!
@Junferno
Жыл бұрын
@@peatral Thanks! Clarification footnoted.
@peatral
Жыл бұрын
@@Junferno Nice, that is a really good footnote!
He completely lost me when he started explaining that 2D array thing, but then he put Rei Evangelion in the video and completely won me over
@pierce9019
Жыл бұрын
2D arrays are great! 3D arrays are even more awesome. It's not as complicated as it seems.
@Purpial
Жыл бұрын
same
@kakyoindonut3213
Жыл бұрын
I like it when she appears and says her catchphrase "it's rein' time!" And fires a deadly rays of gamma radiation
@zyrgr2940
Жыл бұрын
@@kakyoindonut3213 hilarious and original
@QWERTY-gp8fd
Жыл бұрын
@@zyrgr2940 ironic
Can't believe I got baited into watching an informative video just because it had a picture of Misato on it
@UCmDBecUtbSafffpMEN3iscA
Жыл бұрын
Lmao same
@ryanlee9150
Жыл бұрын
omg did we really AHAHA 😭😭
@blast6190
Жыл бұрын
literally
@ritik1428
Жыл бұрын
we are all goofy ahh people
@10Diamonds
Жыл бұрын
you jus like me fr
This video should be renamed from "Intro to Competitive Programming" to "Overexplaining Dijkstra's Algorithm"
@eigenenvy9371
Жыл бұрын
The title and the content of the video together perfectly captures what it's like to be a first-year CS student.
@____-gy5mq
Жыл бұрын
you mean uniform cost search
@KaosFireMaker
Жыл бұрын
"Overexplaining Dutch Geography"
@prashantd6252
Жыл бұрын
He must be a fan of Neil Degrasse Tyson!
@Entropy67
Жыл бұрын
"Overexplaining ____________ Algorithm" = second/first year cs classes lmao
"this is a list of Kirby antagonists" ... "Stable marriage"
@elwan_
Жыл бұрын
Stable marriage, the biggest Kirby antagonist.
@beefax
Жыл бұрын
russian peasant
@kabliss4111
Жыл бұрын
Link cut tree.
@kabliss4111
Жыл бұрын
Or just Z
@jerebenitez8542
Жыл бұрын
@@kabliss4111 that sounds like a Zelda speedruning technique
They asked me how well I understood theoretical computer science. I said I had a theoretical degree in computer science. They said welcome aboard.
@kajxqeirscl
Жыл бұрын
lmao
@Justhappydog
Жыл бұрын
New vegas, love it!
@LunizIsGlacey
Жыл бұрын
A "theoretical degree" lol ha.
@jinanren2026
Жыл бұрын
u have a degree in theory huh, well that's professional enough! like, haggle your way out the coding interview, maybe!
@hithere640
Жыл бұрын
Newsflash: Fantastic is irreplaceable.
Competitive programmers realizing their entire livelihood consists of only inverting binary trees 💀
@arsenypogosov7206
Жыл бұрын
Never in my competitive life have I inverted binary trees
@LavaSaver
Жыл бұрын
@@arsenypogosov7206 You are in denial.
@zojaXII
Жыл бұрын
funny fast kirby man !
@austinscott4695
Жыл бұрын
Looks like you have never did competitive programming.
@bampo8436
Жыл бұрын
L
as a Dutch I'm impressed with the pronunciation of these dutch cities, given Dutch is next to impossible to pronounce.
@youreyesarebleeding1368
Жыл бұрын
Every time I hear it, it makes my mouth feel weird because i'm imagining a muscle spasm in the roof of my mouth
@776Mine
Жыл бұрын
just do the hard G and you’ve got the entire language down
@iXenox
Жыл бұрын
As a non Dutch I will disagree, others failings to pronounce something might be because the people you are using for examples are English. The english language kinda sucks for pronounciation.
@groetjesuitdehel
Жыл бұрын
@@unclassifiedsignal it is, we just learn to connect different sounds to the same letters.
@gabriel_ito8247
Жыл бұрын
And when ya used to it it takes ages to learn any other language ever
I like to imagine Jun got IP banned from CodeForces for playing Bad Apple on their verdict page
@aourt
Жыл бұрын
he probably did 💀
@PurpleSpiritFoxFire
Жыл бұрын
It was worth it tho😂😂
@arolimarcellinus8541
Жыл бұрын
wait....how can he playing bad apple in the verdict page?? is there any some system that we can use??
@PurpleSpiritFoxFire
Жыл бұрын
@@arolimarcellinus8541 I just say what i see and am not knowledgeable about playing bad apple on anything...i think he just makes each frame with rows of text that instead of pixels use characters to make the frame. You can probably see the code when he ctrl+v it in there.
@lucdombar4527
Жыл бұрын
@@PurpleSpiritFoxFire About what he show at the end, it's most probably just javascript on his client side, as the timestamps stay constant (and the update is too fast compared to the start update time). But that would probably just be for the gag at the end of the video and not the actual attempt that made him banned, as it don't send anything to the server
I love this kind of low-budget, high-humor videos also He explained it very intuitively
@abhijeetas7886
Жыл бұрын
there is something charming about videos made on a not so big budget. but with a lot of effort
@stain5570
5 ай бұрын
I also love no money high funny videos
i immediately love your videos more for taking a brief moment to list the cons of the VPN you used to counter the unintentional endorsement of non-sponsored product use.
@oreos3174
Жыл бұрын
me too, I actually paused to read them all
an evangelion themed competitive programming video made for me honestly
@nixel1324
Жыл бұрын
It even has Touhou music to match your profile pic!
@burnedpizzacrust1199
Жыл бұрын
@@nixel1324 who's on the profile pic?
@nixel1324
Жыл бұрын
@@burnedpizzacrust1199 Marisa Kirisame, probably the closest Touhou has to a central protagonist after Reimu.
I can't believe you tricked me into reliving my algorithms and data structures class
@Immadeus
Жыл бұрын
All it took was anime
I should have expected the end but it somehow took me by surprise
As someone who finished up algorithms as one of my final courses out of college, this would have been a great video to show to our class on Dijkstra's.
@snowman4933
Жыл бұрын
You do them in final course? Our mf prof. just taught us C and went straight to Narasimha Karaumachi's DSA book.
@Error_code_1001
Жыл бұрын
everyone would pay attention when the rei part would come on
0:29 I love how you translated this sentence to specifically Chinese Russian and Polish, this describes the top competition pretty well
6:51 the amount of whiplash between these two sentences is too much lmao. I love it
@alizzz255
Жыл бұрын
I was so lost at that point that I didn't even notice it lmao
@decksteroussnail
Жыл бұрын
Instead of the Gorilla Basket problem. This is the Programming Rei McDonalds problem.
7:45 When he started listing the algorithms, I was surprised by the amount of algorithms I never knew. Then I heard “Fecto Elfilis algorithm” and realized “wait.. that doesn’t sound right”
"This is a list of Kirby antagonists, actually." Three seconds earlier: "Stable Marriage"
Somehow the consistent Bad Apple endings manage to keep surprising me. I may have developed early-onset dementia since becoming a viewer.
I always wanted to learn about competitive programming! now i want to forget
"The other city in the netherlands" 😂😂 funniest way to avoid saying groningen
The entire explanation of the Dijkstra's algorithm was done in a way that maximized Jun's ability to flex his Dutch pronunciation.
Amazing pronunciation on everything, even "VM7WC".
My dad went to a very small university in Canada and was on the programming team They actually ended up going to the world championship in Hawaii and beat schools like MIT and Harvard I never knew much about how it actually worked so this was a very nice way for me to be able to appreciate his achievements a bit more He is still probably the smartest person I know Thank you for the great video
@gerrardandeminem
Жыл бұрын
He must be crazy smart cuz this is actually extremely intellectually difficult feet to accomplish
@isaac10231
Жыл бұрын
You should probably pick up programming you might have a gift for it too.
@khoiduongminh5111
9 ай бұрын
Is it Waterloo?
@jun9491
9 ай бұрын
@@khoiduongminh5111Waterloo isn’t small
Dickstroke's Algorithm was the thing that broke my brain when I tried to program it for my class and I didn't understand it before I came across this video. Now, after watching this video, I still don't understand it. Thanks, Junferno!
@themanthathasanninhisname2095
Жыл бұрын
Dickstroke's algorithm
@Jubinmail
Жыл бұрын
you were in the wrong class
Loving these videos. Hope you keep making more
I SHOULD HAVE EXPECTED "IT" AT THE END
firstly I would like to wish you well and to say a huge thank you for uploading these videos as they have been an invaluable resource to
I was on my university’s first real programming team. There were so few people interested that we didn’t even have to try out. We just volunteered and we were instantly on the team. We didn’t have enough time to learn all the relevant algorithms so my position on the team was to solve problems that nobody knew the algorithm for lol. I remember one of my ad hoc solutions being too slow for the judge so we wrote code that printed out a C array of the first 100 primes. Then we took that array and hardcoded it into the solution to reduce the final processing time.
Glad you managed to put Bad Apple in again. I felt it's abstinence in the last video. 10/10
Thanks for your easy to follow explanations, one step at a ti. It makes learning less overwhelming!
Your videos are quite often the highlight of my day
Wow this sure would've been helpful in my first ever competitive programming contest last week wow truly a crazy world am I right
I've been waiting for this kind of video for a really long time.
i understood less than usual and laughed more than usual, banger video thank you Junferno 🙏
As a competitive programming nerd who took part in the Sud West European Regional Contest for ICPC of last year (my team lost, since we're not Russian), I can attest that this video is truthful, and also that competitive programming is a great source of -frustration- satisfaction.
Currently preparing for British Informatics Olympiad this year, I open KZread and see new Junfero competitive programming video with anime woman in thumbnail, nice algorithms very cool
Great style. Excited to see your next video.
I love how your videos have the power of curing my depression even though I've literally never coded anything in my entire life
Very nice surprise to see my country in your vid. Your pronounciation is on point! Having been to all these places myself I guess I have to agree with you :D The dijkstra guy kinda reminds me of walter white for some reason
Cool video! Honestly learning all the graph + sorting algorithms seems fun
How is He putting so much information into my brain so fast. This video is 12 minutes long, and I feel like I've watched 1 hour long video essay.
First time to your channel and I accidentally got an explanation of the Dijkstra's algorithm. Came for the thumbnail, stayed for the informative tutorial (can I call it a tutorial though?). Anw, thank you and can't wait to see more videos like this.
now im a god thank you junferno
I didn’t really understand this video when it first came out but now but now it finally makes some sort of sense. I was learning about weighted graphs in data structures and algorithms today and instantly remembered this video
New favorite channel. Delivery is art
Loved your dedication! Nice video!
This was funny af, subscribed !
BROTHER, YOU ARE THE BEST!!! You oooh really helped me!! THANK YOU VERY MUCH!
Less go, new junferno vid
Not sure what Misato has to do with this but I’m glad she’s here regardless
This is so well made!
great video, can't wait to come back to it in two weeks when my professor finally teaches us about djikstra's algorithm
Before the video, I didn't know anything about competitive programming. Now that I've watched this, it's just as before. Thanks for explaining.
@bent3942
8 ай бұрын
Yep 100% agree.
love this channel
HAHAHAHAHA I laughed a lot when you started showing the algorithm names, good video!
holy shit new junferno video
You have my highest respect I love the style
that dijkstra example is exactly how my professor explained it (at utrecht university no less)
Hey! Thanks so much for this video!
I am fuckin SCREAMING at the ending, Juneferno strikes again
Damn, I loved the way this vid was put was together subbed XD
I just want to say that I love your content.
the final problem reminds me of that way of decrypting a decryption key with only one one pair of encrypted/decrypted messages. instead of randomly guessing 100 different consecutive decryptions (a already encrypted encryption is recrypted several times to increase security) in order to find the proper decryption key, one can instead guess 50 decryptions on the encrypted message and do 50 reverse encryptions on the decrypted message and meet in the middle and compare all of the different half decrypted keys and see which ones match. Because the time needed to break an encryption increases exponentially with every layer of encryption, decreasing the time needed from t^100 to 2*t^50 where t is the time to guess a single layer of decryption is an extremely effective method. Thus, it is also extremely hard to have 2 middle points instead of 1 because there is no secure launching point to 'save progress'.
I am very glad that I stumbled upon your video
This was interesting and very funny, good job Junferno! As Captian Falcon would say, "I lika ya moves!"
Your pronunciation is... Excellent. Very respectful to learn it!
I clicked on your video because the thumbnail has to be the most eye catching thing ever. What does misato have to do with competitive programming? I‘ve seen it now and I am unable to turn down my urge to get an answer for the question. Props to that. Genius.
I'll be totally honest here: really, the main reason I clicked on this video is because I saw Misato in the thumbnail _{Misato Katsuragi best Evangelion girl}_
brooo im 43 seconds in & im already dying of laughter lmaoo and having a good time , i had a terrible day today & obviously very stressed but your video changed that , subscribed !!(no brainer)
MY GOD THIS MELTY SOUNDTRACK SOLD YOUR VIDEO TO ME
cool video bro! keep it up!
I literally spaced out listening to flowering night. You really need to add more obscure touhou references.
Nice video, finally i can add in to my resume 10y competitive programing experience
God, I'm glad I found your video that helped me
I LOVE your videos
This was fantastic
i was worried there wasnt gonna be a bad apple this time. absolutely relieved
THANK YOU SO MUCH! ❤
Wow! I'm now motivated to become a competitive programmer with absolutely no skills in programming. Thank you for letting me see the other side of the window
your dedication to the bad apple meme is commendable
It's a good day when you see a Junferno upload
gettin hit straight outta the gate with eltnum's theme made me leave a like. gonna go watch the rest of the vid now
you really put Misato Katsuragi on the thumbnail and I clicked for that but stayed for the content.
HAHAHAHAHA instant subscribe, so well made videos kudos
"Intro to Competitive Programming" *Casually starts explaining Dijkstra's Algorithm
It was interesting to learn what Rei Evangelion would look like while working at McDonald’s. Very helpful and educational video, thanks!
Thank you for backdor
Wasn't planning on watching this video but the thumbnail won me over
10/10 great Dijkstra's lecture i learned a lot
Really nice and helpful... Thanks!
hanks lot Sir.. You helping us..
the best video i have ever watched
Much love
guess I'm going back into competitive programming dunno whether to thank or resent you lol. Vid is pretty good regardless 🔥🔥
That was great. Thank you.
You did prett well pronouncing those dutch cities. Definetly better that most non-dutch speakers.
Nice video 👍🏼
I really liked this explanation of Dijkstra.