In the ACTG problem, I focused on the number of queries and forgot about the running time. Let's say the time limit is huge, like 50 seconds :D And the constraint for a[i] in GCD problem is actually 10^12, not 10^5.

@sajalagrawal1430

4 жыл бұрын

Thanks

@shivamnegi7848

4 жыл бұрын

Informative video Looking forward for more of this kind of stuff.

@Rahulpal-xq2hu

4 жыл бұрын

When will you post next video on dynamic programming..eagerly waiting for that..

@masternobody1896

4 жыл бұрын

Can you show me how to make a game in python or anything

@yoda6994

4 жыл бұрын

It will be great if you can cover problems related to probability/expected values in your future videos. Thanks for such great explanation.

i absolutely adore randomized algorithm! Thanks Errichto!

I always wanted a tutorial on randomized algorithms. Thank You

Thank you so much for your videos. Please keep making videos. You are helping out a lot of people. Cheers !!

Thank you, Kamil! I liked the video a lot and I'm looking forward the next part of the lecture! :)

thanks very much Errichto.Hope you reach out to a larger audience.

Thank you Errichto!

Quality stuff. Thank you very much.

Very interesting lecture Keep it up!

as always a great video please make more such edu videos. Thank you for your time and effort.

Hey amazing video scholar!!

fantastic !

Hi, is there a catalog of good problems to learn & solve , any reference ?

I took a whole grad course on randomized algorithms and all I learned was chebyshev, this is much better!

Recently bumped into a question which says to write a function which generates random numbers within a given range, provided I can't use any pre-defined function or any functions defined within any third party packages.Any suggestion on how to do it..?

For Line through N/4 problem, do we check for each ~200 pair of points the number of points on the same line? So O(200n) = O(n) and take the line with maximum number of points?

@Errichto

4 жыл бұрын

Yes, exactly that.

Can you talk about the Simulated annealing next time?

19:45 seemed like you are talking about reverse engineering a trading algorithm

6:33 Can you explain how you found the complexity so fast? i don't understand where n^2 pair come from

@admar3387

4 жыл бұрын

Zenen Hornstein the algorithm goes through every point and checks with every other point so n^2

at 14:49 after the observation of skipping last character ,isn't it should be (1 + 2 + 3 )/3 instead of (1 + 2 + 3 + 3)/4 as we have skipped last char and maximum query we gonna ask is 3 ? please reply...

@so7am96

4 жыл бұрын

I have the same question

@Errichto

4 жыл бұрын

That's a good question. It isn't correct to say that there are three equally likely possibilities. There are four. It's just that two of them give the same result (number of queries). Imagine that you take a 6-sided die and change one number from 6 to 5. The expected value of pipes you get is now (1+2+3+4+5+5)/6. There are still six possibilities, you just change one of their outcomes. Let's say you go with order CATG. There are four possibilities which character is hidden: A, C, T, G. You need 2, 1, 3, 3 queries, respectively.

For problem ACTG , we can find answer in 2*N+2 queries without random.

@Errichto

4 жыл бұрын

I don't see how to do it deterministically. Can you elaborate? 3*N is easy (just ask about A, C, T) but how to improve it?

Sir but every time coin is tossed probability is 1/2 , does not depends on previous toss , so repeating is not sure

Just wanted a suggestion from you: Would you change your entire approach towards a question if you don't get the correct solution (even when you know there is a slight change required) or try to find that small mistake when in a competition?

@shashwat_hai9164

4 жыл бұрын

What would you prefer a new start or making minor changes in your current approach?

@Errichto

4 жыл бұрын

I will first try to find a mistake. If I can't do it for a long time and the code is short, then I would rewrite it.

Hi, I'm so glad to see you do what you're doing and I want you do very well so excuse me for this unsolicited advice: Maybe it would help you to go to a voice coach, or an average logopeda ;) ? I know it helped me a lot and it would give you a boost not just on youtube, it gave my Charisma +3. It's unbelievable how ppl want to listen to you and hang around you more if you hv a great command of your voice.

@Errichto

4 жыл бұрын

Yes, I do plan that. The issue is lack of time :( similar thing with gym: I want to go there often but I'm lazy plus there are so many other things to do.

In problem 3 ( Given n points , find a line that passes through max possible of them ) , can we say if we select a pair of points , they have probability atleast 1/16 that these pair of points will be in line that passes through maximum points . Now if we select another different pair of points , it will also have probability 1/16 for the same event . So , if we repeat the process 16 times , then probability will be 16*(1/16) , that at least one of these 16 pairs will be included in the line that passes through maximum points . This don't really seem right to me , can somebody please explain where i am going wrong ?

@amarnathprasad9986

3 жыл бұрын

Hey, it's been a year. I hope you've understood by now, but I'll leave an explanation should anyone else face the same doubt in the future. You have to multiply the probabilities (1/16) and (1/16) and not add them. That's why, if you repeat the selection 16 times, the probability will be (1/16)^16 and not 16*(1/16). That's because they are independent and separate events.

In the problem selection of 1st point probability is 4/16 = 1/4 while selection of other point will be 15/16. So (1/4)*(15/16) will be equal to ~1/21. And not 1/16

in some sense it's very similar to the pigeon hole principal

can you make a tutorial video from scratch

@Errichto

4 жыл бұрын

This was a tutorial video from scratch :|

can you please add donation button to your stream so we can help you to get more content like this. I hope many viewers want to help you

In YES/NO problems, you can use randomized algorithm! With 50% chance print YES in other cases print NO.

toss a coin to your witcher

I am engineer. I cant wait to show those methods to my pure mathematic friend! I hope not kill his self :D