Teoria do konkursów algorytmicznych

Wywiady ze zwycięzcami, wpisy na tym forum, zdrowy rozsądek...wszystko to podpowiada, że kluczem do dobrych rezultatów w konkursach algorytmicznych typu PA jest po prostu praktyka, rozwiązywanie kolejnych zadań. Pytanie, czy tej praktyki nie uniemożliwią braki w teorii, bardziej zaawansowanej matematyce/informatyce?
Jaki zakres materiału trzeba mniej więcej opanować, aby móc spokojnie przejść do treningu, z przekonaniem, że kolejnym zadaniom jeśli nie sprostamy, to tylko w wyniku braku umiejętności, a nie wiedzy?

Oczywiście zdaję sobie sprawę z tego, że precyzyjna odpowiedź na powyższe pytanie może być niemożliwa. Zadowolę się danymi szacunkowymi.

Wiem też, że teoretycznie wszystko można wyprowadzić w trakcie. Specyfika tych konkursów, zwłaszcza ich ograniczenia czasowe, nie pozwalają jednak na wynajdowanie koła na nowo, dlatego też moje pytanie dotyczy tego, co jest potrzebne praktycznie.

Z góry dzięki za odpowiedzi.

1. Znajomość algorytmów i struktur danych (poziom Cormena minimum) bo nie ma co wymyślać koła na nowo. Szczególnie że niektóre algorytmy i struktury wymyślali długo dość ogarnięci ludzie i wątpliwe że sobie to wymyślisz w kilkanaście minut...
2. Znajomość teorii złożoności obliczeniowej, żeby umieć od razu oszacować czy nas pomysł nie jest O(n!) albo O(nⁿ) i czy będzie się liczył w skończonym czasie ;]
3. Znajomość klasycznych problemów NP zupełnych, żeby nie zrobić genialnej redukcji problemu z zadania do problemu NP zupełnego ;) Zwykle jest to możliwe, czasem nawet bardzo proste, tylko że potem zostajemy z problemem trudniejszym niż ten początkowy i marnujemy czas próbując rozklepać komiwojażera podczas gdy w zadaniu wystarczyłby cykl eulera... ;]

i wsio?

Nie. To są warunki konieczne a nie wystarczające :P

mógłbyś coś więcej rzec o tym drugim? swoją drogą, dzięki za dotychczasowe i mam nadzieję kolejne ;)

Tzn? Chodzi o szacowanie takiego parametru jak http://pl.wikipedia.org/wiki/Asymptotyczne_tempo_wzrostu
Wyobraź sobie że masz dwa algorytmy, jeden ma złożoność O(n³) a drugi O(n²), bo na przykład jeden rozwiązuje jakiś problem za pomocą trzech zagnieżdżonych pętli for a drugi za pomocą dwóch pętli, bo pętlę wewnętrzną zastąpiło na przykład użycie hashmapy.

Przykład takiego algorytmu: mamy daną tablicę NxN i chcemy policzyć ile razy w takiej tablicy każda z liczb się powtarza.
Algorytm naiwny zakłada że mamy listę/tablicę która przechowuje informacje o danej liczbie i o tym ile razy wystąpiła. Za każdym razem musimy w tej tablicy znaleźć analizowaną liczbę, co wymaga liniowego czasu względem rozmiaru tablicy (musimy średnio przeglądnąć połowę tablicy aż znajdziemy).
Algorytm sprytniejszy zakłada że mamy hashmape która dla liczby zwraca nam ilość wystąpień i robi to w czasie stałym.

Jak widać w obu algorytmach stałym członem jest O(n²) bo musimy przeglądnąć całą wejściową tablicę. Różnica pojawia się w tym co robimy z każdą analizowaną liczbą. Algorytm naiwny wykonuje średnio n/2 operacji żeby znaleźć w tablicy zliczającej analizowaną liczbę, algorytm sprytny takie wyszukiwanie wykonuje w czasie stałym.

Załóżmy że dla danych o rozmiarze X oba algorytmy działają 0.001 sekundy (np. przypadek kiedy masz tablicę 1x1 :P)
Co się stanie jeśli zwiększymy rozmiar danych 10 razy?

• dla n³ mamy 10³ = 1000 więc algorytm będzie pracował 0.001 sekundy * 1000 = 1 sekundę
• dla n² mamy 10² = 100 więc algorytm będzie pracował 0.001 sekundy * 100 = 0.1 sekundy
  A jak dane zwiększymy 100 razy?
• dla n³ mamy 100³ = 1000000 więc algorytm będzie pracował 0.001 sekundy * 1000000 = 1000 sekund = 16,6 minut!
• dla n² mamy 100² = 10000 więc algorytm będzie pracował 0.001 sekundy * 10000 = 10 sekund

Często musisz od razu "widzieć" że jakieś rozwiązanie nie przejdzie bo ma za wysoką złożoność i nie ma sensu marnować na nie czasu tylko mysleć nad czymś lepszym.

dzięki ;)

Swoją drogą powstała nawet ciekawa praca magisterska dostępna w sieci "Algorytmika praktyczna w konkursach informatycznych". Można w niej zobaczyć, jak różne zagadnienia teoretyczne łączą się z konkretnymi zadaniami z konkursów. Pod danym tematem (np. o ścieżkach i cyklach Eulera) są zadania z PA, OI, czy ICPC, w których tę teorię powinno się wykorzystać. Poza tym na końcu są porady odnośnie treningów od np. Tomka Czajki.