Your browser is not supported. Please, update your browser or switch to a different one. Learn more about which browsers are supported.
Tasks Details
hard
1.
Refueling
Given the locations of cities and the amount of fuel at each of them, compute the maximum number of cities that can be visited.
Task Score
100%
Correctness
100%
Performance
100%
Task description
There are N cities arranged in a row (numbered from 0 to N−1). The K-th city is located at position X[K] and contains A[K] liters of fuel. Getting from city J to city K requires |X[J] − X[K]| liters of fuel.
Tom is planning a trip. He wants to visit as many cities as possible. Unfortunately, he is limited by the available fuel. To be precise, at the departure time from city J, leaving for city K, the tank should contain at least |X[J] − X[K]| liters of fuel. When Tom visits a city, he refuels his car with all the available fuel at this city. He can refuel at each city just once at most. The fuel tank has an infinite capacity.
Tom can arbitrarily choose the city from which to start his trip. Tom begins with an empty tank and immediately refuels his car at the starting city. He wants to know how many cities he can visit.
Write a function:
class Solution { public int solution(int[] A, int[] X); }
that, given two arrays A, X consisting of N integers each, returns the maximum number of different cities that Tom can visit.
Examples:
1. Given A = [4, 1, 4, 3, 3], X = [8, 10, 11, 13, 100], the function should return 4. One of the possible trips is: 1 → 2 → 0 → 3.
- Tom starts his trip in city number 1 and refuels 1 liter of fuel.
- Then he drives to city number 2 (it costs |10 − 11| = 1 liter of fuel) and refuels 4 liters of fuel.
- Next he drives to city number 0 (it costs |11 − 8| = 3 liters of fuel) and refuels 4 liters of fuel.
- Finally he drives to city number 3 (it costs |8 − 13| = 5 liters of fuel) and refuels 3 liters of fuel.
- Tom has insufficient fuel to reach city number 4.
2. Given A = [0, 10, 0], X = [1, 2, 3], the function should return 3. Tom can start his trip in city number 1. Then he can visit city number 0 followed by city number 2 (or vice versa). It costs 3 liters of fuel in total.
3. Given A = [0, 1, 0, 1, 1, 1, 0], X = [1, 2, 3, 4, 5, 6, 7], the function should return 4. Tom can start his trip in city number 3. Then he visits cities 4, 5 and 6, respectively.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..700];
- each element of array A is an integer within the range [0..1,000,000];
- each element of array X is an integer within the range [1..1,000,000];
- X[K] < X[K + 1] for each K within the range [0..N−2].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 21
Time spent on task 1 minutes
Notes
not defined yet
Task timeline
Code: 11:15:58 UTC,
java,
autosave
Code: 11:16:02 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int rightDirection1(int[] A, int[] X) {
int visited_cities = 1;
int max_visited_cities = 1;
for (int i = 0; i < X.length; i++) {
int numOfLiterals = A[i];
visited_cities = 1;
int endPoint = i;
int rightDistance = 0;
if (A[i] > 0) {
for (int j = i; j < X.length - 1; j++) {
if (numOfLiterals < (X[j + 1] - X[j])) {
break;
} else {
visited_cities += 1;
numOfLiterals -= (X[j + 1] - X[j]);
numOfLiterals += A[j + 1];
rightDistance += (X[j + 1] - X[j]);
endPoint = j + 1;
}
}
numOfLiterals -= rightDistance;
if (max_visited_cities < visited_cities) {
max_visited_cities = visited_cities;
}
if (visited_cities == X.length) {
return visited_cities;
}
for (int j = i; j > 0 && endPoint > i;) {
if (numOfLiterals < (X[j] - X[j - 1])) {
// if(A[i]>=(2*(X[endPoint]-X[i]))){
// numOfLiterals += (2 * (X[endPoint] - X[endPoint - 1]));
// }else if(A[i]-(2*(X[endPoint-1]-X[i]))>0){
// numOfLiterals += (A[i]-(2 * (X[endPoint-1] - X[i])));
// }
numOfLiterals += (2 * (X[endPoint] - X[endPoint - 1]));
numOfLiterals -= A[endPoint];
visited_cities -= 1;
endPoint--;
}
if (numOfLiterals >= (X[j] - X[j - 1])) {
visited_cities += 1;
numOfLiterals -= (X[j] - X[j - 1]);
numOfLiterals += A[j - 1];
j--;
}
if (max_visited_cities < visited_cities) {
max_visited_cities = visited_cities;
}
if (visited_cities == X.length) {
return visited_cities;
}
}
}
}
return max_visited_cities;
}
public int leftDirection1(int[] A, int[] X) {
int visited_cities = 1;
int max_visited_cities = 1;
for (int i = 0; i < X.length; i++) {
int numOfLiterals = A[i];
visited_cities = 1;
int endPoint = i;
int leftDistance = 0;
if (A[i] > 0) {
for (int j = i; j > 0; j--) {
if (numOfLiterals < (X[j] - X[j - 1])) {
break;
} else {
visited_cities += 1;
numOfLiterals -= (X[j] - X[j - 1]);
numOfLiterals += A[j - 1];
leftDistance += (X[j] - X[j - 1]);
endPoint = j - 1;
}
}
numOfLiterals -= leftDistance;
if (max_visited_cities < visited_cities) {
max_visited_cities = visited_cities;
}
if (visited_cities == X.length) {
return visited_cities;
}
for (int j = i; j < X.length - 1 && i > endPoint;) {
if (numOfLiterals < (X[j + 1] - X[j])) {
// if(A[i]>=(2*(X[i]-X[endPoint]))){
// numOfLiterals += (2 * (X[endPoint+1] - X[endPoint]));
// }else if(A[i]-(2*(X[i] - X[endPoint+1]))>0){
// numOfLiterals += (A[i]-(2 * (X[i] - X[endPoint+1])));
// }
numOfLiterals += (2 * (X[endPoint+1] - X[endPoint]));
numOfLiterals -= A[endPoint];
visited_cities -= 1;
endPoint++;
}
if (numOfLiterals >= (X[j + 1] - X[j])) {
visited_cities += 1;
numOfLiterals -= (X[j + 1] - X[j]);
numOfLiterals += A[j + 1];
j++;
}
if (max_visited_cities < visited_cities) {
max_visited_cities = visited_cities;
}
if (visited_cities == X.length) {
return visited_cities;
}
}
}
}
return max_visited_cities;
}
public int solution(int[] A, int[] X) {
int V1 = rightDirection1(A, X);
if (V1 == X.length) {
return V1;
}
int V2 = leftDirection1(A, X);
return Math.max(V1, V2);
}
}
Analysis
Code: 11:16:10 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int rightDirection1(int[] A, int[] X) {
int visited_cities = 1;
int max_visited_cities = 1;
for (int i = 0; i < X.length; i++) {
int numOfLiterals = A[i];
visited_cities = 1;
int endPoint = i;
int rightDistance = 0;
if (A[i] > 0) {
for (int j = i; j < X.length - 1; j++) {
if (numOfLiterals < (X[j + 1] - X[j])) {
break;
} else {
visited_cities += 1;
numOfLiterals -= (X[j + 1] - X[j]);
numOfLiterals += A[j + 1];
rightDistance += (X[j + 1] - X[j]);
endPoint = j + 1;
}
}
numOfLiterals -= rightDistance;
if (max_visited_cities < visited_cities) {
max_visited_cities = visited_cities;
}
if (visited_cities == X.length) {
return visited_cities;
}
for (int j = i; j > 0 && endPoint > i;) {
if (numOfLiterals < (X[j] - X[j - 1])) {
// if(A[i]>=(2*(X[endPoint]-X[i]))){
// numOfLiterals += (2 * (X[endPoint] - X[endPoint - 1]));
// }else if(A[i]-(2*(X[endPoint-1]-X[i]))>0){
// numOfLiterals += (A[i]-(2 * (X[endPoint-1] - X[i])));
// }
numOfLiterals += (2 * (X[endPoint] - X[endPoint - 1]));
numOfLiterals -= A[endPoint];
visited_cities -= 1;
endPoint--;
}
if (numOfLiterals >= (X[j] - X[j - 1])) {
visited_cities += 1;
numOfLiterals -= (X[j] - X[j - 1]);
numOfLiterals += A[j - 1];
j--;
}
if (max_visited_cities < visited_cities) {
max_visited_cities = visited_cities;
}
if (visited_cities == X.length) {
return visited_cities;
}
}
}
}
return max_visited_cities;
}
public int leftDirection1(int[] A, int[] X) {
int visited_cities = 1;
int max_visited_cities = 1;
for (int i = 0; i < X.length; i++) {
int numOfLiterals = A[i];
visited_cities = 1;
int endPoint = i;
int leftDistance = 0;
if (A[i] > 0) {
for (int j = i; j > 0; j--) {
if (numOfLiterals < (X[j] - X[j - 1])) {
break;
} else {
visited_cities += 1;
numOfLiterals -= (X[j] - X[j - 1]);
numOfLiterals += A[j - 1];
leftDistance += (X[j] - X[j - 1]);
endPoint = j - 1;
}
}
numOfLiterals -= leftDistance;
if (max_visited_cities < visited_cities) {
max_visited_cities = visited_cities;
}
if (visited_cities == X.length) {
return visited_cities;
}
for (int j = i; j < X.length - 1 && i > endPoint;) {
if (numOfLiterals < (X[j + 1] - X[j])) {
// if(A[i]>=(2*(X[i]-X[endPoint]))){
// numOfLiterals += (2 * (X[endPoint+1] - X[endPoint]));
// }else if(A[i]-(2*(X[i] - X[endPoint+1]))>0){
// numOfLiterals += (A[i]-(2 * (X[i] - X[endPoint+1])));
// }
numOfLiterals += (2 * (X[endPoint+1] - X[endPoint]));
numOfLiterals -= A[endPoint];
visited_cities -= 1;
endPoint++;
}
if (numOfLiterals >= (X[j + 1] - X[j])) {
visited_cities += 1;
numOfLiterals -= (X[j + 1] - X[j]);
numOfLiterals += A[j + 1];
j++;
}
if (max_visited_cities < visited_cities) {
max_visited_cities = visited_cities;
}
if (visited_cities == X.length) {
return visited_cities;
}
}
}
}
return max_visited_cities;
}
public int solution(int[] A, int[] X) {
int V1 = rightDirection1(A, X);
if (V1 == X.length) {
return V1;
}
int V2 = leftDirection1(A, X);
return Math.max(V1, V2);
}
}
Analysis
Code: 11:16:15 UTC,
java,
final,
score:
100
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int rightDirection1(int[] A, int[] X) {
int visited_cities = 1;
int max_visited_cities = 1;
for (int i = 0; i < X.length; i++) {
int numOfLiterals = A[i];
visited_cities = 1;
int endPoint = i;
int rightDistance = 0;
if (A[i] > 0) {
for (int j = i; j < X.length - 1; j++) {
if (numOfLiterals < (X[j + 1] - X[j])) {
break;
} else {
visited_cities += 1;
numOfLiterals -= (X[j + 1] - X[j]);
numOfLiterals += A[j + 1];
rightDistance += (X[j + 1] - X[j]);
endPoint = j + 1;
}
}
numOfLiterals -= rightDistance;
if (max_visited_cities < visited_cities) {
max_visited_cities = visited_cities;
}
if (visited_cities == X.length) {
return visited_cities;
}
for (int j = i; j > 0 && endPoint > i;) {
if (numOfLiterals < (X[j] - X[j - 1])) {
// if(A[i]>=(2*(X[endPoint]-X[i]))){
// numOfLiterals += (2 * (X[endPoint] - X[endPoint - 1]));
// }else if(A[i]-(2*(X[endPoint-1]-X[i]))>0){
// numOfLiterals += (A[i]-(2 * (X[endPoint-1] - X[i])));
// }
numOfLiterals += (2 * (X[endPoint] - X[endPoint - 1]));
numOfLiterals -= A[endPoint];
visited_cities -= 1;
endPoint--;
}
if (numOfLiterals >= (X[j] - X[j - 1])) {
visited_cities += 1;
numOfLiterals -= (X[j] - X[j - 1]);
numOfLiterals += A[j - 1];
j--;
}
if (max_visited_cities < visited_cities) {
max_visited_cities = visited_cities;
}
if (visited_cities == X.length) {
return visited_cities;
}
}
}
}
return max_visited_cities;
}
public int leftDirection1(int[] A, int[] X) {
int visited_cities = 1;
int max_visited_cities = 1;
for (int i = 0; i < X.length; i++) {
int numOfLiterals = A[i];
visited_cities = 1;
int endPoint = i;
int leftDistance = 0;
if (A[i] > 0) {
for (int j = i; j > 0; j--) {
if (numOfLiterals < (X[j] - X[j - 1])) {
break;
} else {
visited_cities += 1;
numOfLiterals -= (X[j] - X[j - 1]);
numOfLiterals += A[j - 1];
leftDistance += (X[j] - X[j - 1]);
endPoint = j - 1;
}
}
numOfLiterals -= leftDistance;
if (max_visited_cities < visited_cities) {
max_visited_cities = visited_cities;
}
if (visited_cities == X.length) {
return visited_cities;
}
for (int j = i; j < X.length - 1 && i > endPoint;) {
if (numOfLiterals < (X[j + 1] - X[j])) {
// if(A[i]>=(2*(X[i]-X[endPoint]))){
// numOfLiterals += (2 * (X[endPoint+1] - X[endPoint]));
// }else if(A[i]-(2*(X[i] - X[endPoint+1]))>0){
// numOfLiterals += (A[i]-(2 * (X[i] - X[endPoint+1])));
// }
numOfLiterals += (2 * (X[endPoint+1] - X[endPoint]));
numOfLiterals -= A[endPoint];
visited_cities -= 1;
endPoint++;
}
if (numOfLiterals >= (X[j + 1] - X[j])) {
visited_cities += 1;
numOfLiterals -= (X[j + 1] - X[j]);
numOfLiterals += A[j + 1];
j++;
}
if (max_visited_cities < visited_cities) {
max_visited_cities = visited_cities;
}
if (visited_cities == X.length) {
return visited_cities;
}
}
}
}
return max_visited_cities;
}
public int solution(int[] A, int[] X) {
int V1 = rightDirection1(A, X);
if (V1 == X.length) {
return V1;
}
int V2 = leftDirection1(A, X);
return Math.max(V1, V2);
}
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N**2) or O(N**2*log(N))
expand all
Correctness tests
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.008 s
OK
1.
0.008 s
OK
2.
0.012 s
OK
3.
0.004 s
OK
1.
0.008 s
OK
2.
0.004 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
1.
0.008 s
OK
2.
0.004 s
OK
small_each_group_needs_change_direction
N <= 50, many groups of cities are unreachable to each other. There is only one group with optimal solution.
N <= 50, many groups of cities are unreachable to each other. There is only one group with optimal solution.
✔
OK
1.
0.004 s
OK
2.
0.004 s
OK
expand all
Performance tests
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.012 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
large_one_big
Maximal N, exactly one city has significantly more available fuel than other cities.
Maximal N, exactly one city has significantly more available fuel than other cities.
✔
OK
1.
0.012 s
OK
2.
0.012 s
OK
1.
0.012 s
OK
2.
0.012 s
OK
1.
0.012 s
OK
2.
0.008 s
OK
large_each_group_needs_change_direction
Maximal N, many groups of cities are unreachable to each other. There is only one group with optimal solution.
Maximal N, many groups of cities are unreachable to each other. There is only one group with optimal solution.
✔
OK
1.
0.004 s
OK
2.
0.008 s
OK