PROBLEM LINK:
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.
