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.