2

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 Ai and Ai+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 A1, A2,…,AN 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 ≤ 105
  • 1 ≤ Ai ≤ 109
  • Sum of N over all test cases do not exceed 2⋅105

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

enter image description here

Improve this question
4
  • Is your code working well always, but failing in some test cases nevertheless? Commented Apr 23, 2022 at 17:20
  • Actually I have tried with the given and some custom test cases and it's working. But when I am submitting the code it passes 4 out of 7 subtasks and getting WA in another 3 subtasks. Commented Apr 23, 2022 at 17:28
  • 1
    What if you try with 3 1 2? Commented Apr 23, 2022 at 17:29
  • 1
    My point is that if you compare 3 and 1, you get a failure and then if you compare 1 with 2, it is not failing, yet 3 is greater than 2 as well, therefore it should fail. Your algorithm does not tackle this case. You also compare the earlier elements again and again... Commented Apr 23, 2022 at 17:34

3 Answers 3

Reset to default
2

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

#include <stdio.h>

int main() {
    int failCount = 0, i = 1, n = 3;
    int ara[3] = {3, 2, 1};
    int prevMax = ara[0] - 1;
    while ((failCount < 2) && (i < n)) {
        if (ara[i - 1] > ara[i]) {
            failCount++;
        }
        if (failCount < 2) {
            if ((i > 1) && (prevMax > ara[i])) failCount++;
            if (prevMax < ara[i - 1]) prevMax = ara[i - 1];
        }
        i++;
    }
    printf("%d", failCount);
    return 0;
}

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.

Sample tests

2 0 1

enter image description here

Improve this answer
Sign up to request clarification or add additional context in comments.

13 Comments

@chqrlie 3 2 1 must be a NO, because the single swap that you propose is between the 0'th and the 2'nd element, which are not neighbors. It is a pseudo-sorted set according to the definition if you can convert it to a sorted set by swapping two neighbors once at most. In the case of 3 2 1 you can achieve that with a single swap, but not between neighbors.
my bad, I misread the assignment.
I'm afraid your implementation is not strict enough: 1 2 0 should output NO. Furthermore, there is no useless inner loop, nor any real performance issue. One could get rid of the array keeping only the last 3 values read and avoid converting the remainder of the line once a failure has been identified, but such optimisations seem off topic.
@chqrlie thank you for your observations, I have made adjustments to my answer's wording and code.
int prevMax = ara[0] - 1; does not work for 2 0 3. you should use if (i > 1 && prevMax > ara[i]) failCount++; Furthermore you should perform the swap otherwise prevMax = ara[i - 1]; is incorrect and the next test if (ara[i - 1] > ara[i]) won't test the updated value for ara[i - 1].
|
1

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;
}
Improve this answer

2 Comments

"Your code produces a value of 2 for count, but swapping A1 and A3 gets the array sorted so the answer should be YES instead of NO." This is not an option in this task, because the pseudo-sorted set is defined by a maximum of one swap of neighbors (!), yet, in the case of 3 2 1 the single swap that you proposed is not between neighbors. Relevant quote from the specification: "Choose an i such that 1≤i≤N−1 and swap Ai and Ai+1" (in the context of what is a valid way to convert a pseudo-sorted set to a sorted one)
@LajosArpad: you are correct. i misread the assignment.
0

There is no way to avoid scanning the whole array to make sure that there is no more than one inversion. If we find an inversion, we also need to check if a swap will restore non-decreasingness. I guess that the code below does a minimum of comparisons.

int i;

// Detect the first inversion, if any (b is always a[i-1])
b= a[0];
if (b > ara[1]) {
    i= 1;
}
else {
  b= a[1];
  for (i= 2; i < n; b= ara[i], i++) {
    if (b > ara[i]) {
      // If b = a[i-1] will cause a non-decreasing sequence, fail
      if (ara[i-2] > ara[i])
        return false;
      else
        // The swap might fix the inversion
        i++;
        break;
    }
  }
}

// Detect the second inversion, if any
for ( ; i < n; b= ara[i], i++) {
  if (b > ara[i]) {
      // There is a second inversion, fail
      return false;
  }
}

return true;

There is a subtlety: when a first inversion is found, we check if ara[i-2] <= ara[i], but not ara[i-1] <= ara[i+1]. In fact, we leave this second test to the detection of a second inversion, with b still ara[i-1] and continuing from ara[i+1].

We also handled the first two elements differently, to avoid ara[i-2] being undefined.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.