Consider two sequences of non-negative integers \(p_1 \ge p_2 \ge \dots \ge p_n\) and \(q_1 \ge q_2 \ge \dots \ge q_m\) satisfying \(\sum_{i=1}^n p_i = \sum_{i=1}^m q_i\). The Gale-Ryser theorem states that a simple bipartite graph exists with left vertices having degrees \(p_1, p_2, \dots, p_n\) and right vertices having degrees \(q_1, q_2, \dots, q_m\) if and only if for all \(k \in [1, n]\):

[\sum_{i=1}^k p_i \le \sum_{i=1}^m \min{q_i, k}] ### Proof of Necessity

Label the left vertices as \(u_1, u_2, \dots, u_n\) and right vertices as \(v_1, v_2, \dots, v_m\), where \(\deg(u_i) = p_i\) for all \(i \in [1, n]\) and \(\deg(v_i) = q_i\) for all \(i \in [1, m]\).

For any selection of \(k\) vertices from the left partition, examine the sum of they degrees. Each right vertex \(v_i\) can contribute at most \(\min\{q_i, k\}\) edges to these \(k\) left vertices, as it has degree \(q_i\) and can connect to at most \(k\) distinct vertices. Therefore, the degree sum of any \(k\) left vertices is bounded above by \(\sum_{i=1}^m \min\{q_i, k\}\).

Since the top \(k\) degrees \(p_1, p_2, \dots, p_k\) represent the maximum possible degree sum for any \(k\) vertices, we have \(\sum_{i=1}^k p_i \le \sum_{i=1}^m \min\{q_i, k\}\).

Proof of Sufficiency

We employ an inductive construction to build the bipartite graph.

Assume we have constructed a graph satisfying: \(\deg(u_k) < p_k\), \(\deg(u_i) = p_i\) for \(i < k\), \(\deg(u_i) = 0\) for \(i > k\), and \(\deg(v_i) \le q_i\) for all right vertices. We seek to increase \(\deg(u_k)\) by one while maintaining all constraints.

There must exist a vertex \(v_a\) with \(\deg(v_a) < \min\{q_a, k\}\), otherwise we would have \(\sum_{i=1}^k p_i > \deg(u_k) + \sum_{i=1}^{k-1} p_i = \sum_{i=1}^m \deg(v_i) = \sum_{i=1}^m \min\{q_i, k\}\), contradicting the theorem condition.

If edge \((u_k, v_a)\) doesn't exist, simply add it.

Otherwise, by the pigeonhole principle, some vertex \(u_b\) with \(b < k\) lacks an edge to \(v_a\). Since \(\deg(u_b) = p_b \ge p_k > \deg(u_k)\), there exists \(v_c\) with edge \((u_b, v_c)\) but no edge \((u_k, v_c)\). Remove edge \((u_b, v_c)\) and add edges \((u_b, v_a)\) and \((u_k, v_c)\).

This operation increases \(\deg(u_k)\) by one while preserving all constraints. Starting from \(k = 1\) with no edges, we repeatedly apply this construction until all degree requirements are satisfied.

Applications

Problem: Conditional Mix (Codeforces 1740F)

Analysis reveals that each set in the partition must contain distinct values, and every valid partition corresponds to a valid configuration.

Let \(b_x\) denote the frequency of value \(x\) in the input array. By Gale-Ryser, configuration \(M\) is achievable iff a bipartite graph exists with left degrees \(\{b_i\}\) and right degrees from \(M\). This translates to checking prefix sum constraints against upper bounds.

Define \(f[i][j][k]\) as the number of ways to write \(i\) numbers (sorted descending) with sum \(j\) and last element \(k\). Since \(i \times k \le n\), there are \(O(n^2 \log n)\) states. Transition by enumerating the previous element with suffix sum optimization achieves \(O(n^2 \log n)\) complexity.

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int MAXN = 2010;

int freq[MAXN], bound[MAXN], ways[MAXN][MAXN], suffix[MAXN][MAXN];

void addMod(int &x, int y) { x = (x + y >= MOD) ? x + y - MOD : x + y; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n; cin >> n;
    for (int i = 0, val; i < n; ++i) {
        cin >> val;
        freq[val]++;
    }
    
    for (int k = 1; k <= n; ++k)
        for (int j = 1; j <= n; ++j)
            bound[k] += min(freq[j], k);
    
    for (int sum = 1; sum <= bound[1]; ++sum)
        ways[sum][sum] = 1;
    
    int result = (bound[1] == n) ? 1 : 0;
    
    for (int cnt = 2; cnt <= n; ++cnt) {
        for (int sum = cnt - 1; sum <= bound[cnt - 1]; ++sum) {
            int maxVal = sum / (cnt - 1);
            suffix[sum][maxVal] = ways[sum][maxVal];
            for (int val = maxVal - 1; val >= 1; --val)
                suffix[sum][val] = (suffix[sum][val + 1] + ways[sum][val]) % MOD;
        }
        
        for (int sum = cnt; sum <= bound[cnt]; ++sum) {
            for (int val = 1; val * cnt <= sum; ++val) {
                int prevSum = sum - val;
                ways[sum][val] = (prevSum <= bound[cnt - 1]) ? suffix[prevSum][val] : 0;
            }
        }
        
        if (bound[cnt] == n)
            for (int val = 1; val * cnt <= n; ++val)
                addMod(result, ways[n][val]);
    }
    
    cout << result << "\n";
    return 0;
}

Problem: Cookies (JOISC 2023 Day3)

Apply Gale-Ryser to verify box validity: sort boxes by capacity descending, check each prefix sum against its upper bound.

Define state \((i, j, k)\): processed first \(i\) largest boxes, current capacity \(j\), sum is \(k\). With \(i \times j \le \sum a_l\), we have \(O(n^2 \log n)\) states. Use bitset optimization for \(O(n^2 \log n / w)\) complexity.

To reconstruct: greedi assign each cookie type to largest available boxes. An exchange argument proves validity of this greedy apporach.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15010;

int n, totalSum, cookieCount[MAXN], upperBound[MAXN];
bool isValidSize[MAXN];
vector<bitset<MAXN>> state[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> cookieCount[i];
        totalSum += cookieCount[i];
        upperBound[1]++;
        upperBound[cookieCount[i] + 1]--;
    }
    
    for (int i = 1; i <= totalSum; ++i) {
        upperBound[i] += upperBound[i - 1];
        if (i > 1) upperBound[i] += upperBound[i - 1];
    }
    
    int m; cin >> m;
    for (int i = 0, size; i < m; ++i) {
        cin >> size;
        isValidSize[size] = true;
    }
    
    bitset<MAXN> reachable;
    for (int i = 1; i <= upperBound[1]; ++i) reachable[i] = true;
    
    state[1].resize(upperBound[1] + 1);
    for (int sz = 1; sz <= upperBound[1]; ++sz)
        if (isValidSize[sz]) state[1][sz][sz] = 1;
    
    if (upperBound[1] == totalSum && isValidSize[totalSum]) {
        cout << "1\n" << n << " ";
        for (int i = 1; i <= n; ++i) cout << i << " \n"[i == n];
        return 0;
    }
    
    for (int cnt = 2; cnt <= totalSum; ++cnt) {
        for (int j = upperBound[cnt - 1] + 1; j <= upperBound[cnt]; ++j)
            reachable[j] = 1;
        
        bitset<MAXN> accumulated;
        state[cnt].resize(upperBound[cnt] / cnt + 1);
        
        for (int sz = upperBound[cnt] / cnt, prevSz = upperBound[cnt - 1] / (cnt - 1); 
             sz >= 1; --sz) {
            if (!isValidSize[sz]) continue;
            while (prevSz >= sz) accumulated |= state[cnt - 1][prevSz--];
            state[cnt][sz] = (accumulated << sz) & reachable;
            
            if (state[cnt][sz][totalSum]) {
                cout << cnt << "\n";
                vector<int> boxSizes;
                int currSz = sz, remaining = totalSum, curr = cnt;
                
                while (curr) {
                    while (!state[curr][currSz][remaining]) ++currSz;
                    boxSizes.push_back(currSz);
                    remaining -= currSz;
                    --curr;
                }
                
                vector<vector<int>> assignments(boxSizes.size());
                priority_queue<pair<int,int>> pq;
                for (size_t idx = 0; idx < boxSizes.size(); ++idx)
                    pq.emplace(boxSizes[idx], idx);
                
                for (int type = 1; type <= n; ++type) {
                    vector<pair<int,int>> temp;
                    while (cookieCount[type]--) {
                        auto [cap, idx] = pq.top(); pq.pop();
                        temp.emplace_back(cap - 1, idx);
                        assignments[idx].push_back(type);
                    }
                    for (auto &p : temp) pq.push(p);
                }
                
                for (auto &box : assignments) {
                    cout << box.size();
                    for (int t : box) cout << " " << t;
                    cout << "\n";
                }
                return 0;
            }
        }
    }
    
    cout << "-1\n";
    return 0;
}