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