Ranking 800

Postanowiłeś rozpocząć swoją przygodę z programowaniem konkursowym. Twoim celem jest osiągnięcie tytułu Grandmastera na platformie Codeforces i zastanawiasz się, jakie zagadnienia warto opanować na początku. Aby ułatwić Ci ten proces, przeanalizowałem 100 zadań o poziomie trudności 800, aby zidentyfikować kluczowe tematy, które warto przyswoić, aby móc skutecznie rozwiązywać zadania o tym poziomie trudności.

Zasada Pareta

Zadania o poziomie trudności 800 są bardzo zróżnicowane, a ich pełne opanowanie wymaga przyswojenia szerokiego zakresu wiedzy. Jednak z pomocą przychodzi zasada Pareta, która mówi, że opanowanie około 20% materiału pozwala na rozwiązanie 80% problemów. W kontekście programowania konkursowego oznacza to, że skupiając się na kluczowych zagadnieniach, będziesz w stanie rozwiązać większość zadań na tym poziomie. Młodzież mówi, że są to tematy, które “oddają”. Poniżej przedstawiam listę tematów, których opanowanie pozwoli Ci skutecznie rozwiązywać znaczną część zadań o rankingu 800.

• Podstawy C++ – Rozwiązanie każdego zadania będzie wymagało napisania odpowiedniego fragmentu kodu. Oznacza to, że niezbędna jest znajomość programowania. Choć teoretycznie możesz wybrać dowolny język programowania, w dalszej części będę zakładał, że posługujesz się językiem C++. Na początek zapoznaj się z tym, jak napisać pusty program w C++, jak skompilować go oraz uruchomić. Opanowanie tych podstawowych kroków jest kluczowe przed przystąpieniem do bardziej zaawansowanych zagadnień.
• Zmienne – Zmienne stanowią podstawowy element programowania imperatywnego, dlatego warto zacząć naukę od zapoznania się z nimi. Na początek wystarczy, że zrozumiesz działanie jednego typu zmiennych — typu całkowitoliczbowego, czyli int. Naucz się, jak deklarować zmienne oraz jak przypisywać im wartości, co stanowi fundament dla dalszego rozwoju umiejętności programistycznych.
• Wczytywanie i wypisywanie – Każde zadanie będzie wymagało od Ciebie umiejętności wczytania danych oraz wypisania ich na standardowe wyjście.
• Działania arytmetyczne – Mając już podstawową wiedzę o zmiennych oraz umiejętność wczytywania i wypisywania danych, kolejnym krokiem będzie zapoznanie się z operacjami arytmetycznymi, które można wykonywać na zmiennych. Szczególną uwagę zwróć na operację dzielenia, ponieważ może ona działać inaczej, niż się spodziewasz. Ważną operacją w informatyce jest liczenie reszty z dzielenia. Zwróć uwagę na to, że C++ stosuje się do kolejności wykonywania działań, a w przypadku potrzeby zmiany tej kolejności, użyj nawiasów w wyrażeniach matematycznych.
• Instrukcja warunkowa – Kolejnym krokiem w nauce programowania będzie poznanie nowego typu danych — bool, który reprezentuje wartości logiczne. Zapoznaj się z operatorami logicznymi (and, or, not) oraz operatorami porównania (<, <=, ==, !=, >=, >). Następnie przejdź do zrozumienia instrukcji warunkowych, które występują w trzech formach: if, if … else oraz if … else if … else. Aby utrwalić tę wiedzę, napisz program, który wyznacza większą z dwóch liczb, oraz program obliczający wartość bezwzględną liczby.
• Pętle – Pętle pozwalają na wielokrotne wykonanie określonych fragmentów kodu, co jest kluczowe w programowaniu. Zapoznaj się z dwoma podstawowymi typami pętli: while oraz for. Temat ten może sprawiać trudności początkującym programistom, dlatego upewnij się, że opanowałeś użycie pętli i czujesz się z nimi komfortowo, zanim przejdziesz do bardziej zaawansowanych zagadnień.
• Systemy liczbowe – W wielu zadaniach będziesz musiał operować na cyfrach danej liczby. Istnieje prosta pętla while, która umożliwia wyodrębnienie cyfr liczby. Co ciekawe, może ona również posłużyć do konwersji liczby na dowolny system liczbowy. Jest to dobry asumpt aby dowiedzieć się co nieco o systemach liczbowych, z szczególnym uwzględnieniem systemu binarnego. Stąd już tylko krok aby nauczyć się systemu U2 i dowiedzieć się jak komputery reprezentują liczby całkowite. Wiedza ta pomoże Ci również zrozumieć, dlaczego w języku C++ istnieją różne typy zmiennych dla liczb całkowitych i kiedy stosować typ int, a kiedy long long. Wiedza ta okaże się kluczowa przy wielu zadaniach programistycznych..
• Tablice – Tablica jest jedną z podstawowych struktur danych, którą warto poznać na początku nauki programowania. Jako ćwiczenie, spróbuj odwrócić tablicę. W tym celu przydatna będzie umiejętność zamiany miejscami dwóch zmiennych.
• Znaki – Nadszedł czas na poznanie nowego typu danych — char. Kluczowe jest zrozumienie, że char jest w rzeczywistości zmienną całkowitoliczbową, na której można wykonywać operacje arytmetyczne. Komputer konwertuje litery na ekranie za pomocą tablicy ASCII. Zwróć uwagę na tzw. sekwencje ucieczki i naucz się, jak zmieniać wielkość liter oraz jak odczytywać liczby naturalne zapisane jako znaki.
• Algorytmy przyrostowe – Podstawową techniką rozwiązywania problemów związanych z tablicami jest metoda przyrostowa. Główną ideą tej metody jest analiza, jak zmienia się wynik obliczeń, gdy do tablicy dodawany jest nowy element. Następnie symulujemy dodawania kolejnych elementów, począwszy od tablicy pustej, aż do osiągnięcia pełnej tablicy. Dwa podstawowe algorytmy ilustrujące tę technikę to wyszukiwanie minimum w tablicy oraz obliczanie sumy elementów tablicy.
• Permutacje – Codeforces kocha permutacje. Chociaż wiele problemów dotyczących permutacji można rozwiązać bez pełnego zrozumienia tej koncepcji, lepiej jest opanować ją przed rozpoczęciem zawodów. Warto szczególnie zwrócić uwagę na sposób obliczania permutacji odwrotnej, ponieważ ta umiejętność może okazać się przydatna w różnych kontekstach.
• Zliczanie – Ostatnią techniką, którą warto opanować, jest technika zliczania. Pozwala ona na określenie liczby wystąpień określonych wartości w zadanej tablicy. Jest to niezwykle przydatna umiejętność, która znajduje zastosowanie w wielu problemach programistycznych.

Pozostałe tematy

Wśród 100 analizowanych przeze mnie zadań pojawiły się tematy, które występowały na tyle rzadko, że nie zalecałbym ich nauki na tym etapie. Sugeruję, abyś skupił się na zagadnieniach omówionych w poprzednim rozdziale, a mniej istotne tematy zostawił na później albo w ogóle zignorował je – wrócimy do nich później, gdy zaczną pojawiać się częściej.

• Podzielność i liczby pierwsze
• Symulacja
• Sortowanie
• Algorytmy zachłanne
• Strategia wygrywająca
• Porządek leksykograficzny
• Przesunięcia cykliczne
• MEX
• Liczby rzeczywiste (double)

Tematy o których warto wiedzieć

Niektóre tematy, choć niekoniecznie bezpośrednio przyczyniają się do rozwiązywania nowych zadań, mogą znacząco ułatwić życie programistyczne. Do takich zagadnień należą:

• Jak się uczyć
• Jak czytać zadanie
• Jak trenować
• Metody rozwiązywania zadań
• Jak debugować swój program
• Wcięcia
• Rzutowanie typów
• Widoczność zmiennych
• Niezdefiniowane zachowanie (UB)
• Funkcje

Opanowanie podstawowych technik i zagadnień programistycznych to pierwszy krok w kierunku stania się skutecznym uczestnikiem zawodów konkursowych. Teraz, gdy masz solidne fundamenty, zachęcam Cię do dalszego eksplorowania i czerpania radości z rozwiązywania wyzwań. Życzę Ci owocnej zabawy i sukcesów w Twojej przygodzie z algorytmami!