Omówienie zadań i testy

17.06.2009

Analiza programów

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.

05.06.2009
Trudność

Prestiż

  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.

04.06.2009

Planowanie potopu

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.

04.06.2009

Testy do zadań z rundy drugiej

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

04.06.2009
Trudność

Górskie szlaki

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.

03.06.2009

Testy do zadań z rundy pierwszej.

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

03.06.2009
Trudność

Migający tłum

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ść $ O(n) $ byli w stanie odpowiadać na kolejne zapytania w czasie $ O(1) $ (czyli stałym). Jest to optymalne rozwiązanie tego problemu oraz podejście, którego się spodziewaliśmy.

02.06.2009
Trudność

Płatności

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ć).

02.06.2009
Trudność

Porównywanie ofert

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.

02.06.2009
Trudność

Żmudne dzielenie

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*106>. 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ń.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com