algorithm - 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

这样想：

步骤 1：表征 1 枚黑客导弹可以覆盖 2 枚导弹的情况

给定 2 枚导弹 i 和 j 使得 t _j >= t _i（导弹按到达时间排序）：

如果 i 和 j 之间的频率差异小于或等于它们到达之间的时间量（因为将频率更改 1 需要 1 个单位时间），我可以使用相同的黑客导弹来阻止 i 和 j。

更正式地说，相同的黑客导弹可以同时覆盖i 和 j，如果：

t _j - t _i >= |f _i - f _j |

让我们简化一下：

第 2 步：做出假设

我们现在假设

f _i > f _j

所以我们可以摆脱讨厌的绝对值符号，产生

t _j - t _i >= f _i - f _j

我们稍后会删除这个假设。

两边加f _j

t _j - t _i + f _j >= f _i

将 t _i添加到两边

t _j + f _j >= t _i + f _i

我们知道我们至少需要一枚黑客导弹来覆盖第一枚到达的导弹。问题是，它还能覆盖多少其他到达的导弹？

好吧，通过列表进行线性扫描会告诉我们这一点。我们可以检查每个后续值是否满足不等式。但这会给我们 O(n ² ) 时间，我们可以做得更好。

第 3 步：在假设的情况下找到一个有效的解决方案

首先，让我们按到达时间对值进行排序，以 t _i + t _{j打破平局}

这类似于代码中的行：

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

（代码作者随后将其反转为std::lower_bound可以使用的，我们需要它，因为它将返回一个迭代器到一个值 >= 查询值，而std::upper_bound严格地是 < 查询值）

既然我们知道我们至少需要一枚黑客导弹来覆盖第一个到达的导弹，让我们将我们的黑客导弹添加到我们将要部署的黑客导弹列表中，并用最新的 t _i +f _i标记它们他们覆盖。

那么我们该怎么办？当我们遍历来自 A 国的导弹列表时，我们需要尝试在 B 国部署的黑客导弹列表中找到可以覆盖它的导弹。

这简化为通过我们部署的导弹列表进行二分搜索，以便它也可以覆盖新导弹。回想一下，导弹可以同时覆盖 i 和 j，如果

t _j + f _j >= t _i + f _i

我们列表中的黑客导弹与 t _i + f _i相关联，我们需要覆盖的新导弹与 t _j + f _j相关联

如果我们能找到这样的黑客导弹，请将其相关的 t _i + f _i替换为 t _j + f _j

执行此操作的代码行是

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

从文档中：

lower_bound(first, last, val) 返回一个迭代器，指向范围 [first,last) 中不小于 val 的第一个元素。换句话说，它搜索大于或等于val的值

我们希望不必颠倒列表并使用lower_bound，但要upper_bound严格检查 <，而不是 <=。所以我们需要满足于反转和使用lower_bound 注意，运行时间lower_bound是对数的，因为它本质上是一个二进制搜索。如果它失败了，我们插入一个新的黑客导弹来覆盖我们的新导弹。

n代码的作者通过创建一个大小的黑客导弹列表并将它们与无穷大的值相关联来绕过严格的插入：

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

当我们尽可能地用第一枚黑客导弹覆盖最新的导弹时，我们最终得到了一个最小集合。现在我们只需要获取我们添加到列表中的黑客导弹的数量。如果我们进行严格插入，我们可以调用vector.size()，但由于作者没有，他执行迭代器减法以获取开始和与无穷大（或vector.end()）相关的第一个黑客导弹之间的元素数量：

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

这篇文章是一个正在进行的工作，我会在我弄明白的时候更新它。

Answer 2

我将尝试解释代码（无论我能理解什么）。IMO 它不是作为最大匹配算法来解决的，因为它是基于区间的并且它减少了很多搜索空间。

该代码使用以下思想。假设在时间 t1 和 t2 有两个导弹。

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

现在也将hackerX导弹t2用于t1，
t1-t2 > f1-f2（为简单起见，去掉mod）
或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;

Answer 3

使用Dilworth's Theoren将上述问题简化为 O(nlogn)

关于上述定理的一个很好的教程可以在这里找到。