Matrix Exponentiation Coding (Part 1/2)
Вставка
- Опубліковано 13 чер 2024
- It's time to code problems from Matrix Exponentiation training contest. This is part 1 with solutions to easy-medium problems ABCDEF.
contest link: codeforces.com/gym/102644
cf article and hints: codeforces.com/blog/entry/80195
matrix expo tutorial video: • Matrix Exponentiation ...
part 2 with GHI: • Matrix Exponentiation ...
0:00 Introduction
0:35 A. Random Mood
11:45 B. String Mood
16:11 C. Fibonacci
24:43 D. Count Paths
34:04 E. Knight Paths
50:29 F. Min Path
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
Why this legendary channel isn't verified yet? 😓
Love the way you teach! Big fan sir, gym contest after the tutorial is really helping alot, u r providing all resources to learn a topic at a single place. Great work brother.
you're a source of motivation sir, keep going!!
Your way of teaching is awesome . Please continue making more videos on competitive programming and algorithms 😊
Training content in single topic are such a pure gem I wish we have more such
These tutorials deserve a lot more attention. Pozdrowienia z Francji!
A nice way to think about the solution for E is, that the solution effectively adds a new node to the graph of cells. Every cell goes to this new node and the node has a self loop, such that the number of paths of previous states aren't lost.
your voice is soo soothing i sometimes watch your videos as a form of ASMR. don't judge me.
Do a training contest on other topics too....best way to learn
I totally agree
Hey Sumanto, I'm kind of surprised to find you here 🤣
@@aksharkottuvada lol world is so small 😂
I agree too
You are a Legend!
thank you.
Awesome!
Hey Errichto, do python submissions not get more time limit?
when can we expect part2? I am stuck on last problem that why. or if you could just give me a small hint.
please make a video about linux command you use for coding basic tutorial like making testcase etc. whatever you use in live stream .. if you can do that it will be very helpful... thanks for helping us..
On E - Knight Paths, why do we have to elevate to power k + 1, instead of k?
REP(i,2) product.a[i][i]=1;
just create a identity matrix..
(Identity matrix =diagonal element is 1 ,other element is 0)
because if A is a matrix and B is a identity matrix .
then A=A*B.(just like a=10,b=1,a=a*b).
In Problem E, can you elaborate a little bit on how the cumulative answer is getting generated?
it would be great if you release a video on facebook hacker cup 2020 problem soving!!!
Hi @Errichto, I was trying to solve Question: {C. Fibonacci}.
My Approach was diffrent from yours.
int MOD = (int) 1e9 + 7
long a = 1;
long b = 1;
for (long i = 3; i
Can someone explain Knight Paths ? I am not getting the recurrence for it and how it is transformed into a matrix
please provide amazon link of the chair you've got
Great video! By the way, my dumb ass solved B as:
M = [[18 5 1]
[5 18 2]
[0 0 26]]
F(0) = [[1]
[0]
[1]]
F(n) = M ^ n * F(0)
f(n, happy) = 26 ^ (n - 1) (any string that ends with H) + 5 * f(n - 1, sad) (any sad string + a flip character) + 18 * f(n - 1, happy) (any happy string + a do nothing character)
f(n, sad) = 2 * 26 ^ (n - 1) (any string that ends with S or D) + 5 * f(n - 1, happy) (any happy string + a flip character) + 18 * f(n - 1, sad) (any sad string + a do nothing character)
Nice to know that I can simply care about H -> H, H -> S, S -> H or S -> S.
Now let's see if I can solve the last two!
@Errichto Pls can you make geany and cygwin set-up tutorial ?
He already did.
do fb Hackercup editorial if possible
Didn't understand [8*new_row+new_col], how did you combine them in knight paths
it will change every cell into a unique value from 0 to 63. First row is 0,1,2,3,4,5,6,7, second row is 8,9,...,15, and so on.
pls make video on how to learn dsa and from where, how to implement them??
He has I think, checkhis some video.
@@shivamjalotra7919 yaa he has Covered some algos but i also wanted to learn data structures
Thanks
For learning, the way I generally do is Google "data structure", read a blog, go through a code snippet or see a video. Then go to codeforces and search easy problems on that ds usage, then solve 3-4 problems by implementing the ds in all the problems. Note this case is for advanced data structures. I will not code stack, queue or priority_queue from scratch. STL has great support on them.
why you use geany
not vim
Lol you are such a IDE dogmatic snob. Who cares about that?
My Java code timesout for test 22 for DP solution. I tried various versions:
codeforces.com/submissions/shanns
1. precompute jumps: 89171521
2. compute jump on the fly: 89170970
I guess doing mod operation is taking too long.
Any suggestions?
I think there is an error in problem E.
From cell (0,0) a knight can reach two other cells in one move, and there are 4 different ways to reach these two cells, not 3 as the problem stipulates.
And for k=2 which means two moves, 28 possible ways not 15.
Take your pencil and paper and try it on a board.
Anyway, the problems are interesting and the solution more interesting.
Great job kid!
sir can you teach us some language which will be helpful for beginner to learn code..
How can I be like you ,what course should I do ,plz sir help me plz suggest me something ! That can I follow in daily basis to improve coding 🙏🙏🙏🙏🙏♥️♥️♥️♥️
There’s no stupid question!
I shouldn’t be watching this video before I attempt to do the problems
:*
make a collab with Willam lin
Yo