Reorder a Prefix with Weighted Adjacent Swaps
Autumn Tournament (2022)
Submission name: reorder.cpp
Problem summary
An adjacent swap of values x and y costs x+y. For each independent query R, reorder the array to minimize the sum of swap costs plus A times the sum of its first R values.
Source clarification. The full author approach uses rebuilt hull blocks with line deletion. Complexity is stated honestly in terms of exchanges; no unproved linear bound is assumed.
Input
N Q A, then N positive values, then Q query lengths R.
Output
One minimum total cost per query, in input order.
Constraints
1≤Q,R≤N; 1≤vi,A≤1000000. Full multi-query subtask: N≤50000; single-query subtasks: N≤1000000.
Worked example
Original statement sample.
Input
4 1 6 4 1 2 3 2
Output
29
Solution analysis
- Choose which original elements form the final prefix and preserve relative order within both chosen and unchosen groups. Every inverted chosen/unchosen pair must cross once, paying the sum of its values. Extra swaps cannot help since all values are positive.
- For k chosen indices, expand all crossing costs. If prefix[i] includes vi, choosing index i contributes (A+i-k-1)*vi+prefix[i]. Pairwise interactions among selected indices cancel into the -k*vi term. Therefore the optimum is the sum of the k smallest line values Li(k), where Li(x)=ci+mi*x, ci=(A+i-1)*vi+prefix[i], mi=-vi.
- For a single query evaluate all lines and use nth_element to select the k smallest in expected O(N) time. For multiple queries advance k from1 onward. Insert the cheapest outside line, then exchange the most expensive inside line with the cheapest outside line while that improves the total. On termination the chosen set is exactly a k-smallest set.
- Dynamic line removal is handled by slope blocks. Sort lines by slope, divide into square-root-sized blocks, and build each block’s lower hull of outside lines and lower hull of negated inside lines. Negation turns maximum into minimum. A membership change rebuilds only its own block; querying scans every block and binary-searches its hull. Equal slopes keep the smallest intercept.
- Maintain sums of chosen intercepts and slopes. At x=k the answer is sumIntercept+k*sumSlope. Precompute only through the largest requested prefix length, then answer in input order.
- For the sample, k=2 gives contributions[20,10,19,31]. Indices2 and3 are cheapest, totaling29. Concretely swap4 past1 and2, paying5+6, then pay6*(1+2)=18. Total29 matches the transformed answer.
Why it works
Stability minimizes swaps for a fixed chosen set: each inverted chosen/unchosen pair must cross, and stable partition crosses it exactly once. Algebra gives independent line contributions, so choosing the k smallest is optimal. Every exchange strictly reduces the selected sum. If none is possible, no outside line is cheaper than an inside line, proving that the selected set is k-smallest. Hull extrema implement these exact comparisons.
Complexity: Single query: expected O(N) time and O(N) space. Multiple queries: O(N log N+(N+E)*(B+(N/B)*log B)) time and O(N) space, B≈sqrt(N), E the number of improving exchanges. Rebuilds cost O(B), extrema scan O(N/B) hulls. This is an output-sensitive bound for the intended practical hull-block strategy, not an unsupported worst-case O(N log N) claim.
Watch out. Prefix sums include vi. Negate both intercept and slope for inside maxima. Do not exchange ties. Use long long for costs and sums. The fast single-query branch is needed for N up to one million. Exchange count is data-dependent.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<cmath>
#include<iostream>
#include<limits>
#include<numeric>
#include<utility>
#include<vector>
using namespace std;
struct Line{
long long slope;
long long intercept;
int id;
long long at(int x)const{
return slope*x+intercept;
}
};
struct Hull{
vector<Line>lines;
void append(Line line){
if(!lines.empty()&&lines.back().slope==line.slope){
if(lines.back().intercept<=line.intercept){
return;
}
lines.pop_back();
}
while(lines.size()>=2){
Line a=lines[lines.size()-2];
Line b=lines.back();
// Slopes decrease; remove a middle line with no useful interval.
long long left=(b.intercept-a.intercept)*(b.slope-line.slope);
long long right=(line.intercept-b.intercept)*(a.slope-b.slope);
if(left<right){
break;
}
lines.pop_back();
}
lines.push_back(line);
}
pair<long long,int>minimum(int x)const{
if(lines.empty()){
return {numeric_limits<long long>::max(),-1};
}
int left=0;
int right=static_cast<int>(lines.size())-1;
while(left<right){
int middle=(left+right)/2;
if(lines[middle].at(x)<=lines[middle+1].at(x)){
right=middle;
}
else{
left=middle+1;
}
}
return {lines[left].at(x),lines[left].id};
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
int queries;
int multiplier;
cin>>n>>queries>>multiplier;
vector<Line>lines(n);
long long prefix=0;
for(int i=0;i<n;++i){
long long value;
cin>>value;
prefix+=value;
lines[i]={-value,(multiplier+static_cast<long long>(i))*value+prefix,i};
}
vector<int>requested(queries);
for(int&count:requested){
cin>>count;
}
if(queries==1){
int k=requested[0];
vector<long long>values(n);
for(int i=0;i<n;++i){
values[i]=lines[i].at(k);
}
if(k<n){
nth_element(values.begin(),values.begin()+k,values.end());
}
cout<<accumulate(values.begin(),values.begin()+k,0LL)<<'\n';
return 0;
}
int blockSize=max(1,static_cast<int>(sqrt(n)));
int blocks=(n+blockSize-1)/blockSize;
vector<int>order(n);
iota(order.begin(),order.end(),0);
sort(order.begin(),order.end(),[&](int a,int b){
return lines[a].slope>lines[b].slope;
});
vector<int>blockOf(n);
for(int i=0;i<n;++i){
blockOf[order[i]]=i/blockSize;
}
vector<bool>inside(n,false);
vector<Hull>outsideHull(blocks);
vector<Hull>insideHull(blocks);
auto rebuild=[&](int block){
outsideHull[block].lines.clear();
insideHull[block].lines.clear();
int first=block*blockSize;
int last=min(n,first+blockSize);
for(int i=first;i<last;++i){
int id=order[i];
if(!inside[id]){
outsideHull[block].append(lines[id]);
}
}
for(int i=last-1;i>=first;--i){
int id=order[i];
if(inside[id]){
insideHull[block].append({-lines[id].slope,-lines[id].intercept,id});
}
}
};
for(int block=0;block<blocks;++block){
rebuild(block);
}
auto minimum=[&](const vector<Hull>&hulls,int x){
pair<long long,int>best{numeric_limits<long long>::max(),-1};
for(const Hull&hull:hulls){
best=min(best,hull.minimum(x));
}
return best;
};
long long slopeSum=0;
long long interceptSum=0;
auto change=[&](int id,bool selected){
inside[id]=selected;
int sign=selected?1:-1;
slopeSum+=sign*lines[id].slope;
interceptSum+=sign*lines[id].intercept;
};
vector<long long>answers(n+1);
int maximumRequested=*max_element(requested.begin(),requested.end());
for(int k=1;k<=maximumRequested;++k){
int added=minimum(outsideHull,k).second;
change(added,true);
rebuild(blockOf[added]);
while(k<n){
auto cheapest=minimum(outsideHull,k);
auto negatedLargest=minimum(insideHull,k);
if(-negatedLargest.first<=cheapest.first){
break;
}
int removed=negatedLargest.second;
added=cheapest.second;
change(removed,false);
change(added,true);
rebuild(blockOf[removed]);
if(blockOf[added]!=blockOf[removed]){
rebuild(blockOf[added]);
}
}
answers[k]=interceptSum+slopeSum*k;
}
for(int count:requested){
cout<<answers[count]<<'\n';
}
}