






"""simple docstring"""



# This Python program implements an optimal binary search tree (abbreviated BST)
# building dynamic programming algorithm that delivers O(n^2) performance.
#
# The goal of the optimal BST problem is to build a low-cost BST for a
# given set of nodes, each with its own key and frequency. The frequency
# of the node is defined as how many time the node is being searched.
# The search cost of binary search tree is given by this formula:
#
# cost(1, n) = sum{i = 1 to n}((depth(node_i) + 1) * node_i_freq)
#
# where n is number of nodes in the BST. The characteristic of low-cost
# BSTs is having a faster overall search time than other implementations.
# The reason for their fast search time is that the nodes with high
# frequencies will be placed near the root of the tree while the nodes
# with low frequencies will be placed near the leaves of the tree thus
# reducing search time in the most frequent instances.
import sys
from random import randint

class 	a					:







    def __init__(      self							,		_lowerCamelCase							,		_lowerCamelCase	):
      lowercase							   =	key
      lowercase							   =	freq







    def __str__(      self	):
      return F'Node(key={self.key}, freq={self.freq})'


def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  List[Any]		, __snake_case      :  Union[str, Any]		, __snake_case      :  Any		, __snake_case      :  Optional[Any]		, __snake_case      :  List[str]		, __snake_case      :  Tuple   ):





  '''simple docstring'''





  if i > j or i < 0 or j > len(__snake_case   ) - 1:
    return

  lowercase							   =	root[i][j]
  if parent == -1:  # root does not have a parent
    print(f'{key[node]} is the root of the binary search tree.'   )
  elif is_left:
    print(f'{key[node]} is the left child of key {parent}.'   )
  else:
    print(f'{key[node]} is the right child of key {parent}.'   )

  print_binary_search_tree(__snake_case		, __snake_case		, __snake_case		, node - 1		, key[node]		, __snake_case   )
  print_binary_search_tree(__snake_case		, __snake_case		, node + 1		, __snake_case		, key[node]		, __snake_case   )
def 						_SCREAMING_SNAKE_CASE			(   __snake_case      :  List[str]   ):





  '''simple docstring'''





  nodes.sort(key=lambda __snake_case   : node.key   )

  lowercase							   =	len(__snake_case   )

  lowercase							   =	[nodes[i].key for i in range(__snake_case   )]
  lowercase							   =	[nodes[i].freq for i in range(__snake_case   )]

  # This 2D array stores the overall tree cost (which's as minimized as possible);
  # for a single key, cost is equal to frequency of the key.
  lowercase							   =	[[freqs[i] if i == j else 0 for j in range(__snake_case   )] for i in range(__snake_case   )]
  # sum[i][j] stores the sum of key frequencies between i and j inclusive in nodes
  # array
  lowercase							   =	[[freqs[i] if i == j else 0 for j in range(__snake_case   )] for i in range(__snake_case   )]
  # stores tree roots that will be used later for constructing binary search tree
  lowercase							   =	[[i if i == j else 0 for j in range(__snake_case   )] for i in range(__snake_case   )]

  for interval_length in range(2		, n + 1   ):
    for i in range(n - interval_length + 1   ):
      lowercase							   =	i + interval_length - 1

      lowercase							   =	sys.maxsize  # set the value to "infinity"
      lowercase							   =	total[i][j - 1] + freqs[j]

      # Apply Knuth's optimization
      # Loop without optimization: for r in range(i, j + 1):
      for r in range(root[i][j - 1]		, root[i + 1][j] + 1   ):  # r is a temporal root
        lowercase							   =	dp[i][r - 1] if r != i else 0  # optimal cost for left subtree
        lowercase							   =	dp[r + 1][j] if r != j else 0  # optimal cost for right subtree
        lowercase							   =	left + total[i][j] + right

        if dp[i][j] > cost:
          lowercase							   =	cost
          lowercase							   =	r

  print('Binary search tree nodes:'   )
  for node in nodes:
    print(__snake_case   )

  print(f'\nThe cost of optimal BST for given tree nodes is {dp[0][n - 1]}.'   )
  print_binary_search_tree(__snake_case		, __snake_case		, 0		, n - 1		, -1		, __snake_case   )
def 						_SCREAMING_SNAKE_CASE			(   ):





  '''simple docstring'''





  lowercase							   =	[Node(__snake_case		, randint(1		, 50   )   ) for i in range(10		, 0		, -1   )]
  find_optimal_binary_search_tree(__snake_case   )


if __name__ == "__main__":
    main()










"""simple docstring"""



def 						_SCREAMING_SNAKE_CASE			(   ):





  '''simple docstring'''





  for a in range(3_00   ):
    for b in range(a + 1		, 4_00   ):
      for c in range(b + 1		, 5_00   ):
        if (a + b + c) == 10_00 and (a**2) + (b**2) == (c**2):
          return a * b * c

  return -1
def 						_SCREAMING_SNAKE_CASE			(   ):





  '''simple docstring'''





  for a in range(3_00   ):
    for b in range(4_00   ):
      lowercase							   =	10_00 - a - b
      if a < b < c and (a**2) + (b**2) == (c**2):
        return a * b * c

  return -1
def 						_SCREAMING_SNAKE_CASE			(   ):





  '''simple docstring'''





  import timeit

  print(
      timeit.timeit('solution()'		, setup='from __main__ import solution'		, number=10_00   )   )
  print(
      timeit.timeit(
          'solution_fast()'		, setup='from __main__ import solution_fast'		, number=10_00   )   )


if __name__ == "__main__":
    print(F'''{solution() = }''')


