Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
HowTo: ICPC Vorbereitung
Nachdem der Anteil an Erstis bisher angenehm hoch ist was die Anmeldungen für den WC betrifft und der Kenntnisstand, wie man sich vernünftig vorbereiten kann geschweige denn was das überhaupt ist indirekt proportional niedrig, werde ich (und vllt noch ein paar andere Erfahrenere) ein paar Zeilen niederschreiben wie man sich als Einsteiger an die Materie heranwagen kann um beim WC eine gute Figur zu machen. (Nachdem dazu schon einige Erstis angefragt haben und die Anleitungen auf den Seiten etwas suboptimal sind).
In erster Linie geht es im Contest darum Aufgaben zu lösen, um ein Gefühl dafür zu bekommen was für eine Art Aufgaben das sind sollte man sich mal so Aufgaben ansehen und vielleicht sogar lösen.
Dazu registriert man sich bei http://icpcres.ecs.baylor.edu/onlinejudge/index.php praktisch DIE Seite um ICPC Aufgaben zu lösen und zu trainieren. Das Interface ist eigentlich recht intuitiv.
Links kann man auf Browse Problems drücken, dann sucht man sich eins von den 2000 Problemen aus liest sichs durch und versucht es zu lösen (oder legt es weg weil es zu schwer ist oder man keine Idee hat). Wenn man dann eine Lösung programmiert hat kann man auf Submit drücken, die entsprechende Sprache die man verwendet hat auswählen und seinen Code dann submitten. Anschließend kann man in “My Submissions” das Ergebnis ansehen.
Die ist in der Regel eins von folgenden:
Accepted - Dein Programm ist richtig
Wrong Answer - Dein Programm ist falsch
Presentation Error - Dein Programm ist im Prinzip richtig, produziert aber zuviel/zuwenig/falsche Whitespaces
Time Limit Exceeded - Dein Programm ist zu langsam
Memory Limit Exceeded - Dein Programm braucht zuviel Speicher
Runtime Error - Dein Programm stürzt aus irgendeinem Grund ab (Endlosrekursion, Exceptions,…)
Compile Error - Dein Programm kompiliert nicht (da bekommt man in der Regel auch die Compilemeldung)
Da die meisten Erstis wahrscheinlich in Java programmieren noch folgender besonderer Hinweis. Das Programm muss aus einem File namens “Main.java” bestehen und dort muss eine public class Main mit einer main-Methode vorhanden sein, also in etwa so:
public class Main {
public static void main(String[] args) {
System.exit(0); //Damit sollte man sein Programm standardgemäß beenden
}
}Input kommt über die Standardeingabe (System.in), also BufferedReader oder Scanner verwenden und Ergebnisse müssen auf die Standardausgabe ausgegeben werden (System.out), keinenfalls etwas auf System.err ausgeben.
Wenn ihr durch die Problemlisten schaut, werdet ihr noch 2 Statistiken entdecken in Form von %-Werten. Der erste Wert gibt an wieviel % aller Submissions das Problem korrekt gelöst haben und der zweite Wert wieviel % der User die das Problem versucht haben (==mindestens eine Lösung submittet) letztendlich irgendwann lösen konnten. Wenn beide Werte relativ hoch sind ist das ein guter Indikator dass es sich hier um ein eher leichtes Problem handelt.
Soviel zur grauen Theorie, wer sich an einer kleinen Auswahl an Aufgaben probieren will, hier sei eine kleine Auswahl (in Form von den Nummern) von mir zum Einstieg (Schwierigkeitsangaben rein subjektiv):
100 - relativ einfach mit einem kleinen Fallstrick (GENAU die Aufgabenstellung lesen dbzgl.)
101 - einfach
102 - sehr einfach
103 - ein wenig anspruchsvoller
104 - nicht ganz ohne
105 - programmierlastig
106 - ein bisschen mathe aber nicht allzu heftig
107 - nicht ganz leicht aber sehr schön
108 - anspruchsvoll (für alle die sich beschweren man lernt in AuD zuwenig Divide n Conquer…)
109 - nervig
110 - SEHR nervig
113 - fast ein Einzeiler
11216/11217 - 
Zum Schluss sei noch das UVA Toolkit erwähnt http://www.uvatoolkit.com/ dort kann man sich zu verschiedenen Aufgaben Outputs produzieren lassen wenn das eigene mal nicht tut und man gern wissen würde wie der Output zu speziellen Testcases lautet.
Hier exemplarisch eine Lösung für die Aufgabe 530 - Binomial Showdown (war auch eine Zusatzaufgabe in AuD):
In Java:
import java.util.*;
public class Main
{
public static long binom(long n, long k)
{
long bin = 1;
if (k > n-k) k = n-k;
for (int i = 1; i <= k; i++)
{
bin *= n--;
bin /= i;
}
return bin;
}
public static void main(String[] args)
{
Scanner s = new Scanner(System.in);
long n = -1;
long k = -1;
n = s.nextInt();
k = s.nextInt();
while (n != 0)
{
System.out.println(binom(n, k));
n = s.nextInt();
k = s.nextInt();
}
System.exit(0);
}
}und in C++
#include <iostream>
using namespace std;
unsigned long long binom(unsigned long long n, unsigned long long k)
{
unsigned long long bin = 1;
if (k > n-k) k = n-k;
for (unsigned int i = 1; i <= k; i++)
{
bin *= n--;
bin /= i;
}
return bin;
}
int main()
{
unsigned long long n,k;
while (cin >> n >> k && n != 0)
{
cout << binom(n,k) << endl;
}
return 0;
}
nicht ganz, da fehlt doch ein (n-k)!
Heute schon nen Bruch gekürzt? 
Ja, beide
Verdammt! Ich hatte versucht, das über Aufbauen des Pascalschen Dreiecks zu lösen
Geht mit DP ja in quadratischer Zeit, nur ohne DP … 