Informatyka UJ forum

smas

[link widoczny dla zalogowanych]

cct · pijak Dołączył: 21 Mar 2006 Posty: 202 Przeczytał: 0 tematów

Niniejszym oficjalnie zgłaszam swoją [link widoczny dla zalogowanych] na rezultat działania ASD w kategorii "najsympatyczniejszy ANS" :D

cct · pijak Dołączył: 21 Mar 2006 Posty: 202 Przeczytał: 0 tematów

Wzorcóweczkę może ktoś ma? Bo jakoś mi Athina płacze, że ANS... ;/

EDIT: dobra, głupie pytanie, mogę napisać przecież kwadratówkę ;)) sorry za zawracanie głowy.

dzendras

Się ludziom nudzi:
[link widoczny dla zalogowanych]

:lol:

chlebek

jakby komus nie chcialo sie pisac kwadratowki to binarka jest tutaj:
[link widoczny dla zalogowanych]

exeman

Szkoda, ze na athine nie mozna posylac binarek :P

Fen

ufff... udało mi się to posłać i dostałem OK, chociaż dwie gwiazdki i tak musiałem zaliczyć ;|

@chlebek - dzienks za binarkę, przydała się do debugu :)

Roxel

Dla tych co jeszcze nie wiedzą, to algorytm jest opisany tutaj:
[link widoczny dla zalogowanych]
Idea jest dobrze opisana, ale kod zawiera kilka blędów, także nie obejdzie się
bez lekkiego pomyślunku :P

cedric

Dla tych którzy nie wiedzą, algorytm do wyszukiwania palindromów nazywa się
algorytmem Manachera
algorytm ten jest bardzo porządznie i z dobrym wstępem (np mówiącym o tym jak manacher wynika z bruta) jest opisany
[link widoczny dla zalogowanych]

od 12 strony :-) tak w ogóle to nie bójcie się tych chińskich krzaczków na początku

tak w ogóle to tam jest kilka różnych podejść do znajdowania palindromów, ale tam znajdują tylko parzyste palindromy, ale to żaden problem bo tam wystarczy delikatnie zmienić procedurę żeby to działało dla nieparzystych palindromów

I żeby nie było że jestem jakimś lizusem czy coś, ale jak przeczytacie całego pdfa to zobaczycie że uczą nas czegoś porzytecznego o czym świadczy fakt że jest to skrypt z instytutu biotechnologii :-D

kg86

na wazniaku tez mozna znalezc ten algorytm, nawet sa identyczne oznaczenia :P chociaz rozni sie w jednym detalu, ktory i tak do niczego nie jest potrzebny ;P
no i jest po polsku :D

Rogal

Co do algorytmu z ważniaka... Przeklepałem - nie działał. Poprawiłem to co od razu było widać, że jest źle - dalej nie działał...

Makros

kg86

@rogal - no bo nie jest to zupelnie poprawny algorytm... trzeba zmienic w nim kilka rzeczy(usunac jednego ifa, dodac warunki czy indeks nie wychodzi poza tablice i w jednej instrukcji warunkowej != zamienic na < albo >, nie pamietam :P), tak samo w tym, co zapodal cerdic :P

Prezioso

Czy znacie jakieś bardzo upierdliwe testy?? Bo od 2 godzin generuję własne, wszystko się zgadza z wynikami binarki chlebka a athina - ANS :(

chlebek

ten test powinien znalezc bledy dzialania algortymu, jesli takie sa :]
[link widoczny dla zalogowanych]

Prezioso

Jasko

Prezioso

Jasko

Skrobocik

Macie może jakieś pomysły, gdzie może łapać RTE :?:
Po jakimś czasie mi RTE wyskoczyło, nie od razu, i nie wiem co może być źle :?
Wydaje mi się, że poobsługiwałem dobrze warunki brzegowe, obym się nie mylił ;)

smas

Skrobocik

Powiem krótko: "Algorytm Skrobotera"(R) też przechodzi przez Athinę :D

exeman

Moglby ktos wypisac bledy jakie sa w wazniaku? Ja mam tylko te:
- niepotrzebny if
- na poczatku trzeba sprawdzic czy rad[1] faktyczne bedzie 0, bo moze byc 1 jesli dwa pierwsze sa rowne
- dopisac warunki brzegowe prawe i lewe w pierwszym i drugim whileu?

Nie działa.

Btw. Monacher tez nie dziala. Sa tam jakies bledy?

r4ku

to co jest na wazniaku to wlasnie manacher.
tam tablica indeksowana jest od 1, wiec jesli wczytujesz %s to musisz przeskalowac czytanie, albo algorytm
przede wszystkim while(i<n) a nie n/2
zabezpieczenie przed wyjsciem z tablicy (z obu stron)
wywalic tego ifa(ale zostawic to co jest w ifie tylko bez ifa :P )
w kolejny whilu zabezpieczyc sie zeby k<=j
i tyle
on jest dla palindormow parzystych, dla nieparzystych musisz
x[i+1+j] w whilu na poczatku zamienic na x[i+j]

exeman

thx raku. przykladowe piknie daja dobre odpowiedzi, a athina ans od razu, nawet queued nie widze :/