USACO 2022 January Contest, Gold Problem 1. Drought

Category: 國(guó)際競(jìng)賽, 計(jì)算機(jī)國(guó)際競(jìng)賽 Date: 2022年7月5日下午3:11

USACO 2022 January Contest, Gold Problem 1. Drought

The grass has dried up in Farmer John's pasture due to a drought. After hours of despair and contemplation, FJ comes up with the brilliant idea of purchasing corn to feed his precious cows.

FJ’s? $N$ ?( $1 \leq N \leq 100$ ) cows are arranged in a line such that the? $i$ th cow in line has a non-negative integer hunger level of? $h_{i}$ . As FJ’s cows are social animals and insist on eating together, the only way FJ can decrease the hunger levels of his cows is to select two adjacent cows? $i$ ?and? $i + 1$ ?and feed each of them a bag of corn, causing each of their hunger levels to decrease by one.

FJ wants to feed his cows until all of them have the same non-negative hunger level. Although he doesn't know his cows' exact hunger levels, he does know an upper bound on the hunger level of each cow; specifically, the hunger level? $h_{i}$ ?of the? $i$ -th cow is at most? $H_{i}$ ?( $0 \leq H_{i} \leq 1000$ ).

Your job is to count the number of? $N$ -tuples of hunger levels? $[h_{1}, h_{2}, \dots, h_{N}]$ ?that are consistent with these upper bounds such that it is possible for FJ to achieve his goal, modulo? $10^{9} + 7$ .

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains? $N$ .The second line contains? $H_{1}, H_{2}, \dots, H_{N}$ .

OUTPUT FORMAT (print output to the terminal / stdout):

The number of? $N$ -tuples of hunger levels modulo? $10^{9} + 7$ .

SAMPLE INPUT:

3
9 11 7

SAMPLE OUTPUT:

There are? $(9 + 1) \cdot (11 + 1) \cdot (7 + 1)$ ? $3$ -tuples? $h$ ?that are consistent with? $H$ .

One of these tuples is? $h = [8, 10, 5]$ . In this case, it is possible to make all cows have equal hunger values: give two bags of corn to both cows? $2$ ?and? $3$ , then give five bags of corn to both cows? $1$ ?and? $2$ , resulting in each cow having a hunger level of? $3$ .

Another one of these tuples is? $h = [0, 1, 0]$ . In this case, it is impossible to make the hunger levels of the cows equal.

SAMPLE INPUT:

4
6 8 5 9

SAMPLE OUTPUT:

SCORING:

$N$ ?is even in even-numbered tests and odd in odd-numbered tests.

Tests 3 and 4 satisfy? $N \leq 6$ ?and? $H_{i} \leq 10$ .
Tests 5 through 10 satisfy? $N \leq 50$ ?and? $H_{i} \leq 100$ .
Tests 11 through 20 satisfy no further constraints.

Problem credits: Arpan Banerjee and Benjamin Qi

USACO 2022 January Contest, Gold Problem 1. Drought 題解(翰林國(guó)際教育提供，僅供參考)

題解請(qǐng)注冊(cè)或登錄查看

[/hide]

(Analysis by Andi Qu, Arpan Banerjee, Benjamin Qi)

Case 1:? $N$ ?is even

Note that if some starting? $N$ -tuple can make all cows end up with hunger level? $x$ , then it can also make all cows end up with hunger level? $0$ ?(by feeding each consecutive pair of cows? $x$ ?bags of corn). So it suffices to find the number of? $N$ -tuples that can be converted to all? $0$ 's.

If we want to check whether a specific? $N$ -tuple can be converted to all? $0$ 's, then the following pseudocode suffices:

for (i in 2..N) {
  h[i] -= h[i-1]
  assert(h[i] >= 0)
}
assert(h[N] == 0)

The reasoning behind this is that if? $h_{1}, \dots, h_{i - 2}$ ?are all equal to zero already, then the only way to make? $h_{i - 1} = 0$ ?is by feeding? $h_{i - 1}$ ?bags of corn to each of cows? $i - 1$ ?and? $i$ .

Motivated by this, we can define a DP array where? $dp [i] [j]$ ?is the number of ways to choose? $h_{1} \dots h_{i}$ ?satisfying? $h_{k} \leq H_{k}$ ?for all? $1 \leq k \leq i$ ?such that after the? $i$ -th iteration of the loop in the pseudocode above,? $h_{i} = j$ . Then

dp [i] [j] = \sum x = 0 H i ? j dp [i ? 1] [x] .

That is, if? $h_{i - 1} = x$ ?and? $h_{i} = j + x \leq H_{i}$ ?before the? $i$ -th iteration of the loop, then? $h_{i - 1} = 0$ ?and? $h_{i} = j$ ?after the? $i$ -th iteration of the loop. The final answer will be? $dp [N] [0]$ .

A straightforward implementation of this algorithm runs in? $O (N (max H)^{2})$ ?time, which is already fast enough. However, we can speed this up by using prefix sums for the transition since we are summing over a contiguous range. Specifically, define? $pref [i] [j] = \sum_{x = 0}^{j} dp [i] [x]$ ; then? $dp [i] [j] = pref [i - 1] [H_{i} - j]$ . This results in a runtime of? $O (N (max H))$ .

Andi's code:

#include <iostream>
#include <algorithm>
#include <cstring>
typedef long long ll;
using namespace std;
 
const ll MOD = 1e9 + 7;
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, h[101];
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    ll dp[1001], pref[1001];
    for (int i = 0; i <= h[1]; i++) pref[i] = i + 1;
    for (int i = h[1] + 1; i <= 1000; i++) pref[i] = h[1] + 1;
    for (int i = 2; i <= n; i++) {
        memset(dp, 0, sizeof dp);
        for (int j = 0; j <= h[i]; j++) {
            dp[j] = pref[h[i] - j];
            if (dp[j] >= MOD) dp[j] -= MOD;
        }
        for (int j = 0; j <= 1000; j++) {
            pref[j] = dp[j];
            if (j) pref[j] += pref[j - 1];
            if (pref[j] >= MOD) pref[j] -= MOD;
        }
    }
    cout << pref[0];
    return 0;
}

Case 2:? $N$ ?is odd

In this case, it is?not?true that if a starting? $N$ -tuple can make all cows end up with hunger level? $x$ , then it can also make all cows end up with hunger level? $0$ . In fact, if a starting? $N$ -tuple can make all cows end up with hunger level? $x$ , then? $x$ ?must be unique (as mentioned in the Bronze analysis). So it suffices to sum the number of starting? $N$ -tuples over all final hunger levels? $x$ ?satisfying? $0 \leq x \leq min H$ .

To count this quantity for a fixed? $x$ , consider subtracting? $x$ ?from all? $h_{i}$ ?and? $H_{i}$ . Then the problem reduces to converting tuples to all? $0$ 's, which was described above.

The final time complexity for this case is? $max H$ ?times that of the complexity for the previous case, or? $O (N (max H)^{2})$ .

Andi's code:

#include <iostream>
#include <algorithm>
#include <cstring>
typedef long long ll;
using namespace std;
 
const ll MOD = 1e9 + 7;
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, h[101];
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    int mn = *min_element(h + 1, h + n + 1);
    ll dp[1001], pref[1001], ans = 0;
    do { 
        // on x-th iteration of loop, count number of tuples
        // that can make all heights equal to x-1
        for (int i = 0; i <= h[1]; i++) pref[i] = i + 1;
        for (int i = h[1] + 1; i <= 1000; i++) pref[i] = h[1] + 1;
        for (int i = 2; i <= n; i++) {
            memset(dp, 0, sizeof dp);
            for (int j = 0; j <= h[i]; j++) {
                dp[j] = pref[h[i] - j];
                if (dp[j] >= MOD) dp[j] -= MOD;
            }
            for (int j = 0; j <= 1000; j++) {
                pref[j] = dp[j];
                if (j) pref[j] += pref[j - 1];
                if (pref[j] >= MOD) pref[j] -= MOD;
            }
        }
        ans += pref[0]; 
        if (ans >= MOD) ans -= MOD;
        for (int i = 1; i <= n; i++) h[i]--;
    } while (n % 2 && mn--);
    cout << ans;
    return 0;
}

Interestingly, each DP transition is equivalent to reversing a subarray of the previous prefix sum array, so we can code a very short (and fast) solution using functions from C++'s standard library.

#include <algorithm>
#include <cstdio>
#include <numeric>
using namespace std;
 
int mod_add(int x, int y) {
    int res = x + y;
    if (res >= 1000000007) res -= 1000000007;
    return res;
}
 
int main() {
    int n, h[101], mn, mx, dp[1001], ans = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", h + i);
    mn = *min_element(h, h + n), mx = *max_element(h, h + n);
    do {
        fill(dp, dp + mx + 1, 1);
        for (int i = 0; i < n; i++) {
            reverse(dp, dp + h[i] + 1);
            fill(dp + h[i] + 1, dp + mx + 1, 0);
            partial_sum(dp, dp + mx + 1, dp, mod_add);
        }
        ans = mod_add(ans, dp[0]);
        for (int i = 0; i < n; i++) h[i]--;
    } while (n % 2 && mn-- && mx--);
    printf("%d\n", ans);
    return 0;
}

[/hide]