ASP - Editorial

PROBLEM LINK:

Practice
Contest

Author: Jingbo Shang
Tester: Xiaoxu Guo
Editorialist: Pushkar Mishra

DIFFICULTY:

Simple

PREREQUISITES:

Ad-hoc

PROBLEM:

Given an array A, output “YES” if the array is sortable by moving the elements at maximum one index from their respective positions, otherwise output “NO”.

EXPLANATION:

The given array is indexed from 1 to N. We maintain an auxiliary array Mark which is initially set to 0.

Now, let us consider the first two elements of the array, i.e., A[1] and A[2]. If A[1] \leq A[2] then we needn’t do anything. However, if A[1] > A[2] then we need to swap A[1] and A[2]. If we swap A[1] and A[2], we change Mark[2] from 0 to 1. Doing so tells us that the element at position 2 wasn’t at this position in the original array.

Next we consider elements at positions A[2] and A[3]. If Mark[2] = 1, this would mean that the element at position 2 actually came from position 1. Since it has already been moved from its position, it can’t be moved to the further right. This tells us that if Mark[2] = 1 and A[2] > A[3], then the array can’t be sorted according to the given rules. On the other hand, if A[2] \leq A[3], then we simply go onto the next pair of elements, i.e., A[3] and A[4]. If Mark[2] = 0 and A[2] < A[3], then we swap A[2] and A[3], change Mark[3] from 0 to 1 and again proceed to considering the next pair of elements, i.e., A[3] and A[4].

This gives us the first part of our algorithm:

func sortable(A)
{
        Mark = {0};

        for (int i = 1 to N-1)
        {
                if (A[i] > A[i+1] and Mark[i] == 1)
                {
                        return false;
                }
                else if (A[i] > A[i+1])
                {
                        Mark[i+1] = 1;
                }
        }

        /* MORE CODE TO BE ADDED. READ ON! */

        return true;
}

The function isn’t complete. It only checks whether the swaps made were valid are not. There is one more thing we need to check before we can return true. After all the swaps have been made and the function hasn’t returned false, we need to check whether the array is actually sorted or not. Thus, the complete algorithm is as follows:

func sortable(A)
{
        Mark = {0};

        for (i = 1 to N-1)
        {
                if (A[i] > A[i+1] and Mark[i] == 1)
                        return false;
                
                else if (A[i] > A[i+1])
                        Mark[i+1] = 1;
        }

        for (i = 1 to N-1)
        {
                if (A[i] > A[i+1])
                        return false;
        }
        
        return true;
}

COMPLEXITY:

\mathcal{O}(N) per test case.

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

1 Like

Same logic in Python NZEC why ?? bcoz of whitespaces ?? it should be rejudged !! or people who were trying to do with python should be given some kind of advantage now !! Bad Test cases…for python

a simpler program…
link

Many people got AC with O(nlogn) algorithm just by using faster io. This should not have happened after the author had written the statement “Please try to write a very efficient algorithm and implementation.”

1 Like

It isn’t a good idea to use very tight limits in such cases, since it’s easy to make efficient solutions fail and inefficient ones pass.

A better approach would be to make the problem interactive in some way, or pack it into something more complex that’d require e.g. a higher degree of log for basic sorting.

2 Likes

My java submission not getting aced.Its giving an NZEC runtime error.The same happened with my python submission.I guess there are unnecessary spaces in input.

JAVA SOLUTION : link

PYTHON SOLUTION : link

But the same idea in C++ getting aced.

C++ SOLUTION : link

Easy Solution…Don’t know why it passed!! soln
Are test cases weak?

1 Like

THE AUTHOR’S SOLUTION IS WRONG.

It fails for the test case 3 1 2.

According to Author’s solution, after the swaps the elements become 1 2 3, which is in sorted order and prints YES, but the number 3 is 2 places away from its position.

8 Likes

Test case are weak
people passed with code like insertion sort with only one swap(which is incorrect)

Running insertion sort with checks
for more than one swap worked too.

Insertion sort runs in almost O(n) for
partially sorted arrays and if you
break when the array is not partially
sorted, the entire code is around O(n)

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

These kind of code fails with input like:
5
5 1 2 3 4
or
5
1 4 2 3 5
etc
@admin look into this

1 Like

why my program is not getting accepted its getting tle
can anyone help me through this?
https://www.codechef.com/viewsolution/8591937

@sashi jey, ans for 1 5 8 is yes but yours soln will show no.
For Tle, use scanf printf and “\n”…

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

This is my solution.Please help , I am getting wrong answer.

Also I saw a correct solution , with a condition [ if(A[i-2]>A[i]) >>>> cout<<“NO”; Flag=1;break;] .

Cant understand why it works , since it gives 4 1 5 2 as Yes where as 4 and 2 are clearly off by 2 positions.
Thanks for help]

@vaibhav1224

Many other solutions are bugged. So dont’ trust them :slight_smile:

Your code fails for the following case:

1

5

1 0 4 2 5

This is funny. I had never seen a problem with so many incorrect solutions being accepted…

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

Getting WA,
Unable to identify the error. Can someone help?

@ash24jal

The idea with your algo is ok, but you have a problem with your iteration.
When you break your iteration on “i”, you don’t read the remaining values. So next time you iterate on “t” you read incorrect values.

Try for instance with the following input.

2

5

10 100 11 12 13

5

1 2 3 5 4

@beroul

thank you so much for identifying that silly mistake…

@beroul You provided cases which includes test cases as this-

1

5

1 0 4 2 5

But as mentioned in constraints 1 <= a[i] <= 10^9
. 0 cannot be a valid input for a[i].

Try this one
https://code.hackerearth.com/4042b6r?key=1f1cb8bcc910e53476316147dba318ea

https://www.codechef.com/viewsolution/13425638 where my code failing …