Flatland Space Stations

Solutions

Quadratic solution

This Python solution by Davide Peron calculates the difference for each combination of city/station, keeps the minimum for each city and then takes only the maximum.

1
2


def flatlandSpaceStations(n, c):
    return max(min(abs(city - sta) for sta in c) for city in range(n))

Linear solution

The problem can be solved linearly.

Assume \(arr[i]=1\) if the \(i^th\) city has a space station, \(0\) otherwise. Now calculate \(c[i]\) which denotes the distance to the nearest space station on the left. if \(arr[i]=1\), then \(c[i]=0\), otherwise \(c[i]=c[i-1]+1\).

Now calculate the distance to the nearest space station to the right using the same technique. The minimum of these values is the distance to the nearest space station. Among all these values, print the maximum one.

Here is an implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


int n, m;
cin >> n >> m;
vector<int> c(n, numeric_limits<int>::max());
int currC;
while (m--)
{
    cin >> currC;
    c[currC] = 0;
}
auto currCount = -1;
for (auto i=0u; i<n; ++i)
{
    if (c[i] == 0)
        currCount = 1;
    else if (currCount != -1)
    {
        c[i]=currCount++;
    }
}
currCount = -1;
for (auto i=n-1; i>=0; --i)
{
    if (c[i] == 0)
        currCount = 1;
    else if (currCount != -1)
    {
        c[i]=min(currCount++, c[i]);
    }
}
cout << *max_element(begin(c), end(c));

The following C++ solution makes use of the prefix sum pattern:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


int n, m;
cin >> n >> m;
vector<int> c(n, numeric_limits<int>::max());
int currC;
while (m--)
{
    cin >> currC;
    c[currC] = 0;
}
auto updateFn = [](int currVal, int r){
	return min(r, currVal<numeric_limits<int>::max() ? currVal + 1 : currVal);
};
partial_sum(begin(c), end(c), begin(c), updateFn);
partial_sum(rbegin(c), rend(c), rbegin(c), updateFn);
cout << *max_element(begin(c), end(c));

This Javascript solution by Beatrice Liberi keeps the half minimum distance between two state.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


function flatlandSpaceStations(n, c) {
    c.sort(function(a, b){return a-b});

    let max = 0;
    for(let i = 0; i < c.length - 1; i++){
        let mean = Math.floor((c[i+1] - c[i])/2)
        max = Math.max(max, mean)
    }

    max = Math.max(max, c[0])
    max = Math.max(max, n-1-c[c.length - 1])
    return max
}

prefix sum