Shifting Sort#13066
Hint : since a_i \le 2\cdot 10^5 , the largest possible is , so each index can give at most different values.
Solution:
let \mathsf{val}[i][j] be the value of a_i after shifting it times , and let \mathsf{dp}[i][j] be the minimum cost required to sort the prefix [1 , 2 , \ldots , i] if we used the j_{\text{th}} value for the i_{\text{th}} element , at first fill it with a huge number let it be .
when i=1
\mathsf{dp}[1][j] = j for each (0 \le j \le 18).
otherwise ,since only i-1 matters , let be the number of times we have shifted i-1 , and let be the candidate number of shifts for index .
if \mathsf{val}[i-1][k] \le \mathsf{val}[i][j] , we can sort the prefix , and the cost is
the final answer will be \min(\mathsf{dp}[n][j]) where 0 \le j \le 18.
if equals then it's impossible to sort the array so the answer is .
Time complexity : \mathcal{O}(n \cdot \text{log}^2(\text{max}(a)))
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define F first
#define S second
using namespace std;
const int N = 2e5 + 1;
const int M = 1e9 + 7;
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int tc = 1;
cin>>tc;
while(tc--)
{
int n;
cin>>n;
int a[n+1] , dp[n+1][21];
vector<int>val[n+2];
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
int x = 63 - __builtin_clzll(a[i]) , cur = a[i];
for(int j=0;j<=x;j++)
{
val[i].push_back(cur);
cur *= 2;
if(cur & (1LL<<(x+1)))
{
cur ^= (1LL<<(x + 1));
cur ^= 1;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=20;j++)
{
dp[i][j] = INT_MAX;
}
}
for(int i=0;i<val[1].size();i++)
{
dp[1][i] = i;
}
for(int i=1;i<n;i++)
{
for(int j=0;j<val[i].size();j++)
{
for(int k=0;k<val[i+1].size();k++)
{
if(val[i][j] <= val[i+1][k])
{
dp[i+1][k] = min(dp[i+1][k] , dp[i][j] + k);
}
}
}
}
int ans = INT_MAX;
for(int i=0;i<val[n].size();i++)
{
ans = min(ans , dp[n][i]);
}
cout<<(ans == INT_MAX ? -1 : ans)<<endl;
}
}