Orientacja

 

“Journey is the reward” – Steve Jobs

Dlaczego warto poznać algorytmikę?

Bez użycia szybkich algorytmów wiele technologii, których używasz na co dzień, nie miałoby racji bytu. Wyobraź sobie, że jadąc samochodem, czekasz 10 minut zanim GPS zlokalizuje twoje położenie. Gdy przeglądasz Facebooka nie ładuje ci się ściana, bo akurat jest przeciążenie serwera. Wyszukiwarka nie znajduje stron, których szukasz, a Youtube podpowiada filmy, które w ogóle cię nie interesują. To nie przypadek, że te sytuacje nie zdarzają się praktycznie wcale. Ale jak to wygląda od kuchni?

Powyższe systemy w swoim “jądrze” zawierają zaawansowane algorytmy, które pozwalają im szybko i skutecznie działać do tego stopnia, że większość ludzi nie wyobraża sobie bez nich dzisiaj życia. To, co odróżnia ludzi piszących duże systemy – specjalistów z Google, Facebooka, Microsoftu i innych znanych firm od przeciętnych programistów zajmujących się nudnym i żmudnym “klepaniem kodu” jest właśnie znajomość algorytmów. Jeśli chcesz zostać jednym z nich, to algo jest miejscem dla Ciebie.

Algorytm i algorytmika

Algorytm to nic innego jak sposób postępowania prowadzący do rozwiązania problemu. Każdy problem da się rozwiązać na wiele sposobów – od topornych i nieefektywnych do eleganckich i optymalnych. Nauką o poszukiwaniu poprawnych i wydajnych rozwiązań problemów (algorytmów) jest algorytmika.

Czego nauczysz się na kółku?

Zadania z algorytmiki wymagają od nas przede wszystkim logicznego myślenia. W każdym zadaniu musimy dokonać pewnych obserwacji. Na podstawie tych obserwacji tworzymy rozwiązanie, którego poprawności musimy dowieść. Najważniejszy jest sam pomysł na rozwiązanie i dobór algorytmów, natomiast znajomość składni schodzi na dalszy plan. Dzięki temu znając tylko podstawy składni, możemy przejść do rozwiązywania naszych łamigłówek, a znajomość języka programowania nie stanowi żadnej bariery.
Zadania na kółku stanowią spore wyzwanie i są dużo trudniejsze od zadań wykonywanych na lekcjach informatyki. Dlatego też, koło zrzesza ludzi lubiących wymagające zagadki, chcących się rozwijać i systematycznie dążących do obranych przez siebie celów. Jeżeli celujesz wysoko, dołącz do nas 🙂

Algorytmika a pisanie zwykłych aplikacji

Przy robieniu zadań z algorytmiki jest rozwiązywany jeden zasadniczy problem. Rozwiązanie piszesz w formie aplikacji konsolowej: program wczytuje dane z wejścia (np. klawiatury), przeprowadza obliczenia i wypisuje wynik. Programy, które będziemy pisać nie posiadają interfejsu graficznego, menu ani nawet swojej ikonki – liczyć się będzie pomysł, algorytm i jego szybka implementacja.

“Tysiącmilowa podróż zaczyna się od pierwszego kroku” – Konfucjusz

Pierwsze zadanie

Wystarczy teorii – czas napisać (i wysłać na serwer) nasze pierwsze zadanie. Jeśli nie robiłeś tego wcześniej – bez obaw, wszystko opiszemy krok po kroku.
Rozwiążemy rozgrzewkowe zadanie Wojtek i jego tata I na serwisie Codeforces (CF).

Jeśli nigdy wcześniej nie byłeś CF, oto co należy zrobić:

  1. Otwórz stronę www.codeforces.com.
  2. Utwórz nowe konto klikając Register.
  3. Dołącz do grupy naszego koła wybierając typ członkostwa Participant.
  4. Kliknij w zakładkę CONTESTS (pod głównym menu).
  5. Wybierz contest Rozgrzewka – semestr letni 16/17.
  6. Otwórz zadanie Wojtek i jego tata I

Przeczytajmy uważnie polecenie. W zadaniu proszą nas, by wczytać liczbę n i wypisać sumę wszystkich liczb od 1 do n. Nie wydaje się trudne, prawda? Rozwiążmy je najprościej jak się da.

Wyjaśnienie wszystkich instrukcji znajdziesz w tym wpisie.

“Błąd jest przywilejem filozofów, tylko głupcy nie mylą się nigdy” – Sokrates

Testowanie rozwiązania

Skompiluj i uruchom program. Zanim go wyślesz do sprawdzenia koniecznie przetestuj go na testach przykładowych i sprawdź, czy zwraca dobry wynik. Wprowadź jeszcze kilka swoich testów (np. z większymi liczbami). Jeśli upewniłeś się, że wszystko jest ok, możemy wysłać rozwiązanie na sprawdzarkę.

Wysyłanie rozwiązanie na sprawdzarkę

Wybieramy nasz plik z rozszerzeniem .cpp (czyli ten w którym jest kod). Szukamy okienka Submit. Wybieramy odpowiedni kompilator: najczęściej będzie to G++. Jeśli mamy do wyboru kilka wersji, wybieramy najświeższą (np. G++14 – 14 oznacza 2014 rok). Przesyłamy plik.

Werdykt serwera

Zostałeś przeniesiony do listy z twoimi submitami (próbami rozwiązań). Po chwili powinieneś zobaczyć ostateczny werdykt. Accepted – oznacza, że na wszystkich testach kod zwrócił dobre odpowiedzi.

Gratulacje, właśnie rozwiązałeś swoje pierwsze zadanie!

… ale czy na pewno optymalnie? Przejdźmy teraz do drugiego zadania “Wojtek i jego tata I i pół”

Spróbuj przesłać ponownie swój kod do zadania. Czy twój program przekracza limit czasu? Jeśli tak, to nie martw się, zaraz wszystko się wyjaśni. Porównajmy treści obu zadań. Różnią się one tylko w jednym miejscu: w Inpucie.

“Wojtek i jego tata I”: Jedna liczba całkowita n (1 ≤ n ≤ 50 000)

“Wojtek i jego tata I i pół”: Jedna liczba całkowita n (1 ≤ n ≤ 1 000 000 000)

Na czym polega twoje rozwiązanie? W pierwszym zadaniu dodajesz po kolei wszystkie liczby od 1 do 50 000, tzn. 1+2+3+4+…+50 000. W drugim zaś próbujesz dodać znacznie więcej liczb: od 1 do 1 000 000 000, tzn. 1+2+3+4+5+…+1 000 000 000. Komputer wykonuje ok. 100 milionów operacji na sekundę. W pierwszym zadaniu wykonujesz tylko 50 tysięcy dodawań, dlatego też twoje rozwiązanie może przejść testy. W drugim zadaniu twoje rozwiązanie będzie za wolne (limit to 1 sekunda a potrzebujemy ok. dziesięciu). Jak zatem przyspieszyć twój program? Dokonajmy pewnych obserwacji.

Zauważmy, że mamy do czynienia z ciągiem arytmetycznym od 1 do n:

1, 2, 3, 4, … n

Wojtek liczy sumę wszystkich liczb ciągu, a więc jest to suma ciągu arytmetycznego. Sumę ciągu arytmetycznego liczymy ze wzoru:

Sn=(a1+an)⋅n / 2

Dzięki zastosowaniu tego wzoru zawsze będziemy wykonywać tylko 3 operacje, niezależnie od wielkości liczby n: jedna operacja dodawania, jedna operacja mnożenia i jedna operacja dzielenia, w przeciwieństwie do poprzedniego rozwiązania, w którym wykonywaliśmy n-1 operacji dodawania.

UWAGA!

Co się stanie, gdy Sn=(1+8)⋅8 / 2?

Najpierw wykonujemy dodawanie i uzyskujemy 9. Jeżeli teraz 9 podzielilibyśmy przez 2, to uzyskalibyśmy 4 (gdy zmienna jest typu całkowitego, tj. int, long, long long), nie zaś 4,5. Dlatego ważne jest, aby uzyskaną sumę najpierw pomnożyć przez n, a potem podzielić przez 2.

Cały program wygląda następująco:

Wydaje się być wszystko dobrze. Spróbujmy wysłać teraz nasz program na sprawdzarkę. Czy otrzymałeś Wrong Answer na jednym z dalszych testów? Nasza liczba n zawiera się w przedziale od 1 do miliarda i jest typu int. Zmienna typu int może przyjmować wartości: od -2*10^9 do 2*10^9.  Wydaje się być wszystko dobrze, gdyż najmniejsza i największa wartość zmiennej n zawierają się w tym przedziale. Problemem jest inna liczba znajdująca się w programie: (n+1)*n/2. Jaką największą i najmniejszą wartość może przyjmować ta liczba? Najmniejszą uzyskamy, gdy n = 1, czyli (1+1)*1/2. Największą wartość uzyskamy, gdy n = 10^9,
czyli (1+10^9)*10^9/2, tj. szacunkowo 10^18. O ile pierwsza z wartości może być intem, to druga już nie, gdyż 10^18 >  2*10^9. Musimy zatem użyć typu o większej pojemności – long long.

Program po zmianie wygląda następująco:

Lekcja na przyszłość

Przed przesłaniem kodu na serwer zawsze warto go przetestować dla największych liczb, aby upewnić się, że użyte typy danych są wystarczające.

Gratulacje, właśnie rozwiązałeś drugie zadanie!

Jak napisać i skompilować kod w terminalu?

Do pisania kodu używa się edytorów tekstu, takich jak: Codeblocks czy DevC++. Można z ich poziomu kompilować i odpalać kod, ale jest dużo lepszy sposób:

http://home.agh.edu.pl/~danpoc/dydaktyka/Kompilator%20MinGW.pdf

UWAGA!

W tutorialu podana jest kompilacja programu w języku C. Aby skompilować program w języku C++ należy zmienić dwie rzeczy: rozszerzenie pliku z .c na .cpp oraz gcc na g++.

Jak szybko testować rozwiązania?

Tworzymy plik tekstowy w tym samym folderze, co plik z kodem. Do pliku tekstowego wklejamy nasze dane o nazwie test z rozszerzeniem .txt (np. test.txt). Kompilujemy nasz program wyżej wymienioną metodą. Po skompilowaniu powstaje plik wykonywalny (executable): nazwa_pliku.exe

czyli coś, co możemy odpalić. W konsoli przechodzimy do folderu z kodem i wpisujemy: nazwa_pliku.exe < test.txt

i naciskamy enter. Linijka ta sprawi, że nasz program wczyta dane wejściowe z pliku tekstowego tak jak byśmy wpisywali je ręcznie. Jest to o tyle wygodne, że gdy znajdziemy błąd w naszym kodzie i skompilujemy program jeszcze raz, to wystarczy wrócić do terminala, wcisnąć strzałkę w górę (powrót do poprzedniej komendy) i nacisnąć enter, by przetestować go jeszcze raz bez mozolnego wpisywania całego testu.

Opis komunikatów serwera

Wbrew pozorom nie zawsze dostaje się Accepted po pierwszym wysłaniu rozwiązania. Niestety, czasem proces walki z błędami trwa dość długo. Tutaj znajdziesz opis najczęstszych komunikatów, gdy twoje rozwiązanie jest niepoprawne razem ze wskazówkami, na co należy zwrócić uwagę.

Zadanie domowe

Spróbuj rozwiązać zadanie Wojtek i jego tata II. Zwróć uwagę na limity na dane wejściowe.