ssense's blog

By ssense, history, 4 months ago,

After searching on the internet I couldn't get a definitive answer, so I am asking here.

Does Fast Fourier Transform come up in Olympiads often or at all?

• +17

 » 4 months ago, # |   -30 They do appears but rarely
 » 4 months ago, # |   +112 Fast Fourier Transform is listed as explicitly excluded in the IOI Syllabus. This means that knowledge of FFT should not help the contestants in obtaining simpler solutions / solutions worth more points for IOI problems.As a consequence, most national OIs also won't use problems that require FFT. (In ICPC and other university-level competitions FFT is already fair game.)
 » 4 months ago, # | ← Rev. 2 →   +50 You can see it as "explicitly excluded" in IOI Syllabus 2019, here: https://ioinformatics.org/files/ioi-syllabus-2019.pdfAs for other contests, after considering the above, they may still use any topic they see fit.Edit: beaten :) .
 » 4 months ago, # | ← Rev. 2 →   0 This is the only OI problem I remember seeing where fft was intended (I assume?) (not even polynomial multiplication, only literally coding just ntt lol). I'm sure there are a few other that at least have unintended fft sols for computing number sequences, and china NOI is p orz so it wouldn't be surprising there, but overall you can basically say you don't need to know it, at least very likely you won't, for reasons stated in above comments. I've also seen problems use the "FFT Graph" shown in the statement of this problem, and while it is useful construction to know and relates to fft algo the actual fft algo is unnecessary in problems involving this construction.
 » 4 months ago, # |   +7 On Polish OI it happened once, 3 years ago, in finals. You can find this task here.
•  » » 4 months ago, # ^ |   -15 _NTT?
•  » » 4 months ago, # ^ |   -13 Do you read the comments before posting? SuperJ6 posted the same problem 2 hours before you did.
•  » » » 4 months ago, # ^ |   0 Oh, right, didn't notice before, my bad :(
 » 4 months ago, # |   +4 APIO 2016 Boat can be solved in $O(N^2 \log N)$ with FFT, just so you know.
 » 4 months ago, # |   +12 IOI: We explicitly excluded FFT from the Syllabus.RMI: haha Chimichangas goes brrr.Note: You can find the English version of the statement if you search for "Chimichangas RMI"
 » 4 months ago, # |   +30 As people mentioned, it happened on POI a few years ago, but everybody in Poland agree that it was a bad idea.