Problem Link:
[contest] (CodeChef: Practical coding for everyone)
Editorialist:
[Shivam Paliya] (paliya_64 | CodeChef User Profile for Shivam Paliya | CodeChef)
Difficulty:
Medium
Prerequisites:
Sorting, DP, greedy
PROBLEM:
we can perform one type of operation: swap any index with given X value such that value at chosen index is greater than X
We have to return minimum number of such operations required to sort the entire array.
Quick Explanation
The main fact that allows us to solve this problem is that the value of x always increases after swaps, and since the resulting sequence should be sorted, the indices of elements we swap with x also increase. So keep swapping iteratively every possible case and if at end array is sorted return count else return -1
Explanation
The above observation is actually enough for us to implement a dynamic programming solution of the form “dp[i, j] where dp[i][j] is the minimum number of actions we have to perform to reach the following situation: the last integer we swapped with X was a[i], and the current value of a[i] is j”. Depending on your implementation, it works either in O(n^3) or in O(n^2).
There exists a much simpler to code greedy solution too considering constraints: Scan the array from left to right until it is sorted, and find the first element such that we can apply the operation to it. The key fact that is required to prove it is that if we can apply an operation to some position, but don’t do it and instead apply this operation to some position to the right of that one, the elements on these two positions are no longer sorted (if we can apply the operation to some position i, then ai>x, but if we apply the operation to position j instead, then after it a[i]>a[j] ). Since we can’t go backward, the resulting array cannot be sorted by any means — that’s why we can’t skip elements in this greedy solution.
Solutions:
Editorialist's Solution
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
int t=1;
cin>>t;
while(t--){
ll n,x,cnt=0;
cin>>n>>x;
ll arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
if(is_sorted(arr,arr+n));
cout<<0<<endl;
else{
for(int i=0;i<n;i++){
if(is_sorted(arr,arr+n)){
break;
}
if(arr[i]>x){//greedily choose what comes
swap(arr[i],x);
cnt++;
}
}
if(!is_sorted(arr,arr+n))
cout<<-1<<endl;
else cout<<cnt<<endl;
}
}
}
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int n, x;
cin >> n >> x;
vector<int> a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
if(is_sorted(a.begin(), a.end()))
{
cout << 0 << endl;
continue;
}
vector<vector<int>> dp(n, vector<int>(501, int(1e9)));
for(int i = 0; i < n; i++)
{
if(a[i] > x && (i == 0 || a[i - 1] <= x))
dp[i][x] = 1;
if(i < n - 1 && a[i] > a[i + 1])
break;
}
int ans = int(1e9);
for(int i = 0; i < n; i++)
for(int j = 0; j <= 500; j++)
{
if(dp[i][j] == int(1e9))
continue;
if(i == n || (j <= a[i + 1] && is_sorted(a.begin() + i + 1, a.end())))
ans = min(ans, dp[i][j]);
bool good = true;
for(int k = i + 1; k < n; k++)
{
int pr = k == i + 1 ? j : a[k - 1];
if(good && a[i] >= pr && a[i] < a[k])
dp[k][a[i]] = min(dp[k][a[i]], dp[i][j] + 1);
good &= a[k] >= pr;
}
}
if(ans == int(1e9))
ans = -1;
cout << ans << endl;
}
}