My solutions seems to work for the inputs I give, but I’m getting WA as the result when I submit. Can someone please help? Here’s a link to my solution:
CodeChef: Practical coding for everyone
I am getting WA in the following code. I tried most of the possible test cases and it is giving the correct answers but getting WA still. Can someone help me, what I am missing ?
Thanks in advance 
link to code : CodeChef: Practical coding for everyone
i am not getting why maximum difference is 100 it should be 99 because if we start from 1 and difference is 99 then next number is 100 but otherwise next number will be 101 which is out of range ??
can you tell me where i am getting WA
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
ll a[200001],dp[200001];
ll fastexp(ll x, ll y){ll a=1;while(y>0){if(y&1)a=(ax)%mod;y=y>>1;x=(xx)%mod;}return a;}
int main()
{
ios_base::sync_with_stdio(false);
int t,i,j;
ll cur,res,n;
cin>>t;
while(t–)
{
cin>>n;
for(i=0;i<n;i++)
{
cin>>a[i];
}
res=0;
for(i= -99;i<=99;i++)
{
ll sum[101]={0};
dp[0]=1;
sum[a[0]]=1;
cur=1;
for(j=1;j<n;j++)
{
if((a[j]-i)>=1 && (a[j]-i)<=100)
{dp[j] = (sum[a[j]-i]+1);
if(dp[j]>=mod)dp[j]%=mod;}
else
dp[j]=1;
sum[a[j]] = (sum[a[j]] + dp[j]);
if(sum[a[j]]>=mod)sum[a[j]]%=mod;
cur = (cur + dp[j]);
if(cur>=mod)cur%=mod;
}
res = (res + cur);
if(res>=mod)res%=mod;
res = (res - n);
}
res = (res + n);
if(res>=mod)res%=mod;
res = (fastexp(2,n)-1-res);
cout<<res<<endl;
}
return 0;
}
slight error: make it 2^n-1 instead of n^n -1.
8 Likes
Please update the links to Author’s and Tester’s solution.
that’s not a “slight error” !!!
1 Like
Well in mathematical terms, no, but i merely meant it in terms of the number of characters he got wrong.
The complexity given is for a single test case .
there is also O(100*N) solution. This can be done in a much faster way.
You can make it even more faster by fast exponentiation.
So, the time limit is not strict at all
It is due to the way compiler works…
i also asked for the same here:
http://discuss.codechef.com/questions/44751/c11-just-a-pretty-face
@sansid There were many more optimisation that remove tle
like summing up the ans after all operation would be 100*200 which is 10 times faster than doing it after each modification.
Also you can use int here instead of long long. Using int my time was reduced by half.
long long int was giving me tle…changing to int gives AC
2 Likes
The time complexity should not depend upon the usage of int/long long int. Ideally the questions should focus on algorithmic or logical details rather than other things.
4 Likes
@dpraveen i am not able to understand why “sum” array is not set to 0 for each diff in the psuedo-code. Someone please explain this because even in editorial it is not mentioned that sum should be set to 0 for each diff, but sum[x] is supposed to contain sum of dp[i]'s such that A[i]=x for a particular value of diff.
the recursive dp was giving me TLE. changing it to a bottom up implementation got me AC
Just tried it practice section and it works!
Thanks Ayush… I could not have guessed it.