USACO 2019 US Open Contest, Gold Problem 1- Snakes

 Problem Link
Algorithm Used: Dynamic Programming
Time Complexity: O(N³)

There are N groups of snakes given, of varying sizes. Nets are used to catch the snakes. Each net must be at least the size of the group of snakes being caught. Every time a group of snakes is caught, the space wasted is the difference in the size of the net and the size of the current group of snakes. To minimize the total amount of wasted space, the net size may be changed up to K times. Find the minimum total space that must be wasted in order to catch all the snakes.

At first glance, the way the nets are changed doesn't seem to follow any specific pattern that leads to a greedy/binary search/sorting solution, so the only other option is brute force. There are N groups of snakes and nets may be changed N times so there are N² possible states. For each state, the net size must be calculated by scanning the groups of snakes, so that a net that is smaller than the current group of snakes is not chosen. Then, computing the wasted space for each state takes O(N) time. The resulting time complexity of this approach is O(N⁴), which is too slow. Dynamic Programming can be used to speed up the brute force approach.

Instead of calculating wasted space to catch the ith group of snakes, we calculate the sum of net sizes used to catch the ith group of snakes, and then subtract the sum of snake group sizes from the sum of net sizes to find out the wasted space.

Compute the sum of net sizes used till the ith group of snakes, using j net size changes. This value will be stored in dp[i][j]. If the net is changed, then it may be changed at the ith group of snakes, or at any group before i, wherever the sum of net sizes gets reduced the most. 

As shown in this picture, the red range shows the snake groups that new net would catch, while the blue range shows the snake groups that the old nets catch. The sum of net sizes in the blue range would be dp[m][j-1], where m is the mth group of snakes. The sum of net sizes in the red range would be size of maximum group of snakes in red range * size of red range, since only one net is used to catch all snakes in the red range.

Size of red range would be i - m (all arrays are 1-indexed). Maximum group of snakes in red range can be calculated by keeping a running maximum. dp[i][j] is the minimum of the sum of the blue range and the red range. In my code, I increase the size of the red range, so there is a loop from i to 1 instead of 1 to i. I also store the running maximum is stored in a variable called reverse_highest.

Code

#include <bits/stdc++.h>

using namespace std;

const int INF = 1000000000;

int main() {

    freopen("snakes.in", "r", stdin);

    freopen("snakes.out", "w", stdout);

    int n, k;

    cin >> n >> k;

    vector<vector<int>> dp(n+1, vector<int>(k+1));

    vector<int> snakes(n+1);

   

    for (int i = 1; i <= n; i++)

        cin >> snakes[i];

    int highest = 0, total = 0;

   

    for (int i = 1; i <= n; i++) {

        highest = max(highest, snakes[i]);

        dp[i][0] = highest * i;

        for (int j = 1; j <= k; j++) {

            dp[i][j] = INF;

       

            int reverse_highest = snakes[i];

            for (int m = i-1; m >= 0; m--) {

                dp[i][j] = min(dp[i][j], dp[m][j-1] + reverse_highest * (i - m));

                reverse_highest = max(reverse_highest, snakes[m]);

            }

        }

        total += snakes[i];

    }

    cout << dp[n][k] - total << '\n';

}