We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Lego Blocks
  5. Discussions

Lego Blocks

  • dehaka
     + 1 comment

    O(n * m^2), strange this passed, since it requires at least 1 billion operations. can be modified to O(t*n*m) by calculating each height individually in response to the query, instead of calculating all 1 <= n <= 1000

    there's probably a O(n* m) algo by finding a constant time method to calculate the number of bad layouts of length m+1 from smaller length bad layouts, but this O(n* m^2) algo already pass all tests so i cant be bothered

    void legoBlocks(vector<vector<long>>& total, vector<vector<long>>& bad) {
    vector<long> oneRow = { 0, 1, 2, 4, 8 };
    for (int i = 5; i <= 1000; i++) oneRow.push_back((oneRow[i-1] + oneRow[i-2] + oneRow[i-3] + oneRow[i-4]) % 1000000007);
    total.push_back(oneRow);
    for (int i = 2; i <= 1000; i++) {
        total.emplace_back();
        for (int j = 0; j <= 1000; j++) total.back().push_back((oneRow[j] * total[i-1][j]) % 1000000007);
    }
    for (int n=1; n <= 1000; n++) {
        bad.emplace_back(vector<long>{0, 0});
        for (int m=2; m <= 1000; m++) {
            long temp = 0;
            for (int i=1; i < m; i++) temp = (temp + total[n][i] * (total[n][m-i] - bad[n][m-i])) % 1000000007;
            bad[n].push_back(temp);
        }
    }
}

int main()
{
    int t, n, m;
    vector<vector<long>> total = {vector<long>(1001)}, bad = {vector<long>(1001)};
    legoBlocks(total, bad);
    cin >> t;
    for (int i=1; i <= t; i++) {
        cin >> n >> m;
        cout << (total[n][m] - bad[n][m] + 1000000007) % 1000000007 << '\n';
    }
}