Potyczki algorytmiczne 2013 – zmagania

Potyczki algorytmiczne

Potyczki algorytmiczne


W dniach 21-28 maja odbyły się Potyczki Algorytmiczne. Jest to otwarty ogólnopolski konkurs algorytmiczny, co oznacza, iż każdy obywatel naszego kraju może w nim wystartować. W tym roku wystartowałem w drużynie z Admixiorem oraz jego bratem Łukaszem. Cała olimpiada rok rocznie przebiega w dość specyficzny sposób – codziennie (z wyjątkiem niedzieli) pojawiają się zadania, na których rozwiązanie ma się określony czas – w większości przypadków do końca dnia następnego.

Początek

Pierwsza sprawa będąca trudnym zadaniem, gdy startuje się w drużynach jest jej nazwa. Zawsze komuś coś się nie podoba. Mimo wielu pomysłów ostatecznie padło na „dendroFile”, jednakże Admixior, który jest wielkim trollem, napisał całą nazwę małymi literami… No cóż, można się przyzwyczaić, zwłaszcza, iż hasło wcale lepsze nie było :P.
Przy okazji w rankingu drużynowym znalazłem jedną drużynę o ciekawej nazwie – „luna”. Po pewnych domysłach i napisaniu wiadomości w odpowiedniej grupie na facebooku poznałem jej skład – pozdrowienia dla Marka, Szymona i Przemka – oraz jeszcze innej, także ciekawej osoby – kolejnego Szymona :).

Na początku – jak zwykle – szło gładko. Zadanie z pierwszej rundy było oczywiście trywialne i okazały się bardzo podobne do śpiewników z I etapu VI OIGa. Druga i trzecia runda były cięższe, jednakże udało nam się znaleźć wzorcowe rozwiązania. Niestety – popełniliśmy banalne błędy. W drugiej rundzie Łukasz pisząc kod niestety zaindeksował tablicę w pętli od złej zmiennej i stwierdził, iż kod jest poprawny. Z tegoż to powodu, ale także trudności analizy przykładów (sporo liczenia i łatwo o pomyłkę) nie sprawdzaliśmy dokładnie kodu. Dostaliśmy tylko 2/10 pkt, wszystko przez 3 złe znaki w kodzie :(. W trzeciej rundzie osobno myśląc (ja byłem w szkole) wymyśliliśmy dwa rozwiązania o złożoności czasowej liniowej, czyli mieliśmy dwie wzorcówki – moja oparta na odejmowaniu oraz Admixiora na mnożeniu. Po stwierdzeniu, iż kod kolegi zużywa mniej pamięci i odwołuje się do pamięci sekwencyjnie, co sprzyja tzw. cache hit wysłaliśmy jego kod. Dostaliśmy 4/10 pkt. Wprawdzie wynik przechowywaliśmy w 64-bitowej zmiennej, jednakże nie uniknęliśmy integer overflowa, bo mnożyliśmy dwie zmienne 32-bitowe przez siebie.

Z kolejnymi zadaniami było coraz ciekawej – długie rozkminy na Google Hangout do północy :). Runda 4. była bardzo ciekawa. Mieliśmy sporo pomysłów, jednakże wszystkie – jak spostrzegłem się trochę późno – były heurami. Zebrałem więc wszystkie pomysły i doznałem olśnienia. Wprawdzie nadal pozostała to heura, ale za to bardzo szybka – otrzymaliśmy 7/10 pkt! Później było tylko gorzej – na rundę dostawaliśmy po dwa zadania, z czego tylko jedno rozwiązywaliśmy. W rundzie 5. ostro myśleliśmy i coś wpadło nam do głowy. Jak się później okazało – „tuż przed końcem, ok. 1h” okazało się, iż to jest heura. Nadzieja powoli znikała, jednakże do głowy wpadły mi nie wiadomo skąd słowa „Shut up and don’t give up!” (które bardzo mi się spodobały) i po chwili doznałem olśnienia. Prosto przed północą zdążyłem wysłać poprawiony kod. Szymon, który rzekomo miał super-szybkie rozwiązanie, które cały czas zachwalał zapomniał wysłać zgłoszenia :P. Następnego dnia rano patrzę na stronę – nie ma wyników – „co jest?” – myślę i patrzę w harmonogram. Pomyliłem sobie północe – mieliśmy 24h więcej czasu. Ostatecznie dostaliśmy za to zadanie 5/10 pkt (brutek), a Szymon przekonał się, że jego niezwykłe rozwiązanie jest błędne :P. Runda 7? Katastrofa. Jedno zadanie bez pomysłu (Admixior nie zdążył zakodzić brutka mimo gotowego pseudokodu ode mnie… walnął rand()’a :P), a na drugie pomysł miałem od początku – o dziwo – jednakże okazało się to brutkiem. Dostaliśmy za nie 4/10 pkt.

Nie udało nam się być w top 20% rankingu (oni dostają koszulki). Gdyby tylko nie ta 2. i 3. runda… Wniosek na przyszłość dotyczący pracy w drużynie – jeżeli masz czas – sprawdzaj pomysły i kod. Kilka dni później pisze do mnie Szymon, że moja drużyna wygrała koszulki. Nie wierzyłem, ale zobaczyłem – po ostatniej rundzie zostaliśmy wylosowani! Na głównej stronie była (aktualnie nadal tam jest) nazwa naszej dryżyny – dendrofile :).

Pokrótce opisałem zmagania mojej drużyny w Potyczkach Algorytmicznych 2013. Wiem, wprawdzie nic ciekawego, dlatego post jest krótki, ale niektóre osoby z chęcią to przeczytają :). Pozdrawiam serdecznie!

5 myśli nt. „Potyczki algorytmiczne 2013 – zmagania

  1. Heh.. a pamiętam jak rok temu patrzyłem na was podczas obozu jak rozwiązywaliście zadania z Andrzejem (a ja ani me, ani be, brak wiedzy o podstawowej składni), a teraz całe oczko wyżej! Pozdrawia współlokator ;>

    • Wiesz, Andrzej to olał, a ja postanowiłem wystartować w OIu, który podniósł moje umiejętności. Do tego w tym roku wystartowałem z Admixiorem i jego bratem, którzy też mają trochę podstawowej wiedzy 🙂 Choć nadal z algorytmiki jestem słaby… :/

  2. Przynajmniej moge podnieść swoją samoocenę, że nie jestem aż takim laikiem ;). Kto wie, może się zobaczymy na OI w następnym roku.

    • Zazwyczaj jeździłeś na obozy organizowane przez Stworzyszenie Talent – jak jedziesz do Milówki k. Żywca to spotkamy się wcześniej 🙂

Dodaj komentarz