TPRODUCT: Getting wa

general
, ,
1

I am getting a wrong answer for the practice problem TREE PRODUCT. Can anyone tell me the problem with my solution? It seems to be a pretty straightforward question and I am quite sure the logic I am using is correct…

2

for(;j>=1;j–)
{
long big=max(a[2j],a[2j+1]);
a[j]=((long long)a[j]*big)%MOD;
}
printf("%ld\n",a[1]);

did you try to compute the modulo only at the end ?
because max(mod(a),mod(b)) is different from mod(max(a,b)).

1 Like
3

@cyberax

thanks a lot! I submitted this solution and it got accepted. But I have a small doubt-

I am using two arrays-
i) a long dobule array p, which stores the products without calculating the mod.
ii) a long long array a, which stores the products after calculating the mod.

I dont understand how the array p is dealing with overflow…

4

be careful : long long is an 8-bytes integer, and long double is a 10-bytes float. moreover, the maximum value of Pi is pow(pow(10, 9), 15), which means pow(10, 135), and it fits perfectly in a long double. you probably had luck with float approximations.