I recently came across problem 1861D and I'm having trouble understanding the solution provided by one of the users . The solution is given below:
Link to question -> ((http://codeforces.net/contest/1861/problem/D)
#include<bits/stdc++.h>
using namespace std;
int t,n,a[200005];
int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int ans=INT_MAX,a2=0,a1=0;
for(int i=1;i<n;i++)if(a[i]>=a[i+1])a2++;
ans=min(ans,a2);
for(int i=1;i<n;i++){
if(a[i]>=a[i-1])a1++;
if(a[i]>=a[i+1])a2--;
ans=min(ans,a2+a1);
}
cout<<ans<<"\n";
}
return 0;
}
Could you please explain how this solution works? Specifically, I'm having trouble understanding the logic behind the a1 and a2 variables and how they are used to calculate the minimum number of operations needed to sort the array in strictly ascending order.
Auto comment: topic has been updated by maverick_2003 (previous revision, new revision, compare).
If we want to sort the entire array in positive ascending order, we can do the following greedy strategy: if $$$A_i \le A_{i+1}$$$, then we multiply the range $$$[i+1, N]$$$ by some large positive integer (the actual value of $$$x$$$ doesn't matter). In the code provided, the # of moves required for this greedy strategy is $$$a2$$$.
Since we can also use negative values of $$$x$$$, we might want some prefix of the array to become negative, and the remaining suffix positive. We can just do the reverse of the previous greedy algorithm, and find the # of moves needed to make the array strictly decreasing (Increase the range $$$[1,i]$$$ whenever $$$A_i \le A_{i+1}$$$). This is the value $$$a1$$$ in the solution provided. The # of moves needed for a descending array is equivalent to a negative ascending array: we can just assume that our last value of $$$x$$$ was $$$-x$$$.
In the code above, the author decrements $$$a2$$$ while computing $$$a1$$$. This means that at any given position $$$i$$$, the value $$$a1$$$ represents the # of moves needed to sort $$$[1, i]$$$ in negative ascending order, the value $$$a2$$$ represents the # of moves to sort $$$[i+1,N]$$$ in positive ascending order, and the total # of moves is just $$$a1+a2$$$. The optimal answer can then be found taking the minimum value of $$$a1+a2$$$ throughout this iteration.
But i have one slight doubt while calculating a1 don't you think you will have to make all the prefix elements negative , like you can't have some parts of elements of array which are negative , so why a1 is only incremented when a[i]>=a[i+1] , also if you are making prefix negative by multiplying it with a negative number then it must be originally in descending order of positive numbers