0
\$\begingroup\$

I was coding the problem here. I think I have solved it, but I ran into time limit exceeded issues. I am new in Competitive Programming, so I was looking for a better, time efficient logic for solving the same.

Time limit: 1 secs

My time: 3.01 secs

The problem in short:

Given the numbers [1 .. N ] to be put in a binary search tree and a sequence of m searches (\$s_1\$ , \$s_2\$ , . . . , \$s_m\$ ), solve the optimal BST problem with the cost as the sum of the distances between every two consecutive searches \$s_i\$ and \$s_{i+1}\$ on the BST.

Cost(T,S) = Depth(\$s_1\$) + Distance(\$s_1\$, \$s_2\$) + Distance(\$s_2\$, \$s_3\$) + ... + Distance(\$s_{m-1}\$, \$s_m\$).

import sys

def getLevel(node, data):
    if (node.key == data) : 
        return 1
    downlevel= 1+getLevel(node.left, data)  
    if (downlevel != 0) : 
        return downlevel  
    downlevel = 1+getLevel(node.right,data)                            
    return downlevel

def pathToNode(node, path, k):
    path.append(node.key) 
    if node.key == k : 
        return True
    if ((node.left != None and pathToNode(node.left, path, k)) or
            (node.right!= None and pathToNode(node.right, path, k))): 
        return True
    path.pop() 
    return False


def distance(node, x, y):
    path1 = [] 
    pathToNode(node, path1, x) 
    path2 = [] 
    pathToNode(node, path2, y) 
    i=0
    while i<len(path1) and i<len(path2): 
        if path1[i] != path2[i]: 
            break
        i = i+1  
    return (len(path1)+len(path2)-2*i) 

class newNode: 
    def __init__(self, item):  
        self.key=item 
        self.left = None
        self.right = None




def constructTrees(start, end):  
    list = []  
    if (start > end) :   
        list.append(None)  
        return list    
    for i in range(start, end + 1):  
        leftSubtree = constructTrees(start, i - 1)  
        rightSubtree = constructTrees(i + 1, end)  
        for j in range(len(leftSubtree)) : 
            left = leftSubtree[j]  
            for k in range(len(rightSubtree)):  
                right = rightSubtree[k]  
                node=newNode(i) 
                node.left = left    
                node.right = right   
                list.append(node)    
    return list

if __name__ == '__main__': 
    b1,c1=input().split(' ')
    b1=int(b1)
    c1=int(c1)
    ar = input()  # 1 3 2 1 2
    ar = ar.split(' ')
    ar = [int(x) for x in ar]
    min= sys.maxsize
    totalTreesFrom1toN = constructTrees(1, b1)  
    for i in range(len(totalTreesFrom1toN)):
        dist = getLevel(totalTreesFrom1toN[i],1)-1
        for j in range(len(ar)-1):
            dist=dist+distance(totalTreesFrom1toN[i], ar[j], ar[j+1])
        if(dist<min):
            min=dist
    print(min)

Can anyone tell me where I can possibly refine the code?

\$\endgroup\$
  • 3
    \$\begingroup\$ Links can rot or become broken. Please include a description of the challenge here in your question. \$\endgroup\$ – dfhwze Jul 20 '19 at 18:10
  • \$\begingroup\$ Maybe I don't understand the code, but I don't see how it could work. For example, neither getlevel() nor pathtonode() handle the case where node is None or alternatively don't recurse if node.left or node.right are None. \$\endgroup\$ – RootTwo Jul 21 '19 at 4:51
  • \$\begingroup\$ @RootTwo for pathnode() if node has no left or right child, it will pop the node value and return False signifying that there is no path ahead to go. For getlevel() I think I missed the back recursion condition. Thanks for pointing it out. \$\endgroup\$ – Excelsior Jul 21 '19 at 14:56
  • \$\begingroup\$ @dfhwze yes you are right, I will edit the question accordingly. \$\endgroup\$ – Excelsior Jul 21 '19 at 14:59
1
\$\begingroup\$

Use the properties of a BST

In a BST, if the value being search for is less than the key of the current node, then it is in the left subtree and if the value is greater than the key of the current node, then it is in the right subtree. Your code always searches the left subtree first and then searches the right subtree if needed. This code only searches one subtree:

def pathToNode(node, path, k):
    path.append(node.key) 
    if node.key == k : 
        return True

    elif k < node.key:
        if node.left and pathToNode(node.left, path, k):
           return True

    else:
        if node.right and pathToNode(node.right, path, k): 
           return True

    path.pop() 
    return False

The same applies to getlevel().

distance() determines the path from the root to each node. Then determines the common prefix of each path. This can be simplified as observing that if both nodes are in the same subtree, then the root of the current tree isn't on the path between the nodes.

def distance(node, x, y):
    if x < node.key and y < node.key:
        return distance(node.left, x, y)

    elif node.key < x and node.key < y:
        return distance(node.right, x, y)

    else:
        path1 = []
        pathToNode(node, path1, x) 
        path2 = [] 
        pathToNode(node, path2, y)

        return len(path1) + len(path2) - 2

Note: you don't actually need the path of a node, just it's depth.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.