PROBLEM LINK:
Author: Abhigyan Khaund
Tester: Vishal Anand
Editorialist: Abhigyan Khaund
DIFFICULTY:
MEDIUM
PREREQUISITES:
Bipartite Graphs, Maximum Matching/Max-Flow, Sieve of Eratosthenes, Prime Factorization
PROBLEM
N planes are located at a N bases described by integer coordinates (x,y) which needs to go to one of M targets defined by integer coordinates(x,Y) and then go to one final coordinate (baseX,baseY). Each coordinate has an integer ID. The time taken for a plane to go from a base to a target is the prime factor of the Manhattan Distance between the base and the target that is just greater than the ID of the source base (In case the ID is greater than or equal to the largest prime factor, then consider the ID itself) . Similarly time is defined from the target to the final coordinats.
Each Aircraft needs to leave the base, reach target and come back to the main base in a maximum time of T.
Find the maximum number of targets that can be reached in the enemy territory.
QUICK EXPLANATION:
Use sieve to store the smallest prime number. Make a bipartite graph between the base and targets where edge exists if its possible to for a plane to from base to target and then to final coordinate in time T. Find all primes for the Mahattan distance on the fly in logarithm time. Use any biparite matching algorithm to find maximum targets.
EXPLANATION:
First step is to find prime factors. Use Sieve of Eratosthenes to store the smallest prime factor upto 10^7. Do not store all the prime factors for a number, as that would lead to TLE.
Make a bipartite graph between the first N set of nodes(i.e. the bases) and M nodes of second set (i.e. the targets). The graph can be built as an adjacency matrix (this is possible as small constraints).
Two nodes has an edge if the time between the two nodes + time between the node of target set and final base node is less than equal to T. The time between two nodes can be found by first finding the manhattan distance (abs(x1-x2) + abs(y1-y2)) and then finding the list of prime factors of the distance using the smallest prime factor list to continuously divide and get the prime factors of the distance and store the primes locally. Then use upper-bound (or linear search since number of prime factors would be very less) to find the prime factor just greater than ID. The complexity of getting the prime factors is O(log n).
Now use a maximum matching algorithm (based on max-flow) like Ford-Fulkerson algorithm , Hopcroft–Karp Algorithm in this graph will give the maximum the number of nodes reachable in the second set.
AUTHOR’S SOLUTION:
Author’s solution can be found here
