I am trying to solve the following challenge on Codility (screenshot here) from a now closed challenge here here.

I have managed to get a O(N³) solution (basically using DFS) working as below -

from copy import deepcopy

def solution(fuel_arr, dist_arr):
    
    n = len(dist_arr)
    if n == 1:
        return 1

    st = [([town], set([town]), fuel_arr[town]) for town in range(n)]
    max_num_towns = 1
    while st:
        path_so_far, visited, fuel_left = st.pop()
        cur_town = path_so_far[-1]
        for town in range(n):
            if town not in visited and fuel_left >= abs(dist_arr[cur_town] - dist_arr[town]):
                new_visited = deepcopy(visited)
                new_visited.add(town)
                new_path = deepcopy(path_so_far)
                new_path.append(town)
                new_fuel = fuel_left - abs(dist_arr[cur_town] - dist_arr[town])   fuel_arr[town]
                max_num_towns = max(max_num_towns, len(new_path))
                if max_num_towns == n:
                    return n
                st.append((new_path, new_visited, new_fuel))
    return max_num_towns

However, I am still getting time limit exceeded errors, which makes me think the ideal solution is O(N²). Does anyone have any ideas on how to further optimise the runtime?

EDIT

The text of the question is reproduced below. For a screenshot of the question text (as it has better formatting), please refer here

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:

def solution(A, 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.
The picture describes the first example test.

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].

CodePudding user response：

Given any solution, following the exact same path except visiting each city the first time you drive past it gives another solution that cannot be worse than the original.

If we only consider solutions that do this, at any point in time we have visited all of the cities from i to j, we are actually at either city i or city j, and we have some amount of gas. Given any two partial solutions, the one which has more gas having seen the same cities and arrived at the same place cannot do worse from then on. So we only need to consider the most gas we might wind up with there.

So the trips of length k we need to think about can all be described as (i, j, j) or (i, j, i) where i <= j and i k = j 1. From one of those trips, the next trip (if possible) can be described as (i-1, j, i-1) or (i, j 1, j 1). And the only fact we need about a trip is current fuel. Which we can store in a dictionary.

We can start with a dictionary of all trips of 1 city. Which will look like:

trip = {
    (0, 0, 0): fuel_arr[0],
    (1, 1, 1): fuel_arr[2],
    ...
}

We can then calculate all trips of length 1. Then all trips of length 2. And so on until no trip can add a city. At which point we have the answer.

I'll leave coding it as an exercise. But if you're clever, you should be able to use O(n) memory and O(n^2) time. Which will be sufficient for Codility.

CodePudding user response：

Try to think about the problem with a greedy approach.

As you have inf fuel capacity, you should always try to fuel at each city. You also want to make the biggest jump.

Now, if you just go to the furthest city from the current location and make a jump from there it may not be optimal. So, in that case, you have to choose the city in a range from which you can make the longest jump (more fuel than the distance that needs to be traveled).

So, if you have three nodes (a, b, c),

distance: a->b->->c->->->->->d->->->e ...
fuel:     4  10   2          2      1 ...

From a you can reach both b and c, even though c is the furthest city from a, you should choose b, as from b you can fuel your tank to cover way more distance.