Permutation Minimize Product#12340

Permutation Minimize Product (Editorial)

Problem Author:	Khoi Le
Prepared by:	Khoi Le
Edited by:	Hasan Saleh (MathModel)

Observation : The minimum value is always achieved when either the index distance or the value difference is small.

We want to minimize $V = ∣ p_{i} - p_{j} ∣ \cdot ∣ i - j ∣$ V = |p_i - p_j| \cdot |i - j|. We shall prove that we only need to check $j$ such that $∣ i - j ∣ \leq n$ |i - j| \le \sqrt{n} or $∣ p_{i} - p_{j} ∣ \leq n$ |p_i - p_j| \le \sqrt{n}.

Proof:

Let the minimum product for index $i$ be $ans_{i}$ \text{ans}_i. We can always pick a $j$ such that $∣ p_{i} - p_{j} ∣ = 1$ |p_i - p_j| = 1 (by choosing the value $p_{i} + 1$ p_i+1 or $p_{i} - 1$ p_i-1). Since $∣ i - j ∣ < n$ |i - j| < n, it follows that $ans_{i} < 1 \cdot n = n$ \text{ans}_i < 1 \cdot n = n.

Now, suppose there exists an optimal $j$ such that both $∣ i - j ∣ > n$ |i - j| > \sqrt{n} and $∣ p_{i} - p_{j} ∣ > n$ |p_i - p_j| > \sqrt{n}. Then:

∣ p_{i} - p_{j} ∣ \cdot ∣ i - j ∣ > n \cdot n = n

|p_i - p_j| \cdot |i - j| > \sqrt{n} \cdot \sqrt{n} = n

This contradicts our finding that $ans_{i} < n$ \text{ans}_i < n. Therefore, at least one of the factors must be $\leq n$ \le \sqrt{n}. In the implementation, we use $C = 2 n$ C = 2\sqrt{n} to provide a safe constant margin.

#include <bits/stdc++.h>
using namespace std;
#define int long long


void solve(){
    int n;cin>>n;
    vector<int>p(n);
    for(auto &i:p)cin>>i;
    vector<int>mp(n+1);
    for(int i=0;i<n;i++){
        mp[p[i]]=i;
    }
    for(int i=0;i<n;i++){
        //we first look by index
        int c=sqrtl(n)*2;
        int ans=1000'000'000'000LL;
        for(int j=max(0LL,i-c);j<=min(n-1,i+c);j++){
            if(j!=i)ans=min(ans,abs(p[i]-p[j])*abs(i-j));
        }
        //second we look by value of p[i]
        int cur=p[i];
        for(int j=max(1LL,p[i]-c);j<=min(n,p[i]+c);j++){
            if(j!=cur){
                ans=min(ans,abs(j-cur)*abs(mp[j]-mp[cur]));
            }
        }
        cout<<ans<<" ";
    }
    cout<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t=1;cin>>t;
    while(t--) solve();
}

C++