Editorial for Polynomial Calculator


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.
eps = 1e-3

# Python code to insert a node in AVL tree
# https://www.geeksforgeeks.org/insertion-in-an-avl-tree/
# Generic tree node class
class TreeNode(object):
    def __init__(self, val, intercept, slope, quadratic):
        self.val = val
        self.intercept = intercept
        self.slope = slope
        self.quadratic = quadratic
        self.left = None
        self.right = None
        self.height = 1

# AVL tree class which supports the
# Insert operation
class AVL_Tree(object):

    # Recursive function to insert key in
    # subtree rooted with node and returns
    # new root of subtree.
    def insert(self, root, key, intercept, slope, quadratic):

        # Step 1 - Perform normal BST
        if not root:
            return TreeNode(key, intercept, slope, quadratic)
        elif key < root.val:
            root.left = self.insert(root.left, key, intercept, slope, quadratic)
        else:
            root.right = self.insert(root.right, key, intercept, slope, quadratic)

        # Step 2 - Update the height of the
        # ancestor node
        root.height = 1 + max(self.getHeight(root.left),
                        self.getHeight(root.right))

        # Step 3 - Get the balance factor
        balance = self.getBalance(root)

        # Step 4 - If the node is unbalanced,
        # then try out the 4 cases
        # Case 1 - Left Left
        if balance > 1 and key < root.left.val:
            return self.rightRotate(root)

        # Case 2 - Right Right
        if balance < -1 and key > root.right.val:
            return self.leftRotate(root)

        # Case 3 - Left Right
        if balance > 1 and key > root.left.val:
            root.left = self.leftRotate(root.left)
            return self.rightRotate(root)

        # Case 4 - Right Left
        if balance < -1 and key < root.right.val:
            root.right = self.rightRotate(root.right)
            return self.leftRotate(root)

        return root

    def leftRotate(self, z):

        y = z.right
        T2 = y.left

        # Perform rotation
        y.left = z
        z.right = T2

        # Update heights
        z.height = 1 + max(self.getHeight(z.left),
                        self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left),
                        self.getHeight(y.right))

        # Return the new root
        return y

    def rightRotate(self, z):

        y = z.left
        T3 = y.right

        # Perform rotation
        y.right = z
        z.left = T3

        # Update heights
        z.height = 1 + max(self.getHeight(z.left),
                        self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left),
                        self.getHeight(y.right))

        # Return the new root
        return y

    def getHeight(self, root):
        if not root:
            return 0

        return root.height

    def getBalance(self, root):
        if not root:
            return 0

        return self.getHeight(root.left) - self.getHeight(root.right)

    def search(self, root, key):
        if not root:
            return None
        elif key <= root.val - eps:
            return self.search(root.left, key)
        elif key >= root.val + eps:
            return self.search(root.right, key)
        else:
            return root

tree = AVL_Tree()    
root = None

m,n = map(int, input().split())

a = list(map(float, input().split()))

queryPoints = list(map(float, input().split()))

for i in range(n):
    x = queryPoints[i]
    current = tree.search(root, x)

    if current is not None:
        print(current.intercept + current.slope * (x - current.val) + current.quadratic * (x - current.val) * (x - current.val) / 2)
    else:
        intercept = a[0] + a[1] * x
        slope = a[1]
        quadratic = 0
        xp = 1

        for j in range(2,m+1):
            quadratic += j * (j - 1) * a[j] * xp
            xp *= x
            slope += j * a[j] * xp
            intercept += a[j] * xp * x

        root = tree.insert(root, x, intercept, slope, quadratic)
        print(intercept, end=" ")