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(paths(), key=lambda (h, m): m) # Gets max path based on the money it makes
What I'm doing at the moment is going through each location and then going through each inhabited house for that location to find the max income location.
Pseudocode:
max_money = 0
max_location = 0
for every location in 1 to length * 4 + 1
money = 0
for house in inhabited_houses:
money = money + shortest_dist * num_people_in_this_house
if money > max_money
max_money = money
max_location = location
This is too slow since it's O(LN) and won't run in under a second for the largest test case. Can someone please simply tell me how to do it in the shortest run time (code isn't required unless you want to) since this has been bugging me for ages.
EDIT: There must be a way of doing this in less than O(L) right?