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

  • shanefostersmith
     + 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];
    }