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
@fkhan_iitbhu
As stated above please change int to long long int since large values of int cause overflow and then try again.
explain plz
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.
-> now you can understand code.
1 Like
Just add modulo everywhere because there can be overflow.
AC code - CodeChef: Practical coding for everyone
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 …
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
I explained my approach in the code as a separate answer as this didn’t fit comment. Check that out too.
1 Like