CODEWITHSUNDEEP
algorithmperformancedynamic-programming
NJrslv
NJrslv

Reputation: 25

Dynamic programming algorithm speedup

Problem description:

On a road, there are golden coins scattered in some places. For each coin, its location is known, which is given by a single integer - the distance in meters from the point '0' meters. All coins are located to the right of the starting point at different distances from the beginning. Ali-Baba runs along the road and collects coins, starting to do so at time 0. He runs exactly one meter per second. Each coin has a deadline by which it must be picked up, otherwise the coin will disappear. Ali-Baba must collect all the coins and do so in the shortest possible time. He can start at any point on the line, collect the coins in any order, but he must definitely collect all the coins and minimize the time spent doing so.

Example:

Input: The first line contains an integer n (n <= 10000) - coins. Each of the next n lines contains two integers d and t, the first of which specifies the position of a coin (1 ≤ d ≤ 10 000), and the second - the deadline in seconds (1 ≤ t ≤ 10 000), before which it is necessary to collect this coin (at time exactly t it is also possible to pick up a coin). The coins are listed in order of increasing distance from the beginning (from left to right).

input.txt:

5
1 3
3 1
5 8
8 19
10 15

output.txt:

11

My solution(O(n^2)):

Statement that can be made for this problem:

For any subsequence of coins, we will finish collecting coins either on the last or on the first one.

dp[i][j]

Let the array dp[i][j] be the minimum time to cover the area(i...j) with coins, assuming you finished on coin j.

Optimality of substructure.

Consider the segment i..j, then we can finish on coin i or j. If we ended on j. then we could arrive at it by solving subtask [i..j-1] and going from j-1 to j coin, or by solving subtask [j..i+1](i+1 < j) and jumping from i+1 to j coin. Similarly, if we finish on i coin, from the previous subtask we can jump from its two ends to a larger problem.

Base.

if i = j, then dp[i][j] = 0, because we can start from any coin.

Dp with memoization


std::vector<coin> in; // input array
std::vector<std::vector<int64_t>> dp; // with default values = -1;

int64_t dist(const coin& cstart, const coin& cend, int64_t prev_time) {
    if(cend.ctime - prev_time - std::abs(cend.cdist - cstart.cdist) >= 0)
        return std::abs(cend.cdist - cstart.cdist);
    else 
        return INT64_MAX;
}

int64_t F(size_t i, size_t j) {
    if (i == j) {
        dp[i][j] = 0;
    } else if(dp[i][j] == -1) {
        if(j > i){
            int64_t i_to_j_min_1 = F(in, dp, i, j - 1);
            int64_t j_min_1_to_i = F(in, dp, j - 1, i);
            dp[i][j] = std::min(add(i_to_j_min_1, dist(in[j - 1], in[j], i_to_j_min_1)) , 
                                add(j_min_1_to_i, dist(in[i], in[j], j_min_1_to_i)));

            int64_t i_plus_1_to_j = F(in, dp, i + 1, j);
            int64_t j_to_i_plus_1 = F(in, dp, j, i + 1);
            dp[j][i] = std::min(add(i_plus_1_to_j, dist(in[j], in[i], i_plus_1_to_j)),
                                add(j_to_i_plus_1, dist(in[i + 1], in[i], j_to_i_plus_1)));
        }
    }
    return dp[i][j];
}

My Problem

Can i make my algorithm faster?

Upvotes: 2

Views: 233

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

In some cases we can reduce the number of coins to consider.

Observe that if we have three coins c1, c2, c3 with distance(c1) ≤ distance(c2) ≤ distance(c3) and deadline(c1) ≤ deadline(c2) and deadline(c3) ≤ deadline(c2), then we can forget about c2 – the other coins guarantee a timely visit. All forgettable coins can be removed in linear time using a variant of Andrew’s monotone chain algorithm.

Upvotes: 1

Related Questions