Tasks Details
hard
1.
NewMotorway
Given a number of cities located along a road, build a motorway between two cities to minimize the sum of distances from all cities to the easternmost one.
Task Score
100%
Correctness
100%
Performance
100%
There are N cities (numbered from 0 to N-1) located along a road. The K-th city is situated A[K] from the beginning of the road in the west. Cities are numbered in ascending order of position, and no two of them lie in the same place. Formally, A[K] < A[K + 1] holds for every K from 0 to N-2.
The time needed to travel east from city X to the easternmost city equals A[N - 1] - A[X] unless there is a city Y to the east of X (as cars can drive only to the east) with a motorway to the easternmost city built. Then, travel time decreases to A[Y] - A[X] (time spent on the motorway is not considered). If city X has a motorway built, then the travel time from it equals 0.
There are no motorways right now, but one from any city to the easternmost city is planned to be built. Decide where to build it in order to minimize the sum of travel times from every city to the easternmost one.
Write a function:
def solution(A)
that, given an array A of N integers, returns the minimum total travel time as described above.
As the result might be large, return its remainder when divided by 109 + 7.
Examples:
1. Given A = [1, 5, 9, 12], the function should return 7.
- With the motorway from the 0th city the travel times would be: 0 for the 0th city as it has a motorway, 7 for the 1st city and 3 for the 2nd city: that is 10 in total.
- With the motorway from the 1st city the travel times would be: 4 for the 0th city, 0 for the 1st city and 3 for the 2nd city: that is 7 in total.
- With the motorway from the 2nd city the travel times would be: 8 for the 0th city, 4 for the 1st city and 0 for the 2nd city: that is 12 in total.
2. If A = [5, 15], the function should return 0.
We can only build a motorway from the 0th city to the 1st. Travel time from the city to the motorway is 0, so 0 is the answer.
3. If A = [2, 6, 7, 8, 12], the function should return 9.
- With the motorway from the 0th city the total travel time is equal to 0 + 6 + 5 + 4 = 15.
- With the motorway from the 1st city the total travel time is equal to 4 + 0 + 5 + 4 = 13.
- With the motorway from the 2nd city the total travel time is equal to 5 + 1 + 0 + 4 = 10.
- With the motorway from the 3rd city the total travel time is equal to 6 + 2 + 1 + 0 = 9.
The answer is 9, because that is the minimum total time among all motorway placement possibilities.
4. If N = 20 and A[K] = K * (5 * 107) for each K from 0 to 19, the function should return 499999972. The minimal total time among all motorway placement possibilities is 4500000000, whose remainder when divided by 109 + 7 is 499999972.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [2..100,000];
- each element of array A is an integer within the range [0..1,000,000,000];
- the elements of A are all distinct;
- array A is sorted in ascending order.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 30 minutes
Notes
not defined yet
Code: 14:41:24 UTC,
java,
autosave
Code: 14:56:37 UTC,
py,
autosave
Code: 14:56:59 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
result = sum(distances)
for i in range(len(A) - 1):
return result
Code: 14:57:18 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
current = sum(distances)
result = current
for i in range(len(A) - 1):
current
return result
Code: 14:57:29 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
current = sum(distances)
result = current
for i in range(len(A) - 1):
current -=
return result
Code: 14:57:41 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
current = sum(distances)
result = current
for i in range(len(A) - 1):
current -= distances[i]
current += _ * i
return result
Code: 14:58:08 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
current = sum(distances)
result = current
for i in range(len(A) - 1):
current -= distances[i]
current += diffs[i] * i
return result
Code: 14:58:47 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
current = sum(distances)
result = current
for i in range(len(A) - 1):
current -= distances[i ]
current += diffs[i] * i
return result
Code: 14:58:57 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
current = sum(distances)
result = current
for i in range(len(A) - 1):
current -= distances[i]
current += diffs[i] * i
return result
Code: 14:59:39 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [b - a for a, b in zip(A, A[1:])]
distances = [0] [end - a for a in A[:-1]]
current = sum(distances)
result = current
for i in range(len(A) - 1):
current -= distances[i]
current += diffs[i] * i
return result
Code: 14:59:50 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [0] + [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
current = sum(distances)
result = current
for i in range(len(A) - 1):
current -= distances[i]
current += diffs[i] * i
return result
Code: 15:00:08 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [0] + [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
print(diffs)
print(distances)
current = sum(distances)
print(current)
result = current
for i in range(len(A) - 1):
current -= distances[i]
current += diffs[i] * i
print(current)
return result
Code: 15:00:10 UTC,
py,
verify,
result: Failed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [0] + [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
print(diffs)
print(distances)
current = sum(distances)
print(current)
result = current
for i in range(len(A) - 1):
current -= distances[i]
current += diffs[i] * i
print(current)
return result
Analysis
expand all
Example tests
1.
0.036 s
WRONG ANSWER,
got 21 expected 7
stdout:
[0, 4, 4, 3] [11, 7, 3] 21 10 7 12
1.
0.036 s
WRONG ANSWER,
got 10 expected 0
stdout:
[0, 10] [10] 10 0
1.
0.036 s
WRONG ANSWER,
got 25 expected 9
stdout:
[0, 4, 1, 1, 4] [10, 6, 5, 4] 25 15 13 10 9
1.
0.036 s
WRONG ANSWER,
got 9500000000 expected 499999972
stdout:
[0, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000] [950000000, 900000000, 850000000, 800000000, 750000000, 700000000, 650000000, 600000000, 550000000, 500000000, 450000000, 400000000, 350000000, 300000000, 250000000, 200000000, 150000000, 100000000, 50000000] 9500000000 8550000000 7700000000 6950000000 6300000000 5750000000 5300000000 4950000000 4700000000 4550000000 4500000000 4550000000 4700000000 4950000000 5300000000 5750000000 6300000000 6950000000 7700000000 8550000000
Code: 15:00:47 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [0] + [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
print(diffs)
print(distances)
current = sum(distances)
print(current)
result = current
for i in range(len(A) - 1):
current -= distances[i]
current += diffs[i] * i
print(current)
re
return result
Code: 15:00:57 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [0] + [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
print(diffs)
print(distances)
current = sum(distances)
print(current)
result = current
for i in range(len(A) - 1):
current -= distances[i]
current += diffs[i] * i
print(current)
result = min(result, current)
return result
Code: 15:00:58 UTC,
py,
verify,
result: Failed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [0] + [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
print(diffs)
print(distances)
current = sum(distances)
print(current)
result = current
for i in range(len(A) - 1):
current -= distances[i]
current += diffs[i] * i
print(current)
result = min(result, current)
return result
Analysis
expand all
Example tests
1.
0.036 s
OK
stdout:
[0, 4, 4, 3] [11, 7, 3] 21 10 7 12
1.
0.036 s
OK
stdout:
[0, 10] [10] 10 0
1.
0.036 s
OK
stdout:
[0, 4, 1, 1, 4] [10, 6, 5, 4] 25 15 13 10 9
1.
0.036 s
WRONG ANSWER,
got 4500000000 expected 499999972
stdout:
[0, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000] [950000000, 900000000, 850000000, 800000000, 750000000, 700000000, 650000000, 600000000, 550000000, 500000000, 450000000, 400000000, 350000000, 300000000, 250000000, 200000000, 150000000, 100000000, 50000000] 9500000000 8550000000 7700000000 6950000000 6300000000 5750000000 5300000000 4950000000 4700000000 4550000000 4500000000 4550000000 4700000000 4950000000 5300000000 5750000000 6300000000 6950000000 7700000000 8550000000
Code: 15:01:27 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
MOD = 10 ** 9 / 7
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [0] + [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
print(diffs)
print(distances)
current = sum(distances)
print(current)
result = current
for i in range(len(A) - 1):
current -= distances[i]
current += diffs[i] * i
print(current)
result = min(result, current)
return result
Code: 15:01:44 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
MOD = 10 ** 9 + 7
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [0] + [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
print(diffs)
print(distances)
current = sum(distances)
print(current)
result = current
for i in range(len(A) - 1):
current -= distances[i]
current += diffs[i] * i
print(current)
result = min(result, current)
return result
Code: 15:01:57 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
MOD = 10 ** 9 + 7
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [0] + [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
print(diffs)
print(distances)
current = sum(distances)
print(current)
result = current
for i in range(len(A) - 1):
current -= distances[i]
current += diffs[i] * i
print(current)
result = min(result, current)
return result % MOD
Analysis
expand all
Example tests
1.
0.036 s
OK
stdout:
[0, 4, 4, 3] [11, 7, 3] 21 10 7 12
1.
0.036 s
OK
stdout:
[0, 10] [10] 10 0
1.
0.036 s
OK
stdout:
[0, 4, 1, 1, 4] [10, 6, 5, 4] 25 15 13 10 9
1.
0.036 s
OK
stdout:
[0, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000, 50000000] [950000000, 900000000, 850000000, 800000000, 750000000, 700000000, 650000000, 600000000, 550000000, 500000000, 450000000, 400000000, 350000000, 300000000, 250000000, 200000000, 150000000, 100000000, 50000000] 9500000000 8550000000 7700000000 6950000000 6300000000 5750000000 5300000000 4950000000 4700000000 4550000000 4500000000 4550000000 4700000000 4950000000 5300000000 5750000000 6300000000 6950000000 7700000000 8550000000
Code: 15:02:18 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
MOD = 10 ** 9 + 7
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [0] + [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
current = sum(distances)
print(current)
result = current
for i in range(len(A) - 1):
current -= distances[i]
current += diffs[i] * i
print(current)
result = min(result, current)
return result % MOD
Code: 15:02:39 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
MOD = 10 ** 9 + 7
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [0] + [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
current = sum(distances)
result = current
for i in range(len(A) - 1):
current = current - distances[i] + diffs[i] * i
result = min(result, current)
return result % MOD
Code: 15:03:02 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
MOD = 10 ** 9 + 7
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [0] + [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
# start with no highways (worse case)
current = sum(distances)
result = current
# build a highway between each
for i in range(len(A) - 1):
current = current - distances[i] + diffs[i] * i
result = min(result, current)
return result % MOD
Code: 15:03:30 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
MOD = 10 ** 9 + 7
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [0] + [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
# start with no motorway (worse case)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for i in range(len(A) - 1):
# to calculate the new cost:
# * incur the cost of
current = current - distances[i] + diffs[i] * i
result = min(result, current)
return result % MOD
Code: 15:04:00 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
MOD = 10 ** 9 + 7
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [0] + [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
# start with no motorway (worse case)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for i in range(len(A) - 1):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distances[i] + diffs[i] * i
#
result = min(result, current)
return result % MOD
Code: 15:04:31 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
MOD = 10 ** 9 + 7
def solution(A):
# write your code in Python 3.6
end = A[-1]
diffs = [0] + [b - a for a, b in zip(A, A[1:])]
distances = [end - a for a in A[:-1]]
# start with no motorway (worse case)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for i in range(len(A) - 1):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distances[i] + diffs[i] * i
# only remember the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
Code: 15:05:01 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
diffs = [0] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (worse case)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for i in range(len(A) - 1):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distances[i] + diffs[i] * i
# only remember the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
Code: 15:05:16 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# ()
diffs = [0] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (worse case)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for i in range(len(A) - 1):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distances[i] + diffs[i] * i
# only remember the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
Code: 15:05:44 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (worse case)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for i in range(len(A) - 1):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distances[i] + diffs[i] * i
# only remember the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
Code: 15:06:04 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (worse case)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for i in range(len(A) - 1):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distances[i] + diffs[i] * i
# only remember the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
User test case 1:
[10]
Analysis
Code: 15:06:21 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway ()
current = sum(distances)
result = current
# build a motorway between each city, left to right
for i in range(len(A) - 1):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distances[i] + diffs[i] * i
# only remember the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
Code: 15:06:33 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (e.g. if there's only one city)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for i in range(len(A) - 1):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distances[i] + diffs[i] * i
# only remember the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
User test case 1:
[1, 2, 3, 4, 5, 6, 7]
Analysis
Code: 15:07:05 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (e.g. if there's only one city)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for i in range(len(A) - 1):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distances[i] + diffs[i] * i
# only remember the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
Code: 15:07:05 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (e.g. if there's only one city)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for i in range(len(A) - 1):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distances[i] + diffs[i] * i
# only remember the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
User test case 1:
[1, 2, 3, 4, 5]
Analysis
Code: 15:07:25 UTC,
py,
autosave
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (e.g. if there's only one city)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for i in range(len(A) - 1):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distances[i] + diffs[i] * i
# only remember the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
Code: 15:07:56 UTC,
py,
autosave
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (e.g. if there's only one city)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for i in range(len(A) - ):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distances[i] + diffs[i] * i
# only remember the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
Code: 15:08:06 UTC,
py,
autosave
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (e.g. if there's only one city)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for i in range(len(distances)):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distances[i] + diffs[i] * i
# only remember the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
Code: 15:08:30 UTC,
py,
autosave
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (e.g. if there's only one city)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for index, (distance, diff)
for i in range(len(distances)):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distances[i] + diffs[i] * i
# only remember the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
Code: 15:08:46 UTC,
py,
autosave
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (e.g. if there's only one city)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for index, (distance, diff) in enumerate(zip(distances, diffs)):
#for i in range(len(distances)):
# # to calculate the new cost:
# # * remove the cost of the motorway city
# # * add the costs of travelling from the earlier cities to the motorway city
# current = current - distances[i] + diffs[i] * i
# # only remember the cheapest route
# result = min(result, current)
# number big, big number sad, make small
return result % MOD
Code: 15:09:01 UTC,
py,
verify,
result: Passed
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (e.g. if there's only one city)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for index, (distance, diff) in enumerate(zip(distances, diffs)):
current = current - distance + diff * index
result = min(result, current)
#for i in range(len(distances)):
# # to calculate the new cost:
# # * remove the cost of the motorway city
# # * add the costs of travelling from the earlier cities to the motorway city
# current = current - distances[i] + diffs[i] * i
# # only remember the cheapest route
# result = min(result, current)
# number big, big number sad, make small
return result % MOD
User test case 1:
[1, 2, 3, 4, 5]
Analysis
Code: 15:09:16 UTC,
py,
autosave
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (e.g. if there's only one city)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for index, (distance, diff) in enumerate(zip(distances, diffs)):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distance + diff * index
result = min(result, current)
#for i in range(len(distances)):
# # to calculate the new cost:
# # * remove the cost of the motorway city
# # * add the costs of travelling from the earlier cities to the motorway city
# current = current - distances[i] + diffs[i] * i
# # only remember the cheapest route
# result = min(result, current)
# number big, big number sad, make small
return result % MOD
Code: 15:09:26 UTC,
py,
autosave
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (e.g. if there's only one city)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for index, (distance, diff) in enumerate(zip(distances, diffs)):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distance + diff * index
# only rememeber the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
Code: 15:09:56 UTC,
py,
autosave
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (e.g. if there's only one city)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for index, (distance, diff) in enumerate(zip(distances, diffs)):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distance + diff * index
# only rememeber the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
Code: 15:10:01 UTC,
py,
verify,
result: Passed
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (e.g. if there's only one city)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for index, (distance, diff) in enumerate(zip(distances, diffs)):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distance + diff * index
# only rememeber the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
User test case 1:
[1, 4]
Analysis
Code: 15:10:13 UTC,
py,
verify,
result: Passed
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (e.g. if there's only one city)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for index, (distance, diff) in enumerate(zip(distances, diffs)):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distance + diff * index
# only rememeber the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
User test case 1:
[1, 4, 99]
Analysis
Code: 15:10:18 UTC,
py,
verify,
result: Passed
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (e.g. if there's only one city)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for index, (distance, diff) in enumerate(zip(distances, diffs)):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distance + diff * index
# only rememeber the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
User test case 1:
[1, 97, 99]
Analysis
Code: 15:10:24 UTC,
py,
verify,
result: Passed
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (e.g. if there's only one city)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for index, (distance, diff) in enumerate(zip(distances, diffs)):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distance + diff * index
# only rememeber the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MOD
User test case 1:
[1, 97, 99]
Analysis
Code: 15:10:27 UTC,
py,
final,
score:
100
MOD = 10 ** 9 + 7
def solution(A):
# calculate the distance between each adjacent city
# (the first city is measured from 0, but it won't matter)
diffs = [A[0]] + [b - a for a, b in zip(A, A[1:])]
# calculate the distance to the eastern city for each city
distances = [A[-1] - a for a in A[:-1]]
# start with no motorway (e.g. if there's only one city)
current = sum(distances)
result = current
# build a motorway between each city, left to right
for index, (distance, diff) in enumerate(zip(distances, diffs)):
# to calculate the new cost:
# * remove the cost of the motorway city
# * add the costs of travelling from the earlier cities to the motorway city
current = current - distance + diff * index
# only rememeber the cheapest route
result = min(result, current)
# number big, big number sad, make small
return result % MODAnalysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
equal_adjacent_distances
Test cases where distances between adjacent cities are equal. N <= 100.
Test cases where distances between adjacent cities are equal. N <= 100.
✔
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
6.
0.036 s
OK
7.
0.036 s
OK
8.
0.036 s
OK
9.
0.036 s
OK
adjacent_distances_non_decreasing
Test cases where distances between adjacent cities are non-decreasing. N <= 100.
Test cases where distances between adjacent cities are non-decreasing. N <= 100.
✔
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
adjacent_distances_non_increasing
Test cases where distances between adjacent cities are non-increasing. N <= 100.
Test cases where distances between adjacent cities are non-increasing. N <= 100.
✔
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
modulo_needed
Test cases where the result is big and its division remainder has to be returned. N <= 100. Score x 0.5.
Test cases where the result is big and its division remainder has to be returned. N <= 100. Score x 0.5.
✔
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
int64_needed
Test cases where the result is big and 64-bit variables are needed. N <= 100. Score x 0.5.
Test cases where the result is big and 64-bit variables are needed. N <= 100. Score x 0.5.
✔
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
expand all
Performance tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
equal_adjacent_distances_big
Test cases where distances between adjacent cities are equal. N <= 40,000. Score x 2.
Test cases where distances between adjacent cities are equal. N <= 40,000. Score x 2.
✔
OK
1.
0.088 s
OK
2.
0.068 s
OK
3.
0.064 s
OK
adjacent_distances_non_increasing_big
Test cases where distances between adjacent cities are non-increasing. N <= 40,000. Score x 2.
Test cases where distances between adjacent cities are non-increasing. N <= 40,000. Score x 2.
✔
OK
1.
0.076 s
OK
2.
0.092 s
OK
3.
0.080 s
OK
1.
0.132 s
OK
2.
0.132 s
OK
3.
0.088 s
OK
4.
0.164 s
OK
5.
0.056 s
OK
6.
0.164 s
OK
7.
0.036 s
OK
8.
0.184 s
OK