drought (gold)

uh just read the problem yourself, explaining it here would take way too long

so it would be absolute cancer to try and actually calculate if each tuple can get to a level where all cows have the same hunger level
not only that, calculating all the possible tuples themselves...

hm
what if we thought of the problem in reverse?
so like we started at a level where all the cows were equal, and then we added pairs of 1's to cows until we got a random n-tuple that also satisfied the input's upper bounds?
actually that might work!

but here's the thing: we have to handle cases where the number of cows is even differently from the cases where the number of cows is odd
why?
because if the # of cows is even, all levels can be gotten from if all the hunger levels were 0
however, if the # of cows is odd, no level can be achieved from each other

actually yk what just have an example if there we 3 cows, we couldn't get, say, `2 2 2` from `0 0 0` or `1 1 1`
however, if there were 4 cows, we could get `2 2 2 2` from `0 0 0 0`

so if the # of cows is even, we only have to calculate for if we start from 0, but if it's odd, we have to calculate from 0 all the way to the min upper bound

now to get to actually solving it for a random level & upper bound
first let's just subtract the level from all upper bounds so we can just treat it as if we're starting from 0
next, let's define `num_ways[c][l]` as the number of ways to bring crap up from 0 given that:

we only consider the first `c` cows
the last cow's level is `l` (so the dp array is going to be ragged)

after some pain with the first couple values of `c` because of edge cases, we can get this recursion:

``` num_ways[c][0] = sum of all of num_ways[c - 1] num_ways[c][l] = sum of everything EXCEPT THE LAST l ELEMENTS of num_ways[c - 1] ```

the `0` case is just bc we could just pretend `c` didn't exist and sum up all the previous ones for obvious reasons
for the other ones, it works like this:
- to get the last cow to the level `l`, we need to add crap to the prev cow as well
- but the thing is, we can't add too much, or the prev cow's upper bound will be violated and we can't have that
- so we just sum up all the previous levels except where it'll have the prev cow exceed it's upper bound

but constantly calculating the sum of the previous things would take too long, so let's just use a prefix sum as well to make things faster

and yeah, we basically solved the thing!

code here:

```cpp #include <iostream> #include <vector> #include <algorithm> using std::cout; using std::endl; using std::vector; using std::pair; constexpr int MOD = 1e9 + 7; // given the upper bounds, how many ways can we start from all 0's? int num_ways(const vector<int>& levels) { // just handle the first two pesky cases vector<vector<int>> num_ways{vector<int>(levels[0] + 1, 1)}; if (levels.size() >= 2) { int min = std::min(levels[0], levels[1]); num_ways.push_back({1}); for (int i = 1; i <= levels[1]; i++) { num_ways[1].push_back(i <= min); } } vector<int> prefs{0}; for (int i : num_ways.back()) { prefs.push_back(prefs.back() + i); // no need for modding here } for (int c = 2; c < levels.size(); c++) { num_ways.push_back(vector<int>(levels[c] + 1)); for (int l = 0; l <= levels[c - 1]; l++) { num_ways[c][0] = (num_ways[c][0] + num_ways[c - 1][l]) % MOD; } for (int l = 1; l <= levels[c]; l++) { if (l <= levels[c - 1]) { num_ways[c][l] = prefs[levels[c - 1] - l + 1]; } } prefs = {0}; // calculate prefix sums for the next iteration for (int l = 0; l <= levels[c]; l++) { prefs.push_back((prefs.back() + num_ways[c][l]) % MOD); } } // sum everything up @ the end & return it int total = 0; for (int i : num_ways.back()) { total = (total + i) % MOD; } return total; } /** * 2022 jan gold * 3 * 9 11 7 should output 241 * 4 * 6 8 5 9 should output 137 */ int main() { int cow_num; std::cin >> cow_num; vector<int> levels(cow_num); int min_hunger = INT32_MAX; for (int& c : levels) { std::cin >> c; min_hunger = std::min(min_hunger, c); } int total = num_ways(levels); // special odd cases if (cow_num % 2 == 1) { // go through all possible starting levels for (int i = 1; i <= min_hunger; i++) { for (int& c : levels) { c--; } total = (total + num_ways(levels)) % MOD; } } cout << total << endl; } ```

drought (gold) solution