Solution for Gym 102428F - Fabricating Sculptures

Such an elegant and amazing solution.

Solution #

First we can ignore first level of blocks. Let $dp_{s,b}$ be the number of ways to put $b$ blocks on $s$ stacks(some stacks could be empty).

Now let’s consider transition, there are three cases:

The first level is full
The leftmost stack is empty
The rightmost stack is empty

For the first case we can simply ignore the first level and the number of ways is $dp_{s,b-s}$ . For the second and the third case, we can ignore the empty stack and the answer is $2\cdot dp_{s-1,b}$ . However, the two cases overlap, since the scenario where both the leftmost and the rightmost stacks are empty can be reached from both cases. So we need to subtract $dp_{s-2,b}$ . Overall, the formula is:

$dp_{s,b}=dp_{s,b-s}+2\cdot dp_{s-1,b}+dp_{s-2,b}$

This can be calculated recursively with memoization.

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
template<typename... Args>
void write(Args... args) { ((cout << args << " "), ...); cout<<endl;}
 
const int N=5e3+5;
ll dp[N][N];
const int mod=1e9+7;
ll solve(int s,int b){
    if(b==0) return 1;
    if(s<=0) return 0;
    ll& ret=dp[s][b];
    if( ret) return ret;
    ret=0;
    if(s<=b) ret=solve(s,b-s);
    ret=(ret+solve(s-1,b)*2-solve(s-2,b)+mod)%mod;
    return ret;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int s,b;
    cin>>s>>b;
    cout<<solve(s,b-s);
    return 0;
}