Contest Link: Problem Link Contest
Problem Link:Practice section link
Author and Editorialist: Prateek Kumar
Problem Title : Chef and the line segments
PREREQUISITES:
Knowledge of Discrete Fast Fourier Transform and general introduction to Fast Fourier Transform.
PROBLEM:
In the problem statement we are given two arrays containing positive integers.
1.The first array contains the distance of the m points k[j].
2. The second array contains the length of n sticks l[i] (Each stick of length were infinite in number. We were allowed to use at most 2 sticks, so we would need at most 2 sticks of any length.)
We are supposed to count the total values in the first array containing the distances that are equal to any of the stick lengths or the sum of the lengths of any 2 sticks (2 Sticks can be equal as well) . Our task is to print this count.
EXPLANATION:
The 2 methods are as follows:
a) The first method is to use brute force. This would clearly give time limit exceeded.
b)The second method is to use Fast Fourier Transform. Here is the algorithm for the same for giving a fast solution for the stated problem:
- We are supposed to make 2 binary arrays, a[i] and b[i].
- Now a[i]=1 if i is a distance of a point from the chef.
- And b[i]=1 if i is a stick length.
- Now we have to take the convolution of the b[i] with itself, which is given by Discrete FFT, which is as follows:
FFT[i]= (k=0 to i) Σ b[k] * b[i-k] (This is the convolution)
- Now count the number of i for which FFT[i]>0 and a[i]=1, which is the answer for the problem.
POINT TO NOTE
In this problem we are given 2 arrays A[] and B[]. We need to find the number of elements in the array A[] that can be formed by summing up any two elements or by taking a single value from B[]. The elements that are summed up can be same.
FFT provides a faster solution for this problem.