Tipps und Tricks

für Programmierwettbewerbe

Motivation

In Programmierwettbewerben geht es um Geschwindigkeit

• des Laufzeitverhaltens des Algorithmus
• des Programms
• der Entwicklung der Lösung
  1. Lösung ausdenken
  2. Lösung programmieren

Ziel

Möglichst wenig Zeit mit Programmieren zu verbringen

Die Schwierigkeit liegt im Lösungsideen entwickeln, nicht im Code zu schreiben.

Problem lösen

1. Aufgabe genau lesen
2. Limits anschauen, Laufzeit erraten
3. Beispiele durchrechnen
4. Idee entwickeln
5. Korrektheit beweisen/Gegenbeispiele suchen
6. Grobe Implementierung überlegen
7. Programmieren

Brute-Force

Aufgabe mindestens für Teilpunkte lösen!

Container

• std::vector<T>
• std::map<K,V>, std::set<T>
• std::deque<T> (std::stack<T>, std::queue<T>)

vector<int> v(4); // v={0,0,0,0} v.size()==4
v.clear();        // v={}        v.size()==0
v.push_back(4);   // v={4},      v.size()==1
v.push_back(6);   // v={4,6},    v.size()==2
v.push_back(3);   // v={4,6,3},  v.size()==3
v.pop_back();     // v={4,6},    v.size()==2

Nicht nutzen: std::list.

Iteratoren

• Iteratoren sind verallgemeinterte Zeiger
• Anfang: it=container.begin();
• Dereferenzierung: *it = x
• Inkrementierung: it++ und it += n
• Vergleich: it == it2

vector<int> v{5,2,3};
for (auto it=v.begin(); it!=v.end(); ++it)
  std::cout << *it << ' ';
// Ausgabe: 5 2 3

auto it=v.begin();
*it = 0;   // v={0,2,3}
it += 2;   // it zeigt auf 3
*it = 9;   // v={0,2,9}
*--it = 4; // v={0,2,9}

Algorithmen

Machen nützliche Dinge mit Iteratoren!

• std::sort
• std::binary_search, std::lower_bound, std::upper_bound
• std::unique
• std::reverse
• Doku http://en.cppreference.com

Algorithmen nutzen

Algorithmen arbeiten zwischen zwei Iteratoren: Start und Ende (exklusiv).

vector<int> v{5,4,3,2,1};
sort(v.begin(), v.begin()+2); // v={4,5,3,2,1}
sort(v.begin()+2, v.end());   // v={4,5,1,2,3}
sort(v.begin(), v.end());     // v={1,2,3,4,5}

Warum STL

Pro STL:

• Debugging mit -D_GLIBCXX_DEBUG
• Einheitliche Schnittstelle für Algorithmen
• Nicht langsamer

Das heisst:

• Keine Arrays
• Kein new/delete

Eingabe/Ausgabe

#include <iostream>
int n;
cin >> n;
vector<int> v;
for (int i=0; i<n; ++i) {
  int x;
  cin >> x;
  v.push_back(x);
}
cout << n.size() << '\n';

Nicht künstlich langsam machen:

• Kein std::endl!
• std::endl='\n'+std::flush und std::flush ist auf dem Grader sehr langsam.

Vorteil I/O-Streams

Ich empfehle <iostream>

• Keine Flags auswendig lernen
• Keine Bugs mit falschem Flag
• Typ ändern ganz leicht
• Genauso schnell

Schnell machen:

// Synchronisierung mit scanf/printf ausschalten
ios_base::sync_with_stdio(false);

// Automatisches flush von cout bei Einlesen von cin verhindern
cin.tie(0);

Konsolen-Basics

Verzeichnis wechseln:

cd <directory>

Aktuelles Verzeichnis:

pwd

Dateien anzeigen:

ls

Kompilieren

g++ -Wall -Wextra -std=c++11 -g3 -ggdb3 -D_GLIBCXX_DEBUG x.cc -o x

-Wall -Wextra:

Warnungen und zusätzliche Warnungen einschalten

-std=c++11:

C++11 aktivieren. -std=c++14 auch möglich.

-g3 -ggdb3:

Debug-Informationen für gdb.

-D_GLIBCXX_DEBUG:

Speicherzugriffe überprüfen (Index, Iteratoren)

Testen

Eingabe von Beispiel-Datei:

./prog <sample01.in

Eingabe von allen Beispiel-Dateien:

for f in *.in
do
  echo "-- $f --"
  ./prog <$f
done

Kurz:

for f in *.in; do echo "-- $f --"; ./prog <$f; done

                                                                                             

Debugging

Bei Programm-Absturz gdb (Gnu DeBugger):

$ gdb prog
(gdb) run <sample01.in
(gdb) bt

printf-Debugging

Ausgaben in den Code einfügen:

for (int i=0; i<10; ++i) {
  cerr << "i=" << i << " sum=" << sum << '\n';
  sum += i;
}

Nützliches Makro fürs Debuggen:

#define DEB(x) cerr << x << '\n'

for (int i=0; i<10; ++i) {
  DEB("i=" << i << " sum=" << sum);
  sum += i;
}

Vorteil: Nur an einer Stelle auskommentieren

#define DEB(x) // cerr << x << '\n'

Fehlersuche

Wenn Bug im Programm:

1. Gegenbeispiel? Falls ja: printf-Debugging
2. Corner-Cases testen
3. Ist Ansatz wirklich korrekt?
4. Aufgabe nochmal durchlesen
5. Code nochmal durchlesen
6. Andere Aufgaben versuchen
7. Brute-Force-Lösung schreiben und automatisiert Tests generieren

Zeitlimit:

In 1 Sekunde sind 10⁷ Schritte möglich.

Fehler vermeiden

std::assert verwenden.

#include <cassert>

void dfs(int n) {
  // n darf noch nicht besucht sein
  assert(!graph[n].visited);

  graph[n].visited = true;
  for (int nb : graph[n].adj) {
    if (!graph[nb].visited)
      dfs(nb);
  }
}

RTFM

Doku kennen lernen: http://en.cppreference.com