Żaden szanujący się konkurs algorytmiczny, nie odbywa się bez dnia próbnego (albo chociaż sesji próbnej). Dzień próbny jest potrzebny organizatorom, aby upewnić się, że wszystko zostało dopięte na ostatni guzik. Działa sprawdzaczka, zadania zostały odpowiednio załadowane, komputery zostały odpowiednio przygotowane i tak dalej. Dzień próbny jest również istotny dla zawodników, aby mogli się zapoznać ze środowiskiem na jakim będą pracować. Choć zawodnicy często wykorzystują ten dzień, aby rozwiązać proste zadanie (w czym nie ma nic złego), można ten czas wykorzystać dużo bardziej efektywnie. Co za tym należy zrobić w dniu próbnym?
Co jest na komputerze?
Jeśli na konkursie, organizator dostarcza sprzęt, dobrze sprawdzić co na takim komputerze jest i co na tym komputerze być powinno. Oto krótka checklista rzeczy, które warto sprawdzić:
- Kompilator 😉
- Edytor tekstu
- Debugger
- Dokumentacja języka C++ / STLa
- Inne aplikacje z których korzystasz (diff, time)
Przed zawodami warto zapoznać się z regulaminem zawodów oraz ustaleniami technicznymi. Powinno się w nich znajdować lista wszystkich aplikacji, która powinna się znajdować na komputerze. Jeśli na komputerze nie ma czegoś, co powinno się na nim znaleźć, należy o tym poinformować organizatorów. Jeśli nie ma naszego ulubionego edytora, możemy poprosić organizatorów o zainstalowanie go (aczkolwiek jeśli nie ma go w regulaminie, to organizator ma prawo odmówić).
Warto zwłaszcza sprawdzić wersję kompilatora i upewnić się, że to ta sama wersja używana przez sprawdzaczkę (wersja kompilatora powinna znajdować się w ustaleniach technicznych).
Czasami można również poprosić organizatorów o wymianę sprzętu. Na przykład jeśli monitor nie działa, można poprosić o wymianę go na inny. Możemy również poprosić o wymianę klawiatury bądź myszki (na olimpiadzie uczestnik siedzący obok mnie poprosił o wymianę myszki, gdyż nie posiadała ona rolki). Organizatorzy jeśli mają taką możliwość, dostarczą nam nowy sprzęt. Jeśli komputer nie nadaje się do użytku, możemy poprosić o nowe stanowisko.
Sprawdzaczka
Istnieje wiele różnych sprawdzaczek. Każda działa inaczej. Jeśli nie jesteś zapoznany z tą, która jest używana na zawodach (albo chcesz sprawdzić czy nie zaszła w niej jakaś zmiana) powinieneś przetestować w jaki sposób sprawdzaczka działa.
Wiadomo. Jeśli nasz program działa poprawnie – zostanie zaakceptowany. Jeśli działa za długo – otrzyma przekroczenie limitu czasu. Jeśli zwraca błędny wynik – otrzyma błędną odpowiedź. Co jeśli przekroczy limit pamięci? Bo tu sprawa nie jest jasna. Jedna sprawdzaczka powie “przekroczenie limitu pamięci”, inna powie “błąd wykonania”. Jeśli błąd wykonania to sprawdź jakiego typu błąd zwraca sprawdzaczka (jeśli w ogóle). Innym częstym błędem wykonania jest pisanie nie po swojej pamięci oraz dzielenie przez zero. Jeśli sprawdzaczka zwraca numer błędu – sprawdź jakie numery zwraca dla błędów które najczęściej popełniasz.
Zazwyczaj podczas sprawdzania czy odpowiedź zwrócona przez nasz program jest poprawna, sprawdzaczka ignoruje białe znaki. Nie zawsze tak jest. Warto sprawdzić w dniu próbnym czy jeśli wstawimy nadmiarową spację pod koniec linijki to otrzymamy pełne punkty. A co jeśli spację wstawimy na początku linijki? Co jeśli liczby rozdzielimy dwiema spacjami (a nie jedną)? Co jeśli liczby rozdzielimy za pomocą znaku nowej linijki? Czy program wciąż będzie zaakceptowany?
Kompilator (i architektura procesora)
Jeśli nasz program jest poprawnie napisanym programem w języku C++, program powinien działać na każdym kompilatorze (zgodnym ze standardem języka C++) i każdej (sensownej) architekturze. Nikt jednak tak jak zawodnicy nie kocha programować niezgodnie ze standardem języka C++. Lista rzeczy, których zawodnicy używają na zawodach a są niezgodne ze standardem jest naprawdę długa i trudno spisać ją tak, aby niczego nie pominąć. Podejmę jednak próbę.
int T[n];– Variable-length array (VLA) czyli rozmiar tablicy definiowany dopiero po uruchomieniu programu (zmienna n w przykładzie nie jest stałą) a nie w czasie kompilacji. Nie działa na przykład na kompilatorach microsoftu (w chwili pisania artykułu MSVC 19.33)#include<bits/stdc++.h>– Niestandardowa biblioteka kompilatora GCC. Nie występuje w wielu innych kompilatorach.__builtin_clz– Z dokumentacji GCC: GCC provides a large number of built-in functions […]. Some of these are for internal use in the processing of exceptions or variable-length argument lists and are not documented here because they may change from time to time; we do not recommend general use of these functions.__gcd(10,40)– Standard C++17 wprowadził algorytm euklidesa do biblioteki standardowej, ale wielu programistów wciąż jest przyzwyczajonych do używania nieudokumentowanej funkcji, która nie występuje we wszystkich kompilatorach. Żeby było ciekawiej – na niektórych kompilatorach funkcja rzuca wyjątkiem jeśli jej oba argumenty są zerami.__int128– Kilka dodatkowych bajtów przydaje się, gdy potrzebujemy przemnożyć dwa long longi przez siebie (modulo p) lub gdy liczba minimalnie wychodzi nam poza zakres. Niestety nie zawsze możemy liczyć na luksus w postaci zmiennej 128-bitowej.#include <ext/pb_ds/assoc_container.hpp>– Nie występuje we wszystkich kompilatorach.
W używaniu powyższych konstrukcji nie ma nic złego. Jednak warto w dniu próbnym sprawdzić czy takie konstrukcje są akceptowane przez kompilator i mieć plan awaryjny na wypadek gdyby nie były.
