This question appeared on HackWithInfy 2022
Problem Statement
You are given an array of length N containing a permutation of the first N natural numbers i.e (1 to N). You are able to apply the following operation at most once.
- Choose any subarray of size K and reverse it.
Return the minimum inversions in the array after said operations.
Note — Inversion in an array is defined as a pair of indices (i,j) such that Ai > Aj and i < j.
Constraints
1 <= N <= 5 * 10^3
1 <= A[i] <= N
1 <= K <= N
Sample Test Case — 1
Arr = [1, 2, 3, 4], K = 2
Ans — 0
Explanation
Array initially has 0 inversions. Hence no need to apply any operations.
Sample Test Case — 2
Arr = [4, 3, 5, 1, 2], K = 2
Ans — 6
Explanation
If we reverse the subarray [4, 3], we get Arr = [3, 4, 5, 1, 2].
The resultant inversion is 6. It is the minimum that we can get.
Sample Test Case — 3
Arr = [1, 4, 2, 3, 5], K = 3
Ans — 1
Explanation
If we reverse the subarray [4, 2, 3], we get Arr = [1, 3, 2, 4, 5].
The resultant inversion is 1. It is the minimum that we can get.
Can anyone solve this problem ???
Firstly note that the only change in the number of inversions is the change in the number of inversions in the subarray that was reversed (since the relative order of other kinds of pairs of elements remains the same). Now using a sliding window and a Fenwick tree, you can find the number of inversions in each subarray of length $$$k$$$ (for both the original array and the reversed array). From there, you can see which subarray is optimal (or if it is optimal to not reverse any subarray).
Thanks a lot for your approach. But I do not know Fenwick trees. Do you have any other approaches in mind ??
You can use pbds to compute the position of an element in a set and find the kth element in a set.
will brute force work?. Generate every subarray of size k using a sliding window. Then apply inversions of an array questions method . I think generating subarray will take O(n) time using sliding window and find an inversion of array O(N log N) which can be passed in 1sec. Try it
With brute force, you can solve it in $$$O(nk)$$$ too. Just look at what the removal of the leftmost element and the addition of the rightmost element contributes to the change in the number of inversions (this can be done in $$$O(k)$$$ per iteration). Your idea will take $$$O(n^2 \log n)$$$ which should ideally not pass.