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

Aufgabentypen

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

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

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

Andere Grader Probleme

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.

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.

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.)

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.