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?

# | User | Rating |
---|---|---|

1 | tourist | 3682 |

2 | ecnerwala | 3603 |

3 | Benq | 3549 |

4 | Radewoosh | 3494 |

5 | Petr | 3452 |

6 | ksun48 | 3413 |

7 | maroonrk | 3406 |

8 | Miracle03 | 3314 |

9 | scott_wu | 3313 |

10 | Um_nik | 3299 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 214 |

2 | Errichto | 189 |

3 | awoo | 188 |

4 | rng_58 | 187 |

5 | SecondThread | 186 |

6 | Um_nik | 177 |

7 | Ashishgup | 176 |

8 | maroonrk | 173 |

9 | antontrygubO_o | 172 |

10 | -is-this-fft- | 169 |

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?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/20/2021 20:45:11 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

They do appears but rarely

Fast Fourier Transform is listed as

explicitly excludedin 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.)

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 :) .

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.

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

_NTT?

Do you read the comments before posting? SuperJ6 posted the same problem 2 hours before you did.

Oh, right, didn't notice before, my bad :(

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

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"

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