include <bits/stdc++.h>
using namespace std; typedef vector vi; void solve() { int n; cin>>n; vi v(n); for(int i=0;i<n;i++)cin>>v[i];
vi ans(n+1,0);
for(int i=0;i<n;i++)
{
ans[i] = 1e9;
for(int j=i-1;j>=0;j--)
{
if(ans[i]<i-j)
break;
ans[i] = min(ans[i],abs(v[i]-v[j])+(abs(i-j)));
}
for(int j=i+1;j<n;j++)
{
if(ans[i] < j-i)
{
break;
}
ans[i] = min(ans[i],abs(v[i]-v[j])+abs(i-j));
}
cout<<ans[i]<<" ";
}
} signed main() { int T; T=1; cin>>T; while(T--) { solve(); } }
Auto comment: topic has been updated by CodeKar (previous revision, new revision, compare).
This Was Yesterday's Atcoder ABC 283's F, Right?
$$$O(n \sqrt{n})$$$
To prove, there is a theorem that says that any permutation can be decomposed into at most $$$O(\sqrt{n})$$$ increasing or decreasing subsequences. Then, for each of those subsequences, the total work done over that subsequence is bounded by $$$O(n)$$$ (sum of distances between neighbpuring indices is at most $$$2n$$$). Then, total work is bounded by $$$O(n \sqrt{n})$$$.
The bound is, in fact tight. If you consider $$$k=\sqrt{n}$$$ and the permutation to be: $$$[1, k+1, 2k+1, \ldots, k^2+1, 2, k+2, \ldots, k^2+2, \ldots, k, 2k, \ldots, k^2]$$$
The solution would do $$$\Omega (k)$$$ work for each $$$i$$$.
Alright. Thanks! By the way is there is any well known name for this lemma or theorem? Can you please share the rigorous proof of it.
It is a consequence of the Erdős–Szekeres theorem (just apply it multiple times). Maybe the result has a special name of its own, but I don’t know it.
$$$O(n^n)$$$