PROBLEM LINK:Author: Snigdha Chandan DIFFICULTY:CHALLENGE PREREQUISITES:Graph, Trees, Approximation, AdHoc radio networks PROBLEM:You are given a set of N points on a plane. Each point is unique and it is denoted by its x and y coordinates. You can think of each point as a radio transmitter. Your task is to connect the points in a tree and your score is based on the following: Let's consider a vertex v and let u be the farthest direct neighbor of v in the tree. Let d(u, v) be the distance between v and u. Then node v transmits a radio wave of a circular shape with a center in v and a radius d(u, v). Since all nodes in the tree transmit their radio waves, each node is covered by a positive number of these waves. Your task is to construct a tree in such a way, that the number of waves covering a node v is minimal, where v is a node which is covered by the most waves among all nodes in a tree. QUICK EXPLANATION:This is a very hard problem. It is proven that approximate the result within better than logarithmic factor is also very hard. If you are interested in the complexity of the problem, you can check it here EXPLANATION:In order to come up with a really simple solution, you can try any heuristic which runs in the time limit or combine them and select the best one for a current case. Example heuristics:
More sophisticated solutions: You can try to implement an algorithm from this great paper: Minimizing Interference in Ad Hoc and Sensor Networks AUTHOR'S AND TESTER'S SOLUTIONS:To be uploaded soon. RELATED PROBLEMS:To be uploaded soon.
This question is marked "community wiki".
asked 15 Dec '14, 19:22

I'll explain my method here, as it is simple and also got high score. (0.88) I used the fact that points are generated randomly and uniformly. This will mean the answer will be generally small, probably less than 10.
Some crude optimization is in the code but the idea is simple. answered 16 Dec '14, 10:53

What i tried was: answered 15 Dec '14, 20:25

And MST stands for "Minimum Spanning Tree"? It's not so known as BFS/DFS I'd say...