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.
Anyone know how I can improve my score (83.33) to 100.00. I've done all the optimisations I could think of..
class Result {
/*
* Complete the 'legoBlocks' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER n (width)
* 2. INTEGER m (height)
*/
// Cache previous C(n,m) calculations - All Combinations to build a wall with Brick sizes [1,4]
// Cache previous N(n,m) calculations - All Combinations to build a legitimate wall with no breaks
public static Map<String, BigInteger> C_n_m = new HashMap<>();
public static Map<String, BigInteger> N_n_m = new HashMap<>();
public static BigInteger modulo = BigInteger.valueOf(1_000_000_007);
public static BigInteger noBreakWalls(int n, int m) {
String key = n + "," + m;
if (N_n_m.containsKey(key)) return N_n_m.get(key);
BigInteger sum = buildAnyWall(n, m);
for (int i=1; i < n ; i++) {
sum = sum.subtract(buildAnyWall(n-i, m).multiply(noBreakWalls(i, m)));
}
sum = sum.mod(modulo);
N_n_m.put(key, sum);
return sum;
}
public static BigInteger buildAnyWall(int n, int m) {
String key = n + "," + m;
if (C_n_m.containsKey(key)) return C_n_m.get(key);
if (n < 5) {
BigInteger basecase = BigInteger.valueOf(2).modPow(BigInteger.valueOf(m*(n-1)), modulo);
C_n_m.put(key, basecase);
return basecase;
} else {
BigInteger row = buildAnyWall(n-1, 1)
.add(buildAnyWall(n-2, 1))
.add(buildAnyWall(n-3, 1))
.add(buildAnyWall(n-4, 1))
.modPow(BigInteger.valueOf(m), modulo);
C_n_m.put(key, row);
return row;
}
}
public static int legoBlocks(int n, int m) {
return noBreakWalls(n, m).intValue();
}
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Lego Blocks
You are viewing a single comment's thread. Return to all comments →
Anyone know how I can improve my score (83.33) to 100.00. I've done all the optimisations I could think of..
class Result {
}