On Learning FFT

Hello everyone, so in the last 1 week I just learned some FFT problems. Maybe with this blog I can share the knowledge of some good FFT problems I’ve solved:

Interesting ones:

• INC 2020 - Instruction Anagram
• CF 1096G - Lucky Tickets
• GYM 103274B - Basel Problem
• CF 993E - Nikita and Order Statistics
• CF 954I - Yet Another String Matching Problem
• TROC 17G - Guitar Gift

Classic ones:

• SPOJ - ADAMATCH
• SPOJ - POLYMUL
• UVALIVE 6808 - Best Position

To Do:

• CF 958F3 - Lightsabers (hard)
• 1398G - Running Competition
• Kattis kinversions - K-Inversions
• 754E - Dasha and Cyclic Table
• Codechef MMNN01 - Expected Number of Customers
• Codechef PSUM - Power Sum
• Codechef CHEFKNN - Chef and Interval Painting
• HDU 5609 - 3-idiots
• HDU 5730 - Shell Necklace
• URAL 1996 - Cipher Message 3
• Codechef PRIMEDIST - Prime Distance on Tree
• Codechef COUNTARI - Arithmetic Progressions
• HDU 5322 - Hope
• HDU 5323 - Solve this interesting Problem
• GYM 100341C - AVL Trees
• HDU 4656 - Evaluation
• HDU 5307 - He is Flying
• Kattis aplusb - A + B Problem
• HDU 6061 - RXD and functions
• Hihocoder 1388 - Periodic Signal
• https://codeforces.com/problemset?tags=fft

Noted Editorials

Instruction Anagram

Prerequisite: FFT, Polynomial Multiplication, Combinatorics

Please get yourself familiar with those topics before reading this article.

Lets write down some important observations on this problem. Initially, solving the problems of $M = 1$ may solve the case when $M > 1$. WLOG, let’s add another data points where the robot will be at duration $N$. You can obtain this by finding the ending position of the robot.

Now, let’s observe how to count it. define the $x_i$ and $y_i$ as the horizontal and vertical distance of data point $i$ and $i - 1$, and the duration between them is $t_i$.

It’s easy to say, that there will be $\vert x_i \vert + \vert y_i\vert$ fixed direction in each transition. Now, we may put some extras $\texttt{NS}, \texttt{SN}, \texttt{EW}, \texttt{WE}$ to fill in for the rest of the durations, note that it can be put anywhere between the fixed directions.

Let’s see, so far, all the FFT problems I found can be represented as a dynamic programming problem. In here, we also need to do a dynamic programming. We must find the outer answer of the dynamic programming first.

Now, let us define one direction to be our pivot. Pivot here will be used to obtain every other states. This is like save state dynamic programming. Define $dp[i][j]$ as the number of arrows solving the data points $[1,i]$, and $j$ of character $\texttt{S}$ has been used. Now, we know the robot’s exact position at time $i$, so we know how many $\texttt{N}$ characters already in our string.

It might seem that the $\texttt{W}$ and $\texttt{E}$ is out of state, but observe that between each data points, we know how many extra character will be used. Extra here means the directions those are not fixed. So if we determine the fixed pivot, we know how many extra $\texttt{W}$ and $\texttt{E}$ will be used.

So, to shift between transition, define the extra number of direction pair we can put as $e = \dfrac{t_i - \vert x_i \vert - \vert y_i \vert}{2}$ we can define a polynomial $\sum_{i = 0}^{e} c_ix^i$, where $c_i = \dfrac{t_i!}{(\vert x_i \vert + i)! \cdot i! \cdot (\vert y_i \vert + (e - i))! \cdot (e-i)!}$, the denominator is quite tricky, the idea is, you want to count combination having $i$ extra $\texttt{N}$ and $\texttt{S}$ characters, also $e - i$ extra $\texttt{W}$ and $\texttt{E}$ characters.

Now, you have $M + 1$ polynomials. You may multiply it and the answer should be in the terms of $x^{extra\texttt{N}}$, where $extra\texttt{N}$ denotes the non-fixed $\texttt{N}$ available in the string $S$. Also, don’t forget to assert $extra\texttt{N}$ = $extra\texttt{S}$ and $extra\texttt{E}$ = $extra\texttt{W}$.