Almost Sorted ⬀
Given an array of integers, determine whether the array can be sorted in ascending order using only one of the following operations one time.
- Swap two elements.
- Reverse one sub-segment.
Determine whether one, both or neither of the operations will complete the task. Output is as follows.
- If the array is already sorted, output yes on the first line. You do not need to output anything else.
- If you can sort this array using one single operation (from the two permitted operations) then output
yes
on the first line and then:- If elements can only be swapped,
d[l]
andd[r]
, outputswap l r
in the second line.l
andr
are the indices of the elements to be swapped, assuming that the array is indexed from1
ton
. - If elements can only be reversed, for the segment
d[l...r]
, outputreverse l r
in the second line.l
andr
are the indices of the first and last elements of the subarray to be reversed, assuming that the array is indexed from1
ton
. Hered[l...r]
represents the subarray that begins at indexl
and ends at indexr
, both inclusive. - If an array can be sorted both ways, by using either swap or reverse, choose swap.
- If elements can only be swapped,
- If the array cannot be sorted either way, output
no
on the first line.
arr = [2, 3, 5, 4]
Either swap the 4
and 5
at indices 3 and 4, or reverse them to sort the array. As mentioned above, swap is preferred over reverse. Choose swap. On the first line, print yes
. On the second line, print swap 3 4
.
Complete the almostSorted
function in the editor below.
almostSorted
has the following parameter(s):
int arr[n]
: an array of integers
- Print the results as described and return nothing.
The first line contains a single integer n
, the size of arr
.
The next line contains n
space-separated integers arr[i]
where 1 ≤ i ≤ n
.
2 ≤ n ≤ 100000
0 ≤ arr[i] ≤ 1000000
- All
arr[i]
are distinct.
- If the array is already sorted, output yes on the first line. You do not need to output anything else.
- If you can sort this array using one single operation (from the two permitted operations) then output yes on the first line and then:
- a. If elements can be swapped,
d[l]
andd[r]
, outputswap l r
in the second line.l
andr
are the indices of the elements to be swapped, assuming that the array is indexed from1
ton
. - b. Otherwise, when reversing the segment
d[l...r]
, outputreverse l r
in the second line.l
andr
are the indices of the first and last elements of the subsequence to be reversed, assuming that the array is indexed from1
ton
. d[l...r]
represents the sub-sequence of the array, beginning at indexl
and ending at indexr
, both inclusive.
- a. If elements can be swapped,
- If an array can be sorted by either swapping or reversing, choose swap.
- If you cannot sort the array either way, output
no
on the first line.
STDIN Function
----- --------
2 arr[] size n = 2
4 2 arr = [4, 2]
yes
swap 1 2
You can either swap(1, 2)
or reverse(1, 2)
. You prefer swap.
3
3 1 2
no
It is impossible to sort by one single operation.
6
1 5 4 3 2 6
yes
reverse 2 5
You can reverse the sub-array d[2...5] = "5 4 3 2"
, then the array becomes sorted.