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 pretendc
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
- to get the last cow to the level
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;
}
This was the most helpful solution of all. Thanks a lot!!
btw, I like your Eminem-based bio ;)