Why Only Beat 97% ?


  • 0
    F

    Since the algorithm has a small finite limit of input 15 it is as simple as precompute values for N 1...15 and return them from a constant array. But that should be the fastest solution, but still I get a time execution of beating only 97%.

    What are the optimizations employed by the rest 3 % ?

    #shameless pre-computation
    class Solution2(object):
        pre = [0, 1, 2, 3,  8,  10,  36,  41,  132, 250, 700,  750,  4010,  4237,10680,  24679]
    
        def countArrangement(self, N):
            """
            :type N: int
            :rtype: int
            """
            if (N < len(Solution2.pre)):
                #print ('N' , N)
                return Solution2.pre[N]
    
    # brute force - optimized backtracking
    class Solution(object):
        def __init__(self):
            self.pre = {1: 1, 2: 2, 3: 3, 4: 8, 5: 10, 6: 36, 7: 41, 8: 132, 9: 250, 10: 700, 11: 750, 12: 4010, 13: 4237, 14: 10680, 15: 24679}
    
        
       def countArrangement(self, N):
            """
            :type N: int
            :rtype: int
            """
            if (N <= len(self.pre)):
                #print ('N' , N)
                return self.pre[N]
            m = self.getMap(N)
            used = set()
            printable = []
            result = [0]
            self.generate(0, m, used, result, N, printable)
            return result[0]
    
        def getMap(self, N):
            options = [[0]*(N+1) for i in range(N+1)]
            for i in range(1, N+1):
                r  = i
                while (r <= N) :
                    options[i][r] = 1
                    options[r][i] = 1
                    r+=i
            #print (options)
            result = [[j for j in range(len(i)) if i[j] ] for i in options]
            result = result[1:]
            #print (result)
            return result
    
        def generate(self, level, m, used, result, N, printable):
            if level == N :
                result[0] = result[0]+1
                #print ('result', printable, used, result)
            else:
                for v in m[level]:
                    if v > N :
                        return
                    else:
                        if v not in used:
                            used.add(v)
                            printable.append(v)
                            self.generate(level+1, m, used, result, N, printable)
                            printable.pop()
                            used.remove(v)
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.