PROBLEM LINK:
Author: Misha Chorniy
Tester: Tuan Anh Tran Dang
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Tuan Anh Tran Dang
Difficulty
MEDIUM
PREREQUISITE
PROBLEM
Given some integers in the ranges [1…N] you have Q query to answer each have the form of whether you can create a sum of X from those numbers (one number can be used multiple times).
SOLUTION
We will need to use Fast Fourier transform in this problem. For those who do not familiar with the technique it is a method that help us do polynomial multipliation in O(NlogN) whe N is the degree of the polynomial. You can still read this editorial to see how polynomial multiplication can be applied to solved this problem before digging into the FFT.
Consider the polynomial A, B which have coefficients of only 0 or 1. Let C is the polynomial which is the product of A and B. We can see that the coefficients c_i of C will be c_i = Sum of a_x * b_y where a_x and b_y are some coefficients of A and B. c_i is positive only when there is at least a_x and b_y that equal to 1 and x + y = i. With that we can apply the polynomial multiplication to find with the given set of number which number can be created by adding two number in the set. Consider the following example:
A = x^2 + x^3 + x^5
C = A * A = x^4 + 2*x^5 + 3x^6 + 2x^8 + x^10
we can see that the positive coefficients of C is which can be express as the sum of two coefficients of A.
4 = 2 + 2
5 = 2 + 3
6 = 3 + 3
8 = 3 + 5
10 = 5 + 5
So now you may guess how we solve this problem. Notices that we can use same number many times. Let create a polynomial A of degree 200000 with the coeffient a_i = 1 if we have number i (to create sums). A^2 will let us know which sum can be created by adding at most two numbers from the set. Notice that we should have a_0 = 1. Similarly A^4 will show which sum can be created by at most 4 numbers (one number can appear more than once). So basically we just need to calculate A ^ (2^k) where 2^k ≥ N. And of course we only care about the first 200000 coefficients. Now we got our first solution which is multiply the polynomial A with itself logN times. After that the positive coefficients will corressponding to the sums that can be created. logN multiplications take us O(Nlog^2N) - quite good but will not pass the time limit.
One observation can be made is that the larger numbers appear fewer times in the sum so that we can ignore them in the early multiplications. For example 100001 can appear at most once in the sum so we can only add it in the later multiplications.
More specifically we have Logn steps, at the ith step, we try to see which numbers in the range [0…2i] can be created. Let see how we can calculate for each step based on the previous step.
After completed step i - 1 we can have an vector of 0s and 1s where the kth item quals to 1 means that we can create number k. Let enlarge the vector to have 2i items and set 1 at the right places corresponding to the values of F. Now the question is how to find all number can be created in the range [0…2i]. One might say that just multiply a with it self but that is incorrect. Let’s see an example:
After 3rd step we have a = 10000100 which means in the range [0..7] only 0 and 5 can be created.
At 4th step we need to find in the range [0..15] which numbers can be created. For simplicity let assume that we do not have any F in the range [8..15].
If we just multiply a with it self we only got 0, 5 and 10 and missed 15 = 5 + 5 + 5.
The correct solution is multiply a with it self twice. The prof of this is left for you as an exercise.
So with this improve we saved a great deal of calculation. In fact this will give us the complexity of O(1log1 + 2log2 + 4log4 + … + n Logn) = O(nlogn).