Questions Tagged With radio-networkshttps://discuss.codechef.com/tags/radio-networks/?type=rssquestions tagged <span class="tag">radio-networks</span>enMon, 15 Dec 2014 19:22:01 +0530KALKI - Editorialhttps://discuss.codechef.com/questions/58413/kalki-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/PROBLEMCODE">Practice</a><br>
<a href="http://www.codechef.com/CONTESTCODE/problems/PROBLEMCODE">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/nssprogrammer">Snigdha Chandan</a> <br>
<strong>Tester 1:</strong> <a href="http://www.codechef.com/users/xiaodao">Minako Kojima</a><br>
<strong>Tester 2:</strong> <a href="http://www.codechef.com/users/shiplu">Shiplu Hawlader</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>CHALLENGE</p>
<h1>PREREQUISITES:</h1>
<p>Graph, Trees, Approximation, Ad-Hoc radio networks</p>
<h1>PROBLEM:</h1>
<p>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:</p>
<p>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.</p>
<h1>QUICK EXPLANATION:</h1>
<p>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 <a href="http://link.springer.com/chapter/10.1007%2F11963271_2">here</a></p>
<h1>EXPLANATION:</h1>
<p>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.</p>
<p>Example heuristics:</p>
<ol>
<li>
<p>Greedy. Try to construct a tree connecting node v (which is already in the tree) to a node u which is the closest one node to v on the plane. The intuition here is that by selecting the closest neighbors, we try to minimize radiuses of radio waves transmitted by nodes, and we expect that the smaller the radiuses are, the less waves will cover a single node.</p>
</li>
<li>
<p>MST. Based on the same intuition as above, we can try to build a MST over a complete graph on given n nodes.</p>
</li>
</ol>
<p>More sophisticated solutions:</p>
<p>You can try to implement an algorithm from this great paper: <a href="http://www.disco.ethz.ch/publications/DIALM2005b.pdf">Minimizing Interference in Ad Hoc and Sensor Networks</a></p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>To be uploaded soon.</p>
<h1>RELATED PROBLEMS:</h1>
<p>To be uploaded soon.</p>pkacprzakMon, 15 Dec 2014 19:22:01 +0530https://discuss.codechef.com/questions/58413/kalki-editorialradio-networksgraphchallengetreeoptimizationeditorialdec14