I want to request all the popular CP YouTubers like SecondThread, galen_colin, tmwilliamlin168, Errichto and all others (these are my favourite).
Can you guys please make a proper tutorial on FFT, with C++/Java/Python Code implementation as well? I know there are blogs on it but a topic like this seriously needs a video tutorial, it becomes tougher if you do it by text. We learned a mathematical/theoretical version in college i guess, but there is no code it it.
While there are certainly some paid courses which teaches them (not sure) but i don't think i can afford them anyways, so i look up to you all orz. This topic is rare af, and no one has a proper video tutorial on web with code.
UPD: demoralizer orz ! looks like my man is gonna do it ! wishing him 69 years of luck !!
P.S — Don't judge by the ratings on this handle, i use it to shitpost. I really want to learn FFT.
I don't know it myself. Probably best to leave it to the legends (e.g. the other people you mentioned).
XD XD XD XD XD
you can refer this https://www.youtube.com/watch?v=qrGBpexbT-c&t=2810s lecture by kevin
you can watch this : https://youtu.be/Xwu6rq41nE8 by Gaurav sen
I have watched this, but it's theoretical again. I have the understanding, I just need the implementation part
How I learned FFT ("shitpost tutorial"):
(for all valid $i, j, k$; $$$i + j$$$ is calculated modulo the length but that last bit is often irrelevant).
Name checks out
your toturial are very nice detail explained
galen_colin looks like you are not alone XD..I am also going to learn fft now (/^▽^)/
Even though that's not enough for harder problems, that's enough for most problems (and probably the way most people including me "learned" it at first).
I'm gonna change my handle to -is-this-suffix-automata- then
You forgot the EDU guys, pashka and Aksenov239.
Really hope that they would make videos on this as well
This Chinese article is great I think. You can google translate it if you need it.
Can you mention some problems where we really need to know FFT to solve them??
I solved https://open.kattis.com/problems/polymul2 with the code from https://cp-algorithms.com/algebra/fft.html
Thank You!!
https://codeforces.com/problemset/problem/1103/E
https://www.codechef.com/OCT17/problems/XORTREEH
https://www.codechef.com/problems/POLYEVAL
there are more problems like that but these are the ones I can remember/find easily.
Thank You!!
Now I see, these problems are quite rare but can be a gamechanger in some important competition.
Thanks for this blogpost.
Although my name isn't in the blog and I'm nowhere even near the people mentioned, but if none of them do it within a week, I'm doing it. And this one I'll do in English, cuz as you pointed out, it's not available in English either.
Bro, you are an absolute legend! Hoping to see you red soon!
Bold of you to assume that I know how FFT works (I don't)