Matrix Exponentiation + Fibonacci in log(N)
ฝัง
- เผยแพร่เมื่อ 6 ก.ค. 2024
- Codeforces training contest: codeforces.com/gym/102644
This is a tutorial on matrix exponentiation, a tool that allows you to quickly find the n-th Fibonacci number or quickly compute the number of very long paths in a graph. After watching the video, try to solve the first 6 problems in the CF training contest. I will soon post another video (or make a live stream?) with solutions to those problems, and the last 3 hard problems.
0:00 Introduction & Prerequisites
1:13 A. Random Mood
6:17 B. String Mood
15:12 Implementation
19:38 General Recipe
23:17 C. Fibonacci
26:30 C++ Recipe
27:56 Random Again
28:27 Complexity & Summary
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
- Github repository: github.com/Errichto/youtube
- Live streams on 2nd YT channel and on Twitch: / errichto2 & / errichto
- FB and Twitter: / errichto & / errichto
- Frequently Asked Questions: github.com/Errichto/youtube/w...
#Coding #Programming
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.
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.
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 😍
Thanks Errichto sir for training problems and concept videos.
Really like this style, one lecture with homeworks!
Really like the concept, lecture in video and problems to practice in ordered manner. Good for beginner and maybe intermediate ones also
:)
wow,
great timing...
I was just searching for this
Thank you so much for organizing contest for practice! You are awesome!!!
Welcome Errichto Once again. Hope you are well refreshed now.
Hoping for some nice series of topics from now onwards.
Thanks.
He you troll 😂
You know a lot! We Brazilians love your videos, keep it up ...
This video is just legendary. Absolute genius.
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!
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
Where were you for so many days?🤔
Good to see you back Sir 🙌🙌🙌
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.
Bro, please consider the 3 questions posted below... and make a video because your way of explaining and problem solving skills are awsome
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.
great vid, eagerly waiting for Berlekamp-Massey
Thanks for the wonderful lecture! :)
watching an Errichto video makes me happy whether I was happy or sad before
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"
Thank you, Kamil!
Thanks for the awesome lectures string.reverse(limaK)!
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))
Great explanations
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 great video.
Could you tell me the name of the software you use to draw?
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! :)
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
thank you soooo much for what you are doing :D
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.
Can you make a video on how to solve constructive algorithm questions ??
Awesome ❤️
thanks for the video!
Fantastic. Keep it up.
Hey can we expect an Algo & Coding Stream anytime soon. The Atcoder Hard ones were really interesting.
in August
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?
An important set of notes that will definitely help : drive.google.com/file/d/1nhL63QcjUiRm1pGGmzi1QHceKAGeBsRY/view.
Which editor do you use for Competive Programing .......???
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
Are there more training contests you made for other topics?
omg after so long time....are u planning some stream anytime soon?
maybe the end of July ;)
Can we really use matrix exponention in string mood updates problem only soln I can think of is O(nq)
Thank you.
@Errichto Pls can you make geany and cygiwn set-up tutorial on windows?
Man you're just awasome 😎😎😇✌🏻✌🏻✌🏻✌🏻
Thank you😍
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?
Can we solve tower of hanoi dp problem using this?
Thank you so much
You're amazing.
please provide amazon link of the chair you've got
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!
so when I watch TH-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.
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 :)
Amazing
Legend
Perfect !! 😇😇
Please make a tutorial on time complexcity for beginners🙏🙏🙏🙏🙏🙏🙏🙏
will do :)
@@Errichto thanks 🙏🙏🙏🙏
💙
Errichto lots of love from India and huge fan. We want a setup/room tour. Thank you for inspiring me!
yyayayayayayayay another vid!!!
Nanana buenardo
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.
hey @errichto
Should i learn data structure & algorithm first
or just try to do competitive programming?
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.
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.
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.
Just realised Limak is the reverse of Kamil 🤯
😮
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
Can't like this video multiple times, youtube is so broken :(
why u dont use vim?
why geany ?
said a person who has "xd" in name and pic
; :
why u bullying me
Please do a video explaining how to approach hard problems
This tutorial is one such video.
Thank you sir.🙏🙏
: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.
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
where's the flex, Errichto?
like what? :D
@@Errichto how you came up with matrix exponentiation yourself
Need matrices in math
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.
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
we can find nth fibonacci same fast than nth prime, but we can get is this prime faster than is this fibonacci LOL
My IQ went up 10 points just by watching this video
ale, że limak to kamil od tyłu
Did anyone else notice that Errichto looks uncannily similar to Tim Cook, CEO of Apple?
Give a thumbs up if you agree. :D