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:
- Słownik nazw własnych - imion, miejsc itp.
- Sprawdzanie liczb i kiedy dzieje się akcja.
- 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.
- U Mickiewicza można sprawdzać, czy tekst jest trzynastozgłoskowcem.
- 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.
- 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?
- 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.
- 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.