IITKESO207SPA3C  Optimal BST
Problem description
This problem deals with the optimal binary search tree.
For the optimal search tree, we assumed that the search key was always present in the tree. In general this is not true. The search key may not be present in the tree. We can model this situation as follows :
For each i, assume we have probability q_i which gives the probability that a search key, say k, lies between k_i and k_i+1 (the keys are in increasing order). In addition, let q_0 be the probability that a search key k < k1 and q_n be the probability that k > k_n. So in addition to the probabilities for a hit, we have probabilities for a miss.
Implement the optimal BST algorithm to find the optimal BST, and the minimum expected value of the number of comparisons.
Input format
The input will consist of three lines. The first line will have an integer n, which denotes the number of keys in the tree. The second and third line will have n values, which denote the probabilities as defined above. Please refer to the pdf document for the exact question format.
Output format
The output format should consist of two lines. The first should tbe the expected value for the number of comparisons in the optimal binary tree. The second line should contain a recursive structure containing the BST itself. It should be written as follows (root(leftBST)(rightBST))
Note 1 : If one of the children of any node is empty, please print () for that child. Please look at the sample I/O for an example of this.
Note 2 : Please print 2 decimal digits whenever you are printing them in your program. The test cases will have 2 decimal digits. You can see this in the sample output.
Note 3 : In case of multiple trees with the same expected cost, submit those with the smallest elemetn as the root of the tree, and that of the subsequent subtrees.
Note 4 : People for whom the scores were showing as 0, with their code working, the issue was with how SPOJ interpreted spaces. Your code should work now, the judge has been updated. Please do not print any spaces in the output, the first line should have a float value with 2 decimals, and the second line must consist only of parantheses and integers.
Sample input
10
0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.05
0.01 0.04 0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.05
Sample output
3.70
( 5 ( 3 ( 2 ( 1 ) ( ) ) ( 4 ) ) ( 7 ( 6 ) ( 9 ( 8 ) ( 10 ) ) ) )
Scoring method
Please note that apart from the sample test case posted here, there will be other hidden test cases that your code will checked on. The final score you see is a percentage of the test cases you have passed. If you pass only the sample test case, you will get 0/100 (even though your score will be shown as 10/100).
Each of these questions are finally worth the points mentioned in the assignment pdf file. So your credit for this problem shall be your score/100 * points for this question. Your final credit for programming assignment 3 shall be final score / 55 * 100.
Plagiarism and copying
Strict action will be taken against students who are found to be indulging in plagiarism. Please note that changing variable names, removing indentation or moving code around will not help with regards to plagiarism checking.
TA note : The testcases and sample I/O have been updated (13.45, 1/7/17). In case of doubts, please contact the TA at gundeep@iitk.ac.in
The deadline for this problem alone has been extended to 3rd July 2355 hrs. The others need to be submitted by the original deadline.
hide comments
hardik1496:
20170701 18:17:42
Can you tell which solution to print when there exist multiple solutions.


anshulv:
20170701 12:08:17
Last edit: 20170701 12:12:42 

anshulv:
20170701 09:57:59
I think the positions of parentheses should be changed to (6(3(2(1)())(4()(5)))(8(7)(9()(10)))) in the sample output. 

Programming Club, IITK:
20170630 16:05:56
The test cases are being updated. This program will be given an extended deadline. 

pawanrocks:
20170630 15:28:59
Sample input from CLRS Intro to Algo 3rd Ed.  Page 398


apurvsh:
20170630 15:24:30
Total probability ( Sum (pi+qi) ) should be 1 but it's 1.01 in the sample input 

pawanrocks:
20170630 14:53:26
The sample output (the expected number of search comparisons) is '0.96' which is less than 1. There must be atleast one comparison.


anshulv:
20170630 14:23:27
I think the sample output is not correct. 
Added by:  Programming Club, IITK 
Date:  20170627 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  ESO207, IIT Kanpur Summer Semester 2017 