Polska XXVIII Olimpiada Informatyczna
O olimpiadzie
Tej jesieni odbyła się kolejna edycja Olimpiady Informatycznej. Jak co roku uczestnicy zmagali się z zadaniami polegającymi na napisaniu programów rozwiązujących pewne problemy algorytmiczne. Pierwszy etap składa się z pięciu zadań, na których rozwiązanie uczestnicy mają około miesiąc. Pozwala to na dokładną analizę problemów, ich implementację i przetestowanie. W polskiej olimpiadzie wyniki są publikowane dopiero po zakończeniu pierwszego etapu, dlatego przetestowanie rozwiązań we własnym zakresie jest niezbędne by przejść dalej w zawodach.
Od kilku lat na olimpiadzie zadania można rozwiązywać używając języka Python. Jednak doświadczeni zawodnicy od zawsze faworyzują C++, gdyż idealnie nadaje się do zawodów programistycznych. Dzięki temu, że jest to język niskiego poziomu, można bardzo precyzyjnie zakodować wszystkie kroki algorytmu, zaś biblioteka standardowa pozwala skupić się na samej implementacji bez powtarzania powszechnych algorytmów. W tym artykule chciałbym sprawdzić czy Python jest rozsądnym wyborem w pierwszym etapie olimpiady.
Moje rozwiązania bazują na algorytmach opisanych w omówieniu zadań, które można znaleźć w serwisie YouTube. Niestety często dla sam opis algorytmu nie jest wystarczający do jego implementacji, gdyż należy wziąć pod uwagę architekturę sprzętu i specyfikę języka. Inaczej pomysł rozwiązana będzie zapisany w C++, a inaczej w języku Python, Kotlin czy Haskell, mimo że koncepcja jest dokładnie taka sama.
TL;DR
Rozwiązania znajdują się w tym repozytorium.
Cukiernia
Pierwsze zadanie polegało na tym by dla zadanej macierzy n x 3 wybrać jeden element w każdym wierszu tak by całkowity koszt był możliwie najmniejszy. Koszt został zdefiniowany jako suma niewybranych elementów. Z tym zastrzeżeniem, że dla każdej kolumny, która nie zwiera samych zer, musi zostać wybrany jeden element, tak aby każde dwa wybrane elementy pochodziły z różnych wierszy. Ostatnie zdanie znacząco utrudnia całe zadanie, jednak tak zdefiniowane treść już trochę bardziej ułatwia jego rozwiązywanie. Jeżeli mamy do wyboru 3 wartości, możemy przeiterować się przez wszystkie kombinacje i wybrać taką, której koszt jest najmniejszy. Niestety takie rozwiązanie działa w czasie O(n³) i na pewno da się to zrobić szybciej. Kolejny pomysł polega na wyborze największych wartości z każdej kolumny. Jeśli je wybierzemy, to nie będą wliczone w całkowity koszt i możliwe, że da to optymalny wynik. Tylko musielibyśmy wtedy rozwiązywać remisy pomiędzy maksymalnymi wartościami w kolumnach, które mogą powodować inne konflikty, ponieważ wybrane wartości nie mogą pochodzić z tego samego wiersza. Na tym etapie można zauważyć że rozwiązanie ma szansę działać w czasie O(n ㏒ n) jeżeli to podejście by zadziałało. Do poprawnego rozwiązania jest już całkiem niedaleko. Zamiast wybierać największe wartości musimy wybrać z każdej kolumny te wartości, których wybór będzie najbardziej minimalizował całkowity koszt, czyli takie których różnica z maksymalną wartością w wierszu będzie najmniejsza. Następne spostrzeżenie polega na tym, że możemy wybierać kilka minimalnych wartości w czasie O(n) za pomocą np. kopca. Kilka, czyli dokładnie 3 takie wartości. Tylko tyle wartości potrzeba żeby rozwiązać wszystkie konflikty, ponieważ liczba kolumn jest stała i równa 3. Ostatecznie rozwiązanie działa w czasie O(n).
Sama implementacja w Pythonie wydaje mi się bardzo czytelna, a za pomocą funkcji z biblioteki standartowej takich jak itertools.product() heapq.nsmallest() możemy zaoszczędzić kilka linijek kodu.
Licznik długu
Kolejne zadanie polegało na dodawaniu dwóch dużych liczb, które zostały podane na wejście programu. Dokładniej mamy podawać cyfrę na pewnej pozycji sumy dwóch liczb. Dodatkowo cyfry składników sumy mogą być zmieniane w pomiędzy zapytaniami.
Takie zadanie można rozwiązać poprzez zwykłe dodawanie liczb w słupku. Dla liczb długości n i liczbie z zapytań rozwiązanie działa ze złożonością O(n∙z). Niestety takie proste rozwiązanie jest dosyć wolne, ponieważ po każdej zmianie musimy na nowo dodać wszystkie kolumny. Lepszym pomyłem byłoby zwiększenie liczby cyfr w pojedynczej kolumnie i dodawanie cyfr grupami. Dzięki temu gdy sumujemy liczby w słupku, procesor jest w stanie szybciej dodać składniki sumy. Na przykład dodając 20081086 + 15071410, zamiast dodawać po kolei 6 + 0 = 6, 8 + 1 = 9 itd. możemy dodawać cztery kolumny jednocześnie 1086 + 1410 = 2496 oraz 2008 +1507 = 3515, co daje 35152496. Oczywiście trzeba wtedy pamiętać o poprawnym obsłużeniu przeniesienia z poprzedniej kolumny. Grupowanie w dodawaniu u słupku gdy robimy to ręcznie nie daje żadnych korzyści, bo i tak musimy “po ludzku” dodać liczby po kolei. Jednakże dla komputera dodawanie dwóch liczb zawsze trwa tylko samo czasu i nie ma znaczenia czy dodajemy liczby jedno cyfrowe czy 4-cyfrowe kolumny. Komputer musi poświęcić tyle samo cykli na wykonanie operacji o ile liczby mieszczą się w jednym słowie procesora.
Taki zabieg pozwala przyśpieszyć sumowanie 4-krotnie. Możemy zwiększyć szerokość kolumn co jeszcze bardziej przyśpieszy działanie. Niestety, aby się mieścić w jednym słowie procesora maksymalnie możemy użyć kolumn o szerokości 18 cyfr, gdyż większe liczby nie zmieszczą się w typie unsigned long long, ponieważ ㏒₁₀(2⁶⁴) ≈ 19,2. Zmiana cyfr pomiędzy zapytaniami nie jest też skomplikowana, gdyż wystarczy obliczyć kolumnę, w której znajduje się cyfra, a następnie ją podmienić za pomocą działań modulo. Jeżeli dodatkowo zamiast obliczać wszystkie kolumny sumy, będziemy obliczać ją do kolumny, której dotyczy zapytanie, algorytm przyśpieszy jeszcze bardziej, oczywiście w optymistycznym przypadku. Program nadal działa w czasie O(n∙z) jednak ze znacznie niższą stałą.
Drugi sposób polega na tym, aby w dodatkowej tablicy przechowywać sumy kolumn, które mogą być większe niż 9. W tej wersji nie będziemy propagować przeniesienia.
Załóżmy, że zapytanie dotyczy cyfry na i-tej pozycji sumy. W tym rozwiązaniu należy utrzymywać strukturę, która pozwoli nam wyszukać pierwszą cyfrę, która nie jest dziewiątką na prawo od pozycji i. Jeżeli liczba na wyszukanej pozycji jest ≤ 8 to nie będzie występowało przeniesienie i możemy wypisać cyfrę sumy bezpośrednio na pozycji i-tej. W innym przypadku nastąpi przeniesienie więc musimy dodać 1 do zwracanego wyniku. Na końcu musimy podzielić wynik modulo 10, aby uzyskać cyfrę na tej pozycji. Na przykład dodając 20081086 + 15071410 zapisujemy w tablicy sumy kolejne wartości [3, 5, 0, 15, 2, 4, 9, 6].
Indeksując od zera od lewej, dla zapytania o cyfrę na pozycji 0 powinniśmy zwrócić cyfrę 3. Dla pozycji 5 z wartością 4 wyszukujemy następną pozycję cyfry, która nie jest dziewiątką na prawo, czyli pozycję 7, na której wartość sumy wynosi 6, wiec wypisujemy 4 nie dodając jedynki, ponieważ nie występuje przeniesienie. Gdyby na pozycji 7 znajdowała się liczba większa niż 9, czyli np 14, zwrócilibyśmy 5, bo 4 + 1 % 10 = 5.
W języku C++ możemy użyć struktury std::set, która pozwala przeprowadzić wyszukiwanie za pomocą funkcji upper_bound() w czasie O(㏒(n)). Niestety Python używa zbiorów opartych o hashset, a nie drzew tak jak C++, dlatego trzeba samemu zaimplementować treeset lub tak jak ja wykorzystać w rozwiązaniu drzewo przedziałowe. Działa ono w tym samym czasie co set, czyli w O(㏒(n)) i jest dużo łatwiejsze w implementacji. Ostatecznie otrzymujemy złożoność O(z ㏒(n)).
Oczywiście można by połączyć oba rozwiązania :)
W samej implementacji Python okazał się mało użyteczny, ponieważ nie posiada w bibliotece standartowej struktur drzewiastych i trzeba samemu ją zaimplementować lub zakodować drzewo przedziałowe.
Tablica Binarna
W tym zadaniu operujemy na tablicy binarnej n×m, w której wraz z kolejnymi zapytaniami musimy odwracać komórki wewnątrz prostokątów o podanych współrzędnych. Po każdym zapytaniu musimy podać liczbę operacji prostych, która pozwoli wyzerować całą tablicę. Operacją prostą nazywamy zapytanie, w którym prostokąt posiada lewy góry narożnik w lewym górnym narożniku tablicy.
Najprostsze rozwiązanie polegałoby na zaalokowaniu tablicy, a następnie odwracanie po kolei wszystkich komórek należących do prostokąta.
Zacznijmy od oszacowania maksymalnej złożoności działania algorytmu na jaką możemy sobie pozwolić. Pomiar czasu jest estymowany za pomocą modelu procesora o częstotliwości 2GHz. To zadanie posiada dopuszczalny czas wykonania równy 6 sekund. To oznacza że rozwiązanie wzorcowe powinno wykonać się w 3 sekundy, aby uzyskać maksymalną liczbę punktów. Czyli maksymalnie możemy wykonać ±3∙10⁹ operacji. Maksymalny rozmiar tablicy to 1000×1000. Liczba zapytań q jest w zakresie <1; 10⁵>.
Dla przykładowo policzmy, czy najprostsze rozwiązanie zdąży się wykonać zanim dostaniemy TLE. Zaalokujmy tablicę n×m, a następnie dla każdego zapytania odwracajmy po kolei wszystkie komórki należące do prostokąta. Póki co wychodzi O(qnm), co będzie trwać około 5∙10⁷, a to dopiero połowa zadania. Gdybyśmy mogli obsłużyć pojedyncze zapytanie w czasie O(n∙㏒(m)) i tym samym mielibyśmy rozwiązanie ze złożonością O(q∙n∙㏒(m)) to powinniśmy zmieścić się w przewidzianym czasie. Można by spróbować użyć n drzew przedziałowych i prawdopodobnie takie rozwiązanie sprawdziłoby się gdybyśmy mieli po każdym zapytaniu odpowiedzieć ile komórek w tablicy jest odwróconych. Ale musimy wciąż odpowiedzieć na pytanie ile potrzeba operacji prostych, aby wyczyścić tablicę…
Kolejny pomysł polega na trzymaniu współrzędnych prostokątów w strukturze danych, która pozwoli szybko odpowiadać na pytania czy dane dwa prostokąty przecinają się np. implementując R-drzewo. Dzięki temu moglibyśmy ciąć nakładające się prostokąty i działać na powierzchniach zamiast na pojedynczych komórkach. Dla dużych prostokątów takie podejście dałoby duże zyski, ale powstaje wtedy problem, gdy pozostałe prostokąty są bardzo małe, wtedy utrzymanie drzewa staje się nieopłacalne. A to właśnie takich testów możemy się spodziewać w trzecim podzadaniu.
Podsumowując, czujemy że nie należy symulować czyszczenia tablicy, ponieważ nawet gdybyśmy umieli obsłużyć zapytanie w czasie O(1), to dla np. testu układającego prostokąty we wzór szachownicy potrzebowalibyśmy ½nm operacji, aby odpowiedzieć na jedno zapytanie, a to zdecydowanie za wolno.
Czyli liczba operacji prostych powinna wynikać z aktualnego stanu tablicy. Analizując dokładnie operacje na tablicy, można zauważyć że dwa prostokąty przylegające do siebie krawędzią tworzą jeden prostokąt. Dlatego można by zaznaczyć tylko brzeg prostokąta zamiast wszystkich należących do niego komórek. Albo jeszcze lepiej byłoby zaznaczać tylko jego narożniki.
To pozwoliłoby na zmianę stanu tablicy w czasie stałym. Musielibyśmy tylko zapisywać liczbę potrzebnych operacji w zależności od stanu. Po dłuższych badaniach i głębszej analizie okazuje się, że za każdym razem gdy zmienimy narożnik w tablicy z niezaznaczonego na zaznaczony, liczba prostych operacji potrzebnych do wyzerowania tablicy wzrasta o jeden, zaś gdy zmieniamy zaznaczony na niezaznaczony, ta wartość maleje o 1. Na końcu, jeśli przestawimy dowolną operacją za pomocą czterech operacji prostych to otrzymamy rozwiazanie działające w czasie O(q).
Zadanie było trudne koncepcyjnie, trzeba było zauważyć wiele przesłanek, zaś sama implementacja okazała się bardzo prosta, dlatego rozwiązanie go w Pythonie nie było trudne.
Gra Planszowa
Kolejne zadanie wykorzystywało algorytmy grafowe i polegało na obliczeniu liczby skoków potrzebnych do przejścia pewnej planszy gry platformowej. Zaczynając na lewym skraju planszy możemy iść w prawo, spaść przez dziurę na platformę niżej, przeskoczyć dziurę w prawo, bądź wskoczyć przez dziurę na platformę wyżej. Przykładowa plansza wygląda w następujący sposób.
Jest na niej zaznaczona ścieżka zaczynająca się na trzeciej platformie i wymaga ona zrobienia jednego skoku. Planszę możemy przedstawić w postaci ważonego grafu skierowanego:
Na wejściu programu otrzymujemy pozycje dziur dla kolejnych platform w kolejności posortowanej, dlatego możemy skompresować graf, pomijając większość krawędzi o wadze 0. Podczas wczytywania należy zapisać pozycje dziur do tablicy oraz zapamiętywać tablicę z pozycjami dziur z poprzedniej platformy. Będziemy starać się ponumerować każdy ciągły odcinek platformy oraz poprawnie je połączyć. Za pomocą dwóch iteratorów możemy wybierać kolejną bliższą lewej strony dziurę z dwóch tablic, podobnie do metody w drugim etapie algorytmu sortowania przez scalanie. Jeżeli dziura pochodzi z poprzedniej platformy, musimy poprowadzić nową krawędź o wadze 1 do platformy znajdującej się za dziurą oraz krawędź o wadze 0 z platformy leżącej przed dziurą do aktualnej platformy. W przeciwnym przypadku dziura leży na aktualnej platformie i należy no niej poprowadzić krawędź o wadze 1, a następnie zaktualizować indeks nowego odcinka. Skompresowany graf powinien wyglądać w następujący sposób:
W ten sposób maksymalnie ograniczamy liczbę krawędzi i wierzchołków, a samo budowanie grafu dla dwóch tablic z dziurami o długościach n i m jesteśmy w stanie wykonać w czasie O(n+m). Zadanie precyzuje, że dziur jest nie więcej niż 2000000, więc budowanie grafu powinno zając maksymalnie 1 sekundę.
Kolejnym krokiem jest zauważenie, że zamiast uruchamiać algorytm Dijsktry dla każdego zapytania możemy odwrócić graf i dodać jeden “wirtualny” wierzchołek, który będzie połączony z każdym skrajnie prawymi wierzchołkami platform:
Dzięki temu gdy uruchomimy algorytm Dijkstry z wierzchołka “wirtualnego” odległości każdego skrajnie lewego wierzchołka będą odpowiadały odległości tego wierzchołka do prawej strony planszy.
Ostatnim ulepszeniem całego algorytmu jest wykorzystanie algorytmu 0–1 BFS, który da nam ten sam wynik co algorytm Dijkstra. Z tą różnicą, że nie będziemy musieli utrzymywać kolejki priorytetowej przechowującej odległości do nieodwiedzonych wierzchołków. Zamiast tego będzie wystarczyła dwukierunkowa kolejka (deque) co znacząco przyśpieszy działanie całego programu.
Wzorcowe rozwiązanie wymagało płynności w posługiwaniu się algorytmami grafowymi i transformacjami grafów. Przydatna była znajomość wariantu algorytmu BFS dla grafu o wagach 0 i 1. Rozwiązanie w Pythonie nie różni się od rozwiązania w C++, jednak ponieważ algorytm był dosyć skomplikowany, dużo łatwiej było go debugować w Pythonie.
Niestety rozwiązanie w Pythonie nie zdobyło maksymalnej liczby punktów.
Gang Biciaków
Ostatnie zadanie należało do najtrudniejszych w tym etapie. Należało w nim dla podanej struktury drzewa odpowiadać na zapytania o liczbę unikalnych liczb leżących na krawędziach w ścieżce pomiędzy korzeniem, a wybranych wierzchołkiem. Dodatkowo liczby na krawędziach mogły się zmieniać pomiędzy zapytaniami.
Jest to zadanie do którego trudno się zabrać bez znajomości konkretnego algorytmu adresującego ten problem. Oczywiście można przechowywać stan wszystkich krawędzi i dla każdego zapytania iść w stronę korzenia i zliczać unikalne liczby. Jednak takie rozwiązanie jest zbyt wolne.
Pierwsze spostrzeżenie polega na tym, że jeżeli dłuższa ścieżka A zawiera krótszą ścieżkę B, to możemy wykorzystać odpowiedź dla ścieżki B, aby sprawniej odpowiedzieć na zapytanie dla ścieżki A.
Zauważenie tej zależności nie było trudne, problem sprawiało wykorzystanie tego spostrzeżenia. Jeżeli zadanie nie wymagałoby zmian na krawędziach wystarczyłoby zaimplementować algorytm DFS, a następnie zbierać napotkanie liczby na krawędziach w multiset’cie. Nowa liczba z krawędzi byłaby dodawana do zbioru przy wchodzeniu do wierzchołka i usuwana po przetworzeniu wszystkich jego potomków. Dla każdego wierzchołka moglibyśmy w ten sposób określić i zapisać liczebność utrzymywanego zbioru, co pozwoliłoby na odpowiedź dla każdego zapytania w czasie stałym. Ale musimy jeszcze obsłużyć zmiany na krawędziach. Należy zastanowić się, czy moglibyśmy dla ustalonej i przetworzonej już ścieżki wraz z odpowiadającemu jej zbiorowi napotkanych na krawędziach liczb, dokonać zmiany liczby na konkretnej krawędzi, tak żeby stan zbioru odpowiadał stanowi po zmianie liczby na krawędzi? Żeby uzyskać taki efekt musielibyśmy usunąć ze zbioru liczbę, która znajduje się aktualnie na odwiedzonej krawędzi, dodać do zbioru liczbę, która ma się znajdować na krawędzi po zmianie oraz zaktualizować zapamiętaną zawartość krawędzi. Jeżeli zmiana dotyczy krawędzi, która nie znajduje się na odwiedzonej ścieżce to wystarczy tylko zaktualizować zapamiętaną zawartość krawędzi.
W ten sposób możemy przeprowadzać zmiany dotyczące dwóch wymiarów. Pierwszy wymiar to aktualnie odwiedzony wierzchołek. Drugi dotyczy aktualnego stanu wszystkich krawędzi, który zmienia się w czasie. Czyli możemy określić dane zapytanie za pomocą dwóch współrzędnych v dla wierzchołka oraz t dla czasu i tym samym stanu krawędzi drzewa. Gdybyśmy mogli nie tylko poruszać się zgodnie z kolejnością zapytań, ale w dowolnej kolejności, możliwe że bylibyśmy w stanie uszeregować je w taki sposób, aby maksymalnie wykorzystać nasze spostrzeżenie. Ze zmianą liczby na krawędzi nie będzie większego problemu. Podczas wczytywania zapytań ze zmianami liczb na krawędziach wystarczy, oprócz zapamiętywania numeru krawędzi oraz nowej liczby, zapisać także poprzednią wartość oraz aktualizować na bierząco zapisany stan krawędzi. Dzięki temu zawsze będziemy mieli zapisaną poprzednią i następną liczbę. Tym samym będziemy w stanie bez problemu odwrócić zmianę na danej krawędzi. Trudniej jest poruszać się pomiędzy zapytaniami w wymiarze wierzchołków. Idąc zgodnie z kolejnością DFS iterujemy się po wszystkich potomkach wierzchołka i po powrocie wznawiamy przeglądanie potomków w miejscu, w którym skończyliśmy. Moglibyśmy zasymulować przechowywanie tego stanu implementując wersję iteracyjną algorytmu, jednak wciąż poruszanie się naprzeciw kolejności DFS będzie bardzo skomplikowane. Zamiast tego możemy przejść po drzewie za pomocą algorytmu DFS i zapisać kolejno w tablicy dfsOrder[] numer wierzchołka za każdym razem gdy do niego wchodzimy i gdy z niego wychodzimy. Dodatkowo dla każdego wierzchołka w tablicy preorder[] możemy zapisać moment, w którym odwiedzamy go po raz pierwszy:
Mając przygotowane takie dwie tablice, możemy określić nasze położenie w wymiarze v za pomocą zmiennej dfsStage, która odpowiada za aktualny indeks w tablicy dfsOrder[]. Zanim zaczniemy przetwarzać zapytania algorytm DFS znajduje się w korzeniu drzewa, odpowiada to indeksowi 0 w tablicy, czyli zmienna dfsStage=0. Na przykład, gdy napotkamy zapytanie o wierzchołek 5 możemy spojrzeć w tablicy preoreder[] ile kroków algorytmu DFS musielibyśmy wykonać, aby algorytm DFS do niego “dotarł”. Dla powyższego przykładu preorder[5] = 6. Oznacza to, że musimy inkrementować dfsStage sześciokrotnie, za każdym przetwarzając po drodze wierzchołki na indeksach 1..6 z tablicy dfsOrder. Jeżeli kolejny wierzchołek nie znajduje się w aktualnej ścieżce, musimy dodać go do ścieżki oraz dodać liczbę, która znajduje się na krawędzi do zbioru napotkanych liczb. Jeżeli wierzchołek znajduje się w odwiedzonej ścieżce oznacza że odwiedzamy go już drugi raz i musimy usunąć go z aktualnej ścieżki oraz usunąć liczbę, która znajduje się na krawędzi łączącej wierzchołek i jego rodzica. Teraz jesteśmy w stanie nie tylko poruszać się zgodnie z kolejnością dfsOrder, ale także w przeciwnym kierunku!
To jednak nie jest rozwiązanie wzorcowe. Okazuje się, że kolejność zapytań na wejściu jest losowa i możemy je uszeregować dużo lepiej.
Na szczęście nie musimy implementować problemu komiwojażera, żeby znaleźć najkrótszą ścieżkę. Znalezienie jej zajęło by cenny czas, który musimy poświęcić na przemieszanie się pomiędzy zapytaniami. Bez przeprowadzania głębszego dowodu najlepsze uszeregowanie zapytań daje posortowanie je według pary (⌊t / √z⌋, preorder[v]), gdzie z to liczba wszystkich zapytań, zaś v to numer wierzchołka, którego dotyczy zapytanie. Musimy użyć preorder[v], zamiast v ponieważ chcemy wykorzystać kolejność odwiedzania ich zgodnie z algorytmem DFS, zamiast numerowania z wejścia programu który jest losowy. Wtedy odwiedzenie kolejnego wierzchołka będzie wymagało jak najmniejszej liczby operacji w przestrzeni v i tym samym ścieżki będą miały najwięcej części wspólnych. Kolejność ta odpowiada idei uszeregowania zapytań w algorytmie Mo¹.
Zadanie było dość skomplikowane. Na początku zaimplementowałem je w Pythonie. Nie zdobyło maksymalnej liczby punktów, więc powtórzyłem implementację w języku C++. Samo użycie C++ nakierowało mnie na mnóstwo optymalizacji. Używanie tego języka sprawia że programista stara się pisać optymalnie, że “myśli” optymalniej. Porównałbym to do mówienia w innym języku i gdy chcemy przekazać jakieś zadanie i używamy innej składni oraz zwrotów, czasem oszczędniejszych mimo że przekaz jest ten sam.
Niestety rozwiązanie w Pythonie nie zdobyło maksymalnej liczby punktów.
Wnioski
Rozwiązania zostały uruchomione na stronie szkopul.edu.pl. Pozwoliło to zweryfikować poprawność i czas działania implementacji. Aż 3 zadania udało się rozwiązać z maksymalną liczbą punktów przy implementacji w języku Python 🎉.
Aby dostać się do drugiego etapu trzeba było zdobyć 200 punktów. Zatem rozwiązania w Pythonie pozwoliłyby na to z dużym zapasem. Jednakże spodziewałem się że rozwiązania wzorcowe zdobędą 500 punktów niezależnie od użytego języka. Widać także, iż limity czasowe są dobrane z ogromnym zapasem. Na przykład dla zadania gan najdłuższej wykonujące się rozwiązanie w języku C++ działa w czasie 2.05s, przy limicie wynoszącym aż 12.00s. Jednak w tym samym teście rozwiązanie w Pythonie zostaje przerwane przez TLE. Czyli Python w tym zadaniu musi być ponad 6 razy wolniejszy.
Poniżej zamieściłem tabelę z czasami wykonania zadań. W zadaniu cuk o złożoności O(n) lwią część czasu zajmuje zbudowanie kopca, które nie jest przez nas zaimplementowane w Pythonie tylko pochodzi ze standardowej biblioteki. Działa tak samo szybko jak w C++. Podobnie w zadaniu tab o złożoności O(q) kod jest bardzo prosty i Python dorównuje wydajnością do C++. W zadaniu lic ze złożonością O(z ㏒(n)) Python wypada zaledwie 3x gorzej, więc drzewo przedziałowe działa nieco wolniej niż std::set z C++. Pomysł ze zwiększeniem szerokości kolumn wypada niestety aż 10 razy wolniej i to przy implementacji w C++. Zadanie gra ma złożoność O(n+K+z) i Python wypada w nim dwa razy wolniej. Całe jest dość złożone i nawet rozwiązania w C++ zajmują kilka sekund, więc dwukrotne spowolnienie programu uniemożliwia zdobycie pełnej liczby punktów. Ostatnie zadanie gan ma złożoność O(n√n) i tutaj Python wypada najmniej korzystnie bo aż 20 razy wolniej.
Widać zależność, w której im więcej kodu faktycznie wykonuje się w Pythonie, a nie w standardowej bibliotece oraz im większa jest złożoność czasowa problemu, tym różnice w czasie są większe.
Istnieją także benchmarki² porównujące wydajność języków, w których Python jest od 2 do nawet 150 razy wolniejszy od C++ zależnie od typu zadania.
Powyższe testy wykonałem na moim komputerze, ponieważ dodałem kilka dużych testów w zadaniu lic, aby uwypuklić różnice. Co do testowania na szkopuł, nie jestem pewien czy środowisko serwisu jest dokładnie takie samo jak to używane podczas zawodów. Implementacja zadania licznik długu w wersji ze zmianą podstawy systemu liczbowego zdobyła maksymalną liczbę punktów, podczas gdy na szkopuł ten sam kod przekracza dozwolony czas w dwóch ostatnich testach. Możliwe też że zadania są uruchamiane na nieco innych testach.
Podsumowując, Python ułatwia pisanie kodu i sprawdzanie różnych koncepcji. Świetnie nadaje się do prototypowania i pisania rozwiązań Brute Force, gdy nie jest ważny czas wykonania. Jednak końcowe programy, uważam że warto byłoby przepisać na C++. Można wtedy maksymalnie wykorzystać dostępny czas, ponieważ jeżeli nie odkryliśmy wzorcowego algorytmu, na pewno możemy zdobyć więcej punktów.
