Wrong answer in DP question SUBINC-->https://www.codechef.com/LRNDSA07/problems/SUBINC

CodeChef-DSA-learners
, , , , ,
1

I checked for each element in array if it is bigger than the previous then add 2 else add 1(being one with only that element) to previous dp.

#include <iostream>
using namespace std;

int main() {
    long int t ;
    cin>>t;
    while(t--){
   long long int i,n;
   cin>>n;
   long long int a[n];
   for (i=0;i<n;i++)
   {
       cin>>a[i];
   }
   long long int dp[n];
   dp[0]=1;
   for(i=1;i<n;i++)
   {
       long long int j,cnt=0;
       if(a[i]>a[i-1])
        {cnt++;}
       cnt++;
       dp[i]=dp[i-1]+cnt;
   }

   cout<<dp[n-1]<<endl;}
	return 0;
}```
2

Try this input : 4 1 2 3
correct answer : 7
your answer : 6

HINT: if (array[i]>=array[i-1]) then dp[i] = dp[i-1]+1, final answer = ∑(all) dp[i]

1 Like
3 
#include <iostream>
using namespace std;

int main() {
    long int t ;
    cin>>t;
    while(t--){
   long long int i,n;
   cin>>n;
   long long int a[n];
   for (i=0;i<n;i++)
   {
       cin>>a[i];
   }
   long long int dp[n],flag1=0,flag=0;
   dp[0]=1;
   for(i=1;i<n;i++)
   {
       long long int j,cnt=0;
       if(a[i]>a[i-1])
        { cnt++;
          flag1=1;
            
        }
        else 
        { 
            flag1=0;
        }
        if(flag1==1 && flag==1)
        {
            cnt++;
        }
       cnt++;
       dp[i]=dp[i-1]+cnt;
       flag=flag1;
   }
cout<<dp[n-1]<<endl;
	}return 0;
}

can you plz tell me now why it is wrong ?
i took one flag variable which increases count for above mentioned cases .

4 
#include <iostream>
using namespace std;

int main() {
    long int t ;
    cin>>t;
    while(t--){
   long long int i,n;
   cin>>n;
   long long int a[n];
   for (i=0;i<n;i++)
   {
       cin>>a[i];
   }
   long long int dp[n],flag1=0,flag=0;
   dp[0]=1;
   for(i=1;i<n;i++)
   {
       long long int j,cnt=0;
       if(a[i]>a[i-1])
        {
            dp[i]=dp[i-1]+1;
        }else
        {
            dp[i]=dp[i-1];
        }
        
   }int sum=0;
for(i=0;i<n;i++)
{
    sum=dp[i]+sum;
}
cout<<sum<<endl;
	}return 0;
}

tried this approach also but still getting wa.

5

First things first, Look at your indentation.
Secondly, cnt can never exceed 3 in your code, however that is not the case.
Can you explain what each increment and if condition is doing.
Here’s your code with proper indentation

#include <iostream>
using namespace std;

int main() {
    long int t;
    cin >> t;
    while (t--)
    {
        long long int n;
        cin >> n;
        long long int a[n];
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        long long int dp[n], flag1 = 0, flag = 0;
        dp[0] = 1;
        for (int i = 1; i < n; i++)
        {
            long long int j, cnt = 0;
            if (a[i] > a[i - 1])
            {
                cnt++;
                flag1 = 1;
            }
            else
            {
                flag1 = 0;
            }
            if (flag1 == 1 && flag == 1)
            {
                cnt++;
            }
            cnt++;
            dp[i] = dp[i - 1] + cnt;
            flag = flag1;
        }
        cout << dp[n - 1] << endl;
    }
    return 0;
}
3 Likes
6 
#include <iostream>
using namespace std;

int main() {
    long int t;
    cin >> t;
    while (t--)
    {
        long long int n;
        cin >> n;
        long long int a[n];
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        long long int dp[n], flag1 = 0, flag = 0;
        dp[0] = 1;
        for (int i = 1; i < n; i++)
        {
            long long int j, cnt = 0;
            if (a[i] > a[i - 1])// this is for  array of size 2;
            {
                cnt++;
                flag1 = 1;
            }
            else
            {
                flag1 = 0;
            }
            if (flag1 == 1 && flag == 1)
            {
                cnt++;//this is for any increasing array at that i (except of size 2)
            }
            cnt++; //this is for single element array 
            dp[i] = dp[i - 1] + cnt;
            flag = flag1;
        }
        cout << dp[n - 1] << endl;
    }
    return 0;
}
7

i got it,my code is wrong thanks !

1 Like
8

//this is for any increasing array at that i (except of size 2)

How can you claim that there is only one at that i.
Consider the test case

1 2 3 4
1 Like
9

yes ,i got it

10

plz help in right approach

11

Let’s go by your dp state. Let dp_i denote the number of subarrays that end before i. We can maintain a variable cnt, that stores the number of increasing subarrays till i. To convert it to i-1 to i, we just need to check if A_i\ge A_{i-1}. If it is, then any increasing subarray that ends at i-1 can be extended to form an increasing subarray till i. There is also a subarray that just contains A_{i}, so we have to add 1. If A_i<A_{i-1}, then there is only one increasing subarray till i, which is A_i itself.
We also know that dp[i]+dp[i-1]+cnt.

Implementation 
#include <iostream>
using namespace std;
int main() {
    long int t ;
    cin>>t;
    while(t--){
        long long int n;
        cin>>n;
        long long int a[n];
        for (int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        long long int dp[n];
        dp[0]=1;
        int cnt=1;
        for(int i=1;i<n;i++)
        {
            cnt++;
            if(a[i]<a[i-1]){
                cnt=1;
            }
            dp[i]=dp[i-1]+cnt;
        }
        cout<<dp[n-1]<<endl;
	}
	return 0;
}
2 Likes
12

thanks a lot!