# Flatland Space Stations

# Flatland Space Stations

+ 29 comments Posting an alternate solution to this..

Consider all the cities to be a chain. Ex, with 8 cities, it would look like this 0-1-2-3-4-5-6-7-8.

Now, each space station will break the chain. What we are trying to achieve are chains of cities without space stations. If we have stations in 2 and 6, we just take them out. We are left with three chains here. 0-1, 3-4-5, 7-8

We just find the longest chain and the answer would be (length+1)/2. This is the length from the middle of the chain to a station.

There are two special cases when the longest chain without station is leading or trailing. I would leave it here...

+ 7 comments A solution in C# with a bit of explanation.

using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static void Main(String[] args) { string[] tokens_n = Console.ReadLine().Split(' '); int nCities = Convert.ToInt32(tokens_n[0]); int mSpaceStations = Convert.ToInt32(tokens_n[1]); string[] c_temp = Console.ReadLine().Split(' '); int[] spaceStationArr = Array.ConvertAll(c_temp,Int32.Parse); /*The array has to be sorted. According to MSDN arrays that are sorted by using the Heapsort and Quicksort algorithms, in the worst case, this method is an O(n log n) operation, where n is the Length of array.*/ Array.Sort(spaceStationArr); //Set an initial max distance which can sensibly be the distance between City 0 and first space station int maxDistance = spaceStationArr[0] ; /*We are interested in the cities that are in the middle of two space stations as this city will be furthest for that set of two space stations City : 0,1,2,3,5,6,7,8 SpaceStation : .,.,2,.,.,.,7,. In the example above, 5 is in the middle of space station 2 and 7 and the distance to the closest one is 2 and can be calculated as (7-2)/2 = 2 */ for(int i=1 ; i<spaceStationArr.Length; i++) { int distance = (spaceStationArr[i] - spaceStationArr[i-1])/2; if(distance > maxDistance) maxDistance = distance; } //Check the distance of last spaceStation and last city. int lastSpaceStationDistance = nCities-1 - spaceStationArr[mSpaceStations-1] ; if( lastSpaceStationDistance > maxDistance) { maxDistance = lastSpaceStationDistance; } Console.WriteLine(maxDistance); } }

+ 4 comments My Java Solution

private static int solution(int[] arr, int n){ Arrays.sort(arr); int maxDistance = arr[0]; for(int i = 1; i < arr.length; i++){ int distance = (arr[i] - arr[i-1]) / 2; if(maxDistance < distance) maxDistance = distance; } int lastGap = (n-1) - arr[arr.length - 1]; return (lastGap < maxDistance) ? maxDistance : lastGap; }

+ 2 comments there's a typo in the problem description example: it should be "city 0, city 1, and city 2", not "city 1, city 2, and city 3", since in the test cases that the code actually runs with, cities are indexed starting from 0

+ 4 comments Python solution: Sort the array in incresing order. 1. Take the maximum distance from the starting city (0) and from the last city from the nearest station. Also eliminate the case of only 1 staion. 2. Now take the maximum distance from the given station to any city using formula (a[i+1]-a[i])/2. Just draw the diagrams and you will get the formula. 3. The maximum value of distance is the answer.

def flatlandSpaceStations(n, c): c.sort() maxd = max(c[0], n-1 - c[-1]) for i in range(len(c)-1): maxd = max((c[i+1]-c[i])//2, maxd) return maxd

Sort 714 Discussions, By:

Please Login in order to post a comment