Algorithm (prob. solving) achieving fastest runtime

Question

For an algorithm competition training (not homework) we were given this question from a past year. Posted it to this site because the other site required a login. This is the problem: http://pastehtml.com/view/c5nhqhdcw.html Image didn't work so posted it here: It has to run in less than one second and I can only think about the slowest way to do it, this is what I tried: ``` with open('islandin.txt') as fin: num_houses, length = map(int, fin.readline().split()) tot_length = length * 4 # side length of square houses = [map(int, line.split()) for line in fin] # inhabited houses read into list from text file def cost(house_no): money = 0 for h, p in houses: if h == house_no: # Skip this house since you don't count the one you build on continue d = abs(h - house_no) shortest_dist = min(d, tot_length - d) money += shortest_dist * p return money def paths(): for house_no in xrange(1, length * 4 + 1): yield house_no, cost(house_no) print house_no, cost(house_no) # for testing print max(path…

Accepted Answer

Suppose the list `houses` is composed of pairs `(x,pop)` with `0 <= x < 4*L` the location and `pop` the population.

The objective function, which we want to maximize, is

```
def revenue(i):
    return sum(pop * min((i-j)%(4*L), 4*L - (i-j)%(4*L)) for j,pop in houses)
```

The naive algorithm O(LN) algorithm is simply:

```
max_revenue = max(revenue(i) for i in range(4*L))
```

But it is incredibly wasteful to entirely re-evaluate `revenue` for each location.

To avoid that, notice that this is a piecewise-linear function; so its derivative is piecewise constant, with discontinuities at two kinds of points:

- at house `i`, the derivative changes from `slope` to `slope + 2*population[i]`

- at the point located opposite house `i` on the island, the derivative changes from `slope` to `slope - 2*population[i]`

This makes things very simple:

- We only have to examine actual houses or opposite-of-houses, so the complexity drops to O(N²).

- We know how to update the `slope` from house `i-1` to house `i`, and it requires only O(1) time.

- Since we know the revenue and the slope at location 0, and since we know how to update the `slope` iteratively, the complexity actually drops to O(N): between two consecutive houses/opposite-of-houses, we can just multiply the slope by the distance to obtain the difference in revenue.

So the complete algorithm is:

```
def algorithm(houses, L):
    def revenue(i):
        return sum(pop * min((i-j)%(4*L), 4*L - (i-j)%(4*L)) for j,pop in houses)

slope_changes = sorted(
            [(x, 2*pop) for x,pop in houses] +
            [((x+2*L)%(4*L), -2*pop) for x,pop in houses])

current_x = 0
    current_revenue = revenue(0)
    current_slope = current_revenue - revenue(4*L-1)
    best_revenue = current_revenue

for x, slope_delta in slope_changes:
        current_revenue += (x-current_x) * current_slope
        current_slope += slope_delta
        current_x = x
        best_revenue = max(best_revenue, current_revenue)

return best_revenue
```

To keep things simple I used `sorted()` to merge the two types of slope changes, but this is not optimal as it has O(N log N) complexity. If you want better efficiency, you can generate in O(N) time a sorted list corresponding to the opposite-of-houses, and merge it with the list of houses in O(N) (e.g. with the standard library's `heapq.merge`). You could also stream from iterators instead of lists if you want to minimize memory usage.

TLDR: this solution achieves the lowest feasible complexity of O(N).

Algorithm (prob. solving) achieving fastest runtime

Solution

Problem

Related problems