Christopher Oezbek, [email protected] 1
ACM Programming Contest TrainingEinführung
Christopher OezbekFreie Universität Berlin, Institut für Informatik
http://www.inf.fu-berlin.de/~oezbek/
Christopher Oezbek, [email protected] 2
Worum geht es?
• Programmieren natürlich!
• Beim berühmtesten Programmierwettbewerb schlechthin Auch nicht übel: International Conference on Functional
Programming Programming Contest => ICFP PC ;-)
• International Collegiate Programming Contest => ICPC
• Veranstalter => ACM Association of Computer Machinerists
• Handwerkerverband für Informatiker Größte Organisation dieser Art
• Hauptsponsor => IBM Imagegewinn Recruiting
Christopher Oezbek, [email protected] 3
Wie läuft das Ganze ab?
• Erste Runde: Lokale Vorauswahl => 35 "Regionals" Unsere Region => South West European Die zwei besten kommen weiter Termin: 19,20 November
• Zweite Runde: Finals Dieses mal (nächstes Jahr) in Texas (9-13 April 06)! Hart: Gute Teams schaffen eine (1) Aufgabe!
• Wir haben noch eine lokale Vorauswahl gemacht, um die Teams herauszubekommen, die überhaupt zu den Regionals fahren sollten, da das Geld knapp ist.
Berlin Programming Contest• Sieger FU => KungFU Monsters• Platz 2 und 3 HU• Platz 4 FU => Computer FUzzys
Christopher Oezbek, [email protected] 4
Wie läuft ein Contest ab?
• 1 Computer, 3 Leute, 8-10 Aufgaben, 5 Stunden Zeit
• Ihr bekommt die Aufgaben mit Beispieldaten, Papier und legt los.
• Wer glaubt mit einer Aufgabe fertig zu sein, schickt diese an die Wettkampfrichter ab (Submission).
• Diese bewerten dann die Einsendung durch ein automatisches Testset (judging).
• Anschließend wird man informiert, ob man etwas falsch gemacht hat oder die Aufgabe als korrekt gewertet wurde.
Korrekte Lösungen geben einen bunten Ballon. Deshalb wird es normalerweise schnell ziemlich bunt um
einen herum!
Christopher Oezbek, [email protected] 5
Folgende Antworten bekommt ihr von den Richtern:
• CORRECT: Yuhuu!
• INCORRECT: Verdammt!
• COMPILE ERROR: Das Programm lies sich nicht kompilieren (ihr schickt immer den Quelltext ab)
• RUNTIME ERROR: Euer Programm ist abgestürzt.
• REPRESENTATION ERROR: Euer Programm liefert die richtigen Ergebnisse, aber die Ausgabe stimmt nicht 100% (z.B. einen Punkt am Ende des Satzes vergessen).
• RUNTIME-LIMIT-EXCEEDED: Euer Programm hat länger als die erlaubte Zeit für das Lösen des Problems gebraucht (meist 5 Minuten).
Christopher Oezbek, [email protected] 6
Denkt daran...
• Bei den Regional Contests gibt es nur 2 Gewinner.
• Das ist ein hartes Brot.
• Ich bin damals mit meinem Team 7te von 88 geworden und uns hätte nur noch eine Aufgabe gefehlt, dann wären wir 2ter gewesen. Argl.
• Nicht traurig sein.
• Dabei sein zählt.
Christopher Oezbek, [email protected] 7
Laber, Laber, jetzt aber bitte mal konkret.
• Genau. Dazu müssen wir uns die Probleme aus einem "Problemset" ansehen.
• Typischer Aufbau einer Aufgabe: Name des Problems Dateinamen, die ihr verwenden sollte Einleitender Text, der das Problem (meist witzig) einführt. Eingabebeschreibung Ausgabebeschreibung Beispieldaten
Christopher Oezbek, [email protected] 11
Wie gehen wir da dran?
• Der Anfang ist immer gleich
• Jedes Problem besteht aus einer Eingabedatei und einer Ausgabedatei.
• Die Eingabedatei besteht aus mehrerer Testfällen und jeder dieser Testfälle ist unabhängig.
• Entweder man sagt uns am Anfang wie viele Fälle es sind oder es gibt einen bestimmten Fall der bedeutet "Jetzt ist Schluß"
• D.h. wir bauen unser Programm so auf: Eingabedatei öffnen, Ausgabedatei öffnen Solange wir noch einen Fall zu bearbeiten haben:
• Bearbeite Fall (Einlesen, Lösen, Ausgeben) Eingabedatei schließen, Ausgabedatei schließen
Christopher Oezbek, [email protected] 12
... Das Template
• Da dies immer so gleich ist, gibt es für euch direkt eine Vorlage.
• Diese dürft ihr als Ausdruck auch mit in den Wettbewerb nehmen.
• Man tippt dies einmal ein und kopiert es dann immer wieder.
Christopher Oezbek, [email protected] 14
• Eingabe und Ausgabe-Funktion sind euere Freunde und helfen euch bei der mühseligen Tipparbeit.
• Da man öfter am Fehlersuchen ist, als man es möchte, ist der Debug-Switch wichtig.
• Nur nicht vergessen diesen vor dem Abschicken wieder auszuschalten.
Christopher Oezbek, [email protected] 15
III: Do-It
• Natürlich steckt dann hier die Intelligenz euerer Lösung.
Christopher Oezbek, [email protected] 17
Teamstrategie
• Wie arbeitet man zusammen?
• Alle zusammen an einem Problem?
• Nein! Damit verschwendet man Gehirnleistung, weil 2 über die selbe Sache nachdenken.
• Insbesondere bei den Regionals ist es wichtig, dass ihr sehr autark arbeiten könnt.
• Da ihr nur eine Tastatur habt, arbeiten immer 2 von euch auf Papier:
Pseudo-Code, den man schnell eintippen kann. Testfälle überlegen Fehler suchen
• Natürlich könnt ihr euch gegenseitig fragen, mehr als 5 Minuten Unterbrechung könnt ihr euch aber nicht leisten.
Christopher Oezbek, [email protected] 18
Start-Strategie
• Ein normales Team hat 3 Mitglieder: Speed-Freak Algorithmus-Freund Simulator
• Beim Beginn des Wettbewerbs passiert folgendes: Der Speed-Freak gibt das Template ein. Die anderen zwei schauen das Problemset durch (einer von
hinten, einer von vorne) und versuchen die Schwierigkeit der Aufgaben einzuschätzen.
Wird eine einfache Aufgabe gefunden, dann wird diese auf dem Anmeldezettel festgehalten (ich mache A) und man legt auf Papier los.
Ist der Speed-Freak fertig, dann darf derjenige loslegen, der eine einfache Aufgabe am weitesten bearbeitet hat.
Christopher Oezbek, [email protected] 19
Debugging Rules
• Debugging sollte man nicht am Computer machen.
• Ausdrucken (mit Zeilenzahlen)
• Voraussetzung für gutes Debugging sind reichlich und gute Testdaten.
D.h. mindestens doppelt so viel, wie als Beispiele mitgegeben werden.
• Strategien: Tracing: Schritt für Schritt durch das Programm durchgehen Make it Fail: Den Testfall, der alles kaputt macht immer
explizit in den Testdaten lassen. Divide und Conquer: Um das Problem zu finden immer
versuchen große Fehlerklassen auszuschließen, z.B. die Eingabe funktioniert, dann können es nur Lösen oder Ausgabe sein.
Christopher Oezbek, [email protected] 20
Die wichtigsten Java-Klassen im Überblick
• String
• StringTokenizer
• Vector
• HashMap
• array
• Arrays/Collection
Christopher Oezbek, [email protected] 21
String - Zeichenkette: "Hallo", "", "30 3"
• Zeilenumbruch/Newline: "\n" Tabulator: "\t"
• Aufteilen: "Hallo,Welt".split(",") => {"Hallo", "Welt"}
• Länge: "Hallo".length() == 5
• Zeichen auslesen: "Hallo".charAt(1) == 'a'
• Teilstring: "Hallo Welt".substring(6,9) => "Wel"
• Vergleich: Nicht ==, sondern "Hallo".equals("Hallo")
• Aneinanderhängen: "Hallo" + "Welt" => "HalloWelt"
• Kleinschreiben: "Hallo".toLowerCase() => "hallo"
• Großschreiben: "Hallo".toUpperCase() => "HALLO"
• Als Zeichen: "Hallo".toCharArray() => {'H','a','l','l','o'}
• Ersetzen: "Halloal".replace("al", "ol") => "Holloal" "Halloal".replaceAll("al", "ol") => "Hollool"
• Leerzeichen abschneiden: " Hallo \n".trim() => "Hallo"
Christopher Oezbek, [email protected] 22
StringTokenizer - Zeichenketten zerlegen
• StringTokenizer st = new StringTokenizer(s, ","); while (st.hasNext()){ String s2 = st.next(); ... }
• Sehr praktisch, kann man auch mit Split machen: String[] splits = s.split(","); for (int i = 0; i < splits.length; i++){ String s2 = splits[i]; ... }
Christopher Oezbek, [email protected] 23
String Zahl, Zahl String
• Integer.parseInt("3") == 3
• "" + 3 == "3"
• System.out.print(3) "3" wird ausgedruckt.
• Achtung: System.out.println(3) "3\n"
• Get auch mit Kommazahlen: Float.parseFloat("3.2") == 3.2 "" + 3.2 == "3.2"
• Achtung: "" + 3 + 2 = "32" "" + (3 + 2) == "5"
Christopher Oezbek, [email protected] 24
Arrays
• int[] intArray = new int[5]; // Feld der Größe 5
• int[0] = 2; int[4] = 3; intArray == {2,0,0,0,3}
• Länge: intArray.length
• Sortieren: int[] newArray = Arrays.sort(intArray);
• Kann man nicht verkleinern oder einzelne Elemente rauslöschen
• for (int i = 0; i < intArray.length; i++){ int data = intArray[i]; ...}
• Initialisieren: Arrays.fill(intArray, 2);
Christopher Oezbek, [email protected] 25
Vector - Flexible Datenstruktur
• Vector v = new Vector();
• v.add("Hallo");
• v.add("Bye");
• v.size() == 2 // Wächst mit!
• v.remove(0); v.get(0).equals("Bye");
• Problem: Mit Java 1.4.2. gibt es noch kein Autoboxing. Mühsam für primitive Datentypen:
v.add(new Integer(2)); ((Integer)v.get(0)).intValue() == 2 (Java 1.5: v.add(2); v.get(0) == 2)
• Gut für Strings, Objekte.
• v.toArray();
• Collections.sort(v);
Christopher Oezbek, [email protected] 26
Hashmap - Verweisliste
• Hashmap s = new HashMap();
• s.put("Hallo", new Integer(3)); // Schlüssel, Wert
• s.put("Bye", new Integer(4));
• s.get("Hallo") == 3, s.get("Bye") == 4
• Schnell und sehr praktisch.
• Achtung, es gibt wieder das Einpack- und Auspackproblem.
• Gibt es einen Schlüssel: s.containsKey("Hallo") == true
Christopher Oezbek, [email protected] 27
Terminkalender
• Donnerstags 17:45 - 21:00 Training.
• 19./20. November Paris
• Neuer Trainingstermin anschließend
• Training läuft während des Semesters Leider sind unsere Semester ja nicht mit sonst üblichen
Trimester (Fall, Spring, Summer) in Einklang.
• Ende des Sommersemesters Berlin Programming Contest und ICFPCP