http://pl.spoj.com/problems/PTWPZ075/
Patrząc na limit czasowy oraz to, że rozwiązanie O(nlogn) z fast I/O daje TLE można wywnioskować, że oczekiwaną złożonością w tym zadaniu jest O(n) (jest jeszcze szansa, że trzeba napisać bardzo efektywną implementację O(nlogn), ale biorąc pod uwagę, że zadanie powinno dać się rozwiązać używając przynajmniej scanf/printf, to nie ma złudzeń, że i taki pomysł się nie powiedzie).
Zastanawiam się nad liniowym rozwiązaniem od dłuższego czasu i jeszcze nie znalazłem żadnego sensownego podejścia. Bardzo mylące jest to, że napisy, które trzeba posklejać mogą zawierać tylko cztery znaki ('A','C','G','T'). Czy wzorcowy algorytm opiera się na tym spostrzeżeniu? Czy należy zakodować te znaki na 2 bitach? Oceniam to jako bardzo mało prawdopodobne, ale czy wtedy w zadaniu nie mielibyśmy większej liczby unikalnych znaków w ciągach? Z drugiej strony ograniczenie do czterech liter może wynikać tylko i wyłączenie z historyjki zawartej w treści.
Napisałem ten post dlatego, że jak wyrzucę z siebie to co mi chodzi po głowie, to często potrafię później wrócić do problemu ze świeżym podejściem i znaleźć rozwiązanie. Może tak będzie i tym razem.
