Zadanie pisarze, jak do tego podejść ?

Zadanie z zeszłorocznej OI PISARZE
Zadanie wydaje mi się ciekawe i oryginalne, tylko jak do tego podejść ? Macie na to jakiś pomysł ?

Wyglada jak wyszukiwanie wzorca w tekscie. KMP np. albo KR

Edit:
Dalej jest napisane, ze rozwiazania nie musza byc idealne co by sugerowalo algorytm liczacy hashe (np. Karp-Rabin) i niesprawdzanie (/niepelne sprawdzanie) czy doszlo do kolizji.

Ja nie jestem pewien czy to KMP. Bo tekst może być całkiem długi.
W przypadku KMP każdy fragment z przypadku testowego wymaga przeskanowania trzech tekstów.
Bardziej mi tu pasuje drzewo sufiksowe, bo nie wymaga skanowania całego tekstu dla każdego przypadku testowego. Tylko konstrukcja drzewa sufiksowego w naiwny sposób jest kosztowna. Metoda Ukkonena konstrukcji drzewa sufiksowego działa szybko, ale chyba nie jest najprostszy w implementacji. Istnieje jeszcze metoda McCreight albo Weinera.
Czy takie proste? chyba nie ; )

Może tablica sufiksów (nie naiwna, tylko indeksy początku i końca) + specjalna bisekcja po tej tablicy by przeszła.

Wygląda ciekawie, fajnie, że OI robi teraz takie zadanka, do tego z limitem kodu. Kilka luźnych pomysłów:

1. Słownik nazw własnych - imion, miejsc itp.
2. Sprawdzanie liczb i kiedy dzieje się akcja.
3. Analizy statystyczne słów, liter itp. Tutaj słownik też będzie ograniczeniem, dla limitu kodu powinno wejść około 1800 słów po 5 znaków każde.
4. U Mickiewicza można sprawdzać, czy tekst jest trzynastozgłoskowcem.
5. Haszowanie grup po 10 słów, ale Pan Tadeusz miał 68 682 wyrazy, więc to pewnie nie przejdzie, ale użycie większych grup pozwoli przejść mniejsze testy.
6. Analiza długości zdań i interpunkcji.

"Zadanie: PIS"
Widać do OI też wcisneli swoich ludzi :)

Analiza słownictwa, jeśli trafimy na słowo występujące tylko w danym dziele, to mamy trafienie. Dalej można lecieć pewnie klasyfikatorem Bayesa.

Ciekawe czy dałoby się przepuścić przez jakiś algorytm Machine Learning / NLP np. kilku stron z Pana Tadeusza, kilku stron z Quo Vadis oraz kilku stron z Lalki - a potem dać na wejściu dać fragment i algorytm na podstawie stylu sam by się domyślił, z czego to jest? Ktoś wie, czy coś takiego byłoby wykonalne?

1. Można by zrobić term-frequency i policzyć jak często dane słowa występują w każdej z książek i potem na tej podstawie wyliczyć prawdopodobieństwo że dany tekst pochodzi z każdej z książek.
2. Można by spróbować policzyć sobie n-gramy (powiedzmy 4 albo 5 liter) i na ich podstawie wnioskować. Działa to świetnie np. do rozpoznawania języków, ale możliwe że tutaj też się sprawdzi o ile słownictwo jest wystarczająco różne.

Prosimy o zwrócenie uwagi, że w zadaniu "Pisarze" uruchamiany program NIE MA dostępu do plików z treściami książek. W szczególności próba czytania z pliku zakończy się błędem "Naruszenie zasad".

wtf

WeiXiao napisał(a):

wtf

W OI nigdy nie można korzystać z zewnętrznych rzeczy (z dokładnością do czasu dla liczb losowych czy czegoś nieinwazyjnego), liczy się tylko strumień wejścia i wyjścia.