CodeKar's blog

By CodeKar, history, 22 months ago, In English

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(); } }

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by CodeKar (previous revision, new revision, compare).

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This Was Yesterday's Atcoder ABC 283's F, Right?

»
22 months ago, # |
  Vote: I like it +16 Vote: I do not like it

$$$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$$$.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
22 months ago, # |
  Vote: I like it -13 Vote: I do not like it

$$$O(n^n)$$$