Matrix Exponentiation Coding (Part 1/2)
Vložit
- čas přidán 4. 06. 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? 😓
you're a source of motivation sir, keep going!!
Training content in single topic are such a pure gem I wish we have more such
Your way of teaching is awesome . Please continue making more videos on competitive programming and algorithms 😊
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.
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.
These tutorials deserve a lot more attention. Pozdrowienia z Francji!
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!
Hey Errichto, do python submissions not get more time limit?
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).
your voice is soo soothing i sometimes watch your videos as a form of ASMR. don't judge me.
when can we expect part2? I am stuck on last problem that why. or if you could just give me a small hint.
Awesome!
On E - Knight Paths, why do we have to elevate to power k + 1, instead of k?
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..
In Problem E, can you elaborate a little bit on how the cumulative answer is getting generated?
thank you.
please provide amazon link of the chair you've got
it would be great if you release a video on facebook hacker cup 2020 problem soving!!!
Can someone explain Knight Paths ? I am not getting the recurrence for it and how it is transformed into a matrix
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
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?
@Errichto Pls can you make geany and cygwin set-up tutorial ?
He already did.
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.
do fb Hackercup editorial if possible
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!
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!
sir can you teach us some language which will be helpful for beginner to learn code..
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?
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!
:*
make a collab with Willam lin
Yo
I shouldn’t be watching this video before I attempt to do the problems