555B – Case of Fugitive (Codeforces)

by afruizc

This is an very interesting problem; The full description is here.

Problem:
Given a set of islands (represented by their [l, r] endpoints), and bridges (represented by their width), we are to assign each one of these bridges to the gaps between the islands so that all of them are connected.

Solution:
The first thing to notice is that what we really care about are the gaps between two contiguous islands, and not the islands themselves. Specifically, a gap between two islands will be represented by a pair of numbers (min_d, max_d), the minimum and the maximum width a bridge can have in order to cover the gap. These two values are easily obtained: min_d = l_{i+1} - r_i and max_d = r_{i+1} - l_i for all i. Now, for every gap, we need to find the right bridge to use, and then, remove that bridge from the set of available bridges.

So far, so good; we have a general idea how to solve this problem. However, there are still some big details missing: how do we pick the right gap to assign a bridge to? How do we search (optimally) for the bridge? How do we delete this bridge from the list of available bridges?

Well, for the last two, our friend set comes to the rescue! As most of you might know, sets in c++ are implemented using a BST. This makes them suitable for search (log time) and deletion (constant amortized time). Hence, we will represent the available bridges as a set. For the first question, I came up with two strategies (only one during contest time), which I will mention for the sake of completeness.

Sort the gaps by minimum size (wrong strategy):
The first strategy that I came up with was to sort the gaps increasingly by the minimum distance and then iterate over this sorted list and look for the right bridge. This strategy fails in cases like the following:

Islands: (1, 8)(9, 10)(12, 13)
Gaps (Sorted by min_d): (1, 10)(2, 4)
Bridges: 3 5

As you see, by using this approach, we will assign the first bridge (width 3) to the first gap, and then (incorrectly) assume that there is no satisfying assignment. This heuristic does not work because we fail to account for the fact that gaps with bigger differences on the endpoints can be covered by bridges of bigger sizes. Which leads us to the second approach…

Sort the gaps by maximum size (accepted strategy):
If you look closely, you will realize (I didn’t at the time of the contest) that sorting the bridges based on the max_d will overcome this issue. Specifically, if we sort the gaps based on their max_d, we get the nice property that we will take care first of the gaps with smaller separation while still giving priority to those with smaller min_d.

Disclaimer: I didn’t solve this problem on the round, and I did have some help looking at the comments after the round ended.

Note: The code looks a bit cluttered because we were asked for the indices of the bridges to use, instead of their values, which made it necessary to store some additional information.

Code:
Here is the code.

#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef pair<pair<ll, ll>, int> lll;
typedef pair<int, int> ii;

int N, M;
ll l1, r1, l2, r2;
// Min, Max distances
vector<lll> to_build;
set<pair<ll, int>> bridges;

void _solve(int N, int M) {
    to_build.clear();
    bridges.clear();

    cin >> l1 >> r1;
    for (int i=0 ; i<N-1 ; i++) {
        cin >> l2 >> r2;
        to_build.push_back(make_pair(make_pair(l2 - r1, r2 - l1), i));
        l1 = l2;
        r1 = r2;
    }

    for (int i=0 ; i<M ; i++) {
        ll b;
        cin >> b;
        bridges.insert(make_pair(b, i + 1));
    }

    sort(to_build.begin(), to_build.end(), [](lll a, lll b) {
            return a.first.second < b.first.second;
    });
    vector<ii> ans;
    for (auto tb : to_build) {
        pair<ll, ll> gap = tb.first;
        auto it = bridges.lower_bound(make_pair(gap.first, 0LL));
        if (it == bridges.end() || (it->first) > gap.second) {
            printf("No\n");
            return;
        }
        ans.push_back(make_pair(tb.second, it->second));
        bridges.erase(it);
    }

    sort(ans.begin(), ans.end());
    printf("Yes\n");
    for (auto i : ans) {
        printf("%d ", i.second);
    }
    printf("\n");
}

int main() {
    while (scanf("%d %d\n", &N, &M) == 2) {
        _solve(N, M);
    }
}