DAG Minimum Path Cover in O(nlogn)?

Question

The following problem was asked in the recent October 20-20 Hack on Hackerrank :

Evil Nation A is angry and plans to launch N guided-missiles at the peaceful Nation B in an attempt to wipe out all of Nation B’s people. Nation A’s missile i will arrive in nation B at the time ti. Missile i communicates with its headquarters by unique radio signals with a frequency equal to fi. Can you help the peaceful Nation B survive by building a defensive system that will stop the missiles dead in the sky?

Defensive system:

The only way to defend Nation B from the attacking missile is by counter attacking them with a hackerX missile. You have a lot of hackerX missiles and each one of them has its own radio frequency. An individual hackerX missile can destroy Evil Nation A’s attacking missile if the radio frequency of both of the missiles match. Each hackerX missile can be used an indefinite number of times. Its invincible and doesn’t get destroyed in the collision.

The good news is you can adjust the frequency of the hackerX missile to match the evil missiles’ frequency. When changing the hackerX missile’s initial frequency fA to the new defending frequency fB, you will need |fB - fA| units of time to do.

If two evil missles with same frequency arrive at the same time, we can destroy them both with one hackerX missile. You can set the frequency of a hackerX missile to any value when its fired.

What is the minimum number of hackerX missiles you must launch to keep Nation B safe?

Input Format: The first line contains a single integer N denoting the number of missiles. This is followed by N lines each containing two integers ti and fi denoting the time & frequency of the ith missile.

Output Format: A single integer denoting the minimum number of hackerX’s you need to defend the nation.

Constraints: 1 <= N <= 100000

0 <= ti <= 100000

0 <= fi <= 100000

t1 <= t2 <= … <= tN

The problem gets reduced to a Minimum Path Cover Problem which is to be solved in O(nlogn) time based on the constrainsts. However the best solution to a Minimum Path Cover Problem is using the Hopcroft–Karp algorithm, that leads to the Maximal Matching Problem. The solution to which is O(n^2.5). But the following solution by icyrhyme9733 solves the problem in O(nlogn) :

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int n;
    cin >> n;
    vector<pair<int, int> > vp;
    for(int i = 0; i < n; ++i) {
        int t, f;
        cin >> t >> f;
        vp.push_back(make_pair(t + f, t - f));
    }
    sort(vp.begin(), vp.end());
    reverse(vp.begin(), vp.end());
    vector<int> last(vp.size(), numeric_limits<int>::max());
    for(int i = 0; i < vp.size(); ++i) {
        *lower_bound(last.begin(), last.end(), vp[i].second) = vp[i].second;
    }
    cout << lower_bound(last.begin(), last.end(), numeric_limits<int>::max()) - last.begin() << endl;
    return 0;
}

Is it solving a Minimum Path Cover Problem in O(nlogn) time ? Or is there an optimization that I am missing ?

I found a similar problem on this thread. They have taken advantage of the fact that the graph is an Interval Graph. Even though being very similar, the same solution cannot be implemented, as the intervals are inverted.

Answer 1

The above problem has been reduced to O(nlogn) using Dilworth's Theoren

A good tutorial on the above theorem can be found here.

Answer 2

Think about it this way:

Step 1: Characterize the case that 1 hacker-missile can cover 2 missiles

Given 2 missiles i and j such that t_j >= t_i (missiles are sorted by arrival time):

I can use the same hacker-missile to stop both i and j if the difference in frequency between them is less than or equal to the amount of time between their arrivals (because it takes 1 unit of time to change a frequency by 1).

More formally, the same hacker-missile can cover both i and j if:

t_j - t_i >= |f_i - f_j|

Let's simplify:

Step 2: make an assumption

Let's for now assume that

f_i > f_j

so we can get rid of the pesky absolute value symbols, yielding

t_j - t_i >= f_i - f_j

We'll remove this assumption later.

Add f_j to both sides

t_j - t_i + f_j >= f_i

Add t_i to both sides

t_j + f_j >= t_i + f_i

We know that we need at least 1 hacker-missile to cover the first arriving missile. The question is, how many other arriving missiles can it cover?

Well, a linear scan through the list would tell us that. We could just check to see if each subsequent value satisfies the inequality. But this would give us O(n²) time, and we can do better.

Step 3: Find an efficient solution given that assumption

First, let's sort the values by arrival time, with ties broken by t_i + t_j

This is akin to the line in the code:

sort(vp.begin(), vp.end());

(The author of the code reverses it afterwards to that std::lower_bound can be used, which we need because it will return an iterator to a value >= queried value, while std::upper_bound is strictly < queried value)

Since we know we need at least 1 hacker-missile to cover the first arriving missile, let's add our hacker-missile to a list of hacker-missiles that we are going to deploy, and let's mark them by the latest t_i+f_i they cover.

So, what do we do? As we iterate over the list of missiles from Nation A, we need to try to find a missile in Nation B's list of deployed hacker-missiles that can cover it.

This reduces to a binary search through our list of deployed missiles for one such that it can also cover the new missile. Recall from above that a missile can cover both i and j if

t_j + f_j >= t_i + f_i

Our hacker-missile in the list is associated with t_i + f_i and our new missile we need to cover is associated with t_j + f_j

If we can find such a hacker-missile, replace its associated t_i + f_i with t_j + f_j

The line of code that performs this operation is

*lower_bound(last.begin(), last.end(), vp[i].second) = vp[i].second;

From the documentation:

lower_bound(first, last, val) Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val. In other words, it searches for a value greater than or equal to val

We'd like to not have to reverse the list and use lower_bound, but upper_bound strictly checks <, not <=. So we need to settle for reversing and using lower_bound Note that the running time of lower_bound is logarithmic because it's essentially a binary search. If it fails, we insert a new hacker-missile to cover our new missile.

The author of the code gets around a strict insertion by just creating a list of hacker-missiles of size n and associating them with values of infinity:

vector<int> last(vp.size(), numeric_limits<int>::max());

When we go about covering the newest missile with the first hacker-missile that we can, we end up with a minimum set. Now we simply need to get the number of hacker-missiles we added to the list. If we went with strict insertion, we could call vector.size(), but since the author did not, he performs iterator subtraction to get the number of elements between the start and the first hacker-missile associated with infinity (or vector.end()):

lower_bound(last.begin(), last.end(), numeric_limits<int>::max()) - last.begin()

This post is a work in progress, and I'll update it as I figure things out.

Answer 3

I'll try to explain the code in bits (whatever I could understand). IMO it is not solved as a maximal matching algorithm because it is interval based and it reduces much of the search space.

The code uses the following idea. Say there are following two missiles at times t1 and t2.

  (t1-f1)------t1------(t1+f1)  
(t2-f2)---t2---(t2+f2)

Now to use hackerX missile t2 for t1 also,
t1-t2 > f1-f2 (getting rid of mod for simplicity)
or t1-f1 > t2-f2

for(int i = 0; i < n; ++i) {
  int t, f;
  cin >> t >> f;

  // pair's first part is max time till this hacker missile will stay valid.
  // pair's second part is t-f for comparison between consecutive missiles.
  vp.push_back(make_pair(t + f, t - f));
}

// sort on the basis of first part of pair.
sort(vp.begin(), vp.end());

reverse(vp.begin(), vp.end());

// vector containing initially very large numbers.
vector<int> last(vp.size(), numeric_limits<int>::max());

// start from the last time.
for(int i = 0; i < vp.size(); ++i) {

   // find the 1st entry that is not smaller than vp[i].second.
   // Make it equal to vp[i].second    
  *lower_bound(last.begin(), last.end(), vp[i].second) = vp[i].second;
}
// The number of new entries = number of hackerX missiles needed.
cout << lower_bound(last.begin(), last.end(), numeric_limits<int>::max()) - last.begin() << endl;