KSPHERES - Editorial

Problem Link

Practice

Contest

Difficulty

Easy

Pre-requisites

Dynamic programming

Problem

Count the number of ways to construct a sequence of nested spheres

How to get 40 points

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

How to get 100 points

The 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][R-1] + F[K-1][R-1]. 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(C2), which fits for our problem.

Setter’s Solution

Can be found here

Tester’s Solution

Can be found here

1 Like

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…

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

4 Likes

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.

I solved it without using DP.Only by Simple logic.

My code is here

Solved like ad-hoc problem.

1 Like

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

@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

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

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 :slight_smile:

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

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

test cases were very weak. i tried to score 40 points with this https://www.codechef.com/viewsolution/8428857 but instead got 100.

2 Likes

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.

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.

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

@torque (a-b)%m is NOT (a%m - b%m)%m instead it is (a%m - b%m + m)%m

thank you very much ,it worked

//