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

Debugging Help
#1

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;
        }
    }
}
#2

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