Ranking 900
Postanowiłeś rozpocząć swoją przygodę z programowaniem konkursowym. Twoim celem jest osiągnięcie tytułu Grandmastera na platformie Codeforces. Opanowałeś już zadania z poziomu 800 i zastanawiasz się co dalej. Przeanalizowałem 100 zadań o poziomie trudności 900, aby zidentyfikować kluczowe tematy, które warto przyswoić, aby móc skutecznie rozwiązywać zadania o tym poziomie trudności.
Sortowanie
Pierwsza dobra wiadomość: Wiedza, którą przyswoiłeś przy okazji zadań z poziomu 800 powinna Ci umożliwić rozwiązać ponad 50% zadań o rankingu 900. Oczywiście – zadania te mogą okazać się trudniejsze niż zadania o rankingu 800. Pamiętaj również o tym, że nawet jeśli wiesz wszystko co jest Ci potrzebne do rozwiązania zadania, to nie oznacza to, że na pewno sobie z nim poradzisz. Zadania często wymagają pomysłu albo zauważenia pewnej własności w zadaniu. Nie przestawaj zatem ćwiczyć!
Druga dobra wiadomość: Tematy jakie powinieneś przyswoić (moim zdaniem) przy tym rankingu, kręcą się wokół jednego tematu: sortowania.
- Sortowanie – naucz się korzystać z standardowej funkcji sortującej. Naucz się również sortować indeksy (tj. tak posortować indeksy w tablicy, aby wskazywały one na elementy zgodnie z ich wartościami, bez zmiany kolejności samych elementów w tablicy). Możesz przy okazji dowiedzieć się w jaki sposób działają różne algorytmy sortujące, aczkolwiek na tym poziomie nie jest to konieczne (zaowocuje to jednak w przyszłości).
- Porządek leksykograficzny – porównywanie liczb jest proste. Jak jednak działa porównywanie ze sobą dwóch napisów? Część zadań z poziomu 900 będzie wymagała od Ciebie tej wiedzy
- Algorytmy zachłanne – większość algorytmów zachłannych wymaga od Ciebie umiejętności sortowania elementów (reszta wymaga znajomości kolejki priorytetowej – ale zadania tego typu nie pojawiły się na poziomie 900).Problemy optymalizacyjne to problemy w których twoim zadaniem jest podanie optymalnego sposobu rozwiązania pewnego problemu (tj. sposobu, który maksymalizuje lub minimalizuje pewną wartość). Niektóre z tych problemów można rozwiązać w sposób zachłanny rozważając na przykład elementy w rosnącej kolejności.
Ponieważ lista w tym odcinku jest niezwykle krótka, polecałbym zapoznanie się z jeszcze jednym tematem, który jest lekki i przyjemny:
- Palindromy – palindromem nazywamy słowo, które czytane od lewej do prawej brzmi tak samo jak czytane od prawej do lewej.
Inne tematy
Inne tematy, które występują w zadaniach o rankingu 900, ale zdarzają się na tyle rzadko, że polecam z nimi jeszcze trochę poczekać:
- Brute-force
- Tablica sum prefiksowych
- MEX
- Algorytm euklidesa
- Dwumian newtona
- Operacje bitowe
- XOR
- Dwa wskaźniki
- Nawiasowanie
- Algorytm przyrostowy z wyborem maksimum
- Łatwe parsowanie napisów
- Strategia wygrywająca
- Przekątne
- Liczby fibonacciego
- Szukanie kontrprzykładów
- Podciągi
- Odległość manhatańska
- Kombinatoryka
- Suma ciągu arytmetycznego
Podsumowanie
Wiele problemów można efektywnie rozwiązać dopiero po uporządkowaniu danych. Dlatego drugim krokiem w twojej przygodzie algorytmicznej powinna być nauka sortowania. Życzę Ci owocnej zabawy i sukcesów w Twojej przygodzie z algorytmami!
