include

using namespace std;

const long long mod = 1000000007; vector f(1111), g(1111), h(1111);

long long pow(long long a, int p) { long long ans = 1; while (p) { if (p % 2) ans = ans * a % mod; a = a * a % mod; p /= 2; } return ans; }

int legoBlocks(int n, int m) { // Initialize f with the number of ways to fill each width f[0] = 1; for (int i = 1; i <= 1000; i++) { f[i] = 0; for (int j = 1; j <= 4; j++) { if (i - j >= 0) f[i] = (f[i] + f[i - j]) % mod; } }

// Compute the number of ways to fill each row with width m
for (int i = 1; i <= m; i++) {
    g[i] = pow(f[i], n);
}

// Compute the number of valid walls
memset(h.data(), 0, h.size() * sizeof(h[0]));
h[0] = 1; // Base case for height 0
for (int i = 1; i <= m; i++) {
    h[i] = g[i];
    long long tmp = 0;
    for (int j = 1; j < i; j++) {
        tmp = (tmp + h[j] * g[i - j] % mod) % mod;
    }
    h[i] = (g[i] - tmp + mod) % mod;
}

return h[m];

}

string ltrim(const string &str) { string s(str); s.erase( s.begin(), find_if(s.begin(), s.end(), not1(ptr_fun(isspace))) ); return s; }

string rtrim(const string &str) { string s(str); s.erase( find_if(s.rbegin(), s.rend(), not1(ptr_fun(isspace))).base(), s.end() ); return s; }

vector split(const string &str) { vector tokens; string::size_type start = 0; string::size_type end = 0; while ((end = str.find(" ", start)) != string::npos) { tokens.push_back(str.substr(start, end - start)); start = end + 1; } tokens.push_back(str.substr(start)); return tokens; }

int main() { ofstream fout(getenv("OUTPUT_PATH"));

string t_temp;
getline(cin, t_temp);
int t = stoi(ltrim(rtrim(t_temp)));

for (int t_itr = 0; t_itr < t; t_itr++) {
    string first_multiple_input_temp;
    getline(cin, first_multiple_input_temp);
    vector<string> first_multiple_input = split(rtrim(first_multiple_input_temp));
    int n = stoi(first_multiple_input[0]);
    int m = stoi(first_multiple_input[1]);
    int result = legoBlocks(n, m);
    fout << result << "\n";
}

fout.close();
return 0;

}

3 months ago+ 0 comments

O(m^2) solution. If you're working in Java, the BigInteger class is very useful for efficient modular power operations. Basically, find all the possible permutations of a single row, then, for each wall width, find all the invalid walls and subtract from all possible walls using DP.

public static long legoBlocks(int n, int m) {
        int mod = 1000000007;
        
        // trivial cases
        if (m == 1) {
            return 1;
        }
        if (n == 1 && m <= 4) {
            return 1;
        }
        if (n == 1) {
            return 0;
        }
        if (m == 2) {
                BigInteger exp = new BigInteger(Integer.toString(n));
                BigInteger newMod = new BigInteger(Integer.toString(mod));
                BigInteger base = new BigInteger("2");
                long result = (long) base.modPow(exp, newMod).longValue() - 1;
                return result;
        }
        // Total Permutations of a single row
        long[] totalWays = new long[m+1];
        for (int i = 0; i <= m; i++) {
            if (i <= 1) {
                totalWays[i] = 1;
                continue;
            }
            if (i == 2) {
                totalWays[i] = 2;
                continue;
            }
            if (i == 3) {
                totalWays[i] = 4;
                continue;
            }
            long newWays = ((totalWays[i-1] + totalWays[i-2] + totalWays[i-3] + totalWays[i - 4]) % mod) % mod;
            totalWays[i] = newWays;
        }
        
        // DP cases
        BigInteger newMod = new BigInteger(Integer.toString(mod));
        BigInteger exp = new BigInteger(Integer.toString(n));
        BigInteger base2 = new BigInteger("2");
        long[] validWalls = new long[m+1];
        long[] invalidWalls = new long[m+1];
        validWalls[1] = 1;
        validWalls[2] = base2.modPow(exp, newMod).longValue() - 1;
        invalidWalls[1] = 0;
        invalidWalls[2] = 1;
        for (int i = 3; i <= m; i++) {
            BigInteger base = new BigInteger(Long.toString(totalWays[i]));
            long totalWalls = base.modPow(exp,newMod).longValue();
            totalDP[i] = totalWalls;
            long currInvalid = 0;
            for (int j = 1; j <= i - 1; j++) {
                long invalidUnseen = (validWalls[j] * validWalls[i - j]) % mod;
                long invalidSeen = (validWalls[j] * invalidWalls[i - j]) % mod;
                long totalInvalid = (invalidUnseen + invalidSeen) % mod;
                currInvalid = (currInvalid + totalInvalid) % mod;
            }
            invalidWalls[i] = currInvalid;
            validWalls[i] = (totalWalls - invalidWalls[i] + mod) % mod;
        }
        // Last row
        return validWalls[m];
    }

4 months ago+ 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';
    }
}

1 year ago+ 2 comments

I've found a good solution here. There are solutions written in Python, Java, C++, and C.

I reformatted the Java code to make easier to understand:

package com.hackerrank.test.prepare.algorights.lego_blocks;

import java.util.*;

public class Solution {
  private static final int MOD = 1000000007; // 10^9+7
  private static final int MAX_SIZE = 1000 + 1; // 1 <= n, m <= 1000
  private static final int UNKNOWN = -1;

  static int[][] allSolutions = new int[MAX_SIZE][MAX_SIZE];
  static int[][] solidSolutions = new int[MAX_SIZE][MAX_SIZE];

  static {
    for (int i = 1; i < MAX_SIZE; i++) {
      Arrays.fill(allSolutions[i], UNKNOWN);
      Arrays.fill(solidSolutions[i], UNKNOWN);
    }
  }

  static int getAllSolutions(final int height, final int width) {
    if (allSolutions[height][width] != UNKNOWN) {
      return allSolutions[height][width];
    }

    long count;
    if (width == 1) {
      count = 1;
    } else if (height == 1) {
      if (width <= 4) {
        count = 2 * getAllSolutions(1, width - 1);
      } else { // width > 4
        count = 0;
        for (int i = 1; i <= 4; i++) {
          count += getAllSolutions(1, width - i);
          count %= MOD;
        }
      }
    } else { // width > 1 && height > 1
      int oneRowSolutions = getAllSolutions(1, width);

      count = 1;
      for (int h = 0; h < height; h++) {
        count *= oneRowSolutions;
        count %= MOD;
      }
    }

    allSolutions[height][width] = (int) count;
    return allSolutions[height][width];
  }

  static int getSolidSolutions(final int height, final int width) {
    if (solidSolutions[height][width] != UNKNOWN) {
      return solidSolutions[height][width];
    }

    long count;
    if (width == 1) {
      count = 1;
    } else {
      count = getAllSolutions(height, width);
      for (int i = 1; i < width; i++) {
        long a = getAllSolutions(height, i);
        long b = getSolidSolutions(height, width - i);
        count -= (a * b) % MOD;
        if (count < 0) {
          count += MOD;
        }
      }
    }
    solidSolutions[height][width] = (int) count;
    return solidSolutions[height][width];
  }

  public static void main(String[] args) {
    try (final Scanner scanner = new Scanner(System.in)) {
      int testCases = scanner.nextInt();
      while (testCases-- > 0) {
        final int height = scanner.nextInt();
        final int width = scanner.nextInt();
        System.out.println(getSolidSolutions(height, width));
      }
    }
  }
}

View more Comments..

1 year ago+ 1 comment

Here is my solution in java, javascript, python, C ,C++, Csharp HackerRank Lego Blocks Problem Solution

Sort by

|

72 Discussions

|

include

Cookie support is required to access HackerRank