How would you break this problem into subproblems and use dynamic programming?

Question

I'm working on an old contest problem from 2019 from this page: https://dmoj.ca/problem/ccc19s4

You are planning a trip to visit N tourist attractions. The attractions are numbered from 1 to N and must be visited in this order. You can visit at most K attractions per day, and want to plan the trip to take the fewest number of days as possible.

Under these constraints, you want to find a schedule that has a nice balance between the attractions visited each day. To be precise, we assign a score a_i to attraction i. Given a schedule, each day is given a score equal to the maximum score of all attractions visited that day. Finally, the scores of each day are summed to give the total score of the schedule. What is the maximum possible total score of the schedule, using the fewest days possible?

Apparently it's a dynamic programming type of problem, which I can see how, but I can't seem to figure out how to break it down to subproblems and how each subproblem would relate to each other, especially when there are two variables N and K.

I threw together a recursive brute-force algorithm which works for smaller inputs but fails when the inputs get too large:

int daysNeeded = (int) Math.ceil((double) N / K);

// n - index of current attraction being visited
// d - days used up
public static long solve(int n, int d) {
    if (d == daysNeeded) { // Base case, stop once we reach the min days required
        if (n == N) // If we visited all attractions, count this answer
            return 0;
        else // If we didn't visit all attractions, don't count this answer
            return Integer.MIN_VALUE;
    }
    
    long result = 0;
    
    // Try to visit attractions up to K
    //
    // i + 1 is the number of attractions to visit in this day
    for (int i = 0; i < K; i++) {
        if (n + i >= N)
            break;
        
        long highestScore = attractions[n];

        // Find the attraction from [n + j ... n + i] with the highest score
        for (int j = 1; j <= i; j++) {
            highestScore = Math.max(highestScore, attractions[n + j]);
        }
        
        long next = highestScore + solve(n + i + 1, d + 1);
        
        // Find the attraction with the highest score out of all attractions from 0 to i
        result = Math.max(result, next);
    }
    
    return result;
}

How would you find an optimized algorithm using DP? I can't seem to find any solutions or hints online for this specific problem.

If you cache solve(n, d) you have a dynamic programming solution. — Paul Hankin
I didn't get what's the point of that "daysNeeded" (N divided by K) ? — mangusta
this looks like an optimization problem but it has two objective functions and unclear which one is given a priority - the max score or the min number of days? your solution assumes that the number of days could be at most N/K (similar to knapsack capacity) but I can't see anything about that constraint in the problem statement — mangusta
ah, moreover you assume that the number of days should EXACTLY be N/K but there could be a better score with more number of days. anyway the problem statement is ambiguous and needs to be revised — mangusta
@mangusta if we can have any number of days, the maximum achievable score would be to simply visit one attraction per day. The number of days isn't at most ceil(n/k), it's exactly ceil(n/k). Any fewer days would achieve a lower score. — גלעד ברקן

Hikmat Farhat Hikmat Farhat · Accepted Answer · 2020-07-05T11:30:44

I will try to give the solution as a recurrence relation. Let m be the number of days to visit all attractions and let P[m][N] be the optimal value you obtain by visiting N attractions in m days. We don't know P yet but we will reason about it.

P[m][N]=max_{i up to k} ( P[m-1][N-i]+max_{l=0 to i-1}(a[l]) )

For example if you get the optimal score by visiting only the last two attractions on the last day then the score for that day is max(a[N],a[N-1]) and the total (optimal) score will be

P[m][N]=max(a[N],a[N-1])+optimal score to visit N-2 attractions in m-1 days

which is exactly the same as the above formula

P[m][N]=max(a[N],a[N-1]+ P[m-1][N-2]

Note that there is a constraint on i> N/k(m-1) because if you don't visit enough attractions on the last day the remaining days might not be enough to visit the rest.

How would you break this problem into subproblems and use dynamic programming?

2 Answers