Lifts: Ordered Requests with Compressed Min-Cost Flow
Autumn Tournament (2022)
Submission name: lifts.cpp
Problem summary
Process N elevator requests in their given order using K elevators. Request i starts on floor l[i] and finishes on floor r[i]. Elevators may initially be placed on any floor for free. Minimize total empty movement between requests assigned to the same elevator; passenger travel is not part of the objective.
Input
Read N K, followed by N pairs l[i] r[i] in chronological order.
Output
Print the minimum total empty distance.
Constraints
1 <= N <= 10000; 1 <= K <= min(30,N); floor numbers from 1 to 10^9; 64 MB.
Worked example
Original statement sample, using the documented local driver for grader tasks.
Input
3 2 5 20 8 100 2 80
Output
12
Solution analysis
- Assigning requests to one elevator forms an increasing-index path. A transition i->j, i<j, costs |r[i]-l[j]|. We seek K paths covering all requests. Using exactly K nonempty paths never costs more than using fewer: splitting a path removes a nonnegative transition, and K<=N.
- Create an input and output node per request. The input-to-output edge has capacity 1 and cost -R, where R=N*10^9+1. Connect source to every input and every output to sink, with capacity 1 and zero cost. Send K flow units. Since R exceeds every possible total repositioning cost, an optimum visits all requests; adding N*R to its cost removes the artificial rewards.
- There are quadratically many chronological transitions, so compress them. Divide a request-index interval into two halves. Every transition crossing from its left half to its right half is handled at this split. Sort left finish floors and right start floors together. An ascending chain charges coordinate differences and realizes transitions whose destination floor is higher; a descending chain realizes the others. Connect a left request output to its two chain positions and connect the right chain positions to their request inputs. Chain distances telescope to the required absolute difference. Recurse within each half.
- The resulting O(N log N)-size network initially has no positive-capacity cycles: every request transition advances time and every individual chain is directed. Obtain initial shortest-path potentials by topological DP, then use K Dijkstra augmentations with reduced costs. Compact adjacency arrays avoid the overhead of a vector per auxiliary node.
- In the sample, one elevator handles request 1 then request 2, paying |20-8|=12. A second elevator starts at floor 2 and handles request 3. Alternative pairings cost 18 or 98, so 12 is optimal. Starting floors are free; do not charge the first trip of either elevator.
Why it works
Every flow path corresponds to an elevator schedule, with exactly the same transition cost. Each chronological pair is represented at the unique divide-and-conquer split separating its endpoints, and its chain route has exactly the absolute floor difference. The reward bound forces maximum coverage, hence all N requests. Minimum-cost flow therefore minimizes precisely the original repositioning objective.
Complexity: The compressed graph has O(N log N) vertices and edges. Building it costs O(N log^2 N) for sorting at every divide-and-conquer level. Topological initialization is linear in graph size; K heap-based shortest-path augmentations cost O(K*N*log^2 N). Space O(N log N), using compact edge and vertex arrays for the 64 MB limit. Distances and rewards require long long.
Watch out. Only i<j transitions are valid. Do not charge passenger movement or initial placement. Use a reward larger than the entire possible reposition cost, not merely a single edge. Negative request rewards require initial potentials; ordinary Dijkstra cannot start with zero potentials. Preserve reverse residual edges and their negated costs.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<functional>
#include<iostream>
#include<limits>
#include<queue>
#include<utility>
#include<vector>
using namespace std;
struct FlowEdge{
long long cost;
int to;
int next;
int capacity;
};
struct LiftFlow{
vector<int>head;
vector<FlowEdge>edges;
explicit LiftFlow(int vertices,int expectedEdges):head(vertices,-1){
edges.reserve(expectedEdges);
}
int vertex(){
head.push_back(-1);
return (int)head.size()-1;
}
void add(int from,int to,int capacity,long long cost){
edges.push_back({cost,to,head[from],capacity});
head[from]=(int)edges.size()-1;
edges.push_back({-cost,from,head[to],0});
head[to]=(int)edges.size()-1;
}
long long minimumCost(int source,int sink,int amount){
int vertices=(int)head.size();
const long long infinity=numeric_limits<long long>::max()/4;
vector<long long>potential(vertices,infinity);
vector<int>indegree(vertices);
for(int from=0;from<vertices;++from){
for(int edge=head[from];edge!=-1;edge=edges[edge].next){
if(edges[edge].capacity>0){
++indegree[edges[edge].to];
}
}
}
queue<int>ready;
for(int v=0;v<vertices;++v){
if(indegree[v]==0){
ready.push(v);
}
}
potential[source]=0;
// The initial positive-capacity network is a DAG, even with negative rewards.
while(!ready.empty()){
int from=ready.front();
ready.pop();
for(int edge=head[from];edge!=-1;edge=edges[edge].next){
if(edges[edge].capacity==0){
continue;
}
int to=edges[edge].to;
if(potential[from]!=infinity){
potential[to]=min(potential[to],potential[from]+edges[edge].cost);
}
if(--indegree[to]==0){
ready.push(to);
}
}
}
for(long long&value:potential){
if(value==infinity){
value=0;
}
}
vector<long long>distance(vertices);
vector<int>previous(vertices);
long long result=0;
for(int unit=0;unit<amount;++unit){
fill(distance.begin(),distance.end(),infinity);
fill(previous.begin(),previous.end(),-1);
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>
pending;
distance[source]=0;
pending.push({0,source});
while(!pending.empty()){
auto current=pending.top();
pending.pop();
int from=current.second;
if(current.first!=distance[from]){
continue;
}
for(int edge=head[from];edge!=-1;edge=edges[edge].next){
if(edges[edge].capacity==0){
continue;
}
int to=edges[edge].to;
long long candidate=distance[from]+edges[edge].cost+potential[from]-potential[to];
if(candidate<distance[to]){
distance[to]=candidate;
previous[to]=edge;
pending.push({candidate,to});
}
}
}
for(int v=0;v<vertices;++v){
if(distance[v]!=infinity){
potential[v]+=distance[v];
}
}
for(int v=sink;v!=source;){
int edge=previous[v];
result+=edges[edge].cost;
--edges[edge].capacity;
++edges[edge^1].capacity;
v=edges[edge^1].to;
}
}
return result;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
int k;
cin>>n>>k;
vector<int>start(n);
vector<int>finish(n);
for(int i=0;i<n;++i){
cin>>start[i]>>finish[i];
}
int levels=0;
while((1<<levels)<n){
++levels;
}
int source=2*n;
int sink=source+1;
LiftFlow flow(2*n+2,8*n*(levels+1));
long long reward=1000000000LL*n+1;
for(int i=0;i<n;++i){
flow.add(source,2*i,1,0);
flow.add(2*i,2*i+1,1,-reward);
flow.add(2*i+1,sink,1,0);
}
function<void(int,int)>connect=[&](int low,int high){
if(low==high){
return;
}
int middle=(low+high)/2;
vector<pair<int,int>>points;
points.reserve(high-low+1);
for(int i=low;i<=high;++i){
points.push_back({i<=middle?finish[i]:start[i],i});
}
sort(points.begin(),points.end());
int previousAscending=-1;
int previousDescending=-1;
int previousCoordinate=0;
for(auto point:points){
int ascending=flow.vertex();
int descending=flow.vertex();
if(previousAscending!=-1){
int gap=point.first-previousCoordinate;
flow.add(previousAscending,ascending,k,gap);
flow.add(descending,previousDescending,k,gap);
}
int request=point.second;
if(request<=middle){
flow.add(2*request+1,ascending,1,0);
flow.add(2*request+1,descending,1,0);
}
else{
flow.add(ascending,2*request,1,0);
flow.add(descending,2*request,1,0);
}
previousAscending=ascending;
previousDescending=descending;
previousCoordinate=point.first;
}
connect(low,middle);
connect(middle+1,high);
};
connect(0,n-1);
cout<<flow.minimumCost(source,sink,k)+reward*n<<'\n';
}