Auf die Tasten, fertig, … los!

oder: Programmieren gegen die Zeit

Prof. Dr. C. Damm - B. Ashirmatov, B.Sc. - A. Khuziakhmetov, B.Sc.

Institut für Informatik


Universität Göttingen

Elf Programmieraufgaben

Fünf Stunden

Drei Programmierer

Ein Computer

Null Internet

(nur Verbindung zum Jury-Server)

ICPC

International Collegiate Programming Contest

screenshot-01.png

Problemlösen und Programmieren im Team

  • anspruchsvolle mathematisch-praktische Probleme
  • Lösungen = Programme in Java, C, C++ oder Python
  • automatischer Test auf Jury-Server
  • Ziel: löse soviele Aufgaben wie möglich in 5 Stunden
  • bei Gleichstand entscheiden Gesamtzeit (inkl. Strafminuten) bzw. Einreichungszeit

Geschichte (siehe Wikipedia)

  • 1970 bis 1976
    Programmierwettbewerb an der Texas A&M University und weitere lokale Wettbewerbe
  • 1977 -- 1997 USA & Kanada
    z.B. 1997: 840 Teams inkl. regionale Ausscheide
  • seitdem international
    z.B. 2006: 6099 Teams (1756 Universitäten/82 Länder)
  • World Finals (Auswahl)
    Tokyo 2007, Banff 2008, Stockholm 2009, Harbin 2010, Orlando 2011, Warschau 2012, St. Petersburg 2013, Yekaterinburg 2014, Marrakech 2015

Teilnehmer

screenshot-02.png

Regionale Vorausscheide in Europa

screenshot-07.png NWERC
NEERC
CERC
SWERC
SEERC
  • harte Wettkämpfe mit anspruchsvollen Problemen
  • je nach Größe der Region kommen nur 2-15 Teams weiter zu den Finals
  • ein bis vier (wechselnde) Austragungsorte
  • GCPC = subregionaler Vorausscheid (Deutschland)

World Finals 2009

GCPC'15 - German Collegiate Programming Contest

1.30h nach dem Start

screenshot-03.png

1.30h vor dem Ende

screenshot-04.png

1h vor dem Ende

screenshot-05.png

Statistik

screenshot-06.png

Die Aufgaben

z.B. Problem K: Upside down primes

Woran muss man denken?

  • Primzahltest
  • String \(\leftrightarrow\) Zahl
  • String \(\leftrightarrow\) char-Feld
  • Zahlen bis \(10^{16}\)

Eine Java-Lösung

import java.util.Scanner;
public class UpsideDownPrimes {
    static boolean isPrime(long n) { // brute-force-Primzahltest
        if ( n <= 1) return false; 
        if ( n == 2 || n == 3) return true; 
        for (int i = 2; i * i <= n; i++)
            if ( n % i  == 0) return false; 
        return true;
    }
    public static void main (String[] args) {
        Scanner input = new Scanner(System.in);
        String s = input.next(); int l = s.length();
        char[] ca = s.toCharArray(), ac = new char[s.length()];
        boolean flag = false; // '3', '4' oder '7' ? 
        for (int i = 0; i < l; i++) // erst ziffernweise umdrehen ..
            switch (ca[i]) {
            case '6': ac[l-i-1] = '9'; case '9': ac[l-i-1] = '6';
            case '3': case '4': case '7': flag = true; 
            default: ac[l-i-1] = ca[i];
            }              // .. dann umgedrehten String erzeugen:
        String t = flag ? "0" : new String(ac); 
        // Strings in Zahlen umwandeln und testen: 
        long m = Long.parseLong(s), n = Long.parseLong(t); 
        System.out.println((isPrime(n) && isPrime(m)) ? "yes":"no"); 
    }
}

Training

Auswahl weiterer Wettbewerbe, zum fit bleiben …

  • Internet Problem Solving Contest (IPSC)
    auch für Schüler, Teams bis 3 Personen, allgemeine Computer-Probleme, Wikipedia etc. erlaubt
  • Google Code Jam (GCJ)
    Einzelwettkampf, 4–8 Minuten Zeit pro Aufgabe, Finale in einem der Google Headquarters
  • TopCoder Open (TCO)
    Phase 1: Programmieren unter starkem Zeitdruck, Phase 2: Fehler in Lösungen anderer finden

Fachpraktika an der Universität Göttingen

"Algorithms for programming contests" (2 Sem.)

cloud.png

  • wöchentliche Aufgaben, eigener Jury-Server
  • Leistungspunkte anrechenbar im Bachelorstudium

Erfolge der Göttinger Studenten

  • GCPC'14: Platz 2 von 64 Teams aus 8 Universitäten
  • GCPC'15: Plätze 6 und 18 von 62 Teams aus 10 Unis
  • NWERC'15: Platz 32 unter den 95 europäischen Top-Teams der Vorrunde

    TheMathemagiciansLEFT_TeamRedundancyTeamRIGHT.JPG
    "The Mathemagicians" und "Team Redundancy Team"

Demnächst

  • Wintercontest am 30. Januar 2016 in Göttingen
  • Interesse an Training und Teilnahme?
  • E-Mail an Bakhodir Ashirmatov <b.ashirmatov@stud.uni-goettingen.de>

Bildnachweis