APIO 2015 - Palembang Bridges

Author: Andi Qu

Table of Contents

K=1K = 1K=2K = 2

Time Complexity: O(NlogN)\mathcal O(N \log N)

Since people only cross bridges when their two buildings are on opposite sides of the river, assume without loss of generality that all the people must cross a bridge.

K=1K = 1

If the bridge is at position xx, then the total cost would be i=1N(Six+Tix)\sum_{i = 1}^N (|S_i - x| + |T_i - x|). Clearly, this value is minimized when xx is the median of all SiS_i and TiT_i.

We can find the median simply by sorting all the numbers in the input.

K=2K = 2

Since each person crosses exactly one bridge, which one would person ii choose? The answer is that they'd choose the bridge that is closest to Si+Ti2\frac{S_i + T_i}{2}.

This means that if we sort the people by Si+TiS_i + T_i, then we can split them into a prefix where people choose bridge 1 and a suffix where people choose bridge 2. Notice how we can use our solution for K=1K = 1 to compute the answer for each bridge.

Now we can simply try out all the places to split the people into prefix and suffix. To maintain a sliding median, we can use two std::priority_queues. (For more details, see CSES Sliding Median)

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b) { return a.first + a.second < b.first + b.second; }
priority_queue<int> lpq;
priority_queue<int, vector<int>, greater<int>> rpq;
ll lsum, rsum;

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!