Link :https://online.acmicpc.org/problems/ceiling
I had an idea to solve this problem in O(n^2) by just presenting tree as String.For example we will have 2 trees(both used to compare each other).If we have List : 5 6 3 9 the string representation of this tree wouls be "RLRR" which means they were added in the tree in following order.After i build both trees i would check if they have same property(amount of L's and R's) if that is the case i would mark those trees the same.
My soulution is giving WA on 7th case and i wonder what it is?
Thanks
If the list is 5 3 6 9 the string representation according to u would be "LRRR" but the same tree is formed
UPDATE : I just did paralell DFS traversal and it passed but i still cant figure it out why string representation wont work...
I used a very similar idea in my solution and got it to work. Basically for ever single number that is added, I added a string representation of the "direction" it took down the tree (i.e. "LRRL") and then added this string representation to a list. I sorted this list and then added the string representation of this list to a set. My answer was the size of said set.
Code: pastebin.com/qKU6jBA6
For input 5 3 6 8, would your solution generate the following string : "LRRR" ?
If so,could you tell me why this solution fails? https://online.acmicpc.org/submissions/2992
I am just generating string for every single tree and storing it sorted(so i can compare it easily with other strings due to L'S and R's numbers),then just traverse N^2 and look for same tree.
I'll read your solution but for 5 3 6 8 my code would generate the following list (I imagine that there is an invisible root of 0): ("R","RL","RR","RRR")
If my understanding is correct, your program would incorrectly assume that 5 6 3 4 1 is the same as 5 9 6 3 4
I solved the problem this way:
The set of all possible trees is infinite and countable so there is a bijection between this set and the natural numbers. So you can build and then "code" every tree using this bijection and use a set to store how many different codes were found.
The coding is given recursively:
code(v) = 0 if v is leaf node
code(v) = f(v->left,v->right) otherwise
f(a,b) should give some unique natural number identifying this pair of subtrees
My implementation: http://pastebin.com/wE4TWs05
I used hashing and a single tree to guide hashing process and which indices to update.
The main idea was to keep an id field in node structure to define which tree a node belongs to, so when we insert a new element, if current id conflicts with the new id then we just change node's key and insertion is done.
For hashing, I used i*2+1, i*2+2 to move along indices for left and right directions to avoid collisions
Code