# A Pie for A Pie (Gold) Binary Search On a Set of Pairs Taking Too Long?

Hi, I’m currently working on the USACO 2017 December Contest Gold problem A Pie for A Pie.
http://www.usaco.org/index.php?page=viewproblem2&cpid=765&lang=en

I have the main solution idea, namely performing a multi-source BFS from all of the “0” pies and finding the shortest distance to every other pie, using a set of pairs and performing lower_bound / upper_bound on it to find the suitable range of pies to traversal to from each current pie. This is a O(N log N) solution, which should pass just fine.

However, when I implemented the solution in C++, I passed the first 4 test cases but timed out on the last 6. I did some time analysis (using clock_t from time.h and calculating the time of each function took to run) on the timed out test cases and found out that the lower_bound and upper_bound on the set of pairs were taking on average, for N up to 100000, around 0.01 seconds, while all of the other operations (including those on a set of pairs, such as lookups and deletion) was running on a scale of 0.0001 seconds (or even less).

The processing of the set of pairs looks like this:

``````set <pair <int, int>>::iterator lowIt = lower_bound(ElsiePiesVis.begin(), ElsiePiesVis.end(), make_pair(BessiePies[cur.first].first-D, 0));
set <pair <int, int>>::iterator highIt = upper_bound(ElsiePiesVis.begin(), ElsiePiesVis.end(), make_pair(BessiePies[cur.first].first, 100000));
vector <pair <int, int>> vals;
while (lowIt != ElsiePiesVis.end() && lowIt!= highIt) {
vals.push_back(*lowIt);
lowIt++;
}
for (pair <int, int> i : vals) {
dist[i.second] = cur.second+1;
tmp.push({i.second, cur.second+1});
ElsiePiesVis.erase(ElsiePiesVis.find(i));
}
``````

Do the library functions such as lower_bound and upper_bound all take such a long time to run on such data structures? Also, how should I go about fixing the problem? Do I need to manually write the binary searches in code?

Thanks!

Then entire code (if more context is needed):

``````#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>

using namespace std;

int main () {
//    freopen("piepie.in", "r", stdin);
//    freopen("piepie.out", "w", stdout);
int N, D;
cin >> N >> D;
int dist[2*N];
fill (dist, dist+2*N, 1e9);
pair <int, int> BessiePies[N], ElsiePies[N];
set <pair <int, int>> BessiePiesVis, ElsiePiesVis;
queue <pair <int, int>> tmp;
for (int i = 0; i < N; ++i) {
cin >> BessiePies[i].first >> BessiePies[i].second;
if (BessiePies[i].second == 0) {
tmp.push({i, 1});
dist[i] = 1;
} else {
BessiePiesVis.insert({BessiePies[i].second, i});
}
}
for (int i = 0; i < N; ++i) {
cin >> ElsiePies[i].first >> ElsiePies[i].second;
if (ElsiePies[i].first == 0) {
tmp.push({i+N, 1});
dist[i+N] = 1;
} else {
ElsiePiesVis.insert({ElsiePies[i].first, i+N});
}
}
while (!tmp.empty()) {
pair<int,int> cur = tmp.front();
tmp.pop();
if (cur.first < N) {
// Bessie Giving Elsie
set <pair <int, int>>::iterator lowIt = lower_bound(ElsiePiesVis.begin(), ElsiePiesVis.end(), make_pair(BessiePies[cur.first].first-D, 0));
set <pair <int, int>>::iterator highIt = upper_bound(ElsiePiesVis.begin(), ElsiePiesVis.end(), make_pair(BessiePies[cur.first].first, 100000));
vector <pair <int, int>> vals;
while (lowIt != ElsiePiesVis.end() && lowIt!= highIt) {
vals.push_back(*lowIt);
lowIt++;
}
for (pair <int, int> i : vals) {
dist[i.second] = cur.second+1;
tmp.push({i.second, cur.second+1});
ElsiePiesVis.erase(ElsiePiesVis.find(i));
}
} else {
// Elsie Giving Bessie
set <pair <int, int>>::iterator lowIt = lower_bound(BessiePiesVis.begin(), BessiePiesVis.end(), make_pair(ElsiePies[cur.first-N].second-D, 0));
set <pair <int, int>>::iterator highIt = upper_bound(BessiePiesVis.begin(), BessiePiesVis.end(), make_pair(ElsiePies[cur.first-N].second, 100000));
vector <pair <int, int>> vals;
while (lowIt != BessiePiesVis.end() && lowIt!= highIt) {
vals.push_back(*lowIt);
lowIt++;
}
for (pair <int, int> i : vals) {
dist[i.second] = cur.second+1;
tmp.push({i.second, cur.second+1});
BessiePiesVis.erase(BessiePiesVis.find(i));
}
}
}
for (int i = 0; i < N; ++i) {
if (dist[i] != 1e9) {
cout << dist[i] << endl;
} else {
cout << -1 << endl;
}
}
}
``````

Note that std::lower_bound provides bad performance on sets because they don’t have random access iterators. Please use built in versions of lower_bound eg.

auto lowIt = ElsiePiesVis.lower_bound(make_pair(BessiePies[cur.first].first-D, 0));

1 Like