We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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...
Flatland Space Stations
You are viewing a single comment's thread. Return to all 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...