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.
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.
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 😍
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
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 .
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 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
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 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?
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.
so when I watch RUclipsrs 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?
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?
ruclips.net/video/eMXNWcbw75E/видео.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 ?
: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!
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.
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.
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.
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
:)
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.
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
Really like this style, one lecture with homeworks!
wow,
great timing...
I was just searching for this
You know a lot! We Brazilians love your videos, keep it up ...
This video is just legendary. Absolute genius.
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 😍
Welcome Errichto Once again. Hope you are well refreshed now.
Hoping for some nice series of topics from now onwards.
Thanks.
He you troll 😂
there are few guys in cp who really enjoys sharing knowledge. He is one of them.
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.
Thank you so much for organizing contest for practice! You are awesome!!!
watching an Errichto video makes me happy whether I was happy or sad before
Thanks Errichto! solving first four was really good ;)
omg after so long time....are u planning some stream anytime soon?
maybe the end of July ;)
Awesome ❤️
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
Where were you for so many days?🤔
Good to see you back Sir 🙌🙌🙌
Thanks for the awesome lectures string.reverse(limaK)!
Hey can we expect an Algo & Coding Stream anytime soon. The Atcoder Hard ones were really interesting.
in August
Long Day No "C"
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!
Thanks for the wonderful lecture! :)
You are the GOAT dude.
Great explanations
great vid, eagerly waiting for Berlekamp-Massey
Can you make a video on how to solve constructive algorithm questions ??
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))
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.
thanks for the video!
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)).
Fantastic. Keep it up.
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 .
Are there more training contests you made for other topics?
Thanks for the great video.
Could you tell me the name of the software you use to draw?
thank you soooo much for what you are doing :D
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 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 :)
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! :)
Which editor do you use for Competive Programing .......???
Thank you😍
Perfect !! 😇😇
Hi, please post Facebook Hackercup rounds. After each round is over, of course. Thanks!
Man you're just awasome 😎😎😇✌🏻✌🏻✌🏻✌🏻
Thank you so much
Thank you.
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
Please make a tutorial on time complexcity for beginners🙏🙏🙏🙏🙏🙏🙏🙏
will do :)
@@Errichto thanks 🙏🙏🙏🙏
You're amazing.
why u dont use vim?
why geany ?
said a person who has "xd" in name and pic
; :
why u bullying me
Just realised Limak is the reverse of Kamil 🤯
😮
Can you do the graph code explanation, i would really appreciate it
Legend
💙
please provide amazon link of the chair you've got
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
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.
@Errichto Pls can you make geany and cygiwn set-up tutorial on windows?
Amazing
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.
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 we solve tower of hanoi dp problem using this?
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
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.
Nanana buenardo
Can we really use matrix exponention in string mood updates problem only soln I can think of is O(nq)
Errichto lots of love from India and huge fan. We want a setup/room tour. Thank you for inspiring me!
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.
Can't like this video multiple times, youtube is so broken :(
where's the flex, Errichto?
like what? :D
@@Errichto how you came up with matrix exponentiation yourself
so when I watch RUclipsrs 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.
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?
yyayayayayayayay another vid!!!
hey @errichto
Should i learn data structure & algorithm first
or just try to do competitive programming?
ruclips.net/video/eMXNWcbw75E/видео.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 ?
: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)
My IQ went up 10 points just by watching this video
Math sharp.
Need matrices in math
An important set of notes that will definitely help : drive.google.com/file/d/1nhL63QcjUiRm1pGGmzi1QHceKAGeBsRY/view.
hard
ale, że limak to kamil od tyłu
we can find nth fibonacci same fast than nth prime, but we can get is this prime faster than is this fibonacci LOL
Did anyone else notice that Errichto looks uncannily similar to Tim Cook, CEO of Apple?
Give a thumbs up if you agree. :D