WA for multiplication while taking mod.
Here is my code: CodeChef: Practical coding for everyone
You are taking mod at each step instead of at the end
Suppose we look at this tree
3
2 500000004
2 2 2 1
The answer should be 35000000042%1000000007
which will give 3
but your solution will give 12
This happens because we are using max function max does not work with remainders
Example
max(5 , 7) = 7
but if we look mod 3
max(5%3 , 7%3)=max(2,1) = 2 = 5%3
Thus the wrong child is getting picked.
To solve this there are 2 ways.
Method 1: what I did. (Kind of long but extremely satisfying if it works)
Instead of taking long long I used a vector to store numbers.
I basically converted all numbers to base 1000000007 and then stored the ‘digits’.
It was given that H<=15 so maybe 16 digits would have been enough. But i stored 18 just to be safe.
Then i wrote a multiply function and a max function for these 1000000007ary numbers and using that I calculated the exact value of P1. Then I output the rightmost digit which is basically the mod 1000000007 part.
I didn’t expect this to pass the time but it did surprisingly well.
My solution: CodeChef: Practical coding for everyone
Method 2: what the editorial says (lame)
convert everything to logarithms so we can store very big numbers easily then add instead of multiply at each level. and when you get to P1 just take the anti logarithm mod 1000000007.
For the integral part just keep multiplying and take mod 1000000007 at each step and for the decimal part use inbuilt antilog function.
I say this is lame cause how is a person supposed to know if the precision required is achieved by floating point numbers? Better to keep calculations in Integers.
1 Like