Omówienie zadań i testy

Analiza wybranych programów wysłanych jako rozwiązania zadań konkursu testowego. Przeglądu kodu dokonał Jakub Łopuszański - doktorant informatyki na UWr, członek drużyny, która zdobyła srebrny medal w finałach mistrzostw świata w programowaniu zespołowym ACM w 2005 r. w Szanghaju, architekt portalu nasza-klasa.

  Patrząc na przykład od razu widzimy, że wśród twierdzeń mogą być zarówno takie, które koniecznie trzeba udowodnić (oczywiście jeżeli zależy nam na rozwiązaniu całej teorii) jak i takie, które udowodnić co prawda można (i być może nawet prowadzi to do zwiększenia prestiżu), ale wcale nie trzeba.

Z ankiety umieszczonej na forum wynika, że zadanie FLOODPLAN sprawiło wam najwięcej kłopotów. Nawet jeśli niektórzy wymyślili poprawne rozwiązanie, to nie udało im się go poprawnie zaimplementować. Tylko trzy osoby zrobiły to zadanie na 10 pkt.

Omówmy najpierw treść zadania. Dana była plansza z liczbami całkowitymi i należało "zalać" jej pewne pola stosując zasadę, że woda spływa w dół na wszystkie osiem pól sąsiadujących.

Dostępne są już testy do zadań z rundy drugiej:

• FLASHMOB.zip
• FLOODPLAN.zip
• MOUNTPATH.zip

Zadanie to okazało się najprostszym w rundzie drugiej. Jednak choć większość zawodników dostrzegła poprawne rozwiązanie, nie wszyscy zadali sobie dodatkowy trud udowodnienia jego poprawności.

Na wejściu dane było drzewo. Należało wyznaczyć minimalną liczbę ścieżek, która wystarzcza do pokrycia tego drzewa. Odpowiedzią okazała się być ilość liści podzielona przez dwa i zaokrąglona do góry.

Dostępne są już testy do zadań z rundy pierwszej:

• MUNDIV.zip
• OFFERCMP.zip
• PAYMENTS.zip

Większość zawodników dokonała tylko jednego zgłoszenia do tego zadania, jednak większość z tych zgłoszeń okazała się niepoprawna. Ci,którym udało się rozwiązać zadanie w większości podeszli do niego jak do problemu grafowego: wyznaczali wszystkie cykle grafu oraz pozycję poszczególnych osób w tych cyklach. Po tym etapie, majacym złożoność byli w stanie odpowiadać na kolejne zapytania w czasie (czyli stałym). Jest to optymalne rozwiązanie tego problemu oraz podejście, którego się spodziewaliśmy.

Zadanie Płatności, zgodnie z zamierzeniami autorów, okazało sie najprostszym zadaniem pierwszej rundy. Po przebrnięciu przez treść rozwiązujący szybko odkrywali, że cały problem sprowadza się do policzenia najmniejszej wspólnej wielokrotności (LCM) ośmiu liczb danych na wejściu. Oczywiście LCM dwóch liczb obliczamy jako ich iloczyn podzielony przez ich największy wspólny dzielnik (GCD). Analogicznie LCM ośmiu liczb jest to ich iloczyn podzielony przez ich GCD (spróbuj to udowodnić).

Rozwiązania nadesłane do tego zadania w wiekszości miały dobre intencje, jednak nie zawsze były poprawnie zaprogramowane. Zdarzyły się też zgłoszenia które, zamiast skorzystać z pomysłu (o którym niżej), opierały się na bardzo skomplikowanych i nieadekwatnych do zadania strukturach z biblioteki standardowej. Nie uzyskały one maksymalnej ilości punktów.

Zadanie to cieszyło się największą popularnością podczas pierwszej rundy, okazało się też zadaniem najtrudniejszym. Ostatecznie tylko pięciu osobom udało się uzyskać za nie maksymalną ilość punktów.

Przypomnijmy treść zadania: Dana jest liczba całkowita z zakresu <2; 8*10⁶>. Należy podzielić ją przez jej najmniejszy dzielnik większy od jedności i powtarzać tę operację tak długo, jak to możliwe. Co bardzo istotne w tym zadaniu, nie wystarczy podać odpowiedzi dla jednej liczby - na wejściu może znaleźć się nawet milion zapytań.