Editorial for Stacking Haybales

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Tommoa

Editorialist: Tommoa

At first look, this looks like an 0-1 knapsack problem, which is actually 100% correct. An 0-1 knapsack typically has the time complexity of \(O({n}\times{W})\), where \(W\) is the target weight. With our target height \({H}\leq{10^{10}}\), and \({N}\leq{25}\), a typical 0-1 knapsack will (given an assumption of roughly \(10^8\) operations per second) run in roughly 2500 seconds in the worst case! So clearly, this is not the correct way to go about solving this problem.

If you scroll down on the wikipedia page linked just a little more, you'll find our answer, the meet-in-the-middle algorithm! This algorithm works by splitting the search space in half (so one side has \(\dfrac{N}{2}\) haybales and the other has \(N-\dfrac{N}{2}\) haybales), generating all of the heights you can make with the subsets of each side, and then combining them together using a binary search. This has a total complexity of \(O(n\times{2^{\dfrac{n}{2}}})\), and again using our assumption of being able to do roughly \(10^8\) operations per second, this will take us roughly \(0.2\) seconds for each test case, given that it has 100 sub-test cases.

#include <bits/stdc++.h>

using namespace std;

long long T, N, H, X[9000], Y[9000], lo, hi, mid;

// Generates the height of each subset and puts it in out
void gen_subsets(long long *out, vector<long long> &in, const long long len, const long long offset) {
    long long n_subsets = 1<<len;
    for (long long i = 0; i < n_subsets; ++i) {
        long long sum = 0;
        for (long long j = 0; j < len; ++j) {
            if (i&(1<<j)){
                sum += in[j + offset];
            }
        }
        out[i] = sum;
    }
}

void solve() {
    cin >> N >> H;

    vector<long long> arr = vector<long long>(N);
    for (auto &a: arr)
        cin >> a;

    long long n = N/2;
    long long n2 = N - (N/2);

    gen_subsets(X, arr, n, 0);
    gen_subsets(Y, arr, n2, n);

    n = 1<<n;
    n2 = 1<<n2;

    sort(Y, Y+n2); // Sort our subsets so we can binary search them

    for (long long i = 0; i < n; ++i) {
        long long diff = H - X[i];
        if (diff < 0)
            continue;
        if (binary_search(Y, Y+n2, diff)) {
            cout << "YAY\n";
            return;
        }
    }
    cout << "NAY\n";
}

int main() {
    cin >> T;

    while (T--)
        solve();
}

Comments

There are no comments at the moment.