Problem: An array A of length N is said to be pseudo-sorted if it can be made non-decreasing after performing the following operation at most once.

Choose an i such that 1≤i≤N−1 and swap A_i and A_{i 1}

Given an array A, determine if it is pseudo-sorted or not.

Input Format
The first line contains a single integer T - the number of test cases. Then the test cases follow.
The first line of each test case contains an integer N - the size of the array A.
The second line of each test case contains N space-separated integers A₁, A₂,…,A_N denoting the array A.

Output Format
For each testcase, output YES if the array A is pseudo-sorted, NO otherwise.

You may print each character of YES and NO in uppercase or lowercase (for example, yes, yEs, Yes will be considered identical).

Constraints:

• 1 ≤ T ≤ 1000
• 2 ≤ N ≤ 10⁵
• 1 ≤ Ai ≤ 10⁹
• Sum of N over all test cases do not exceed 2⋅10⁵

Sample Input 1:

3
5
3 5 7 8 9
4
1 3 2 3
3
3 2 1

Sample Output 1:

YES
YES
NO

My Solution:

#include <stdio.h>

int main()
{
    int T, N, ara[100000], count, i, j;
    scanf("%d", &T);
    for (i = 0; i < T; i  )
    {
        scanf("%d", &N);
        for (j = 0; j < N; j  )
        {
             scanf("%d", &ara[j]);
        }
        count = 0;
        for (j = 1; j < N; j  )
        {
            if (ara[j] < ara[j - 1])
            {
                count  ;
            }
        }
        if (count <= 1)
        {
            printf("YES\n");
        }
        else if (count > 1)
        {
            printf("NO\n");
        }
    }
    return 0;
}

But, I am getting error in some test cases though my code is working well for the given test cases. Can anyone help me to identify the bug(s)?

CodePudding user response：

There could be two problems with your code or only one. First of all, it might be the case that it fails in some cases and frankly, I did not look into it deeply because of the second problem, which is performance.

You do not need an inner loop.

If you have n numbers in ara, then the algorithm would look like this

int failCount = 0;
int i = 1;
while ((failCount < 2) && (i < n)) {
    if (ara[i - 1] > ara[i]) {
        failCount  ;
        if ((i   1 < n) && (ara[i - 1] < ara[i   1])) failCount  ;
    }
}

//If failCount < 2, then it is pseudo-sorted

I'm aware that you do not want to read all of it, so you need to read the numbers during the loop rather than read all of them before the loop, the code above was a simplified code to illustrate the logic.

Also, you need to consider examples such as

3 1 2

where 3 > 1 and that increases the counter, but later you compare 1 < 2 and it looks to be correct, yet, 3 was greater than 2 as well. This is what my second if is solving.

CodePudding user response：

Your test counts the number of cases where 2 adjacent numbers are out of order. This is not sufficient for the problem. Here is a counter-example:

1
3
3 1 2

3 1 2 produces a count of 1 but requires 2 swaps.

Once you detect an element that is out of order, you must test if swapping it with the previous element fixes the problem:

#include <stdio.h>

int main() {
    int T = 0, ara[100000], count, i, j;
    scanf("%d", &T);
    for (i = 0; i < T; i  ) {
        int N = 0;
        scanf("%d", &N);
        for (j = 0; j < N; j  ) {
            ara[j] = 0;
            scanf("%d", &ara[j]);
        }
        count = 0;
        for (j = 1; j < N && count < 2; j  ) {
            if (ara[j] < ara[j - 1]) {
                int temp = ara[j - 1];
                ara[j - 1] = ara[j];
                ara[j] = temp;
                count  ;
                if (j > 1) {
                    j -= 2;
                }
            }
        }
        if (count <= 1) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

You could get rid of the array and avoid converting the remaining numbers once a failure has been identified:

#include <stdio.h>

int main() {
    int T = 0, i, j;
    scanf("%d", &T);
    for (i = 0; i < T; i  ) {
        int N = 0, n1 = 0, n2 = 0, n3, count = 0, c, temp;
        scanf("%d", &N);
        if (N >= 2) {
            scanf("%d%d", &n1, &n2);
            if (n1 > n2) {
                temp = n1;
                n1 = n2;
                n2 = temp;
                count  ;
            }
            for (j = 2; j < N; j  ) {
                n3 = 0;
                scanf("%d", &n3);
                if (n2 > n3) {
                    count  ;
                    if (count > 1)
                        break;
                    if (n1 > n3) {
                        count  ;
                        break;
                    }
                    n1 = n3;
                } else {
                    n1 = n2;
                    n2 = n3;
                }
            }
        }
        /* read and discard the rest of the line */
        while ((c = getchar()) != EOF && c != '\n')
            continue;
        if (count <= 1) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}