no tags 

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(left-BST)(right-BST))

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

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

( 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: 2017-07-01 18:17:42

Can you tell which solution to print when there exist multiple solutions.
For sample input this sequence
also give 3.70 expected value of comparisons

anshulv: 2017-07-01 12:08:17

Last edit: 2017-07-01 12:12:42
anshulv: 2017-07-01 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: 2017-06-30 16:05:56

The test cases are being updated. This program will be given an extended deadline.

pawanrocks: 2017-06-30 15:28:59

Sample input from CLRS Intro to Algo 3rd Ed. | Page 398
0.15 0.10 0.05 0.10 0.20
0.05 0.10 0.05 0.05 0.05 0.10
( 2 ( 1 ) ( 5 ( 4 ( 3 ) ( ) ) ( ) ) )

Last edit: 2017-07-01 13:03:07
apurvsh: 2017-06-30 15:24:30

Total probability ( Sum (pi+qi) ) should be 1 but it's 1.01 in the sample input

pawanrocks: 2017-06-30 14:53:26

The sample output (the expected number of search comparisons) is '0.96' which is less than 1. There must be at-least one comparison.
Also the output for tree: ( 0 ( 2 ( 1 ) ( 4 ( 3 ) ( 6 ( 5 ) ( 7 ( 8 ( 9 ))))))) is a single sided binary tree...
We can definitely create a better tree.

Last edit: 2017-06-30 14:55:30
anshulv: 2017-06-30 14:23:27

I think the sample output is not correct.

Added by:Programming Club, IITK
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:ESO207, IIT Kanpur Summer Semester 2017