ssense's blog

By ssense, history, 4 months ago, In English

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?

 
 
 
 
  • Vote: I like it
  • +17
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it -30 Vote: I do not like it

They do appears but rarely

»
4 months ago, # |
  Vote: I like it +112 Vote: I do not like it

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   Vote: I like it +50 Vote: I do not like it

You can see it as "explicitly excluded" in IOI Syllabus 2019, here: https://ioinformatics.org/files/ioi-syllabus-2019.pdf

As for other contests, after considering the above, they may still use any topic they see fit.

Edit: beaten :) .

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +7 Vote: I do not like it

On Polish OI it happened once, 3 years ago, in finals. You can find this task here.

»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

APIO 2016 Boat can be solved in $$$O(N^2 \log N)$$$ with FFT, just so you know.

»
4 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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, # |
  Vote: I like it +30 Vote: I do not like it

As people mentioned, it happened on POI a few years ago, but everybody in Poland agree that it was a bad idea.