KALKI - Editorial

editorial
, , , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Snigdha Chandan
Tester 1: Minako Kojima
Tester 2: Shiplu Hawlader
Editorialist: Pawel Kacprzak

DIFFICULTY:

CHALLENGE

PREREQUISITES:

Graph, Trees, Approximation, Ad-Hoc 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:

  1. 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.

  2. MST. Based on the same intuition as above, we can try to build a MST over a complete graph on given n nodes.

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.

1 Like
2

What i tried was:
Store all the pairs of points and the distances between them & sort the pairs on the basis of distance. Then, for a particular edge, let p1 & p2 be the points connecting it, and x1 and x2 be the number of points coming under the circle formed by p1 and p2 as center respectively, and length of the egde as radius. I then sorted the pairs on the basis of (x1+x2), and created a graph on the basis of it. Can anyone suggest an improvement over this ?

3

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.

  1. Sort edges ascending by the number of interferences.
  2. Assume answer is 2, and add edges greedily, to make a spanning tree. If the new edge makes the answer > 2, don’t add that edge.
  3. If all edges are processed and tree is not complete, answer=answer+1, delete all edges and go to step 2 again.
  4. Print tree.

Some crude optimization is in the code but the idea is simple.

2 Likes
4

And MST stands for “Minimum Spanning Tree”? It’s not so known as BFS/DFS I’d say…