Binary Search Tree - the algorithm supports the idea to solve "Minimum Cost" (series 8 of 10)

Nov. 20, 2016

Problem statement:

https://www.hackerrank.com/contests/womens-codesprint-2/challenges/minimum-loss



Julia spent a lot of time to try to get used to work on contest algorithms on HackerRank. She saw a lot of efforts she put in, but she was just the beginner of competitor programmer, maybe 10% compared to best talent in the world. 

But, nothing can stop her to mentor herself to get through the stage, and become more confident on the competition. She started to know what to work on in the contest/ after the contest, understand most important things to do in order to get better. 

One thing about the algorithm "Minimum Cost" is to handle the time complexity. Binary Search Tree is good enough algorithm to handle the scale of algorithm. 

Look into the detail of description of problem:
next n years - the span of years - 200000, 0.2 million years, 

n >= 2 and n <= 2 * 10^5, so n^2 will be around 4 * 10^10, 
nlogn is best fit, since logn = 5, if 10 is base of log function. 

No matter the solution is written in C++ or Java, most popular languages used in the top performers, they all chose to use binary search tree based on class, Java TreeSet is most popular one, and then, C++ Set which is also based on binary search tree. 

Here is the just thoughts Julia likes to write a blog about the series, to make it to series of 8 of 10. 

So, in order to understand the contest, competition better, as a former teaching assistant of computer science, Julia likes to study the solution of basic binary search tree, implemented in the way to return the minimum difference as a loss. 

A lot of people stopped in the contest after this second algorithm. Julia felt the same way the difficulty. But she just likes to take one algorithm a time. Do not try to push herself too hard. She stopped on her third algorithm, worked so hard, over 5 hours, messing with recursive/ bugs with concatenating the string - her favorite test case: 2 3 4 6 8, n = 12

She tried so hard to work out on this test case:
    2   3  4  6  8   12
2  T   F  T  T  T   T   -  can divided by 2? 
3
4 
6 
8
  She worked on the backward to find all possible routes - for example, 12, 6, 3, or 12, 6, 2 etc. 

Using Binary search - therefore, it is easy to find the minimum price, O(nlogn)
Maintain a binary search tree!

Study this C# solution using Binary search tree:

https://gist.github.com/jianminchen/c910f5d1f37309c70b489e6c75b0678c

Very classical solution using binary search tree, and very clever solution.

Memorize the solution. Warm up the solution sometimes in the future.