REVSORT Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Tejas Pandey
Tester: Abhinav Sharma, Nishank Suresh
Editorialist: Pratiyush Mishra

DIFFICULTY:

1288

PREREQUISITES:

None

PROBLEM:

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 most X. 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 most X.

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.

We can use a set here to store the sorted array.

TIME COMPLEXITY:

O(NlogN), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

2 Likes

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”.

else if (maxval <= A[i])
maxval = A[i]

4 Likes

@gtushar2000
can you please tell me whats wrong in my solution . Its the same concept .
solution → CodeChef: Practical coding for everyone

Cool

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.

1 Like

There was no video solution released for this problem, please add it soon.

I agree, in the question it should be mentioned that we can perform more than one operations. The editorial is based on this only.

It is possible to sort the array

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.

1 Like

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.