Why am I getting a WA for one test case in the question SUBINC? I get AC for all other test cases.

general
1

Here is the code. The link to the problem statement is https://www.codechef.com/problems/SUBINC

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<set>
#include<vector>
#include<utility>

using namespace std;

int main() {

    int t, n;
    int ar[100004];
    cin>>t;

    while ( t-- ) {
        cin>>n;

        int lindex,rindex;
        for ( int i = 0; i < n; i++ ) {
            cin>>ar[i];
        }

        int res = n;

        rindex = 0;
        lindex = 0;
        while ( ( rindex < (n-1) ) && lindex <  (n-1)  ) {
            if ( ar[rindex] <= ar[rindex+1] ) {
                rindex++;
            }
            else {
                if ( lindex == rindex ) {
                    lindex++;
                    rindex++;
                }
                else {
                    int diff = rindex - lindex;
                    res += ( ( (diff) * (diff+1 ) ) / 2 );
                    lindex = rindex+1;
                    rindex = lindex;
                }
            }
        }
        if ( rindex == (n-1)  ) {
            if ( lindex < rindex) {
                int diff = rindex - lindex;
                res += ( ( (diff) * (diff+1 ) ) / 2 );
            }
        }

        cout<<res<<endl;
    }

    return 0;
}
1 Like
2

Can someone please provide a sample test case that would cause my program to fail???

3

You can use my code to generate test cases. After posting this comment I will go through your code.

https://www.codechef.com/viewsolution/8300004

1 Like
4

Here is your debugged code :wink:

 #include < iostream >

using namespace std;

int main() {

    long long int t, n;      //long long is used for only one test case
    long long int ar[100004];
    cin>>t;

    while ( t-- ) {
        cin>>n;

        long long int lindex,rindex;
        for ( long long int i = 0; i < n; i++ ) {
            cin>>ar[i];
        }

        long long int res = 0;     //initialized as 0 instead of n

        rindex = 0;
        lindex = 0;
        while ( ( rindex < (n-1) ) && lindex <  (n-1)  ) {
            if ( ar[rindex] <= ar[rindex+1] ) {
                rindex++;
            }
            else {
                if ( lindex == rindex ) {
                    lindex++;
                    rindex++;
                    res++;       //when there is only one element in a non-decreasing                                                                                        
                                 //subsequence, then value of res should be increased by 1
                }
                else {
                    long long int diff = rindex - lindex + 1;   //there should be +1 (why?)
                    res += ( ( (diff) * (diff+1 ) ) / 2 );
                    lindex = rindex+1;
                    rindex = lindex;
                }
            }
        }
        if ( rindex == (n-1)  ) {
            if ( lindex < rindex) {
                long long int diff = rindex - lindex + 1;    //again, a +1 (why??)
                res += ( ( (diff) * (diff+1 ) ) / 2 );
            }
            else{
            	res++;    //increased by 1 if only the last element at index (n-1) is left
            }
        }

        cout << res << endl;
    }

    return 0;
}

```
1 Like
5

I have used comments in the lines where I have changed something in your code. Hope that will help you. And I have tested this edited code so, it will definitely give AC. Happy Coding :slight_smile: .

6

@debjitdj, after seeing your answer, I tried one thing, I made just one modification to the code that was previously giving wrong answer. I replaced the int diff; with long long int diff; and now I get all test cases accepted. Looks like the variable diff was not able to handle large difference earlier given that it was only a int before, but now it can. Thanks. Your answer helped me realize the mistake and get AC.

7

Ok! That’s cool. :slight_smile: