OmaeWaMouShenDeiru's blog

Trie problem
By OmaeWaMouShenDeiru, history, 10 years ago, In English

for this problem on spoj, Im getting WA and I don't know why !!

This is my code

Any hints ??

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Your code doesn't always find the lexicographically smallest word. For example, consider the following input...

abc
aabc
aaabc

abc

Your code outputs "aabc", when the correct answer is "aaabc".

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

    well, how can it be done when I'm adding the words in reverse order ??

    because I'm confused with a test case like this:

    a aa aaa

    a

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

      The correct answer in that case is "aa".

      I haven't thought of a good solution yet. Apparently there can be up to 5 million letters in the whole input, so traversing the whole tree for every word will be too slow. I designed an algorithm like that and tried it out to check the speed, but stupid SPOJ is giving me wrong answer, as usual, probably because there's an extra newline, a missing new line or a mosquito flew by.

      I tried every possible input I found on the Internet and my program always gives the right answer, but yet the crystal delicate SPOJ checker is giving me WA.

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

      Then there's the easier solution of mapping every suffix to the shortest word that matches using map...

      But it can be solved using trie too, reversing all words and storing at every node of the trie the two minimal words that are contained in that subtree (two are required in case one of them is the prefix we are looking itself).

      → Reply