Блог пользователя OmaeWaMouShenDeiru

Автор OmaeWaMouShenDeiru, история, 9 лет назад, По-английски

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

This is my code

Any hints ??

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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