Your videos help me understand concepts so much! Your videos (lecture/livestream) on Binary Search were perfect. Also this video! Keep it up. Thank you.
You are just amazing. What I like the most about him is that he knows a ton of things and still he is so humble. This video was very informative. Also, thanks for putting in so much effort to create a wonderful contest. Looking forward to more such amazing content from you. #ErrichtoIsTheBest.
Amazing Video. Please, keep on adding video like these. It motivates us a lot and we get to learn much more than we could with your awesome explanation!
keep the good stuff like this bro .. i like the style of this [contest + explaination + tutorial] your way to teach is very nice .. i wish to teach every topic you know 😍
Sorry if the question is too dumb but in the last complexity analysis, you have a for(int i =0; i < N; i++). So the complexity should not be at least O(N)? I know O(log N) is the correct answer, but I can't understand why.
If something is solvable in constant space with dp (of the form new_dp[j] += dp[i] * m[i][j]), usually we can do matrix exponentiation to move from O(n) to O(log(n)).
Very nice explanation ..Feeling happy after learn something new .great work thanks Errichto . Can you please create video on flow in graph(like Dinic's algo, bipartite) . i found it difficult to understand .
Hi Errichto! Surely the algorithm with the best complexity for finding the nth fibonacci number is simply a modified version of Binet's Formula (Fib(n) = round(pow(phi, n) / sqrt(5)))? This would work in lower time complexity, no? (Nonetheless, the link between matrix exponentiation and Fibonnaci is very interesting)
you will not get the exact value because of precision errors and matrix exponentiation allows to compute n-th term of arbitrary linear recurrence, like f[i] = 2*f[i-1] + 5*f[i-2] or something much more complicated, see the third last problem in CF training contest
Hello Errichto. Currently i'm solving medium level dp problems and it seems too difficult for me. Can you please explain how to reach to the solution of medium and hard level dp problems. Thanks in advance! :)
Hey errichto will you please do videos of kickstart round D question C and D @errichto there are not good resources for these it will be very helpful 😊 thanks in advance
i got somewhat confused between iterative dp and matrix exponentiation at the end u were doing iterative dp, was that the logN time code we get the logN time because of using matrix exponentiation ryt? so why find intermediate states using DP is it possible by directly multiplying the BASE matrix to find the Nth state?
here's a secret reason: I'm in my family town for one week and can't make any youtube content :D and I think that some people will appreciate a week to solve that many problems
The mood changes with probability 'pp' every second, let p(i) - p-ability that he is happy after i-th second p[0] = 1; p[1] = p[0] * (1 - pp) + (1 - p[0]) * pp; p[2] = p[1] * (1 - pp) + (1 - p[1]) * pp; Your p[2] has different statement that this. Why is 'pp' not constant?
He has used, p = p*(1-p) + (1-p)*p = 2p - 2p^2 And if you write p[4] in terms of p[2] then you would get, p[4] = p[2]*[1-(2p-2p^2)] + ... So you can get idea from here why he has done that
@@darshitnasit3130 My question is a bit different. I want to know why p, as mentioned in the video, is changing when it says that the mood changes by p every minute. Why is p changing then? Every minute, the mood changes by p, but not p.
@@Ashish-dn1sc If you are computing P[1], P[2], P[3], P[4], P[5], ... than, yeah you are right there is no need to change p. But in matrix exponentiation you try to count P[1], P[2], P[4], P[8], P[16], ... [ not exactly, but you can assume that it works this way]. So if you have P[i] and you are directly moving to P[2*i] instead of P[i+1] than you have to update your p somehow.
so when I watch UA-camrs do programming problems on leetcode or hackerank , from the constraints or sample space they can already tell if say brute force will be fine or if n^3 wouldn't be too much, how? is there like rough calculation to know the average time or what?
ua-cam.com/video/eMXNWcbw75E/v-deo.html At this time, why are we comparing p[4] with p[2] ? based on what I understood, there is a recurrence between p[i] and p[i-1]. so, p[4] = p[3] * (1-p[3]) + (1-p[3]) * p[3]; Shouldn't this be written instead of p[2] ? I am confused, can someone please help me ?
I have a general question on this: Can we also try something similar with 3 branches and keeping 3 as base? If we change a number as base 3, and then apply same logic ? would that work? we need to divide b by 3 instead 2. What are the implications of this approach? In general I think log N base 2 will be higher than log N base 3 then we we do not explore 3 ? Any specific reasons?
Generally to get the product of two squre-matrices of size k it takes O(k**3) time, because for every row in the matrix you have to choose every column in the second matrix and then find the dot product of these two vectors namely the row that you selected in the first place and also the column that you have selected. Thus O(k**3) time.
Hey! Brother, can you please make a video on the below problem? PLEASE Digit Pairs Problem Description Given N three-digit numbers, your task is to find bit score of all N numbers and then print the number of pairs possible based on these calculated bit score. 1. Rule for calculating bit score from three digit number: From the 3-digit number, · extract largest digit and multiply by 11 then · extract smallest digit multiply by 7 then · add both the result for getting bit pairs. Note: - Bit score should be of 2-digits, if above results in a 3-digit bit score, simply ignore most significant digit. Consider following examples: Say, number is 286 Largest digit is 8 and smallest digit is 2 So, 8*11+2*7 =102 so ignore most significant bit , So bit score = 02. Say, Number is 123 Largest digit is 3 and smallest digit is 1 So, 3*11+7*1=40, so bit score is 40. 2. Rules for making pairs from above calculated bit scores Condition for making pairs are · Both bit scores should be in either odd position or even position to be eligible to form a pair. · Pairs can be only made if most significant digit are same and at most two pair can be made for a given significant digit. Constraints N
:o what a coincidence! I did a video about the same topic and came out almost at the same time :P (I recorded it 2 weeks before but I procastinated the editing, so it ended coming out after this)
And this one too... Problem Description A big group of students, starting a long journey on different set of vehicles need to fill petrol in their vehicles. As group leader you are required to minimize the time they spend at the petrol pump to start the journey at the earliest. You will be given the quantity of petrol (in litres) that can be filled in each vehicle. There are two petrol vending machines at the petrol pump. You need to arrange the vehicles in such a way that they take shortest possible time to fill all the vehicles and provide the time taken in seconds as output. Machine vends petrol @ 1litre/second. Assume that there is no time lost between switching vehicles to start filling petrol. Constraints 1
2N friends (A, B, C ... 2N) are standing in a circle. There is exactly one person standing opposite of one other person. Some of them are facing inwards and some of them are facing outwards. Here given some facts your task is to build the standing positions and answer a few Questions. If the arrangement is not possible or more than one arrangement is possible, then print ARRANGEMENT NOT POSSIBLE The formats of Facts & Questions and its meanings are as follows. Facts : 1AB means : A and B are standing adjacent to each other 2AB means : A and B are standing opposite to each other 3AB means : A is standing to the immediate left of B 4AB means : A is standing to the immediate right of B 5A means : A is facing inwards 6A means : A is facing outwards 7n means : n people are facing inwards, where n is a number 8n means : n people are facing outwards, where n is a number Questions: ?2A means : who is standing opposite of A? ?3A means : who is standing to the immediate left of A? ?4A means : who is standing to the immediate right of A? ?5A means : is A facing inwards? Ans: Y/N ?6A means : is A facing outwards? Ans: Y/N Constraints 1 < N < 10 1 < Total Facts < 30 1 < Total Questions < 20 Input Format First line contains N Then multiple facts, separated by semicolon Then multiple questions, separated by semicolon Output Answers, separated by semicolon corresponding to order of questions OR ARRANGEMENT NOT POSSIBLE Example Input 1 2 2AB;72;1AC;6D;4BD;6C ?2D;?3C;?4B;?5A;?6B Output C;B;D;Y;N Explanation 4 people- A, B, C and D are standing in circle. There are 6 facts separated in semicolons: 2AB ==> A and B are standing opposite 72 ==> 2 people are facing inwards 1AC ==> A and C are standing nearby 6D ==> D is facing outwards 4BD ==> B is standing immediate right of D 6C ==> C is facing outwards From the above facts, we can build the standing positions as below image: There are 5 questions: ?2D ==> who is standing opposite of D? Ans: C ?3C ==> who is standing immediate left of C? Ans: B ?4B ==> who is standing immediate right of B? Ans: D ?5A ==> is A facing inwards? Ans: Y ?6B ==> is B facing outwards? Ans: N Finally printing all answers in a single line separated by semicolon. Example Input 2 4BA;3CA;3CD;5C;5B ?5A;?3D;?4C;?6B Output ARRANGEMENT NOT POSSIBLE Explanation We can arrange 4 people in two different ways as the image below, from the facts provided. Directions of A and D can be set differently.
OK. I got it.
If I am happy and I watch videos from Errichto, I will be happy.
If I am sad and I watch videos from Errichto, I will be happy.
Yeah. This is true for real. I watched this video and successfully solved the problem A.
One of the most important insights from the lecture: "Matrix exponentiation is a tool to speed up the dp with constant space"!
Exactly!
For problem A, You can also find probability at time n using below formula
P(n) = 0.5*(1+(1-2p)^n)
Thanks! Yes, this problem can indeed be done with a better understanding of combinatorics.
can u plz explain it?
tks in advance!
I think you used the binomial theorem to count only the even occurences of switches but how did u come up with the formula?!!!
Is this formula derived using principle of inclusion and exclusion?
Drop the explanation bro!111!1 this shit's givin me a headache
Your videos help me understand concepts so much! Your videos (lecture/livestream) on Binary Search were perfect. Also this video!
Keep it up. Thank you.
You are just amazing. What I like the most about him is that he knows a ton of things and still he is so humble. This video was very informative. Also, thanks for putting in so much effort to create a wonderful contest. Looking forward to more such amazing content from you. #ErrichtoIsTheBest.
Really like the concept, lecture in video and problems to practice in ordered manner. Good for beginner and maybe intermediate ones also
:)
Welcome Errichto Once again. Hope you are well refreshed now.
Hoping for some nice series of topics from now onwards.
Thanks.
He you troll 😂
Errichto keep making good stuffs like this because there are many people who can teach basics but rare people like u who can teach these things.
Thanks Errichto sir for training problems and concept videos.
Can you make a tutorial on NTT, FFT. There is no video on youtube explaining it and it's very hard to understand it from cp blogs.
Amazing Video.
Please, keep on adding video like these. It motivates us a lot and we get to learn much more than we could with your awesome explanation!
there are few guys in cp who really enjoys sharing knowledge. He is one of them.
omg after so long time....are u planning some stream anytime soon?
maybe the end of July ;)
You know a lot! We Brazilians love your videos, keep it up ...
keep the good stuff like this bro .. i like the style of this [contest + explaination + tutorial]
your way to teach is very nice .. i wish to teach every topic you know 😍
Really like this style, one lecture with homeworks!
Where were you for so many days?🤔
Good to see you back Sir 🙌🙌🙌
For the second problem, you could define a simple recursive function: f(0) = 1, f(n) = 13 f(n - 1) + 6 * 26^(n - 1). Solving this recurrence relation gives us f(n) = 13^(n - 1) (7 + 3 * 2^(n + 1))
Bro, please consider the 3 questions posted below... and make a video because your way of explaining and problem solving skills are awsome
wow,
great timing...
I was just searching for this
watching an Errichto video makes me happy whether I was happy or sad before
Sorry if the question is too dumb but in the last complexity analysis, you have a for(int i =0; i < N; i++). So the complexity should not be at least O(N)? I know O(log N) is the correct answer, but I can't understand why.
If something is solvable in constant space with dp (of the form new_dp[j] += dp[i] * m[i][j]), usually we can do matrix exponentiation to move from O(n) to O(log(n)).
This video is just legendary. Absolute genius.
Hey can we expect an Algo & Coding Stream anytime soon. The Atcoder Hard ones were really interesting.
in August
Thank you so much for organizing contest for practice! You are awesome!!!
Thanks Errichto! solving first four was really good ;)
Wow, i'm very surprised of how we can think of matrix exponentation even if we don't know matrices in math. This is very beautiful!
You are the GOAT dude.
Thanks for the awesome lectures string.reverse(limaK)!
great vid, eagerly waiting for Berlekamp-Massey
Awesome ❤️
Very nice explanation ..Feeling happy after learn something new .great work thanks Errichto . Can you please create video on flow in graph(like Dinic's algo, bipartite) . i found it difficult to understand .
Long Day No "C"
Hi Errichto! Surely the algorithm with the best complexity for finding the nth fibonacci number is simply a modified version of Binet's Formula (Fib(n) = round(pow(phi, n) / sqrt(5)))? This would work in lower time complexity, no? (Nonetheless, the link between matrix exponentiation and Fibonnaci is very interesting)
not when n is huge. You would have to use binary exponentiation again and complexity becomes logn
you will not get the exact value because of precision errors
and matrix exponentiation allows to compute n-th term of arbitrary linear recurrence, like f[i] = 2*f[i-1] + 5*f[i-2] or something much more complicated, see the third last problem in CF training contest
@@Errichto Ah, okay. Thank you very much for the clear explanation. Looking forward to the upcoming algo stream next month :)
Great explanations
Which editor do you use for Competive Programing .......???
Thanks for the wonderful lecture! :)
Hello Errichto.
Currently i'm solving medium level dp problems and it seems too difficult for me. Can you please explain how to reach to the solution of medium and hard level dp problems.
Thanks in advance! :)
Hey errichto will you please do videos of kickstart round D question C and D @errichto there are not good resources for these it will be very helpful 😊 thanks in advance
Can you make a video on how to solve constructive algorithm questions ??
i got somewhat confused between iterative dp and matrix exponentiation
at the end u were doing iterative dp, was that the logN time code
we get the logN time because of using matrix exponentiation ryt? so why find intermediate states using DP
is it possible by directly multiplying the BASE matrix to find the Nth state?
Are there more training contests you made for other topics?
Fantastic. Keep it up.
Thanks for the great video.
Could you tell me the name of the software you use to draw?
An important set of notes that will definitely help : drive.google.com/file/d/1nhL63QcjUiRm1pGGmzi1QHceKAGeBsRY/view.
My only concern "One week" is long. 3-4 days are enough for anyone (or may be for me) to give a full attempt to all the problems.
here's a secret reason: I'm in my family town for one week and can't make any youtube content :D
and I think that some people will appreciate a week to solve that many problems
Hi, please post Facebook Hackercup rounds. After each round is over, of course. Thanks!
thanks for the video!
Can u please make an editorial video for CodeChef July Long Challenge "WEIRDMUL" problem
You're amazing.
Please make a tutorial on time complexcity for beginners🙏🙏🙏🙏🙏🙏🙏🙏
will do :)
@@Errichto thanks 🙏🙏🙏🙏
please provide amazon link of the chair you've got
Legend
Thank you.
@Errichto Pls can you make geany and cygiwn set-up tutorial on windows?
thank you soooo much for what you are doing :D
Errichto lots of love from India and huge fan. We want a setup/room tour. Thank you for inspiring me!
Amazing
Can we solve tower of hanoi dp problem using this?
Can we really use matrix exponention in string mood updates problem only soln I can think of is O(nq)
The mood changes with probability 'pp' every second, let p(i) - p-ability that he is happy after i-th second
p[0] = 1;
p[1] = p[0] * (1 - pp) + (1 - p[0]) * pp;
p[2] = p[1] * (1 - pp) + (1 - p[1]) * pp; Your p[2] has different statement that this.
Why is 'pp' not constant?
He has used,
p = p*(1-p) + (1-p)*p = 2p - 2p^2
And if you write p[4] in terms of p[2] then you would get,
p[4] = p[2]*[1-(2p-2p^2)] + ...
So you can get idea from here why he has done that
@@darshitnasit3130 My question is a bit different. I want to know why p, as mentioned in the video, is changing when it says that the mood changes by p every minute. Why is p changing then? Every minute, the mood changes by p, but not p.
@@Ashish-dn1sc If you are computing P[1], P[2], P[3], P[4], P[5], ... than, yeah you are right there is no need to change p. But in matrix exponentiation you try to count P[1], P[2], P[4], P[8], P[16], ... [ not exactly, but you can assume that it works this way].
So if you have P[i] and you are directly moving to P[2*i] instead of P[i+1] than you have to update your p somehow.
Can you do the graph code explanation, i would really appreciate it
Thank you so much
so when I watch UA-camrs do programming problems on leetcode or hackerank , from the constraints or sample space they can already tell if say brute force will be fine or if n^3 wouldn't be too much, how? is there like rough calculation to know the average time or what?
Yeah it's called BigOh notation, you minimise the running time in tbe worst cases scenario.
Thank you😍
ua-cam.com/video/eMXNWcbw75E/v-deo.html
At this time, why are we comparing p[4] with p[2] ?
based on what I understood, there is a recurrence between p[i] and p[i-1].
so, p[4] = p[3] * (1-p[3]) + (1-p[3]) * p[3];
Shouldn't this be written instead of p[2] ? I am confused, can someone please help me ?
How do I register for the contest? I can't submit the problems
Found it by going into "gym", but it should be available from the direct link D:
@Errichto This comment should be pinned.
Nanana buenardo
Perfect !! 😇😇
💙
why u dont use vim?
why geany ?
said a person who has "xd" in name and pic
; :
why u bullying me
Man you're just awasome 😎😎😇✌🏻✌🏻✌🏻✌🏻
yyayayayayayayay another vid!!!
Can't like this video multiple times, youtube is so broken :(
I have a general question on this: Can we also try something similar with 3 branches and keeping 3 as base?
If we change a number as base 3, and then apply same logic ? would that work? we need to divide b by 3 instead 2. What are the implications of this approach?
In general I think log N base 2 will be higher than log N base 3 then we we do not explore 3 ? Any specific reasons?
Just realised Limak is the reverse of Kamil 🤯
😮
it says i need to register to submit, where to register??
Go to the homepage/contest page. You will find this contest,you have to register from there.
why do we need 3 loops? i dont get it why do we need the k loop in fibonacci question.
Generally to get the product of two squre-matrices of size k it takes O(k**3) time, because for every row in the matrix you have to choose every column in the second matrix and then find the dot product of these two vectors namely the row that you selected in the first place and also the column that you have selected. Thus O(k**3) time.
Hey! Brother, can you please make a video on the below problem? PLEASE
Digit Pairs
Problem Description
Given N three-digit numbers, your task is to find bit score of all N numbers and then print the number of pairs possible based on these calculated bit score.
1. Rule for calculating bit score from three digit number:
From the 3-digit number,
· extract largest digit and multiply by 11 then
· extract smallest digit multiply by 7 then
· add both the result for getting bit pairs.
Note: - Bit score should be of 2-digits, if above results in a 3-digit bit score, simply ignore most significant digit.
Consider following examples:
Say, number is 286
Largest digit is 8 and smallest digit is 2
So, 8*11+2*7 =102 so ignore most significant bit , So bit score = 02.
Say, Number is 123
Largest digit is 3 and smallest digit is 1
So, 3*11+7*1=40, so bit score is 40.
2. Rules for making pairs from above calculated bit scores
Condition for making pairs are
· Both bit scores should be in either odd position or even position to be eligible to form a pair.
· Pairs can be only made if most significant digit are same and at most two pair can be made for a given significant digit.
Constraints
N
Please do a video explaining how to approach hard problems
This tutorial is one such video.
Thank you sir.🙏🙏
31:01 I is not hard.. just precalc exponents and use a vector instead of a matrix and take values from the precalc. Cool tho
:o what a coincidence!
I did a video about the same topic and came out almost at the same time :P (I recorded it 2 weeks before but I procastinated the editing, so it ended coming out after this)
where's the flex, Errichto?
like what? :D
@@Errichto how you came up with matrix exponentiation yourself
hey @errichto
Should i learn data structure & algorithm first
or just try to do competitive programming?
Math sharp.
My IQ went up 10 points just by watching this video
And this one too...
Problem Description
A big group of students, starting a long journey on different set of vehicles need to fill petrol in their vehicles.
As group leader you are required to minimize the time they spend at the petrol pump to start the journey at the earliest. You will be given the quantity of petrol (in litres) that can be filled in each vehicle. There are two petrol vending machines at the petrol pump. You need to arrange the vehicles in such a way that they take shortest possible time to fill all the vehicles and provide the time taken in seconds as output. Machine vends petrol @ 1litre/second.
Assume that there is no time lost between switching vehicles to start filling petrol.
Constraints
1
hard
Need matrices in math
we can find nth fibonacci same fast than nth prime, but we can get is this prime faster than is this fibonacci LOL
ale, że limak to kamil od tyłu
2N friends (A, B, C ... 2N) are standing in a circle. There is exactly one person standing opposite of one other person. Some of them are facing inwards and some of them are facing outwards. Here given some facts your task is to build the standing positions and answer a few Questions. If the arrangement is not possible or more than one arrangement is possible, then print ARRANGEMENT NOT POSSIBLE
The formats of Facts & Questions and its meanings are as follows.
Facts
:
1AB means : A and B are standing adjacent to each other
2AB means : A and B are standing opposite to each other
3AB means : A is standing to the immediate left of B
4AB means : A is standing to the immediate right of B
5A means : A is facing inwards
6A means : A is facing outwards
7n means : n people are facing inwards, where n is a number
8n means : n people are facing outwards, where n is a number
Questions:
?2A means : who is standing opposite of A?
?3A means : who is standing to the immediate left of A?
?4A means : who is standing to the immediate right of A?
?5A means : is A facing inwards? Ans: Y/N
?6A means : is A facing outwards? Ans: Y/N
Constraints
1 < N < 10
1 < Total Facts < 30
1 < Total Questions < 20
Input Format
First line contains N
Then multiple facts, separated by semicolon
Then multiple questions, separated by semicolon
Output
Answers, separated by semicolon corresponding to order of questions OR ARRANGEMENT NOT POSSIBLE
Example Input 1
2
2AB;72;1AC;6D;4BD;6C
?2D;?3C;?4B;?5A;?6B
Output
C;B;D;Y;N
Explanation
4 people- A, B, C and D are standing in circle.
There are 6 facts separated in semicolons:
2AB ==> A and B are standing opposite
72 ==> 2 people are facing inwards
1AC ==> A and C are standing nearby
6D ==> D is facing outwards
4BD ==> B is standing immediate right of D
6C ==> C is facing outwards
From the above facts, we can build the standing positions as below image:
There are 5 questions:
?2D ==> who is standing opposite of D? Ans: C
?3C ==> who is standing immediate left of C? Ans: B
?4B ==> who is standing immediate right of B? Ans: D
?5A ==> is A facing inwards? Ans: Y
?6B ==> is B facing outwards? Ans: N
Finally printing all answers in a single line separated by semicolon.
Example Input
2
4BA;3CA;3CD;5C;5B
?5A;?3D;?4C;?6B
Output
ARRANGEMENT NOT POSSIBLE
Explanation
We can arrange 4 people in two different ways as the image below, from the facts provided. Directions of A and D can be set differently.
Did anyone else notice that Errichto looks uncannily similar to Tim Cook, CEO of Apple?
Give a thumbs up if you agree. :D