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.
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=" ")