PROBLEM LINK:
Editorialist: Lalit Kundu
DIFFICULTY:
EASY-MEDIUM
PRE-REQUISITES:
Graphs, Bipartite Matching
PROBLEM:
H(<250) hosts and G guests in a K x K matrix . Each host needs to team up with a single guest. Once teams are decide each host will move towards location of guest and then both will move to (K,K) from there. Assuming distance to be manhattan and unit speed, you need to form maximum teams that can reach (K,K) within time C.
EXPLANATION:
We can make a bipartite graph between hosts and guests where there is an edge between a host and a guest if they can form a team(ie. distance between host and guest + distance between guest and (K,K) is <= C).
Now, maximum bipartite matching in this graph will give us the number of maximum teams possible.
Any biparite matching algorithm would have passed here as limits are less.