Was tun wenn du absolut davon überzeugt bist, dass dein Program funktioniert, der Grader aber nicht deiner Meinung ist.

Geschrieben von Kevin De Keyser.

Graderspezifisches

Aufgabentypen

Output-only Aufgaben

Diese Aufgaben kennst von der ersten Runde der SOI. Man erhält alle test-cases gleich zu Beginn und muss auf irgend eine Art und Weise die Lösung erhalten und muss schliesslich die Dateien wieder hochladen. Im Gegensatz zur ersten Runde der SOI hast du aber bei Contests wie der CEOI oder der IOI oft die test-cases zu Beginn des Contests und kannst während des ganzen Contests (mit normalerweise 5 Stunden) Zeit um den Output zu schicken.

  • Eine allgemeine Lösung für die gegebenen Limits solcher Aufgaben ist teilweise nicht einmal möglich. Man sollte also unbedingt die Testdaten genauer unter die Lupe nehmen und auf spezielle mathematische Eigenschaften untersuchen. Bei einem Graphenproblem lohnt es sich zum Beispiel zu schauen ob die Testdaten spezielle Graphen sind wie z.B.: Bipartite Graphen, DAG, binäre Graphen, . (Bsp. CEOI 2016 Practice problem, CEOI 2016 task 1)

  • Ab und zu ist sogar eine Testdatei dabei, die man von Hand lösen kann!

  • Der Compiler kann dir bei diesem Aufgabentyp helfen! Mit dem Argument -Ofast können noch kleinere Optimierungen vorgenommen werden. Eine Brute-force Lösung ist auch nicht unbedingt schlecht, da du sie ja 4 Stunden laufen lassen kannst. (Du musst aber realisieren, dass sich die asymptotische Laufzeit dadurch nicht rettet.)

  • Pro Tipp von Johannes Kapfhammer: Man kann sehr viel Zeit bei Output-only Aufgaben verbraten, da teilweise jeder einzelne Testfall einen anderen Algorithmus benötigt und man dafür verhältnismässig nur eine geringe Anzahl Punkte erhält.

  • Um Dateien einzulesen kannst du entweder auf der Kommandozeile: (deinprogram < input.txt) | tee output.txt eingeben oder direkt mithilfe von fstream die Datei einlesen und ausgeben. Dabei kannst du einfach cin und cout folgenderweise überladen:

    ifstream cin("input.txt");
    ofstream cout("output.txt");
    

Batch Aufgaben

Aufgaben von diesem Typ kommen am häufigsten in der SOI / CEOI / IOI vor.

Bei diesem Aufgabentyp sind die Testdaten während des Contests nicht verfügbar und du lädst deinen Source-Code hoch, anstelle des Outputs. Zusätzlich hast du ein Zeitlimit (normalerweise nicht mehr als ein paar wenige Sekunden), ein Speicherlimit, sowie ein Limit der Programgrösse. Das Grading-System läuft ausserdem anders ab. Testdaten (test-cases) formen sogenannte batches (normalerweise 10 batches mit je 10 test-cases). Man kann nur Punkte holen in dem man jeden test-case eines Batches löst. Teilaufgaben (subtasks) weisen dabei auf Batches. Wenn du z.B. 40 Punkte für eine \(O(N^2)\) Lösung erhältst und 60 weitere Punkte für eine \(O(N log N)\) weisst das daraufhin, dass \(4 \cdot 10\) Aufgaben in \(O(N^2)\) und alle Aufgaben in \(O(N log N)\) lösbar sind. Diese Art von Grading ist einzig bei der SOI / CEOI / IOI anzutreffen. Andere Programmierwettbewerbe (wie der Helvetic coding contest, ACM, Codeforces, Codechef, CSAcademy & andere online Seiten) erteilen nur dann Punkte, wenn alle Testdaten gelöst wurden. Um diesen Aufgabentyp etwas zu üben, kannst du auf https://clist.by gehen um aktive Programmierwettbewerbe zu finden.

Interaktive Aufgaben

Diese Aufgaben sind ähnlich wie Batch Aufgaben, nur muss man mehrmals einlesen und ausgeben in der selben Instanz. So kann ein Grader dann auf deine Ausgabe reagieren und einen weitere Eingabe schreiben. Stelle sicher, dass du nach deiner Ausgabe deinen Buffer leerst (verwende entweder std::endl oder std::flush in C++). Diese Aufgaben verwenden normalerweise die längste Zeit zum graden. Beispielsaufgaben sind SOI binary search on island.

Bei der CEOI / IOI können diese Aufgaben teilweise verpackt sein in eine Art Library. Du musst dabei die verschiedenen angegebenen Funktionen implementieren. Beispielsaufgaben hierzu: Scales - IOI 2015, ICC - CEOI 2016

Kreative Aufgaben

Diese Aufgabe ist SOI spezifisch und gibt es nur in der ersten Runde. Hier wird ein Problem vorgestellt, welches man nicht optimal lösen kann (zumindest nicht in der vorgegebenen Zeit). Es ist eine interaktive Aufgabe, bei dem später die Programme der verschiedenen Teilnehmer gegeneinander fechten. Wir empfehlen besonders viel Stil einzubauen, sodass es für die Zuschauer am SOI Tag möglichst unterhaltsam wird.

Theoretische Aufgaben

Diese Aufgaben errinern an Schulprüfungen und finden normalerweise nur in der ersten und zweiten Runde der SOI statt. Hier dürfen Teilnehmer neben Kleidung & Schreibutensilien keinerlei Hilfswerkzeuge verwenden. Die Leiter erfreuen sich über besonders kurze & korrekte Antworten, um weniger korrigieren zu müssen. Diese Aufgaben verlangen nicht nur einen optimalen Algorithmus, sondern auch eine gute Begründung weswegen dieser Algorithmus die optimale Laufzeit und Speicherkapazität erfüllt. Um dir das Leben einfacher zu machen, kannst du viele bekannte Algorithmen verwenden, da diese eine bekannte Laufzeit haben und nicht bewiesen werden müssen. Zum Beispiel können die Laufzeiten vom insert / lookup / deletion der jeweiligen STL Datenstrukturen übernommen werden, soweit nichts Anderes angegeben ist.

No feedback

Falls es absolut kein Feedback vom Grader gibt, musst du sicher stellen das dein Program korrekt läuft. Versuche dabei triviale Fälle (wie \(N=0, N=1\)) zu testen, Fälle mit Eingaben nahe an dem Limit und Eckdaten (corner cases), welches Fälle mit speziellen mathematischen Eigenschaften sind. Falls du alle anderen Aufgaben gelöst hast, kannst du auch versuchen ein Program zu schreiben, welches Testdaten generiert. Dabei kannst du dann schauen ob diese Testdaten einen SEGFAULT auslösen, ob dein Program wirklich so lange läuft wie es sollte und ob dein Program richtig terminiert.

Grafische Aufgaben haben typischerweise viele corner cases. Zum Beispiel wenn du ein Program schreiben musst, welches überprüft ob 2 Segmente sich schneiden, solltest du folgende corner cases überprüfen:

  • Die beiden Linien (welche durch die Segmente definiert sind, also unendlich sind) sind parallel und liegen nicht aufeinander.
  • Die beiden Linien liegen aufeinander, aber die Segmente schneiden nicht.
  • Die beiden Linien liegen aufeinander und die beiden Segmente formen ein Schnittsegment zwischen sich.
  • Ein Start- / Endpunkt eines Segments liegt auf dem anderen Segment.

Grader Tricks

Debugging mit dem Grader

Manchmal möchtest du Extrainformationen über die Testdaten erhalten. Zum Glück kann man mit etwas ungenierten Methoden dort nachhelfen. Du kannst nämlich verschiedene Fehlermeldungen auf dem Grader auslösen. So kannst du zum Beispiel die exakten Limits eines Programs herausfinden:

int main() {
    int N; cin >> N;
    while(N > guessedLimit) {}
    return 0;
}

Alle Batches welche WA (wrong answer) als Fehlermeldung besitzen sind in diesem Fall unter dem guessedLimit, während Batches welche TLE zurückgeben über diesem Limit sind. Um weitere Fehlermeldungen vom Grader zu erhalten kannst du entweder ein Signal schicken oder einen anderen Exitcode herausgeben (falls dies der Grader anzeigt):

int main() {
    for(;;) {} // TLE
    raise(SIGSEGV); //Segfault
    return N; // exit codes
}

Der Task Frisbee der SOI Finale von 2016 ist ein guter Kandidat dafür. Tipp: Versuche bei dieser Aufgabe herauszufinden, welche Testdaten N%2!=0 erfüllen.

Globales Ranking

Falls der Grader ein Live-Ranking hat, kannst du sehen welche Aufgaben bereits durch andere Teilnehmer gelöst worden sind. So weisst du ziemlich gut, welche Aufgaben einfacher sind und bei welchen Aufgaben du mehr Zeit investieren solltest (Man kann das z.B. bei Codeforces trainieren.)

Andere Grader Probleme

Auto-detect Source Code

Manchmal ist es möglich sowohl Source-Code mit C++98, als auch mit C++11 oder höher (resp. C98 & C11) zu kompilieren. Schau ausserdem welche compiler flags verwendet werden. Im schlimmsten Fall kann sogar das auto-detect Program C++ als C erkennen.

Grader Blacklist

Ein paar wenige Grader verwenden keine Whitelist, sondern eine Blacklist, um Nutzer daran zu hindern unerlaubter Code auf dem Grader laufen zu lassen. Verhindere also Namen von Variabeln wie kill um eine merkwürdige Fehlermeldung beim Grader zu verhindern.

Compiler Flags unter OS X

g++ unter OS X kompiliert mit der LLVM toolchain anstelle der GNU toolchain. Der Compilerflag -D_GLIBCXX_DEBUG muss mit -D_LIBCPP_DEBUG ersetzt werden. #include  <bits/stc++.h> funktioniert genauso wenig mit der LLVM toolchain, wie policy-based datastructures wie den ordered statistic tree.

Grader Einsendungen - Letzte vs. Beste

Frag gleich am Anfang des Contests ob die letzte oder die beste Einsendung zählt. Falls die letzte Einsendung zählt, mach am besten immer eine Kopie deines bis jetzt besten Programmes. So kannst du in den letzten fünf Minuten noch unbesorgt Veränderungen einschicken und falls der Grader nicht nachkommen würde, kannst du sicherheitshalber das alte Program in der letzten Minute zur Queue hinzufügen.

SEGFAULT

Compiler Flags überprüfen

Falls ein sample-case auf deinem Program funktioniert, aber nicht auf dem Grader, dann kompiliere dein Program mit den gleichen Argumenten wie der Grader (Siehe Andere Graderprobleme für OS X 4.) Falls deine sample-cases stimmen, aber eine der test-cases auf dem Grader einen SEGFAULT zurückgibt, ist es in diesem Moment zu empfehlen auf die Kommandozeile zu wechseln und das Program mit den folgenden Compilerflags zu kompilieren: g++ -Wall -Wextra -std=c++11 -g3 -ggdb3 -D_GLIBCXX_DEBUG main.cpp

Stack-limit exceeded

Falls du einen SEGFAULT erhältst und dir der Compiler auf deinem Computer keine Warnung gibt, könnte es am Stacklimit liegen. Der Grader könnte ein anderes Stacklimit besitzen wie dein Computer und es sollte immer nur mit maximal 100‘000 rekursiven Funktionsaufrufen gerechnet werden (max ~150‘000). Als Lösung kann man eine endständig rekursive Funktion (tail recursive function) in eine iterative Funktion mithilfe eines Stacks umwandeln. Beispiel:

int dfs(int i) {
    if(i % 13000011 == 0) return i;
    else return dfs(i*2+1);
    }
int main() {cout << dfs(42); }

        //Das Program oben ist identisch mit dem Program unten:

int main() {
    stack<int> st;
    st.push(42);
    while(st.size() != 0) {
        int i = st.top();
        st.pop();
        if(i % 13000011 == 0) {cout << i << endl; return 0;}
        else st.push(dfs(i*2+1));
     }
}

Buffer-overflows werden normalerweise vom Compiler detektiert, aber man kann extra vorsichtig sein und Referenzen mit [] mit .at() ersetzen.

Test-cases generieren

Falls dein Program nicht anfällig ist auf ein stack-limit versuche selber zufällige test-cases zu generieren, in der Hoffnung, dass ein SEGFAULT ausgelöst wird. Wenn SEGFAULTS nur bei grossen Testdaten geschehen, versuche selber grosse Testdaten zu generieren. Ab und zu reicht es auch einfach einen String mehrmals zu wiederholen.

Wrong answer (WA)

Versuche zuerst selber Testdaten zu generieren, die zu einem WA führen können. Das kann oft ein trivialer test-case sein, ein corner-case oder ein test-case mit grossen Limits, die bei dir ein overflow oder so auslösen können (siehe unten). Im Gegensatz zu SEGFAULTs, musst du aber die test-cases selber auf Korrektheit prüfen. Testdaten mit grossen Limits sind mühsam zu überprüfen (ausser das Resultat wird z.B. negativ, wenn es positiv sein sollte.)

Probleme mit Overflow / Underflow

Die Limits der Eingabe / Ausgabe können dich täuschen! Auch wenn die Eingabe Platz hat in einem int, kannst du beispielsweise bei einer Multiplikation zweier ints auf ein Overflow stossen. Ein typisches Beispiel hierzu ist das berechnen des Kreuzprodukts in graphischen Problemen (wie z.B. bei der konvexen Hülle berechnen).

Dieser Fehler ist mir so häufig passiert, dass ich generell bei jedem Contest folgendes schreibe:

#include <bits/stdc++.h>
#define int long long
signed main() {
    //insert code here....
}

Das ist generell ein schneller Fix, der ganz unkompliziert 32-bit ints mit 64-bit long longs ersetzt. Einfach darauf achten, dass die main Funktion noch als int erkannt wird. Du kannst einfachheitshalber signed main anstelle von int main schreiben. In einer Notsituation kannst du sogar int mit long double ersetzen und auf gut Glück hoffen.

Falls deine Rechnungen nicht Platz in einem long long hat, kannst du einen Bigint (theoretisch eine beliebige natürliche Zahl) verwenden. Bei Addition und Subtraktion ist eine Implementation noch nicht sehr mühsam und kann in C++ übernommen werden, doch wenn Multiplikation von Bigints benötigt wird, empfiehlt es sich die Java BigInteger Library oder Java BigDecimal Library (für Gleitkommazahlen) zu verwenden, insofern Java erlaubt ist. Geeksforgeeks hat ein schönes Beispiel dazu: http://www.geeksforgeeks.org/biginteger-class-in-java/

Probleme mit Gleitkommazahlen:

Auch hier wenn möglich long doubles verwenden anstelle von floats oder doubles. Zusätzlich sollte gleich am Anfang des Programs mithilfe von cout.setprecision(N) die Genauigkeit der Rechnungen geschrieben werden. Ausserdem wenn verlangt wird, dass die Zahlen immer mit z.B. 10 Nachkommastellen ausgegeben werden, sollte man auch std::fixed bei der Ausgabe verwenden.

int main() {
    std::cout.setprecision(10);
    std::cout << std::fixed << theValue << '\n';
}

//!!!(Als Beispiel könnte man das Problem Kreis mit minimalen Radius der K Punkte umschliesst nehmen von Slovakei 2015.)

Andere Häufige Fehler

  • Stelle sicher, dass wenn man bei Batch-Aufgaben mehrere test-cases auf einmal lösen muss, dass deine STL Container leer werden vor jedem neuen test-case. (Mithilfe von .clear()).
  • cos(180) anstelle von cos(pi) schreiben.
  • Eine Konstante verkehrt abtippen: modulo 100000007 anstelle von modulo 10000007.
  • Du hast einen Greedy-Algorithmus der für die sample cases funktioniert, nicht aber für die test-cases auf dem Grader. Wenn du nicht weiterweisst schreib doch eine Brute-force Lösung, generiere test-cases und schaue bei welchen test-cases dein Greedy-Algorithmus nicht mit der Brute-Force Lösung überein stimmt.

Time limit exceeded (TLE)

Wenn du die Laufzeit deines Programs kennst und sehen möchtest ob dein Program schnell genug ist, kannst du mit ca. \(10^8\) Operationen pro Sekunde ≈ \(2^{27}\) Operationen pro Sekunde rechnen. Wenn dein Algorithmus also \(O(N * M^2)\) dauert, musst du einfach die oberen Limits der jeweiligen Werte einsetzen und sehen ob die Anzahl Operationen \(\leq ~10^8 * T\) ist, wobei T die erlaubte Zeit auf dem Grader ist. Wenn die Operationen nahe bei \(10^8\) sind, aber die Lösung abgelehnt wird, optimiere mit den unteren Methoden.

Laufzeit scheint zu stimmen?

Bist du der Meinung, deine Laufzeit ist ausreichend für die Limits? Hier eine kleine Checkliste:

  • Bei nicht interaktiven Aufgaben kannst du dein Program mit zwei Zeilen optimieren, in dem du folgende Zeilen gleich zu Beginn des main Körpers einfügst:
// Turn off synchronization between cin/cout and scanf/printf
ios_base::sync_with_stdio(false);
// Disable automatic flush of cout when reading from cin cin.tie(0);
cin.tie(0);
  • Flushst du bei nicht interaktiven Aufgaben? Stelle sicher, dass du std::endl mit '\n' ersetzest um nicht unnötig Laufzeit einzubüssen.

  • Entferne einen unnötigen log N Faktor von der Laufzeit deines Programs indem du STL Datenstrukturen wie std::set und std::map mit std::unordered_set und std::unordered_map ersetzt.

  • Vergewissere dich, dass du die Laufzeit deiner STL Datenstrukturen kennst. Wusstest du zum Beispiel, dass std::distance(it1,it2) eine lineare Laufzeit bei Datenstrukturen wie set und map haben? Um diese zu umgehen, kannst du z.B. einen ordered statistic tree (aus den policy based Datenstrukturen der GNU toolchain) verwenden:

    #include <bits/stdc++.h>
    using namespace std;
    
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    #include <ext/pb_ds/detail/standard_policies.hpp>
    
    using namespace __gnu_pbds;
    typedef tree<
    int,
    int, //schreibe hier null_type für ein set
    less<int>,
    rb_tree_tag,
    tree_order_statistics_node_update>
    ordered_statistic_tree;
    //ordered_statistic_tree ist im Prinzip eine gewöhnliche Map <int, int> (die beiden ersten Parameter),
    //nur hat man Zugriff auf .find_by_order() und .order_of_key() in O(log N)
    
    
    int main() {
        ordered_statistic_tree test;
        test.insert({1,2}); //Akzeptiert ein pair wie eine gewöhnliche map
        test.insert({2,1}); //Insert in O(log N)
        test.insert({4,3});
        test.insert({5,2});
    
        //Gibt das n-te element zurück als Pair von key und value.
        cout << test.find_by_order(1)->second << endl;
    
        //Lower_bound und upper_bound funktionieren ganz normal
        cout << test.lower_bound(3) ->second << endl;
    
        //Anzahl von Objekten im Range {3,0} - {5,99999} in O(log N)
        cout << test.order_of_key({5,99999}) - test.order_of_key({3,0}) << endl;
    
        test.erase(4); //Erase vom key in O(log N)
    
        for(auto & it : test) cout << it.first << " " << it.second << endl;
    
        test.clear(); // zum loeschen der Daten
    
        return 0;
    }
    
  • Gut zu wissen: std::vector<bool> ist nicht ein std::vector! Diese spezielle Datenstruktur kann effizient vom Compiler implementiert werden und muss deswegen nicht unbedingt als std::bitset implementiert werden um Laufzeit einzusparen. Du kannst aber keine Referenz auf ein bool & bekommen, brauchst du dieses verhalten ersetze std::vector<bool> mit std::deque<bool>.

  • Deine Implementation stimmt teilweise, aber gibt WA bei ein paar anderen Aufgaben, obwohl du nur 1 entfernt von der Lösung bist? (Siehe Sektion Ad-Hoc random() Lösungen).

Deine Laufzeit stimmt nicht…

Du wirst höchstwahrscheinlich nicht die volle Punktzahl für dieses Program erreichen. Am besten überlegst du dir einen besseren Algorithmus oder wechselst zu einer anderen Aufgabe, aber wenn du keine Zeit mehr hast, gibt es einige Tricks ein paar Punkte zu gewinnen.

Rekursive Funktionen mit DP optimieren

Dein Program läuft nicht mit optimaler Laufzeit, auch nicht wenn du eine DP Optimierung dazu rechnest. ABER! Die test-cases der jeweiligen batches sind nicht immer perfekt und man kann oft noch zusätzliche Punkte gewinnen, in dem man häufige Rechenschritte abspeichert (cached) um sie nächstes mal einfach auszugeben. Am einfachsten setzt man bei jeder rekursiven Funktion eine map an (WICHTIG: Die Funktion muss immer das gleiche Resultat zurückgeben, wenn die Parameter identisch sind).

map<pair<int, string>, vector<int> > func_dp;
vector<int> func(int input1, string input2) {
    if(func_dp.count({input1,input2}) != 0) {
        vector<int> resultat;
        //hier wird vector<int> resultat berechnet.
        func_dp[{input1,input2}] =  resultat;
    }
    return func_dp[{input1, input2}];
}

Ab und zu kann diese Implementation gewisse test-cases zusätzlich lösen, ab und zu nicht, je nach dem wie oft die Parameter aufgerufen werden und wie aufwendig die Berechnungen in der Funktion sind. Wenn es nur bei gewissen test-cases schneller ist und bei anderen dafür langsamer, schaue doch bei der Sektion über Ad-Hoc random() Lösungen nach.

Eine gute Aufgabe dazu ist Kangaroo CEOI 2016 - Tag 1.

Besonders aufwendige Berechnungen, kannst du sogar gleich im Source-Code abspeichern, aber achte dabei auf das ‘program size limit’! (Anwendungsbeispiel: Nimbers berechnen.)

Ad-Hoc random() Lösungen

Ganz wichtig: Setze nie einen random seed in Abhängigkeit von Zeit! Anstelle schreibe einfach einen fixen seed wie z.B.: srand(73);

Das machst du aus dem Grund, dass Einsendungen neu gegradet werden können (sogenanntes regrading) und sich dein Program deswegen anders verhalten kann und du dadurch Punkte verlierst.

Das schöne an einem fixen srand ist, dass du dutzende Programme einschicken kannst, die jeweils einen anderen seed besitzen. Danach schaust du welcher seed dir die grösste Punktzahl gegeben hat und verwendest diesen für deine letzte Submission (falls nur die letzte zählt).

Das ist vor allem nützlich bei Aufgaben, bei denen du entweder immer um 1 verkehrt liegst oder es nur true/false Ausgaben gibt. Ausserdem ist es wichtig bei heuristischen Algorithmen (welche average-case optimale Laufzeit haben), wie z.B. Rabin-Karp string matching algorithm mit dem Rolling Hash.

Programme kombinieren

Ein weiterer Grund random() zu verwenden ist um Programme zu kombinieren. Wenn du 2 Programme hast, die unterschiedliche test-cases lösen können, kannst du zufällig entweder den Input mit dem einen oder mit dem anderen Program lösen.

Besser ist es, wenn du mithilfe von Grader debugging herausfinden kannst, welches Program wann besser funktioniert. Manche Grader sind sogar so schlecht, dass du einfach return N ausgeben kannst und so genau die jeweiligen Testdaten anhand des Exitcodes herausfinden kannst und so für jede Testdatei gezielt das eine oder das andere Program verwenden.

Simulieren

Simulationen sollte der erste Gedanken sein, wenn die Aufgabenstellung von Wahrscheinlichkeit redet (nicht von Kombination oder Variation wohlgemerkt). Hierbei wird einfach ein zufälliger Fall generiert und es wird geschaut ob die Bedingung der Wahrscheinlichkeit erfüllt ist. Wenn dieses simulieren sehr oft wiederholt wird, hat man ein Verhältnis von der Anzahl Programme die ein Problem lösen und eine Anzahl Programme welche das Problem nicht lösen. Eine Beispielsaufgabe dazu wäre Cards vom SOI Final 2015.