You are not logged in. Please login at www.codechef.com to post your questions!

×

Showing Wrong Answer despite of correct output.

Here is my code to the question

#include<stdio.h>
#include<math.h>
    long int A[100005];
    long int sum;
int main(){
   int t,n,i,j;
   scanf("%d",&t);

   while(t--){
        sum=0;

        scanf("%d",&n);
        for(i=0;i<n+1;i++)
            scanf("%ld",A+i);
        for(i=0;i<=n;i++){
            for(j=i+1;j<=n;j++){
                if(i!=0){

                sum=sum+(A[i]*A[j]*pow(2,n+i-j));
                }
                if(i==0)
                    sum=sum+(A[i]*A[j]*pow(2,n+1-j));

            }
        }
        printf("%ld\n",sum);
   }
}

Please help me to find the fault in my code.

asked 04 Sep '17, 22:11

namanjn's gravatar image

4★namanjn
53
accept rate: 0%

edited 05 Sep '17, 18:56


sum=sum+(A[i]*A[j]*pow(2,n+i-j));

n in range of upto ${10}^{5}$ is bound to give you overflow (and hence WA) in sum=sum+(A[i]*A[j]*pow(2,n+i-j));

Read up fast exponentiation, or store the power of 2%mod in an array and use accordingly.

link

answered 04 Sep '17, 23:23

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

@vijju123 In the question there is a line that say: Since the answer can be very large, print the answer modulo 10∆9 + 7. What does it mean.

(05 Sep '17, 14:15) namanjn4★

It means that answer can be as large as ${2}^{100000}$ . Since we cannot store such numbers in conventional data types, we take remainder of the number when divided by ${10}^{9}+7$. Read about properties of % operator. The multiplication and addition properties of it (i.e. (a+b)%m=(a%m+b%m)%m and a*b%m=((a%m)*(b%m))%m can prevent overflow issues. What we have to do is, that at every step, every time we update sum, we do sum%mod , where mod = ${10}^{9}+7$. It is just a random large number given to make sure you dont suffer overflow. Since we do sum%mod at every step, it never exceeds mod

(05 Sep '17, 15:52) vijju123 ♦♦5★

@vijju123 But it is showing wrong answer even for subtask n<10

(05 Sep '17, 19:00) namanjn4★

cause ${A_i}$ is ${10}^{9}$ even for smaller subtask

(05 Sep '17, 19:22) vijju123 ♦♦5★

@vijju123 can you please guide me how should i update my code to get it solved.I have tried some changes but its still showing wrong answer.

(05 Sep '17, 22:23) namanjn4★

Its best to look at editorialist's solution first, because I havent attempted the question yet. If a doubt persists after that, I will happily help :)

(05 Sep '17, 22:43) vijju123 ♦♦5★
showing 5 of 6 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,475
×1,664
×1,491
×856
×139
×15

question asked: 04 Sep '17, 22:11

question was seen: 941 times

last updated: 05 Sep '17, 22:43