I did it! I looked at your solution for the first one briefly before waiting some time and trying it, but still needed help. The second one I did mostly on my own, but needed help understanding how the graph worked. Third one took me an hour, but I did it entirely! Fantastic tool and fantastic video.
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.
here, if you want to calculate [dp1,dp2....dpn] values after 'K' identical transitions where each dp value has identical type of contribution to other dp values in all transitions, you will multiply this 1*n matrix m0 with Kth power of transition matrix. where transition matrix is a n*n matrix which has multiplication coefficients of each dpx value for each other dpx values. if some dpx has no effect on dpy, then multiplication coefficient is 0. It is easy to store m0 (initial state matrix) as 1*n matrix. In transition matrix(n*n), first column will be the coefficient factors A,B,C if dp0=A*dp0+B*dp1+C*dp2, 2nd col is D,E,F if dp1=D*dp0+E*dp1+F*dp2 and 3rd col is G,H,I if dp2=G*dp0+H*dp1+I*dp2 Matrix-Init (m0) (1*n) = [dp0 dp1 dp2] Matrix-transition (mx) (n*n)= [A D G] [B E H] [C F I] Answer = mx * (m0 ^ k) Be sure while implementing matrix multiplication, i,j,k (order is-i,j,k) loop variables are different than floyd warshall (which has order-k,i,j) This is for my own understanding, I needed to watch this video twice during contest, I hope next time I will refer this only. Thanks
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 😍
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)).
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.
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
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 .
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?
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! :)
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
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
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.
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?
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 ?
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.
: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)
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!
I did it! I looked at your solution for the first one briefly before waiting some time and trying it, but still needed help. The second one I did mostly on my own, but needed help understanding how the graph worked. Third one took me an hour, but I did it entirely! Fantastic tool and fantastic video.
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.
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
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
:)
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.
there are few guys in cp who really enjoys sharing knowledge. He is one of them.
here, if you want to calculate [dp1,dp2....dpn] values after 'K' identical transitions where each dp value has identical type of contribution to other dp values in all transitions, you will multiply this 1*n matrix m0 with Kth power of transition matrix. where transition matrix is a n*n matrix which has multiplication coefficients of each dpx value for each other dpx values. if some dpx has no effect on dpy, then multiplication coefficient is 0. It is easy to store m0 (initial state matrix) as 1*n matrix. In transition matrix(n*n), first column will be the coefficient factors A,B,C if dp0=A*dp0+B*dp1+C*dp2, 2nd col is D,E,F if dp1=D*dp0+E*dp1+F*dp2 and 3rd col is G,H,I if dp2=G*dp0+H*dp1+I*dp2
Matrix-Init (m0) (1*n) = [dp0 dp1 dp2]
Matrix-transition (mx) (n*n)= [A D G]
[B E H]
[C F I]
Answer = mx * (m0 ^ k)
Be sure while implementing matrix multiplication, i,j,k (order is-i,j,k) loop variables are different than floyd warshall (which has order-k,i,j)
This is for my own understanding, I needed to watch this video twice during contest, I hope next time I will refer this only.
Thanks
Welcome Errichto Once again. Hope you are well refreshed now.
Hoping for some nice series of topics from now onwards.
Thanks.
He you troll 😂
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!
Thanks Errichto sir for training problems and concept videos.
You know a lot! We Brazilians love your videos, keep it up ...
Really like this style, one lecture with homeworks!
wow,
great timing...
I was just searching for this
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 😍
watching an Errichto video makes me happy whether I was happy or sad before
This video is just legendary. Absolute genius.
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!
Thank you so much for organizing contest for practice! You are awesome!!!
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))
Thanks Errichto! solving first four was really good ;)
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.
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)).
Thanks for the awesome lectures string.reverse(limaK)!
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.
Long Day No "C"
Where were you for so many days?🤔
Good to see you back Sir 🙌🙌🙌
omg after so long time....are u planning some stream anytime soon?
maybe the end of July ;)
Hey can we expect an Algo & Coding Stream anytime soon. The Atcoder Hard ones were really interesting.
in August
great vid, eagerly waiting for Berlekamp-Massey
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
You are the GOAT dude.
Thanks for the wonderful lecture! :)
Please make a tutorial on time complexcity for beginners🙏🙏🙏🙏🙏🙏🙏🙏
will do :)
@@Errichto thanks 🙏🙏🙏🙏
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 .
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?
Can you make a video on how to solve constructive algorithm questions ??
Awesome ❤️
Hi, please post Facebook Hackercup rounds. After each round is over, of course. Thanks!
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! :)
Great explanations
Which editor do you use for Competive Programing .......???
Errichto lots of love from India and huge fan. We want a setup/room tour. Thank you for inspiring me!
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
Fantastic. Keep it up.
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 :)
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 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.
thank you soooo much for what you are doing :D
Please do a video explaining how to approach hard problems
This tutorial is one such video.
Thank you sir.🙏🙏
Can u please make an editorial video for CodeChef July Long Challenge "WEIRDMUL" problem
Can you do the graph code explanation, i would really appreciate it
Just realised Limak is the reverse of Kamil 🤯
😮
Thanks for the great video.
Could you tell me the name of the software you use to draw?
please provide amazon link of the chair you've got
Are there more training contests you made for other topics?
Can we solve tower of hanoi dp problem using this?
@Errichto Pls can you make geany and cygiwn set-up tutorial on windows?
thanks for the video!
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?
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.
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 ?
Can't like this video multiple times, youtube is so broken :(
Man you're just awasome 😎😎😇✌🏻✌🏻✌🏻✌🏻
why u dont use vim?
why geany ?
said a person who has "xd" in name and pic
; :
why u bullying me
You're amazing.
An important set of notes that will definitely help : drive.google.com/file/d/1nhL63QcjUiRm1pGGmzi1QHceKAGeBsRY/view.
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.
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.
Thank you so much
Thank you😍
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.
Amazing
Thank you.
Legend
hey @errichto
Should i learn data structure & algorithm first
or just try to do competitive programming?
My IQ went up 10 points just by watching this video
Perfect !! 😇😇
💙
where's the flex, Errichto?
like what? :D
@@Errichto how you came up with matrix exponentiation yourself
Need matrices in math
Nanana buenardo
yyayayayayayayay another vid!!!
we can find nth fibonacci same fast than nth prime, but we can get is this prime faster than is this fibonacci LOL
: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)
Math sharp.
ale, że limak to kamil od tyłu
hard
Did anyone else notice that Errichto looks uncannily similar to Tim Cook, CEO of Apple?
Give a thumbs up if you agree. :D