I feel the point of algorithm contest is not just to teach you algorithms but to code efficiently.
This is one of the questions where we need to consider of the constant factor in time complexity.
The difference between something taking 10 sec and something taking 1 sec could be a matter of considering the constant
In the editorial,dp[i] means all those AP which are ending at ith digit,suppose we consider the sequence 1 2 3
than
dp[1]=1,
dp[2]=1+dp[1]=2,
dp[3]=1+dp[2]+dp[1]=4,
so total numbers of AP which are ending at the i the digit are 4 but we are having {1},{2},{3},{1,2},{2,3},{1,3},{1,2,3} =7 APās.Can anybody explain it??
actually, dp[i] is itself an array, where dp[i][100+d] refers to all those APs ending at the ith place, with d as their common difference.
In the editorial, the dp array is 1d, because they have used it in a loop from 1 to 200(or from -100 to 100 for that matter).
hence, in the first loop, dp[i] represents all the APs ending at ith place, with common difference -100.
so, add dp[i] from 1 to n to get all APs
Hope this makes it clear!
@wiseboy How dp[i] is a 2d array? In the O(n^2) solution, dp[i] denotes number of APās ending at i and they will use the loop 200 times to check all the possible values,so following the above rules my first comment should be correct.can you please elaborate with an example.
Oh, I am really sorry for the misunderstanding on my part!!
I thought you were talking about the O(n) solution.
yes, you are absolutely correct. and even your comment as well as calculation is.
The only problem is, to find all the APs, you have to do
total APs= summation(i=1 to n)dp[i].
Itās because you have to take in account all the APs, i.e., the APs ending at position 1, then at position 2 and so on.
hence, total=dp[1]+dp[2]+dp[3]=1+2+4=7.
Hope it helped! 
Thanks for your help,I got it
can anyone see why am i getting WA
int t,n;
cin >> t;
while (tā) {
cin >> n;
vi was(n);
vi occ(111,0);
for (int i = 0; i < n; i ++) cin >> was[i];
vvl dp(111,vl(222,0));
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
int curr = was[i];
for (int j = -99; j <= 99; j++) {
int prev = curr - j;
if (1 <= prev && prev <= 100) {
//addmod(dp[curr][j+99],dp[prev][j+99]);
dp[curr][j+99] = (dp[curr][j+99] + dp[prev][j+99]) MOD;
if (curr != prev) {
//addmod(dp[curr][j+99],occ[prev]);
dp[curr][j+99] = (dp[curr][j+99] + occ[prev]) MOD;
}
}
}
occ[curr]++;
//addmod(dp[curr][0+99],1);
dp[curr][0+99] = (dp[curr][0+99] + 1) MOD;
}
ll res = 0;
/*for (int i = 1; i <= 2; i++) {
for (int j = -1; j <= 1; j++) {
cout << dp[i][j+99] << " ";
}
cout << "\n";
}
*/
for (int i = 0; i <= 100; i++) {
for (int j = -99; j <= 99; j++) {
res = (res + dp[i][j+99]) MOD;
}
}
ll pos_seq = power(2,n);
res = (pos_seq - res) % MOD;
cout << res << "\n";
}
why the difference is varying from -100 to 100ā¦ i can see the maximum difference should be +99 and minimum should be -99ā¦ can anyone explain ?
1 Like
Can someone please give more test cases ā¦
Can someone please give more test cases ā¦
hi.i tried a different algo which gives the same answer as one of the correct submission gave.but codechef gives a WA wrong answer to my code.someone please help meā¦
this is my codeā¦i can explain the algoā¦iknow only 1 or 2 test cases are going wrong
http://www.codechef.com/viewsolution/4120150
yes, just for the sake of simplicity
1 Like
i really didnt get the optimizationā¦ if some one can explain it using kinda small dp table that will be really very very gratefulā¦ till now i understood that dp[n]= summation_d=-100 to 100 (dp[n-1][d]); cant understand the optimization
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:
http://www.codechef.com/viewsolution/4120414
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 : http://www.codechef.com/viewsolution/4149667
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 ??
@neweffort if you check the if condition you will find that whenever there is out of range the dp[i] = sum[a[i]-diff]+1, will not be executed. The pseudo code may not be exact. I guess that the editorialist was trying to make us understand the logic. So, better understand the logic.
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;
}