PROBLEM LINK:
Author: Sidhant Bansal
Testers: Hasan Jaddouh
Editorialist: Sidhant Bansal
DIFFICULTY:
medium
PREREQUISITES:
dynamic programming
PROBLEM:
Observation - A dp solution would work because let us say that we have computed the best answer for the subarray i + 1 to (n - (i + 1) + 1) then if want to extend this answer for the subarray i to (n - i + 1) (i.e adding a single element on both sides) then we only need the information wether i + 1 was swapper or not and the information that weather i will be a local maxima/minima.
First for notation let us now use rev(i) = n - i + 1 in the following explanation for simplicity.
This leads us to the dp state -
dp(index, isLocalMaxima, isSwapped) = the minimum no. of swaps required to make the subarray from index to rev(index) a valid subarray where isLocalMaxima (a boolean) denotes wether index is a local maxima or not and isSwapped (a boolean) denotes wether index is swapped with rev(index) or not.
So our final answer would be min(dp(1, 0, 0), dp(1, 0, 1), dp(1, 1, 0), dp(1, 1, 1)), i.e all possibilites of dp states which consider the array from 1 to N.
Now the recurrence forming is hard in this question mainly due to the exhaustive casework.
Firstly for N = even and N = odd, then also for the different conditions of booleans (isLocalMaxima, isSwapped).
Let me demonstrate one of these cases and I expect the reader to form the others in a similar way.
Example -
N = 10 (even)
We have to calculate let us say dp(3, 1, 1). Then dp(3, 1, 1) = answer for subarray from 3 to 8 where the current element(i.e 3 and 8) are swapped and currently 3rd element (after swapping) is the local maxima. Since n is even, so 3 is mapped to 8, where 3 is an odd number and 8 is an even number. This implies that if 3rd element (after swap) is a local maxima then 8th element (after swap) is a local minima.
So here this state is dependent upon 2 cases - (In every case 3rd element is swapped and it is the local maxima, since isLocalMaxima = 1, isSwapped = 1, ).
Case 1 - 4th element is SWAPPED, called if A[rev(3)] > A[rev(4)] and A[3] < A[4]
Case 2 - 4th element is NOT SWAPPED, called if A[rev(3)] > A[4] and A[3] < A[rev(4)]
So here the dp(3, 1, 1) = 1 + min(case1, case2), where we trigger these cases only if the satisfy the conditions and add a +1 because we are swapping the 3rd element.
Here the base cases for N = even, will be filling dp[n/2][a][b], for a = 0 and 1, and b = 0 and 1.
Incase N = odd, we would be filling dp[(n + 1)/2][a][b], for a = 0 and 1, and b = 0 and 1.
Please refer to the author solution for better clarity regarding the base cases and case work. In author solution isUp is equivalent to isLocalMaxima and the satisfy(a, b, c) function checks if the elements a and b satisfy the inequality when a is placed just one index before b and it is the local maxima if c = 1, and a local minima when c = 0.