27.11.2009 - Anna Piekarska
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
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
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
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
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
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
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
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
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
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
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ń
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
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
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
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
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.
|
|
06.02.2009 - Tomasz Czajka
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
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:
|