The natives of Roadland are at it again. They have now upgraded their network so that their is exactly one path between any two cities in Roadland. They have moved onto the next level of urbanisation and now want X-Way outlets (these serve yummy yooters: very popular in Roadland). But as the are Roadlanders, they have their set of constraints. The X-Way mandarins would set up their supply stations in some of the Roadlandian cities, but they would oblige a city only if the maximum of its distance from all other Roadlandian cities is the least possible. At most how many supply centres can their be? Oh, I forgot to tell you that all Roadlandian roads mysteriously have the same length. (This problem is based on a very simple and well known graph theoretical result) - The problem was given by Piyush Srivastava (currently in University of California, Berkley) for NERD Volume 1 Number 2.
No comments:
Post a Comment