Za to ja skomentuję.
Cały problem został doskonale przedstawiony w drugim linku. Pada tam następujące zdanie: "Jeżeli dobrze rozumiem [SPOJ] to jest strona mająca uczyć i wspomagać uczenie pisania algorytmów w różnych językach, a nie kółko do wyszukiwania sztuczek matematycznych". Pogrubiłem definicję SPOJa według autora tego zdania a słowo uczyć - jako najważniejsze w tej definicji i będące przyczyną frustracji - dowydatkowo wyróżniłem kursywą.
Dyskusja sprowadza się do filozofii - co to znaczy uczyć? Ostatnie dwie cyfry silni z pewnością są jakoś związane z nauką bo silnia to pojęcie matematyczne a matematyka jest nauką. Niestety tutaj pewniki się kończą. Nauka to szerokie pojęcie i nie sposób powiedzieć, czy wyznaczanie tych cyfr to coś bardziej matematycznego czy bardziej informatycznego (A może fizycznego, bo tam też są silnie? A może polonistycznego - bo czemu "silnia" a nie "ślńa" albo "factorial"?). Trudno powiedzieć, czy jest to zadanie łatwe, średnie czy trudne - bo niby jak to obiektywnie ocenić? http://pl.spoj.com/problems/AL_09_06/ jest według mnie trywialne. Ale nim je rozwiązałem dziwiło mnie, że tak ciężkie zadanie jest w łatwych - na siłę szukałem tu dzikiego problemu teorii grafów i dopiero niedawno, po zdobyciu niemałej wiedzy o grafach, udało mi się to rozwiązać - po prostu przestałem tu szukać macierzy sąsiedztwa itd. bo zadanie jest elementarne. Trudno powiedzieć jak zadanie "Dwie cyfry silni" wiąże się z nauką nie tylko dlatego, że zależy to od poziomu trudności, ale też dlatego, iż nie da się łatwo powiedzieć co to znaczy "nauka". Chodzi o naukę rozumianą jako tworzenie nowej wiedzy nieznanej światu czy o naukę rozumianą jako zdobywanie wiedzy? A może obie opcje są prawidłowe?
Problem jest trudny i (po)ważny. Tak trudny i tak (po)ważny, że nadaje się na dysertację doktorską: http://www2.im.uj.edu.pl/phd/DymelPhd2009_pl.pdf. Sam uważam, że poza Olimpiadą Informatyczną, Olimpiadą Fizyczną, Olimpiadą Matematyczną i może Olimpiadą Astronomiczną nie ma wartych uwagi Olimpiad w szkole średniej (ściślej: odradzam każdą). Nie jest to tylko moje zdanie - gdy byłem uczniem otwarcie odradzano mi udział w konkursach przedmiotowych a mój matematyk na studiach nie ukrywał swojego dość złego zdania o Olimpiadzie Matematycznej.
Załóżmy, że mówimy o algorytmice. Uznajmy ją za dział matematyki i zapytajmy się, w jaki sposób zadanie to wiąże się z algorytmiką. Z pewnością nie wymaga ono żadnego znanego (i nieznanego też) algorytmu. Niestety nie sposób stwierdzić, czy jest to wada czy też zaleta tego zadania. Może to być zaleta dla osoby nie lubiącej czytać o BFSach wszelakich, ale jest to zdecydowanie wada dla osób, które chcą poznawać algorytmy - w istocie zadanie jest dla nich beznadziejne i stanowi kompletną stratą czasu. Jest to zaleta dla początkujących, ale dużo takich zadań dekoncentruje bardziej zaawansowanych użytkowników. Wreszcie co to znaczy znać algorytmy? Czy znam algorytm Knutha-Morrisa-Pratta jeżeli wiem co on mniej więcej robi i do czego można go wykorzystać a przy tym nie umiem go zaklepać w danym języku albo nawet pseudokodzie w kilka chwil? Nie ukrywam też, że nie umiem udowodnić optymalności ani poprawności tego algorytmu. Nawet nie myślałem o tym by to udowodnić! A może wyrażenie "umieć algorytmy" oznacza odpowiedni sposób myślenia? Może chodzi tu właśnie o to by widząc problem w rodzaju "496. Dwie cyfry silni" być w stanie samemu wymyślić odpowiednie rozwiązanie? A może zadanie to jest błędne i prawidłowe rozwiązanie polega na wyprowadzeniu jakiejś funkcji (matematycznej a nie "programistycznej") nieznanej nauce, która dla danych argumentów podaje w jakiś mniej lub bardziej bezpośredni sposób ostatnie cyfry silni? Swoją drogą - co to jest silnia? Czy wiem co to silnia jeśli nie znam funkcji gamma? A tak w ogóle to może zamiast robić "bzdury" na SPOJu lepiej zacząć od problemu P vs NP?
Czas na krótkie podsumowanie.
Ludziska! SPOJ to tylko SPOJ! Nie szukajcie tutaj cudów bo wcale ich tu nie ma i nigdy nie będzie. Albo jakieś zadanie umiecie zrobić albo nie. Albo jakieś zadanie wam się podoba albo nie. Jeżeli uważacie, że zadanie jest bez sensu i nic wam nie da to po prostu nie rozwiązujcie go. Nikt wam też nie broni szukać rozwiązań w internecie - każdy programista sięga po dokumentację, każdy naukowiec przeszukuje książki i artykuły naukowe, każdy inżynier korzysta z norm, każdy lekarz konsultuje swoje wątpliwości z innym lekarzem, każdy maturzysta ma dostęp do tablic i może tam szukać wartości funkcji trygonometrycznych dla kąta 17 stopni... To tylko zadania i wielu ludzi nie rozwiązało żadnego problemu na SPOJu a są oni dobrymi programistami / naukowcami / nie-wiadomo-kim-jeszcze. Z pewnością są też tacy, którym SPOJ po prostu się nie podoba i wolą inne strony z zadaniami. Wielu analizuje jedynie materiały z olimpiad informatycznych. Sam mam ochotę powiedzieć coś niemiłego o http://pl.spoj.com/problems/HANG/, ale nie zamierzam niczego zarzucać autorowi, który po prostu stworzył zadanie opisane mniej lub bardziej poprawnie i jednoznacznie. Wielu ludzi podołało temu zadaniu, ale ja nie. I nie czuję się przez to gorszy ani nie uważam że autor zadania jest głupi ani nie sądzę, że to zadanie jest bez sensu! Zwyczajnie nie podejmuję entej próby rozwiązania. Może kiedyś, ale teraz wolę robić zadania średnie i poznawać nowe algorytmy a nie bawić się z wisielcem. Jeżeli więc coś wam się nie podoba w danym zadaniu to zwyczajnie go nie rozwiązujcie. Przypominam, że na SPOJu nie ma gwarancji poprawności zadań ani gwarancji nauczenia się czegokolwiek. SPOJ to po prostu SPOJ. Osobiście traktuję go jako fajną rozrywkę intelektualną. Może też tak powinniście zrobić?
Przepraszam, jeżeli to spam.
