WA in PUCMM210 (@aditya_kakarot)

[daft_wullie]

Problem PUCMM210
Separated from previous thread.

[quote="daft_wullie"]You're welcome. I love to help where I can - which isn't that much

#include<stdio.h>
int main()
{
      int t,n,i;
      scanf("%d",&t);
      while(t>0)
      {
                int s=0;
                scanf("%d",&n);
                for(i=n;i>0;i--)
                {
                                s+=(n-i+1)*i*i*i;
                                if(s>1000000003)
                                s=s%1000000003;
                }
                printf("%d\n",s);
                t--;
      }
      return 0;
}

Pls help!![/quote]

The issue is not the modulo operation. Didn't you check? Your code works fine for test cases 113, 114, 115, ...

You should think about overflow problems. What will your code do for test cases near the upper limit? i*i*i might be a huge number

And: it is possible to calculate the result directly, without iterating. You may want to seach the internet for formulas of "Series Sums of the Powers"...

[aditya_kakarot]

Problem PUCMM210

The issue is not the modulo operation. Didn't you check? Your code works fine for test cases 113, 114, 115, ...

Really !! Sorry to waste your time.. Actually iam new to programming and don't know anything beyond arrays,strings and pointers.
But how to check ??
I mean to say,that how can i calculate the exact value of f(113). I just know the value iam getting from my code, how do i crosscheck?? 1^3+2^3+......113^3 is too long to calculate even with calculator.

You should think about overflow problems. What will your code do for test cases near the upper limit? i*i*i might be a huge number

And: it is possible to calculate the result directly, without iterating. You may want to seach the internet for formulas of "Series Sums of the Powers"...

So the actual mistake is i didn't considered Overflow Problems . Right ?? Actually I thought a simple logic would solve this problem, thought nothing beyond that.

[aditya_kakarot]

Problem PUCMM210

You should think about overflow problems. What will your code do for test cases near the upper limit? i*i*i might be a huge number

And: it is possible to calculate the result directly, without iterating. You may want to seach the internet for formulas of "Series Sums of the Powers"...

Hey i have searched on sums of power, but i really can't understand what's different in them.
For eg: In the current problem, the statement should be:

s=( n * n * (n+1) * (n+1) * (n+1) / 4)  -  ( n * (n+1) * (2*n+1) * (3*(n)*(n) + (3*n) - 1)) / 30;

i.e Sum.[ m^3 * (n+1-m) ]
i.e ( (n+1) * Sum.[m^3] ) - Sum.[m^4]
which is huge indeed !!
not even in the range of long long int.
*Sum. stands for Summation.

[daft_wullie]

[quote="aditya_kakarot"]

s=( n * n * (n+1) * (n+1) * (n+1) / 4)  -  ( n * (n+1) * (2*n+1) * (3*(n)*(n) + (3*n) - 1)) / 30;

i.e Sum.[ m^3 * (n+1-m) ]
i.e ( (n+1) * Sum.[m^3] ) - Sum.[m^4]
which is huge indeed !!
not even in the range of long long int.
*Sum. stands for Summation.[/quote]
You are right, these expressions give results which might exceed the range of long long ( I didn't check this.). That's one reason for me to love Python, which is unlimited in the range of integer values
I suppose now it is time to come back to the area of modulo arithmetics. There are rules for modulo operations, like (a+b)%c = (a%c + b%c)%c, which help to avoid overflows.