Problem LinkDifficultyEasy PrerequisitesDynamic programming ProblemCount the number of ways to construct a sequence of nested spheres How to get 40 pointsFirst 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 (K1) 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[K1][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(C^{2}) states of F[][], and it takes O(C) to calculate each of them. So, the total complexity will be O(C^{3}). This solution is capable of solving the first two subtasks, but is too slow to solve the last one. How to get 100 pointsThe solution's idea remains the same. Let's find a way to calculate the values of F[][] in O(1) time. For achieving this, let's note that the value of W[K][R] equals to the W[K][R1] + F[K1][R1]. So now, using the old values of W[][], we can calculate the new one in O(1). Now, since the calculation of every state runs in O(1), we get the total complexity of O(C^{2}), which fits for our problem. Setter's SolutionCan be found here Tester's SolutionCan be found here
This question is marked "community wiki".
asked 06 Oct '15, 07:07

This one is my favorite question in the OCT15 challenge. By some examinations, I knew for a given c, we need to find the sum of product of elements in every subset of size c+1. By googling, I came across a generating function for the solution. I had never coded a polynomial multiplication before. Using a naive n^2 multiplication I was able to solve it. But, instead of finding the result modulo 10^9+7 I found modulo 10^9+9. After getting WA, I tried to come up with another logic and came up with the dynamic programming solution as given above (solving dp by myself gives a lot of pleasure :)). After solving it with dp approach, I tried debugging the first generating function approach and found my mistake. Then I got AC for that. Thanks to the initial mistake, I solved a DP problem. My dp approach : https://www.codechef.com/viewsolution/8464303 My other approach : https://www.codechef.com/viewsolution/8464356 answered 12 Oct '15, 15:21
hi dragonemperor, i have been following your posts on codechef long contest ques, it's been a great learning curve, i learned trie with the help of your amazing insights on REBXOR form sep15, i googled for polynomial function method but only managed to find FFT, can you please share the resource that led you to succesfully implement your code, thanks ..:)
(14 Oct '15, 09:32)
1
A little experiment using pen and paper showed that if first term is present x time, second y times and so on, (ignoring the terms present 0 times), the problem can be reduced to finding product of elements of of subset of side c+1 (and for all other values of c, same thing applies), in the array {x,y,...} Following this link I got the approach http://stackoverflow.com/questions/10106193/sumofproductofsubsets I explained my approach in the code as a separate answer as this didn't fit comment. Check that out too.
(14 Oct '15, 13:36)
(14 Oct '15, 13:38)

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 c1 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 c2 elements of mul array is D+1 answer where D=2. Repeat this process by increasing shifts c1 times answered 26 Dec '15, 01:02

I solved it without using DP.Only by Simple logic. Solved like adhoc problem. answered 12 Oct '15, 15:55
explain plz
(12 Oct '15, 23:55)
1
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.
Then again take the cumulative of mul array and multiply this with copy array with 2 shifting.
> now you can understand code.
(13 Oct '15, 01:02)

Answer is hidden as author is suspended. Click here to view.
answered 12 Oct '15, 19:16

@rb08
Actually I also found only FFT and I didn't understand it. I am still trying to understand that.
Here's my approach. Consider the polynomial (x1)(x2) Coefficient after multiplication with 2, {0,2,+2}
idx is pointing to last element. So the element before it is equal to the coefficient of power 0 before multiplying the x. We need to multiply the constant term 2 to this coefficient 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[idx1]*constant_term) Putting it in a loop, we get I used modular arithmetic on this. answered 14 Oct '15, 13:32
thanks alot for a detailed explanation @dragonemperor, though i still need some time to grasp polynomial multiplication better. awsome work .. :)
(14 Oct '15, 19:45)

It can be solved in clogn using FFT(Polynomial multiplication)..I implemented it here https://www.codechef.com/viewsolution/8318645 But i messed up with the modulo thing..Can anyone please figure out why it is giving WA in few test cases in this code... answered 12 Oct '15, 15:15
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  https://www.codechef.com/viewsolution/8456126 My AC submission  https://www.codechef.com/viewsolution/8456131
(12 Oct '15, 16:11)

Can anybody take a look at my solution please https://www.codechef.com/viewsolution/8430787 I used the same dynamic approach as the OP but I get a wrong answer on one of the test cases. I suspect it maybe a miscalculation with the modulus. Any help will be much appreciated, thanks. answered 12 Oct '15, 15:22
1
@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
(12 Oct '15, 17:54)
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 :)
(12 Oct '15, 18:20)
Happy to help.
(12 Oct '15, 18:42)

i am getting wa in only one subtask out of 14 .i am not able to figure out the cause.please help. my code is here https://www.codechef.com/viewsolution/8456023 answered 12 Oct '15, 18:05
1
@sid9406 Change "long int" to "long long int"
(12 Oct '15, 18:28)
@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
(12 Oct '15, 18:36)
thank you very much ,it worked
(12 Oct '15, 22:36)

Hello, I am a newbie here and never played with DP or modulus thing before. So i learned about modulus from somewhere and implemented this solution. Its getting WA on some cases. I think there is some problem with my 10^9+7 implementation. Can anyone please figure it out? I would be so thankful answered 12 Oct '15, 18:59
just try adding mod where you are using subtraction at each step :). Mine was the same mistake.
(12 Oct '15, 21:57)

Can anyone tell what was the problem with my solution? Was able to pass few files of 2nd and 3rd subtask.Tried alot to get pass all the files,but i think some problem with modulo operation.Please tell me where was I missing something..here's my solution.Would be very thankful. answered 12 Oct '15, 21:44
Well,i found my mistake by reading above comments.I'm a total fool,should have added mod while performing subtraction where ever required.
(12 Oct '15, 21:55)

I am getting WA in only one of the test cases. I am really stuck. I have tried almost everything. Somebody please help. Here's the link to my code.. https://www.codechef.com/viewsolution/8534532 answered 12 Oct '15, 21:59

Can anyone plz take a lokk at my solution, i am getting WA in just one testcase. https://www.codechef.com/viewsolution/8520392 answered 12 Oct '15, 22:42
@fkhan_iitbhu As stated above please change int to long long int since large values of int cause overflow and then try again. :)
(12 Oct '15, 23:31)

@atulshanbhag could you please tell me the reason for use long long everywhere in fkhan_iitbhu solution. Where his solution is getting an overflow. answered 12 Oct '15, 23:25

This was my First DP problem. Thanks to Problem Setter, this was really an amazing problem! :) answered 13 Oct '15, 00:28

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? answered 13 Oct '15, 12:21
Just add modulo everywhere because there can be overflow. AC code  https://www.codechef.com/viewsolution/8537624
(13 Oct '15, 13:10)
Thank you so much. Now I finally understand why I was getting a WA.
(25 Oct '15, 19:27)

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... https://www.codechef.com/viewsolution/8434494 answered 13 Oct '15, 19:44

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 https://www.codechef.com/viewsolution/8370715 .It would be a great help,as this is the first time I got some points in a DP question :) answered 14 Oct '15, 22:33

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 ? answered 25 Oct '15, 19:11
solved it with much simpler approach... https://www.codechef.com/viewsolution/8637581
(25 Oct '15, 20:15)

Getting wrong answer only at one of the parts of subtask 3 https://www.codechef.com/viewsolution/9015974 Any help would be appriciated answered 25 Dec '15, 20:18
Hey I tried to use long long int instead of long int in your code at some places and it gave 100pts. There was an overflow in your code. https://www.codechef.com/submit/complete/9019061
(26 Dec '15, 13:12)

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 (K1) 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[K1][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(C) 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. answered 26 Dec '15, 00:52

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 (K1) 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[K1][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(C) 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. answered 26 Dec '15, 00:53

Hi,
Can someone please tell me why my code is failing only in the second last testcase? https://www.codechef.com/viewsolution/8549224
Thanks :)