Ulubione zadania mistrzów, Zostań zawodnikiem, Dla zawodników

27.11.2009 - Anna Piekarska
Trudność

Sito Eratostenesa

Już starożytni Grecy zastanawiali się nad zagadnieniem liczb pierwszych. Aktualnie problem zdaje się wciąż nie być dostatecznie zbadany. Jednak dziś wiemy nieco więcej niż kiedyś. Do rozwoju teorii przyczynił się zdecydowanie Eratostenes - wymyślił tzw. Sito Eratostenesa czyli dość prosty algorytm znajdowania liczb pierwszych. Prosty oczywiście dla małych liczb. Wciąż nie znamy algorytmu wielomianowego na faktoryzację.

26.11.2009 - Marcin Oczeretko
Trudność

Wyszukiwanie binarne

    W jaki sposób szybko znajdować wartości w posortowanym zbiorze? Istnieje sprytny sposób na sprawne rozwiązywanie tego problemu - wyszukiwanie binarne. Poniższy artykuł umożliwi Wam zapoznanie się z tym potężnym i zarazem bardzo prostym algorytmem.

25.11.2009 - Krzysztof Nowicki
TrudnośćTrudność

Algorytm Dijkstry

Zagadnienie znajdowania najkrótszej ścieżki jest dość często spotykane. Czasem widać je wprost, czasem jest jednak tylko małą częścią trudniejszego problemu, jednak niezbędną, by go rozwiązać.

25.11.2009 - Karol Konaszyński
TrudnośćTrudność

Najdłuższy podciąg rosnący

Wszędzie otaczają nas liczby: większe, mniejsze - żadnej reguły! Trzeba jednak to wszystko ogarnąć i znaleźć jakieś prawidłowości wśród nich. W tym artykule zajmiemy się znajdowaniem najdłuższego podciągu rosnącego, czyli światełko w tunelu dla tych, którzy nie lubią chaosu. Zapraszam do zabawy z liczbami!

25.11.2009 - Damian Rusak
Trudność

Podstawy algorytmów tekstowych

Aby przyswoić zasady działania algorytmów tekstowych trzeba znać podstawowe zagadnienia i definicje z tej dziedziny. Może się wydawać, że nie ma nic bardziej intuicyjnego od posługiwania się tekstem i językiem, jednak to co te pojęcia oznaczają z informatycznego punktu widzenia może być początkowo zaskakujące. Poniższy artykuł ma na celu prezentację (mam nadzieję, w miarę ciekawy sposób) terminologii, której znajomość pozwala nauczyć się wielu fascynujących algorytmów tekstowych.

22.11.2009 - Kuba Łopuszański
TrudnośćTrudność

Odwracanie ogonem kota

Pisząc ten artykuł postanowiłem, że nie zdradzę ani jednego rozwiązania, bo odebrałbym Wam dużo radości. Nie mam ulubionego zadania, ani nie umiem opowiedzieć poruszającej historii na temat zawodów, mogę jednak podzielić się próbką problemów, których rozwiązania na zawsze utkwiły mi w głowie. Oto one, wraz z delikatnymi podpowiedziami.

18.11.2009 - Marcin Oczeretko
Trudność

Permutacje

    Z permutacjami spotykamy się dość często w informatyce, jak również i w codziennym życiu, choć czasem nawet nie zdajemy sobie z tego sprawy. Jeśli pragniesz dowiedzieć się, co kryje się za pojęciem permutacji i nieco sformalizować swoje intuicyjne do niego podejście, zapraszam do lektury poniższego artykułu.

13.11.2009 - Marcin Bieńkowski
TrudnośćTrudność

Pająki

Dłuższą chwilę zastanawiałem się jak nie zacząć tekstu od frazy ,,moim ulubionym zadaniem''.  Poszło łatwiej niż sądziłem, gdyż Pająki (o których jest ten artykuł), są jednym z zadań, które dostarczyły mi głównie mnóstwo frustracji, choć również jeszcze więcej satysfakcji z oszukania systemu. Opisane w tym artykule rozwiązanie zadania wydaje się ciekawe, gdyż redukuje problem grafowy do problemu wyszukiwania wzorca (a nie — jak to zwykle bywa — na odwrót). Ale zacznijmy od początku.

31.10.2009 - Damian Rusak
Trudność

Algorytm Euklidesa

Czym jest Algorytm Euklidesa i jak taki algorytm można zapisać? Do czego służy? Jeżeli chcesz poznać odpowiedź na te pytania, zapraszamy do lektury! Ten algorytm to rzecz niezbędna dla każdego, kto chce wykorzystać w swoich programach siłę liczb.

03.10.2009 - Paweł Gawrychowski
TrudnośćTrudność

Chińska komórka

Nie jest to może moje ulubione zadanie (nie wygrałem dzięki jego rozwiązaniu żadnych zawodów :), ale na pewno jest bardzo fajnym przykładem użycia dość ogólnej techniki, którą warto znać. Także dlatego, że w dość zaskakujący sposób pojawia się w niej geometria obliczeniowa (mam nadzieję, że nie zniechęci to Was to dalszej lektury...), mimo że zadanie na pierwszy (a nawet na drugi) rzut oka nie ma nic wspólnego z geometrią. Ale po kolei...

03.10.2009 - Damian Rusak
TrudnośćTrudnośćTrudność

Maski bitowe

Pomocna w rozwiązaniu wielu problemów algorytmicznych z gatunku programowania dynamicznego bywa  umiejętność zwięzłego zapisu wszystkich możliwych do osiągnięcia stanów. Spotykamy problemy, w których te stany to pewne podzbiory. Co to oznacza? W jaki sposób reprezentować podzbiory i czy faktycznie jest to dobry i skuteczny sposób rozwiązywania problemów algorytmicznych? Odpowiedzi na te pytania znajdziesz w tym artykule.

19.09.2009 - Tomasz Waleń
TrudnośćTrudność

Krasnoludki

Jednym z najciekawszych zadań spośród tych, nad którymi miałem okazję się chwilę zastanawiać, są Krasnoludki. Problem pochodzi z obozu treningowego na IOI drużyny reprezentującej Rumunię, a odnalazłem o nim informację poprzez wpis na blogu Mihai'a Pătraşcu (na którym można znaleźć także wiele innych ciekawych problemów!).

03.08.2009 - Alan Meller
TrudnośćTrudność

Password suspects

Jednym z moich ulubionych zadań algorytmicznych jest Password Suspects z ACM World Finals 2008. Kapitan naszej drużyny przydzielił mi je wtedy mówiąc, że „to chyba jest dość proste”. Po dokładnym przeczytaniu treści tego oraz innych zadań, które miałem rozwiązać tamtego dnia uznałem, że to jednak nie jest zupełnie trywialne i póki co zajmę się innym, prostszym. Niestety, początek tego konkursu był dla nas nieudany i po około półtorej godziny zaczęliśmy być już mocno z tyłu.

31.07.2009 - Władysław Kwaśnicki
TrudnośćTrudnośćTrudność

Query on a tree IV

Zanim przejdziemy do treści i opisu rozwiązania, kilka informacji o zadaniu. Możecie je znaleźć na SPOJu (tutaj), umieścił je tam Qu Jun, ale nie jestem pewien, czy to on jest jego autorem. Niektórzy pewnie zauważyli dziwny pogrubiony napis na dole strony, w pewnym sensie to ja jestem jego sprawcą.

25.07.2009 - Jakub Radoszewski
TrudnośćTrudnośćTrudność

Monotoniczna aproksymacja

Moim bodaj ulubionym zadaniem konkursowym jest zadanie za 500 z czwartej, czyli ostatniej zdalnej, rundy konkursu TopCoder Open 2006. Pewnie dlatego, że wskutek kilku ciekawych zbiegów okoliczności to zadanie okazało się mieć niespodziewany wpływ na historię moich startów w konkursach programistycznych, ale i nie tylko. Zacznijmy jednak od początku.

03.06.2009 - Eryk Kopczyński
TrudnośćTrudnośćTrudność

Football

W tym artykule przedstawiam jedno z ulubionych zadań mojego autorstwa. Zostało ono użyte na zawodach CEPC '03 (Central European Programming Contest) jako zadanie F (chociaż w trakcie pracy było nazywane raczej foo — skrót od Football). Dla pierwszej drużyny, która wysłała prawidłowe rozwiązanie, była ufundowana dodatkowa nagroda — piłka nożna. Podczas całych zawodów udało się to trzem drużynom: z Akademii Górniczo-Hutniczej, z Uniwersytetu Wrocławskiego, i z Uniwersytetu Warszawskiego.

02.06.2009 - Bartosz Walczak
TrudnośćTrudnośćTrudność

Autostrady

Jednym z moich ulubionych zadań z konkursów informatycznych są ,,Autostrady'' z II etapu X Olimpiady Informatycznej 2002/2003. Jego treść (obrana z historyjki) wygląda mniej więcej tak: Na prostej wybrano $ n $ punktów ponumerowanych od $ 1 $ do $ n $ według ich kolejności występowania na tej prostej. Danych jest $ k $ par punktów, które należy połączyć łukami. Każdy taki łuk musi przebiegać w całości po jednej stronie prostej.

06.02.2009 - Tomasz Czajka
TrudnośćTrudnośćTrudność

Snakes on a plane

W maju 2008 roku w Las Vegas odbyły się zawody TopCoder Open 2008. W eliminacjach online turnieju algorytmicznego wzięło udział ponad 1700 zawodników, z czego do finałów w Las Vegas zakwalifikowało się 72 osoby.

04.02.2009 - Marek Cygan
TrudnośćTrudność

Crazy painter

Zadanie polega na jak najszybszym pomalowaniu prostokątnej planszy o m wierszach oraz n kolumnach. Dla każdego z mn pól planszy znany jest kolor, na który trzeba to pole pomalować. Pola mogą być malowane wielokrotnie, przy czym dane pole za każdym razem musi być malowane tym samym kolorem (docelowym). Do malowania możemy wykorzystać następujące operacje:

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com