http://i.minus.com/ivGYg42Gt3fks.png
My solution is in Python, though my algorithm sucks. I wrote this with around 10 minutes to go in the competition, and I think from memory I only passed 6/10 test cases. Algorithmic complexity is O(x^2) - which, when talking to someone who had the same complexity in their C++ algorithm, passed 7/10 test cases. My conclusion therefore is to next year use C++ and not Python :p
Any suggestions to improve on the algorithm are welcome.
Spoiler:I've included a sample test case.
Code:def solve(cities):
calculated = []
total = 0
keys = cities.keys()
keys.sort()
elements = []
for key in keys:
elements.append(key)
count = 0
for i in range(0, len(elements)):
for x in range(i + 1, len(elements)):
count += 1
total += (elements[x] - elements[i]) * max(cities[elements[i]], cities[elements[x]])
print count
return total % 1000000007
search = """2
3
1 3 6
10 20 30
5
5 55 555 55555 555555
3333 333 333 33 35"""
lines = search.split("\n")
try:
for i in range(0, len(lines)):
if i == 0:
amount = lines[i]
else:
if i % 3 == 1:
limit = int(lines[i])
elif i % 3 == 2:
towns = lines[i].split(" ", limit)
elif i % 3 == 0:
population = lines[i].split(" ", limit)
town = {}
for x in range(0, len(towns)):
town[int(towns[x])] = int(population[x])
print solve(town)
except:
pass
