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

Sort by

recency

|

73 Discussions

|

  • mouadaitougrram
     + 0 comments

    Damn this is so hard , I was able to solve this problem for any n>1 but as long as m<= 4 , in this cas the solution is one line (2**n -1)**(m-1) .

    I know this because I wasn't respecting the limiting condition on width <=4 , but I don't know how I can extend it for this condition + also idk how to remove the invalid cases from that

  • samfigueroapico
     + 1 comment

    Hi i share the code in C++ i could solve this like this:

    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;

    }

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

  • dehaka
     + 2 comments

    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';
    }
}

    • giankenbellfore
       + 0 comments

      Lego blocks are more than just colorful plastic pieces; they are a cornerstone of creative play and imaginative building. These versatile bricks allow users to construct everything from simple structures to intricate designs, making them a favorite among children and adults alike. The interlocking mechanism of Lego blocks sportzfy.apk ensures that creations stay together, fostering a sense of accomplishment as builders see their ideas come to life.

    • lengistonjorry
       + 0 comments

      Lego blocks are more than just colorful pieces of plastic; they are a gateway to creativity, problem-solving, and endless possibilities. These interlocking bricks have inspired generations to build everything from simple houses to intricate models of real-world landmarks. Beyond their role as a beloved toy, Lego blocks have educational value, fostering skills like spatial reasoning, fine motor coordination sharp copier repair near me, and teamwork. They appeal to all age groups, offering themed sets that spark imagination or blank canvases for open-ended play. With sustainability in focus, Lego continues to innovate, creating eco-friendly bricks and encouraging a culture of constructive play worldwide.

  • nam_vuhoang
     + 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));
      }
    }
  }
}

    • lengistonjorry
       + 0 comments

      Lego blocks, the timeless and versatile construction toys, have captivated the imaginations of children and adults alike for decades. These colorful interlocking bricks are more than just playthings; they are tools for creativity, problem-solving, and learning. With Lego blocks for Snake Aim tool app, one can build anything from simple structures to intricate models, limited only by imagination.

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in