Problem 4 - Backpacking

Here, we will discuss the solution to Backpacking from AIO 2024.

Solution

Subtask 1: C_i ≤ C_i+1 for all i

In this subtask, it is always cheaper to buy food in earlier towns. Ideally, we would buy all the food in town 1. However, this may not be possible, depending on the size of our backpack. Instead, at each town, we either:

• Buy exactly enough cans to get us to town N, if our backpack can fit this many cans.
• If our backpack is not big enough, then we buy enough cans to completely fill our backpack.

Code for Subtask 1

# Read the values of N, K, D, and C.
N, K = map(int, input().strip().split())
D = list(map(int, input().strip().split()))
C = list(map(int, input().strip().split()))

answer = 0
need_to_buy = sum(D)
curr_backpack = 0

for i in range(N-1):
   # K-curr_backpack is the maximum number of cans we can fit in our backpack
   # need_to_buy is the number of extra cans we need to reach the final town
   to_buy = min(K-curr_backpack, need_to_buy)
   curr_backpack += to_buy
   need_to_buy -= to_buy
   answer += to_buy * C[i]

   # We walk from town i to town i+1, eating D[i] cans
   curr_backpack -= D[i]

# Write the answer.
print(answer)

#include <cstdio>
#include <algorithm>
int N, K, D[200005], C[200005];
int main(void) {
    /* Read the values of N, K, D, and C. */
    scanf("%d%d", &N, &K);
    for (int i = 0; i < N-1; i++) {
        scanf("%d", &D[i]);
    }
    for (int i = 0; i < N; i++) {
        scanf("%d", &C[i]);
    }

    int answer = 0;
    int need_to_buy = 0;
    for (int i = 0; i < N-1; i++) {
        need_to_buy += D[i];
    }

    int curr_backpack = 0;
    for (int i = 0; i < N-1; i++) {
        // K-curr_backpack is the maximum number of cans we can fit in our backpack
        // need_to_buy is the number of extra cans we need to reach the final town
        int to_buy = std::min(K-curr_backpack, need_to_buy);
        curr_backpack += to_buy;
        need_to_buy -= to_buy;
        answer += to_buy * C[i];

        // We walk from town i to town i+1, eating D[i] cans
        curr_backpack -= D[i];
    }

    /* Write the answer. */
    printf("%d\n", answer);
}

Subtask 2: K = 1000000

In this subtask, our backpack is big enough to fit all the cans we will ever need:

• If the first town is the cheapest town then we can buy all our cans in the first town.
• If the first town is not the cheapest town then we don't want to buy all our cans at once.
  • Instead, we buy just enough cans to reach the closest cheaper town. We can then buy more cans in that cheaper town, using the same procedure.

Consider an example with 7 towns that have costs 4, 6, 3, 5, 1, 2, 3:

• At the first town, we should buy just enough cans to reach the third town.
• We do not buy any cans in the second town, because it is more expensive than the first town.
• At the third town, we should buy just enough cans to reach the fifth town.
• We do not buy any cans in the fourth town, because it is more expensive than the third town.
• At the fifth town, we should buy enough cans to reach the final town.

Unfortunately, an algorithm with a time complexity of O(N²) is too slow for this subtask. Luckily, with some careful planning, we can do this process in O(N) time.

• One way is to pretend that we bought all the cans at the first town.
• Then, when we reach a cheaper town, we calculate how much we would save by buying at this town instead of the first town and subtract these savings from the answer.
• The below code uses this approach.

Code for Subtask 2

# Read the values of N, K, D, and C.
N, K = map(int, input().strip().split())
D = list(map(int, input().strip().split()))
C = list(map(int, input().strip().split()))

distance_to_end = sum(D)

# We start by buying every can at town 1
price_paid = C[0]
answer = price_paid*distance_to_end

for i in range(N-1):
   if C[i] < price_paid:
       # C[i] is the cheapest town so far
       # If we bought the remaining cans from this town,
       # we would save price_paid-C[i] dollars per can
       answer -= (price_paid-C[i]) * distance_to_end
       price_paid = C[i]

   distance_to_end -= D[i]

# Write the answer.
print(answer)

#include <cstdio>
#include <algorithm>
int N, K, D[200005], C[200005];
int main(void) {
    /* Read the values of N, K, D, and C. */
    scanf("%d%d", &N, &K);
    for (int i = 0; i < N-1; i++) {
        scanf("%d", &D[i]);
    }
    for (int i = 0; i < N; i++) {
        scanf("%d", &C[i]);
    }

    int distance_to_end = 0;
    for (int i = 0; i < N-1; i++) {
        distance_to_end += D[i];
    }

    int price_paid = C[0];
    int answer = price_paid*distance_to_end;
    for (int i = 0; i < N-1; i++) {
        if (C[i] < price_paid) {
            // C[i] is the cheapest town so far
            // If we bought the remaining cans from this town,
            // we would save price_paid-C[i] dollars per can
            answer -= (price_paid-C[i]) * distance_to_end;
            price_paid = C[i];
        }

        distance_to_end -= D[i];
    }

    /* Write the answer. */
    printf("%d\n", answer);
}

Subtask 3: N ≤ 1000

This problem has many different solutions and we will present just one of them. Our solution combines some of the ideas from subtasks 1 and 2. We consider the towns one at a time, in order. At each town, we either:

• Buy exactly enough cans to reach the closest town that is cheaper than the current town, if our backpack can fit this many.
  • If there is no cheaper town after the current town, then we buy enough cans to reach the end.
  • This is similar to the subtask 2 solution!
• If our backpack is not big enough to buy enough cans to reach the next cheaper town, then we buy enough cans to completely fill our backpack.
  • Unfortunately, this means that we will need to buy cans in a more expensive town later on.
  • This is similar to the subtask 1 solution!

See below for an example of this solution.

Similarly to Shopping Spree, we can use an exchange argument to prove that this greedy algorithm is correct:

• Assume that we buy cans using a different solution (call this solution B), and let town i be the earliest town where this solution differs from our solution (which we will call solution A). We will show that solution B would remain the same or improve if it made the same choices as solution A at town i. Therefore, the choices made by solution A are always optimal.
• If solution B bought fewer cans at town i than solution A did, then solution B is forced to buy more cans later on. Additionally, these cans must have cost equal to or more than C_i:
  • This is because solution A tries to buy cans to get all the way to the next cheaper town. Since solution B bought fewer cans at town i, it must have bought extra cans later on but before the next cheaper town.
  • If solution B had instead bought these cans at town i (like solution A did), these would either cost the same price or be cheaper.
• If solution B bought more cans at town i than solution A did, then solution B could be improved. In particular, we can improve solution B in one of two ways:
  • If solution B bought more cans than are necessary to reach the final town, then we could simply buy fewer cans to obtain a better solution.
  • Otherwise, let town j be the closest town after i that is cheaper than i. Then, solution B must have bought enough cans to reach town j and some extra cans. Solution B could be improved by instead buying these extra cans at town j, since town j is cheaper than town i.
• Therefore the choices made by our solution are always optimal and so our algorithm is correct.

What is the time complexity of this solution?

• At each town, we need to find the closest town after it that is cheaper.
• The easiest way to do this is to loop over the towns and stop once we find a town that is cheaper.
• This has a worst-case time complexity of O(N) per town, giving O(N²) overall. This is fast enough to solve subtask 3, but not fast enough to solve the other subtasks.

Code for Subtask 3

# distance_to_town[i] will store the distance from town 0 to town i (that is, D[0] + D[1] + ... + D[i-1])
distance_to_town = []
    
# firstCheaperAfter[i] will contain the index of the first town after i that is cheaper than i (or N-1) if no town is cheaper than i
firstCheaperAfter = []
    
# Read the values of N, K, D, and C.
N, K = map(int, input().strip().split())
D = list(map(int, input().strip().split()))
C = list(map(int, input().strip().split()))
    
answer = 0
    
# Compute the distance_to_town list
distance_to_town.append(0)
for i in range(1, N):
    distance_to_town.append(distance_to_town[i-1] + D[i-1])
    
# Compute the firstCheaperAfter array
for i in range(N):
    firstCheaperAfter.append(N-1)
    for j in range(i+1, N):
        if C[j] < C[i]:
            firstCheaperAfter[i] = j
            break
    
in_backpack = 0 # in_backpack stores the number of cans in our backpack at the current moment
for i in range(N):
    distance_to_cheaper_town = distance_to_town[firstCheaperAfter[i]] - distance_to_town[i]
    
    # our backpack can hold at most K cans
    distance_to_cheaper_town = min(distance_to_cheaper_town, K)
    
    # we need distance_to_cheaper_town cans to reach the next cheaper town, however we already have in_backpack
    # therefore distance_to_cheaper_town-in_backpack is the number of extra cans we want to buy
    # this value can be negative, which is why we max it with 0
    will_buy = max(0, distance_to_cheaper_town - in_backpack)
        
    answer += will_buy * C[i]
    in_backpack += will_buy
    
    # we now walk to the next town, eating D[i] cans
    if i < N-1:
        in_backpack -= D[i]
    
# Write the answer.
print(answer)

#include <cstdio>
#include <algorithm> // for std::min and std::max

int N, K, D[200005], C[200005];

/*
 * distance_to_town[i] will store the distance from town 0 to town i (that is, D[0] + D[1] + ... + D[i-1])
 */
int distance_to_town[200005];

/*
 * firstCheaperAfter[i] will contain the index of the first town after i that is cheaper than i (or N-1) if no town is cheaper than i
 */
int firstCheaperAfter[200005];

int answer;
int main(void) {
    /* Read the values of N, K, D, and C. */
    scanf("%d%d", &N, &K);
    for (int i = 0; i < N-1; i++) {
        scanf("%d", &D[i]);
    }
    for (int i = 0; i < N; i++) {
        scanf("%d", &C[i]);
    }

    // Compute the distance_to_town array
    for (int i = 1; i < N; i++) {
        distance_to_town[i] = distance_to_town[i-1] + D[i-1];
    }

    // Compute the firstCheaperAfter array
    for (int i = 0; i < N; i++) {
        firstCheaperAfter[i] = N-1;
        for (int j = i+1; j < N; j++) {
            if (C[j] < C[i]) {
                firstCheaperAfter[i] = j;
                break;
            }
        }
    }

    int in_backpack = 0; // in_backpack stores the number of cans in our backpack at the current moment
    for (int i = 0; i < N; i++) {
        int distance_to_cheaper_town = distance_to_town[firstCheaperAfter[i]] - distance_to_town[i];
        
        // our backpack can hold at most K cans
        distance_to_cheaper_town = std::min(distance_to_cheaper_town, K);
        
        // we need distance_to_cheaper_town cans to reach the next cheaper town, however we already have in_backpack
        // therefore distance_to_cheaper_town-in_backpack is the number of extra cans we want to buy
        // this value can be negative, which is why we max it with 0
        int will_buy = std::max(0, distance_to_cheaper_town - in_backpack);
        
        answer += will_buy * C[i];
        in_backpack += will_buy;

        // we now walk to the next town, eating D[i] cans
        in_backpack -= D[i];
    }

    /* Write the answer. */
    printf("%d\n", answer);

    return 0;
}

Full Solution

We can use the same greedy algorithm as subtask 3, but we must improve the time complexity. For each town i, we need to find the closest town after i that is cheaper than town i. This is the slow part of our solution. We can speed it up by utilising the constraint that 1 ≤ C_i ≤ 20 for all i:

• We will loop backwards over the towns.
• While doing this, we have an array that stores, for each c, the most recent town we have seen that has C[i] = c (call this array X, and so X[c] is the most recent town we have seen with C_X[c] = c).
• The closest town that is cheaper is min(X[1], X[2], ..., X[C_i-1]).
• After calculating min(X[1], X[2], ..., X[C_i-1]), we set X[C_i] = i.
• This is fast enough to fully solve the problem!

Click here to go back.