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/entry/71097
Blog about max element problem: codeforces.com/blog/entry/62602
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
- Frequently Asked Questions: github.com/Errichto/youtube/w...
- Github repository: github.com/Errichto/youtube
- KZread channel 1: / errichto (lectures and single problems)
- KZread channel 2: / errichto2 (streams)
- Competitive Programming Discord: discordapp.com/invite/UzaURu7
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/search?sxsrf=A...

Пікірлер: 46

  • @tejassardana6266
    @tejassardana62664 жыл бұрын

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

  • @Errichto

    @Errichto

    4 жыл бұрын

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

  • @anktrj

    @anktrj

    4 жыл бұрын

    @@Errichto lol

  • @musicfan1695

    @musicfan1695

    4 жыл бұрын

    @@Errichto hahahaha

  • @NM-se5ql
    @NM-se5ql4 жыл бұрын

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

  • @aparichitsingh384
    @aparichitsingh3844 жыл бұрын

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

  • @karenmkrtumyan6902
    @karenmkrtumyan69024 жыл бұрын

    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

  • @thaddeusokafor2953
    @thaddeusokafor29534 жыл бұрын

    I'm enjoying this. 🤗

  • @MahbubAlam-ey7nz
    @MahbubAlam-ey7nz4 жыл бұрын

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

  • @TomerBenDavid
    @TomerBenDavid4 жыл бұрын

    Splendid 👌 more theoretical videos please

  • @nandagopalnaskar2452
    @nandagopalnaskar24524 жыл бұрын

    Thank you errichto

  • @sadunozer2241
    @sadunozer22414 жыл бұрын

    Awesome stuff

  • @gauravsinghal516
    @gauravsinghal5164 жыл бұрын

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

  • @chewchew8787
    @chewchew87874 жыл бұрын

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

  • @coder3101
    @coder31014 жыл бұрын

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

  • @shrad6611

    @shrad6611

    4 жыл бұрын

    same

  • @nandagopalnaskar2452

    @nandagopalnaskar2452

    4 жыл бұрын

    Same

  • @AndreOliveira7051
    @AndreOliveira70514 жыл бұрын

    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?

  • @kevaldave4101
    @kevaldave41014 жыл бұрын

    Please make video on graph theory

  • @kovalvictor
    @kovalvictor4 жыл бұрын

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

  • @abhishekprakash23
    @abhishekprakash234 жыл бұрын

    Yay another one

  • @angiras07
    @angiras074 жыл бұрын

    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

    @Errichto

    4 жыл бұрын

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

  • @angiras07

    @angiras07

    4 жыл бұрын

    @@Errichto thanks is it enough

  • @Andravitar
    @Andravitar4 жыл бұрын

    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

    @Errichto

    4 жыл бұрын

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

  • @olliert4840
    @olliert48404 жыл бұрын

    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

    @Errichto

    4 жыл бұрын

    Yes, I mean uniform distribution.

  • @blackpilledbuddha4944
    @blackpilledbuddha49444 жыл бұрын

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

  • @Errichto

    @Errichto

    4 жыл бұрын

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

  • @desantbucie
    @desantbucie4 жыл бұрын

    Epickie

  • @AceHardy
    @AceHardy4 жыл бұрын

    🎉🎂🎈

  • @nbharaths
    @nbharaths4 жыл бұрын

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

  • @juanignaciodiaz28

    @juanignaciodiaz28

    3 жыл бұрын

    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

  • @vadym5245
    @vadym52454 жыл бұрын

    It's 27, not 9

  • @Errichto

    @Errichto

    4 жыл бұрын

    Damn :|

  • @tsimtsima172
    @tsimtsima1724 жыл бұрын

    Please make a video about 2-SAT problems.

  • @Errichto

    @Errichto

    4 жыл бұрын

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

  • @sunils9183
    @sunils91834 жыл бұрын

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

  • @Errichto

    @Errichto

    4 жыл бұрын

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

  • @sunils9183

    @sunils9183

    4 жыл бұрын

    #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

    @sunils9183

    4 жыл бұрын

    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

    @Errichto

    4 жыл бұрын

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

  • @chang4938
    @chang49384 жыл бұрын

    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

    @Errichto

    4 жыл бұрын

    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?