Randomized algorithms lecture #2 - birthday paradox, random shuffle, hashing

Part 2 of Randomized algorithms in Competitive Programming. First part: • Randomized algorithms ...
Codeforces blog with mentioned problems: codeforces.com...
Blog about max element problem: codeforces.com...
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
- Frequently Asked Questions: github.com/Err...
- Github repository: github.com/Err...
- KZbin channel 1: / errichto (lectures and single problems)
- KZbin channel 2: / errichto2 (streams)
- Competitive Programming Discord: discordapp.com...
Solution for last mentioned problem: you can estimate the value of PI by generating random points and counting those inside a circle. This way you will estimate the area of a circle. It's called Monte Carlo method, www.google.com...

[@tejassardana6266]

I am a simple man, when Errichto posts something I smash likes before seeing it.

[@Errichto]

Just don't unmark it after watching the video :D

[@anktrj]

@@Errichto lol

[@musicfan1695]

@@Errichto hahahaha

[@aparichitsingh384]

can you please prepare a lecture on Convex Hull trick and other DP optimizations?

[@coder3101]

Liked even before watching completely. It will be good i know.

[@shrad6611]

same

[@nandagopalnaskar2452]

Same

[@NM-se5ql]

Thanks for making the videos man ! You're awesome keep going your videos get better every day :))

[@MahbubAlam-ey7nz]

bro , you are my idol. i just want to hug you brother you are my inspiration. love you brother.

[@karenmkrtumyan6902]

Cool. Thanks. The only thing was that I paused the video to think about the problem, and then found out I was solving a wrong one :D

[@AndreOliveira7051]

In the Repeated Binary Search problem, why is the probability that the i-th element is the greatest so far equal to 1/i? If we know that the greatest element so far is X, then (assuming that the elements are uniformly distributed in the interval 1 to 10^18) the probability that the next element is the greatest so far is (10^18 - X) / (10^18) (i.e. the probability that a random number from 1 to 10^18 is greater than X), no?

[@kovalvictor]

12:51 - seems a typo: N^N is 27 for 3, not 9, isn't?

[@gauravsinghal516]

Can you please make a video related to bitmask dp. Thanks in advance !!

[@Andravitar]

Hey Errichto i wanna ask you if you could make a video explianing the tools you are using (starting with Windows, Linux or MAC; and then supposing that the language used is c++, what tool you use for writing code (visual code, eclipse etc) and something like that). It really surprises me how fast do you execute tests from topcoder, for example. Pd: I really like your videos, it inspire me to get better and better on maths and also into become a software engineer. Keep it up!

[@Errichto]

I will do that at least for Linux in December, maybe Windows version too.

[@chewchew8787]

hey errichto,can you also do a lecture on dfs and bfs,or just algorithms related to graph theory

[@olliert4840]

Question for the first part: in math, "random" doesn't necessarily imply uniform distribution as you seem to assume for the first bit, so my question is: if you see a similar problem like that on codeforces/wherever that talks about something being random, is it safe to assume that (e.g. pokemon) are distributed uniformly? aka every type has a 1/n chance for each pokemon. Thanks, love the videos =)

[@Errichto]

Yes, I mean uniform distribution.

[@thaddeusokafor2953]

I'm enjoying this. 🤗

[@TomerBenDavid]

Splendid 👌 more theoretical videos please

[@angiras07]

how can i learn all the necessary algorithms used for competitive codings and can you please give some tips to increase my speed while writing code

[@Errichto]

1) Solve problems and read editorials/tutorials. 2) google -> practice fast typing

[@angiras07]

@@Errichto thanks is it enough

[@nandagopalnaskar2452]

Thank you errichto

[@vadym5245]

It's 27, not 9

[@Errichto]

Damn :|

[@sadunozer2241]

Awesome stuff

[@abhishekprakash23]

Yay another one

[@kevaldave4101]

Please make video on graph theory

[@blackpilledbuddha4944]

i have a question ...can i get into competitive programming and have a chancet winning if say that I am poor in math?

[@Errichto]

I don't think it's possible to win contests without a strong math background BUT yes, you can participate and get decent results.

[@nbharaths]

Shouldnt it be j = i + rand() % (n-i) ?

[@juanignaciodiaz28]

As he explained in the video the idea behind the algorithm is that at any point during the loop the prefix is shuffled. Look up mathematical induction for a better understanding of his proof

[@AceHardy]

🎉🎂🎈

[@desantbucie]

Epickie

[@tsimtsima172]

Please make a video about 2-SAT problems.

[@Errichto]

Nah, it's something very specific and not often useful. I have tons of other topics to cover first. Thanks for a suggestion though ;)

[@chang4938]

Are you part of the Mensa(the high IQ society)? I know you spent a lot of time doing competitive programming, but you must have a very high IQ to be that good at solving these coding questions.

[@Errichto]

Mensa test measures problem/puzzle-solving ability so I would likely be able to get there, but why would I pay 50$ a year just for being there?

[@sunils9183]

Can you please make video of Solving Google FooBar Coding Challenge from Level 1 to Level 5.

[@Errichto]

I think the point of that challenge is that you shouldn't know the solution first ;p

[@sunils9183]

#Errichto No, that’s not the case, it’s ongoing game. Solve & move, it’s fully random don’t have any constraints that you know or don’t know solution at all.

[@sunils9183]

Errichto I’m interested into learning how you might make strategic thinking and approach towards each problems, so that I’ll get inspiration from you. Can I learn professional problem solving skills from you. It’s great if you teaching and improving my life.

[@Errichto]

@@sunils9183 I did a lot of videos solving problems, including those from contests.