Prelude-

Before people start bashing me, I just wanted to say that the problem is highly rated(2400), so would be too much for me to solve.

However, after spending a day on it :p , I figured out that I can binary search on the answer by taking a prospective number as the maximum and check if we can form a path using <=k nodes as the path, while the Mac distance from this path would be <= prospective answer.