KSPHERES - Editorial

editorial
, , ,
27

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

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:

29

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

@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

31

Happy to help.

32

Well,i found my mistake by reading above comments.I’m a total fool,should have added mod while performing subtraction where ever required.

33

just try adding mod where you are using subtraction at each step :-). Mine was the same mistake.

34

thank you very much ,it worked

35

@fkhan_iitbhu
As stated above please change int to long long int since large values of int cause overflow and then try again. :slight_smile:

36

explain plz

37

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
38

Just add modulo everywhere because there can be overflow.
AC code - CodeChef: Practical coding for everyone

39

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

40

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
41

https://discuss.codechef.com/questions/75767/kspheres-editorial/76077

42

thanks alot for a detailed explanation @dragonemperor, though i still need some time to grasp polynomial multiplication better.
awsome work … :slight_smile:

43

Hi,

Can someone please tell me why my code is failing only in the second last test-case?
https://www.codechef.com/viewsolution/8549224

Thanks :slight_smile:

44

Thank you so much. Now I finally understand why I was getting a WA.

45

solved it with much simpler approach…
https://www.codechef.com/viewsolution/8637581

46

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