SansPapyrus683/drought_gold.md

## drought_gold.md

      
    Raw
  

              drought_gold.md
            
          
    bro i could passed gold lmao

i actually knew how to solve 2 problems
but anyways, here's the gold p1 editorial on request
(actual problem here,
i won't bother explaining it myself, just read the darn thing)
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 recurion:
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:
#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;
}