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

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

Hi guys! I was trying to solve problem 327 on SGU (http://acm.sgu.ru/problem.php?problem=327) , at the moment I can't acces the link so I will describe it here : We have n (n < = 14) words with length of maximum 30 exnglish letters. We have to determine the shortest string which has all of this words as subsequences and is a palindrome. Time limit : 0.25s

Example :

4 abcd cdef efef fed

Solution : abcdefefedcba

SPOILER ALERT :

It is a problem of Hamilton Cycle , but really don't know how, I think we can add some more n words, the reversed ones of the ones from input.

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

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

Auto comment: topic has been updated by RomeoFantastik (previous revision, new revision, compare).

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

Auto comment: topic has been updated by RomeoFantastik (previous revision, new revision, compare).

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

Does somebody know, how to find Hamilton in less, than O(n!)?

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

Some ideas, please? :)