TPRODUCT - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

The statement has directly shown the way to solve (by formulas) the problem, but it is not very easy to do since the result could be a very large number. It is hardly to use big-number calculating to fit the given time-limit. The problem needs only the result by modulo of 1,000,000,007 but we can not compare the numbers by their remainders.

Fortunately we have an effective way to solve it by combining some mathematical theories as follows:

  • At first, we can store the value of P_i by storing its logarithm instead;
  • Then instead of doing a lot of multiplications (which causes very large results), we just do a series of additions between their logarithms (which are quite small real numbers);
  • At last, we do tracing and calculate the needed result by modulo of 1,000,000,007; this work does not need big-number processing since we can take the remainders after every multiplication.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2 Likes
2

When i am running this code on my computer its giving the correct o/p. but at the time of submission in codechef its giving wrong answer. plz correct me out.

#include <stdio.h>
typedef unsigned long int BIG;
BIG power(BIG,BIG);
int main()
{
BIG h,h1,i,arr[32770];
while(1)
{
scanf("%lu",&h);
if(h==0)
break;

	h1=power(2,h);
	for(i=1;i<=h1-1;i++)
	scanf("%lu",&arr[i]);

 for(i=power(2,h-1)-1;i>=1;i--)
 {
 if(arr[2*i]>=arr[2*i+1])
 arr[i]*=arr[2*i];
 else
 arr[i]*=arr[2*i+1];

 arr[i]%=1000000007;
 }

 printf("%lu\n",arr[1]);

}//while 1
return 0;
}

BIG power(BIG x,BIG y)
{
if(y==0)
return(1);
else
return(x*power(x,y-1));
}

3

The editorial’s trick of using double type for the big integer is problematic when two numbers are very close: they are different as big integers but are rounded to the same value in double.