All Tracks Problem

House Travelling Problem
Tag(s):

Algorithms, Easy-Medium, Greedy, Minimum Spanning Tree

Problem
Editorial
Analytics

Bob is about to visit $$N$$ of his friends' houses. Each house is depicted as a point $$(x_i , y_i)$$ on the $$X-Y$$ plane. The length of roads between two houses $$i$$ and $$j$$ is defined as $$F(i, j) = (x_i - x_j)^2 + (y_i - y_j)^2$$.

There's a $$N \times N$$ matrix $$M$$ filled with 1s and 0s. $$M[i][j] = 1$$ denotes that it is possible to travel to $$i^{th}$$ House from $$j^{th}$$ House and vice versa. If $$M[i][j] = 0$$, it is not possible to travel to $$i^{th}$$ House from $$j^{th}$$ House and vice versa.

Now, Bob wants to visit all the houses, but the sum of length of all roads traveled should be maximum. There's one more restriction, he can use a maximum of $$(N - 1)$$ roads. Before starting the trip, he would like to know what is the maximum distance he can travel which satisfies all the given conditions. If it is not possible to visit all the houses, print out -1.

Input Format:
The first line contains $$N$$, the number of houses Bob wants to visit.
$$N$$ lines follow, each contains two space separated integers $$x_i$$ and $$y_i$$ which denotes the of the $$i^{th}$$ house on the $$X-Y$$ plane.
Again, $$N$$ lines follow, each contains $$N$$ space separated integers, each being 0 or 1, denoting the matrix $$M$$.

Output Format:
Print the required answer in one line.

Input Constraints:
$$1 \le N \le 3000 $$
$$-10^6 \le x_i, y_i \le 10^6$$

Note:
One road can be traversed any number of times , but its contribution would be taken only once. Also, there's large input data, please use faster i/o methods.

SAMPLE INPUT
3
1 2
4 5
8 8
1 0 1
0 1 1
1 1 1
SAMPLE OUTPUT
110
Explanation

enter image description here

This is the image for the given sample. Every house also has a road of length 0 to itself. We can use at max 2 roads which would be from (1,2) -> (8,8) -> (4,5). The total cost is 85 + 25 = 110.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Euromonitor International

Challenge Name

Euromonitor International Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications