LOVEBIRDS - She was in Love with BST
Devo! She has broken up with him again!
And after a series of break ups and patch ups , she is done with him!
Being a geek to keep herself distracted, she picks up her favourite topic of dynamic programming where she comes across this idiot problem which says
Given a integer N , you have to tell the sum of number of structurally unique Binary search trees built on different permutations of the set{x , x such that x belongs to [1,N] and x is an integer}.
A Binary Search tree is said to be built on a permutation iff the in-order traversal of that BST is same as the permutation.
A permutation is said to be distinct from another if there exists a position i such that the i th element of both the permutations is different.
Now, her inability to solve the problem is quite stressful to her! Help her in Solving the problem!
NOTE: She observes that this number can be very large so output this number Modulo 1908 .
Moreover she tells you that there in-order traversal of a Binary search tree is Unique.
For Binary Search Tree Read https://en.wikipedia.org/wiki/Binary_search_tree
Input
The first line of the input consists of T , the number of test cases.
The following T lines consists of a single integer N
(N can be at max 1000 , T can be at max 1000)
Output
You have to Output T lines each consisting of the answer to the problem Modulo 1908
Example
Input: 2 1 2 Output: 1 2
hide comments
priyank:
2015-08-18 17:08:29
@psych_cod3r my 700B source length code in java get accepted. Here normal solution will give tle, some optimization is needed. My code get accepted in 0.15 seconds :) In java scanner gives time limit error.
|
|
newbie:
2015-08-18 10:50:09
how can be the inorder of a BST be any purmutation other than 1,2,3,4......n
|
Added by: | psych_cod3r |
Date: | 2015-08-17 |
Time limit: | 1s |
Source limit: | 1000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 MAWK BC NCSHARP COFFEE DART FORTH GOSU JS-MONKEY JULIA KTLN OCT PROLOG PYPY3 R RACKET SQLITE SWIFT UNLAMBDA |
Resource: | Intuition |