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:
func Solution(A []int) int
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 Go
Time spent on task 28 minutes
Notes
not defined yet
Code: 01:34:20 UTC,
java,
autosave
Code: 01:34:30 UTC,
go,
autosave
Code: 01:49:23 UTC,
go,
autosave
Code: 01:49:44 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
max := 0
for i, k := range A {
}
}
Code: 01:50:14 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
max,index := 0,0
for i, k := range A {
t := i*k
if max < t {
max = t
index = i
}
}
retu
}
Code: 01:50:18 UTC,
go,
verify,
result: Failed
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
max,index := 0,0
for i, k := range A {
t := i*k
if max < t {
max = t
index = i
}
}
return index
}
Analysis
expand all
Example tests
1.
0.001 s
WRONG ANSWER,
got 3 expected 7
1.
0.001 s
WRONG ANSWER,
got 1 expected 0
1.
0.001 s
WRONG ANSWER,
got 4 expected 9
1.
0.001 s
WRONG ANSWER,
got 19 expected 499999972
Code: 01:54:01 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
max,index := 0,0
for i, k := range A {
t := i*k()
if max < t {
max = t
index = i
}
}
return index
}
Code: 01:54:18 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
max,index := 0,0
for i, k := range A {
t := k*(i+1)
if max < t {
max = t
index = i
}
}
return index
}
Code: 01:55:34 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
max,index := 0,0
for i, k := range A {
t := k*(i+1)
if max < t {
max = t
index = i
}
}
return index
}
Code: 01:55:45 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
max,index := 0,0
for i, k := range A {
t := k*(i+1)
if max < t {
max = t
index = i
}
}
return index
}
Code: 01:56:12 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
east := A[len(A)-1]
for i, k := range A {
t := k*(i+1)
if max < t {
max = t
index = i
}
}
return index
}
Code: 01:56:42 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
east := A[len(A)-1]
max, index := 0,0
for i, k := range A {
sum += (east-k)
t := (east-k)*(i+1)
if max < t {
max = t
index = i
}
}
return index
}
Code: 01:56:53 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
east := A[len(A)-1]
max, index := 0,0
for i, k := range A {
sum += (east-k)
t := (east-k)*(i+1)
if max < t {
max = t
index = i
}
}
return sum -
}
Code: 01:57:14 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
east := A[len(A)-1]
max, index := 0,0
for i, k := range A {
sum += (east-k)
t := (east-k)*(i+1)
if max < t {
max = t
index = i
}
}
return sum - (index+1)*(east-A[index])
}
Code: 01:57:17 UTC,
go,
verify,
result: Failed
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
east := A[len(A)-1]
max, index := 0,0
for i, k := range A {
sum += (east-k)
t := (east-k)*(i+1)
if max < t {
max = t
index = i
}
}
return sum - (index+1)*(east-A[index])
}
Analysis
expand all
Example tests
1.
0.001 s
OK
1.
0.001 s
OK
1.
0.001 s
OK
1.
0.001 s
WRONG ANSWER,
got 4500000000 expected 499999972
Code: 01:57:51 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
east := A[len(A)-1]
max, index := 0,0
for i, k := range A {
sum += (east-k)
t := (east-k)*(i+1)
if max < t {
max = t
index = i
}
}
return sum - (index+1)*(east-A[index])
}
Code: 01:58:06 UTC,
go,
autosave
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
east := A[len(A)-1]
max, index := 0,0
for i, k := range A {
sum += (east-k)
t := (east-k)*(i+1)
if max < t {
max = t
index = i
}
}
fmt.Println(sum, max, index)
return sum - (index+1)*(east-A[index])
}
Code: 01:58:12 UTC,
go,
verify,
result: Failed
package solution
// you can also use imports, for example:
// import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
east := A[len(A)-1]
max, index := 0,0
for i, k := range A {
sum += (east-k)
t := (east-k)*(i+1)
if max < t {
max = t
index = i
}
}
fmt.Println(sum, max, index)
return sum - (index+1)*(east-A[index])
}
Analysis
Compile error
# solution workspace/src/solution/solution.go:25: undefined: fmt
Code: 01:58:19 UTC,
go,
verify,
result: Failed
package solution
// you can also use imports, for example:
import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
east := A[len(A)-1]
max, index := 0,0
for i, k := range A {
sum += (east-k)
t := (east-k)*(i+1)
if max < t {
max = t
index = i
}
}
fmt.Println(sum, max, index)
return sum - (index+1)*(east-A[index])
}
Analysis
expand all
Example tests
1.
0.001 s
OK
stdout:
21 14 1
1.
0.001 s
OK
stdout:
10 10 0
1.
0.001 s
OK
stdout:
25 16 3
1.
0.001 s
WRONG ANSWER,
got 4500000000 expected 499999972
stdout:
9500000000 5000000000 9
Code: 01:59:55 UTC,
go,
autosave
package solution
// you can also use imports, for example:
import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
east := A[len(A)-1]
max, index := 0,0
for i, k := range A {
sum += (east-k)
t := (east-k)*(i+1)
if max < t {
max = t
index = i
}
}
fmt.Println(sum, max, index)
return (sum - (index+1)*(east-A[index])
}
Code: 02:00:05 UTC,
go,
autosave
package solution
// you can also use imports, for example:
import "fmt"
// import "os"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
east := A[len(A)-1]
max, index := 0,0
for i, k := range A {
sum += (east-k)
t := (east-k)*(i+1)
if max < t {
max = t
index = i
}
}
fmt.Println(sum, max, index)
return (sum - (index+1)*(east-A[index]))%()
}
Code: 02:00:20 UTC,
go,
autosave
package solution
// you can also use imports, for example:
import "fmt"
import "math"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
east := A[len(A)-1]
max, index := 0,0
for i, k := range A {
sum += (east-k)
t := (east-k)*(i+1)
if max < t {
max = t
index = i
}
}
fmt.Println(sum, max, index)
return (sum - (index+1)*(east-A[index]))%(math.Pow)
}
Code: 02:01:21 UTC,
go,
autosave
package solution
// you can also use imports, for example:
import "fmt"
import "math"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
east := A[len(A)-1]
max, index := 0,0
for i, k := range A {
sum += (east-k)
t := (east-k)*(i+1)
if max < t {
max = t
index = i
}
}
fmt.Println(sum, max, index)
return (sum - (index+1)*(east-A[index]))%1000000007
}
Code: 02:01:31 UTC,
go,
verify,
result: Failed
package solution
// you can also use imports, for example:
import "fmt"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
east := A[len(A)-1]
max, index := 0,0
for i, k := range A {
sum += (east-k)
t := (east-k)*(i+1)
if max < t {
max = t
index = i
}
}
return (sum - (index+1)*(east-A[index]))%1000000007
}
Analysis
Compile error
# solution workspace/src/solution/solution.go:4: imported and not used: "fmt"
Code: 02:01:37 UTC,
go,
verify,
result: Passed
package solution
// you can also use imports, for example:
// import "fmt"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
east := A[len(A)-1]
max, index := 0,0
for i, k := range A {
sum += (east-k)
t := (east-k)*(i+1)
if max < t {
max = t
index = i
}
}
return (sum - (index+1)*(east-A[index]))%1000000007
}
Analysis
Code: 02:01:44 UTC,
go,
verify,
result: Passed
package solution
// you can also use imports, for example:
// import "fmt"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
east := A[len(A)-1]
max, index := 0,0
for i, k := range A {
sum += (east-k)
t := (east-k)*(i+1)
if max < t {
max = t
index = i
}
}
return (sum - (index+1)*(east-A[index]))%1000000007
}
Analysis
Code: 02:01:46 UTC,
go,
final,
score:
100
package solution
// you can also use imports, for example:
// import "fmt"
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(A []int) int {
// write your code in Go 1.4
sum := 0
east := A[len(A)-1]
max, index := 0,0
for i, k := range A {
sum += (east-k)
t := (east-k)*(i+1)
if max < t {
max = t
index = i
}
}
return (sum - (index+1)*(east-A[index]))%1000000007
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 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.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
6.
0.001 s
OK
7.
0.001 s
OK
8.
0.001 s
OK
9.
0.001 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.001 s
OK
2.
0.001 s
OK
3.
0.001 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.001 s
OK
2.
0.001 s
OK
3.
0.001 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.001 s
OK
2.
0.001 s
OK
3.
0.001 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.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
expand all
Performance tests
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 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.004 s
OK
2.
0.004 s
OK
3.
0.004 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.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
4.
0.012 s
OK
5.
0.001 s
OK
6.
0.012 s
OK
7.
0.001 s
OK
8.
0.012 s
OK