This was my First DP problem. Thanks to Problem Setter, this was really an amazing problem! 
I tried quite a few different approaches for this problem but the first one I used is this.
https://www.codechef.com/viewsolution/8373392
I basically used the previous values to ith sequence to get the values of the (i+1)th sequence but yet couldn’t find why I was getting WA in particular cases.
Could someone please help me out?
Nice problem , it made me to think for a sol of polynomial multiplication …
which would not be possible , if i had studied DP earlier
This problem can be solved by multiplying two polynomial iteratively.
by taking 1 polynomial as (1 + a[i]x ) and other as product obtained earlier …
Here’s link to my code… CodeChef: Practical coding for everyone
@rb08
Actually I also found only FFT and I didn’t understand it. I am still trying to understand that.
For the above problem, I only needed to multiply n linear polynomials that made it a bit easy (I don’t know if I could do for higher power).
Here’s my approach.
Consider the polynomial (x-1)*(x-2)
It is equal to x^2-3x+2
For any multiplication we only need the co-efficient of the polynomial (let’s store only the co-efficient in array say coeff). Also, when we are multiplying the first polynomial with x, since it’s co-efficient is 1, the coefficients of the result doesn’t change. Only power of each term increases by 1.
Let’s write x-1 as 0x^2 + 1x - 1. When we are multiplying it with x, the result becomes
1x^2 - 1x +0. The power increases and co-efficient remains same.
When the constant factor is multiplied, the co-efficient change, not the power of each term.
(x-1)(-2) = -2x + 2 (power of each term is constant). Now after multiplication of each part, we need to add the result.
The coeff array before multiplication is {0,1,-1} //0 for x^2
After multiplying x, since the power increases, we can simply shift them to the left as
{1,-1,0} and then add the result of the second multiplication with the constant. This result has power less than the first multiplication result. So we start adding the terms starting from the second term (check below to understand).
Co-efficient after multiplication with x, {1,-1,0}
Co-efficient after multiplication with -2, {0,-2,+2}
Ignoring the first term which is always 0 for second result, and un-altered for first result, we add the remaining corresponding terms. So result is {+1,-3,+2}.
This is the basic approach. Hope you understood.
In my code, I didn’t use multiple arrays for multiplication. I used a single long array initialized to 0. The first element of the array is the co-efficient for the highest power term. (whatever the highest term is after each multiplication). I used a pointer
idx to indicate the last position of the result (co-efficient of power 0, i.e. the constant term). For each multiplication, after multiplying with x, simply increased idx by 1. The new added term is always 0 as initialized. While multiplying the constant part, we need to add the result to corresponding terms. Remember, even though we shifted the co-efficient to the left, their value didn’t change. We can re-use them for the multiplication again. See below
idx is pointing to last element. So the element before it is equal to the co-efficient of power 0 before multiplying the x. We need to multiply the constant term -2 to this co-efficient and add it to the term at idx (see it using pen and paper for better understanding). I did the following to accomplish this
coeff[idx]+=(coeff[idx-1]*constant_term)
Putting it in a loop, we get
for(int i=idx;i>0;i–) //i!=0 as 0th term is the highest power and it’s co-efficient never changes
coeff[i]+=(coeff[i-1]*constant_term)
I used modular arithmetic on this.
1 Like
I am getting 15 points and WA in some of the subtasks ,please can somebody take a look at my solution and tell me what is the problem here CodeChef: Practical coding for everyone .It would be a great help,as this is the first time I got some points in a DP question 
I didn’t understand why F[0][0] is taken ‘1’ and not ‘0’ in the editorial. Also what will be the base case for W[][]? Is F[0][0]=1(if it is correct) enough to solve the problem ?
Getting wrong answer only at one of the parts of subtask 3
https://www.codechef.com/viewsolution/9015974
Any help would be appriciated
thankyou geeks:D
2 Likes
First of all, let’s note that the number of ways construct a sphere of the radii of R is equal to the product of the number of lower hemispheres of the radii of R multiplied by the number of upper hemispheres of the radii of R. Let’s call this number S[R].
Now, let’s denote the number of ways to construct a sequence of K nested spheres with the largest sphere having the radii of R by F[K][R]. Let’s take F[0][0] equal to one.
The rules for the recalculation of f[K][R] are straightfowrward: we need to pick a sequence of (K-1) spheres, where the largest sphere has the radii less than R. The number of such sequences (let’s denote it by W[K][R]) is equal to the sum of F[K-1][J] for all J < R. Now we need to add a sphere of the radii R to the end of each of these sequences. Considering that there are S[R] ways to create a sphere of the radii of R, we obtain that F[K][R] = W[K][R]*S[R].
The number of sequences of K nested spheres will clearly be equal to the sum of F[K][J] for all J between 1 and C.
In total, we need to calculate O(C2) states of F[][], and it takes O© to calculate each of them. So, the total complexity will be O(C3).
This solution is capable of solving the first two subtasks, but is too slow to solve the last one.
2 Likes
First of all, let’s note that the number of ways construct a sphere of the radii of R is equal to the product of the number of lower hemispheres of the radii of R multiplied by the number of upper hemispheres of the radii of R. Let’s call this number S[R].
Now, let’s denote the number of ways to construct a sequence of K nested spheres with the largest sphere having the radii of R by F[K][R]. Let’s take F[0][0] equal to one.
The rules for the recalculation of f[K][R] are straightfowrward: we need to pick a sequence of (K-1) spheres, where the largest sphere has the radii less than R. The number of such sequences (let’s denote it by W[K][R]) is equal to the sum of F[K-1][J] for all J < R. Now we need to add a sphere of the radii R to the end of each of these sequences. Considering that there are S[R] ways to create a sphere of the radii of R, we obtain that F[K][R] = W[K][R]*S[R].
The number of sequences of K nested spheres will clearly be equal to the sum of F[K][J] for all J between 1 and C.
In total, we need to calculate O(C2) states of F[][], and it takes O© to calculate each of them. So, the total complexity will be O(C3).
This solution is capable of solving the first two subtasks, but is too slow to solve the last one.
2 Likes
First find the frequency of upper hemisphere and lower hemisphere in two separate arrays.
Multiply each array index correspondingly and make copy of this array as in code.
Take cumulative sum from end of array and multiply this array by one shifting with copy array in the same mul array.
Sum of c-1 elements of mul array is D+1 answer where D=1.
Then again take the cumulative of mul array and multiply this with copy array with 2 shifting.
Sum of c-2 elements of mul array is D+1 answer where D=2. Repeat this process by increasing shifts c-1 times
2 Likes
Wherever you are doing subtraction add mod value to it i.e. 1000000007. Like in a[i+half] = even[i] - twiddle change it to
a[i+half] = even[i] - twiddle + 1000000007.
Sorry i am unable to confirm if it will give AC because i don’t know vectors but i too was getting WA in nearly same test cases and got AC by adding mod value where i was doing subtraction.
My WA submission - CodeChef: Practical coding for everyone
My AC submission - CodeChef: Practical coding for everyone
@ricola86 While adding currCount to prev(prev+=currCount) , prev can go out of range of int.
So,just take it as unsigned long long and just apply mod operation on it. i.e
prev = ((prev%PRIME)+(currCount%PRIME))%PRIME;
Just this and you will get ac!!!
Link to your changed solution,
https://www.codechef.com/submit/complete/8531991
1 Like
Oh my god, I’m such an idiot. I always make stupid mistakes like that. Thanks very much for taking the time and having a look
@sid9406 Change “long int” to “long long int”
As a long int is a signed integral type that is at least 32 bits, while a long long or long long int is a signed integral type which is at least 64 bits
1 Like
@sid9406
At various places your code might go out of the range of long int and hence cause overflow. You are required to use long long int instead.
Here is the link to your updated solution.
https://www.codechef.com/viewsolution/8532367
Happy to help.
Well,i found my mistake by reading above comments.I’m a total fool,should have added mod while performing subtraction where ever required.
just try adding mod where you are using subtraction at each step :-). Mine was the same mistake.
thank you very much ,it worked