Constructing the Answer for Sonya and Problem Wihtout a Legend
Recently, I got asked how to do CF713C in $O(n \log n)$ while reconstructing the answer.
It is not too hard to use slope trick to obtain the answer. See the code below. I am too lazy to write explanation.
Code
#include <bits/stdc++.h>
using namespace std;
int n;
int arr[1000005];
int ans[1000005];
priority_queue<int,vector<int>> pq;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
cin>>n;
for (int x=1;x<=n;x++) cin>>arr[x];
for (int x=1;x<=n;x++) arr[x]+=n-x;
for (int x=1;x<=n;x++){
pq.push(arr[x]); pq.push(arr[x]);
pq.pop();
ans[x]=pq.top();
}
for (int x=n-1;x>=1;x--) ans[x]=min(ans[x],ans[x+1]);
long long diff=0;
for (int x=1;x<=n;x++) diff+=abs(arr[x]-ans[x]);
cout<<diff<<endl;
}
But there is another method that yields the construction rather easily.
First, note that is a special case of L1-isotonic regression where the graph is a line.
The general cases have appeared in CF1615H and SRM720 Hard.
This comment by Petr reference two useful papers in dealing with this problem.
- https://www.researchgate.net/publication/220779362_Weighted_isotonic_regression_under_the_L_1_norm is the intended solution to CF1615H
- https://web.archive.org/web/20120714065455/https://web.eecs.umich.edu/~qstout/pap/L1IsoReg.pdf is the intended solution to SRM720 Hard, and the solution we will discuss here.
Briefly, for a L1-isotonic regression problem, we can do divide and conquer in the following way:
- Choose $X$ and $X+\epsilon$.
- Find the minimum cost to change all values into either $X$ or $X+\epsilon$ while satisfying all needed inequalities.
- Then the elements which became $X$ will have final value $\leq X$ in the optimal solution while those elements which became $X+\epsilon$ will have final value $>X$ in the optimal solution. (Proof in the paper)
For our case, since the inequality we need to satisfy is $a_1 \leq a_2 \leq \ldots \leq a_n$, so we can find the minimum in $O(n)$ by checking all cases, since there are only $O(n)$ possible cases when we are only allowed to use $X$ and $X+\epsilon$.
Then we can recurse into the $\leq X$ and $\geq X+\epsilon$ part.
Code
#include <bits/stdc++.h>
using namespace std;
int n;
int arr[1000005];
int ans[1000005];
void dnc(int l,int r,int vl,int vr){
if (vl==vr){
for (int x=l;x<=r;x++) ans[x]=vl;
return;
}
int vm=vl+vr>>1;
int cnt=0;
for (int x=l;x<=r;x++) if (arr[x]>vm) cnt++;
int best=cnt,idx=l-1;
for (int x=l;x<=r;x++) {
if (arr[x]<=vm) cnt--;
else cnt++;
if (cnt<best){
best=cnt;
idx=x;
}
}
if (idx!=l-1) dnc(l,idx,vl,vm);
if (idx!=r) dnc(idx+1,r,vm+1,vr);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
cin>>n;
for (int x=1;x<=n;x++) cin>>arr[x];
for (int x=1;x<=n;x++) arr[x]+=n-x;
dnc(1,n,0,1e9+n);
long long diff=0;
for (int x=1;x<=n;x++) diff+=abs(arr[x]-ans[x]);
cout<<diff<<endl;
}
Note that all codes are verified on https://codebreaker.xyz/problem/sonya.