dog_mage's blog

Help with problem C ACM ICPC
By dog_mage, history, 8 years ago, In English

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

Tags acm
  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If the list is 5 3 6 9 the string representation according to u would be "LRRR" but the same tree is formed

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

UPDATE : I just did paralell DFS traversal and it passed but i still cant figure it out why string representation wont work...

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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")

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply