Zadanie z zeszłorocznej OI PISARZE
Zadanie wydaje mi się ciekawe i oryginalne, tylko jak do tego podejść ? Macie na to jakiś pomysł ?
- Rejestracja:prawie 5 lat
- Ostatnio:12 dni
- Postów:354
0
stivens
"Zadanie wydaje mi się ciekawe i oryginalne" - imho wrecz odwrotnie xd
Suchy702
wydało mi się dość ciekawe że użytkownik wpisuje fragment książki a program odpowiada co to za książka, a nie jakieś permutacje palindroliczb, ale to pewnie też dlatego że widziałem mało zadań
stivens
Tzn. zmieszczenie sie w limitach moze byc jak najbardziej wyzwaniem ale sam problem "do ktorego tekstu pasuje ten wzorzec?" jest jakies takie nudne moim zdaniem
- Rejestracja:ponad 8 lat
- Ostatnio:około 8 godzin
1
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.
edytowany 5x, ostatnio: stivens
- Rejestracja:około 9 lat
- Ostatnio:prawie 2 lata
- Postów:1039
0
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.
edytowany 2x, ostatnio: nalik
Zobacz pozostałe 7 komentarzy
Ani drzewa, ani KMP, ani nic korzystającego z tekstów źródłowych nie przejdzie, trzeba zbudować jakiś model i zgadywać. Ciekawe, że nie ma podanego limitu czasu.
Swoja to ja jednak moj post zaakcentowalem na naiwny KR. Co mi tak to KMP wypominacie :p
No ale na czym zrobisz KR? Jak chcesz zrobić wyszukiwanie w tekście, jak nie masz całego tekstu dostępnego? A jak chcesz liczyć hashe, to jak je zapiszesz w kodzie źródłowym z limitem 10kB?
Nie wzialem pod uwage, ze nie mozna otworzyc w programie pliku z tekstami. Nie mialem na mysli tablicowania hashy (te i tak by musialy byc na podciagach roznej dlugosci)
- Rejestracja:prawie 18 lat
- Ostatnio:19 dni
0
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.
edytowany 1x, ostatnio: Afish
Zobacz pozostałe 5 komentarzy
A słowniki od biedy można skompresować np huffmanem. pytanie czy warto.
A jak skompresujesz i jaki będziesz miał z tego zysk?
Policzę kodowanie na tekstach źródłowych słowniku i zahardkoduje. Zysk - być może parę słów więcej. Ale to raczej jak będzie brakować miejsca w tych 10k na słowniki. Bo absolutne nie jest to rozwiązanie, jedynie bida optymalizacja. Musi być jakiś model zbudowany.
Ale Ty chcesz kompresować słownik słów łacińskich? I co będzie tutaj symbolami do Huffmana, litery? Chętnie bym zobaczył, jak chcesz serializować drzewo Huffmana z kodem dekompresji w taki sposób, żeby było to krótsze od zwykłej listy słów. Chyba, że chcesz kompresować całe książki, to w ogóle odpada.
nevermind, chodzilo o skompresowanie reprezentacji slownika, wklapie skompresowanej reprezentacji do kodu, a potem odwtorzenie slownika podczas startu, jakiegokolwiek slownika, by oszczedzic pare bajtow, do czego potrzebujesz tylko klucza do dekompresji wklepanego na stałe. Ale to kompletnie bez znaczenia, bo jak napisalem, nie rozwiazuje problemu, od tak rzucone.
- Rejestracja:około 11 lat
- Ostatnio:około 4 godziny
- Postów:8409
0
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?
Byłoby, ale raczej nie zmieści się w kod źródłowy.
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
2
- 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.
- Rejestracja:prawie 18 lat
- Ostatnio:19 dni
0
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.
tzn. dziwi mnie że jest zadanie bazujące na danych i trzeba "zahardkodować" ich interpretacje w kodzie, czy coś źle rozumiem?
zhardkodowac/napisać trzeba jakis klasyfikator
No gdyby było można, to zadanko by było trywialne