MAXPR - Editorial

editorial
, , , , ,
22

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 :slight_smile:

link to code : CodeChef: Practical coding for everyone

23

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 ??

24

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;

}

25

why I am getting wrong answer link text

26

why i am getting wrong answer for CodeChef: Practical coding for everyone

27

slight error: make it 2^n-1 instead of n^n -1.

8 Likes
28

Please update the links to Author’s and Tester’s solution.

29

that’s not a “slight error” !!!

1 Like
30

Well in mathematical terms, no, but i merely meant it in terms of the number of characters he got wrong.

31

The complexity given is for a single test case .

32

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

33

@dpraveen what was the benefit of choosing limit of N as 2*10^5 instead of 10^5?

34

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

35

@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.

36

long long int was giving me tle…changing to int gives AC

2 Likes
37

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
38

@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.

39

the recursive dp was giving me TLE. changing it to a bottom up implementation got me AC

40

Just tried it practice section and it works!
Thanks Ayush… I could not have guessed it.

41

You are using pow(2,n) to calculate the value of total no of sub-sequences possible. Since
1<=n<=200000, 2^n will be a very huge number. You need to calculate it using fast exponentiation and keep a check when its value becomes more than 10^9+7. The no. of arithmetic progressions possible can also be greater than 10^9+7, so while calculating it keep a check on it also. Your program requires a lot of mod operations. Also long long int might give you TLE, change variables within range to int data type.

1 Like