Chef is deriving weird ways to sort his array. Currently he is trying to sort his arrays in increasing order by reversing some of his subarrays.
To make it more challenging for himself, Chef decides that he can reverse only those subarrays that have sum of its elements at mostX. Soon he notices that it might not be always possible to sort the array with this condition.
Can you help the Chef by telling him if the given array can be sorted by reversing subarrays with sum at most X.
More formally, for a given array A and an integer X, check whether the array can be sorted in increasing order by reversing some (possibly none) of the subarrays such that the sum of all elements of the subarray is at mostX.
EXPLANATION:
In order to solve this problem we will iterate from right to left and sort array accordingly. Now while doing so say we reach an index i, then there can be two cases :
A_i \leq min(A_{i+1},A_{i+2}....A_n): Nothing needed to be done since array A[i,i+1....n] would already be sorted.
Otherwise we will find position j, such that A_j is the largest element in A[i+1...n] , which is less than A_i. Now eventually we would need to swap A_i and A_j and if their sum is greater than x, then it won’t be possible to perform this swap and hence sort the array. All other swaps would involve elements less than A_j(since it is a sorted array) so if swap of A_i and A_j is possible so all other swaps would also be possible.
O(n) solution:
We traverse the array from left to right and keep track of maximum.
For each element A[i], maxval = maximum of A[0…i-1]
if (maxval > A[i])
this implies they are an inversion that must need swapping, so (maxval + A[i] <= X) must be true, if not then output “NO”.
According to the approach in the editorial and also the solutions, if we take the test case as:
1
4 7
4 3 2 5
The program outputs as “Yes” while the obvious answer is “No”. {4,3,2} sum is 9 while X is 7 so the answer should be “No”. Please make an effort to improve the question and the code. This was pointed out in a YouTube tutorial by a person.
i) 4 3 2 5
ii) 3 4 2 5 by reversing the subarray(3,4) (3+4<=7)
2 4 3 5 by reversing the subarray(3,4,2) but here the sum is greater than 7
iii) 3 2 4 5 so by reversing the subarray(4,2)
iv) 2 3 4 5 and then we will reverse the subarray(3,2)
and the array is sorted
The statement says “by reversing some of his subarrays.”, “by reversing subarrays with sum at most X”, and “by reversing some (possibly none) of the subarrays”. Notice the plural everywhere.
In the step 3, we are reversing a subarray which was not part of the original array, wouldn’t that be counted as a subsequence, also it was not mentioned that we can traverse the array more than once nor something similar was mentioned and here clearly we need to do traverse it again. Making it a problem similar to bubble sort.
Still I hold my comment. Those statements can be thought(with good possibility) as we have to perform swapping of some of the subarrays(from the original array) simultaneously in one operation.
(Plus: I am just sharing my feedback and I accept that many of the participants have been able to understood the required intuition behind the problem.)
Just relate this problem with Bubble Sort. In Bubble Sort we take each subarray of size = 2. If we are able to sort the array given in the input with Bubble Sort with an added constraint of subarray sum to be at most X, then “YES” otherwise “NO”. As simple as that.