CHEFINS - Editorial

PROBLEM LINK:

Contest
Practice

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

Fast Fourier transform

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

AUTHOR’S AND TESTER’S SOLUTIONS:

setter
tester

1 Like

Are there any other efficient solutions to this problem?

https://www.codechef.com/viewsolution/12300237

This passed for me.

1 Like

Can you tell me why is this efficient?At the first look it seems O(n^2)

The solution above using FFT , is one the best solution for this problem and one more thing many programmers, solved this problem using some brute force + optimization ( with two loops ) and decrease the number of iterations with some tricks. May be test cases were not so strong.

@admin As usual, None author’s and setter’s solutions can’t be seen. Can you just paste the code on the same page itself from next time?

Can someone give link to solution which uses the technique mentioned in the editorial?

Author and Setter’s solutions not available.

BTW, here is a solution using the first technique mentioned in the editorial with complexity O(n {\log}^{2}n) which passes well within time-limit. Though the constants associated with FFT are large and will prevent most of the naive FFT implementations to pass, but fast FFT implementations will easily pass the time-limit. To prevent this from happening, I guess the time-limit should have been little more strict and test-cases more stronger.

In editorial it is said that,“we just need to calculate A ^ (2^k) where 2^k ≥ N”, but since coefficient of A^i given numbers that are formed when i numbers are added then why do we calculate A ^ (2^k)?

Can anybody comment the complexity of @additya1998 solution?

//