{"id":332,"date":"2014-05-25T00:55:51","date_gmt":"2014-05-25T00:55:51","guid":{"rendered":"http:\/\/soi.inf.ethz.ch\/~acm\/wp\/?p=332"},"modified":"2014-05-25T00:55:51","modified_gmt":"2014-05-25T00:55:51","slug":"swerc-2013-valencia-report","status":"publish","type":"post","link":"https:\/\/blogs.ethz.ch\/acmicpc\/2014\/05\/25\/swerc-2013-valencia-report\/","title":{"rendered":"SWERC 2013 Valencia Report"},"content":{"rendered":"

Daniel Graf<\/em><\/p>\n

Programmieren als Wettbewerb?
\n<\/strong>Die ACM (association for computing machinery) k\u00fcrt neben dem Turing Award Gewinner jedes Jahr auch das Team der besten Informatikstudierenden im algorithmischen Programmieren. Dies im Rahmen des ICPC, dem International Collegiate Programming Contest [1]. J\u00e4hrlich nehmen weltweit Tausende von Dreierteams an regionalen Wettbewerben teil und k\u00e4mpfen um einen der begehrten Pl\u00e4tze am Weltfinal.<\/p>\n

Die ACM-Kommission des VIS organisiert jeden Herbst den lokalen Ausscheidungswettbewerb an der ETH zusammen mit der EPFL. So trafen sich am sp\u00e4ten Samstagmorgen des 12. Oktober eine Studentin und 20 Studenten um den Tag mit Knobeln und Coden zu verbringen. Wer die Vorlesungen ACM-Lab oder Algolab besucht hat, kennt das Format: In f\u00fcnf Stunden gilt es m\u00f6glichst viele Programmierr\u00e4tsel zu l\u00f6sen und zu implementieren. Jeder f\u00fcr sich, ohne Hilfsmittel oder Internet. Als Vorwissen reicht aus, was in \u2018Datenstrukturen & Algorithmen\u2019 behandelt wird. Viele Probleme erfordern einen Standard-Algorithmus (Breitensuche, Dijkstras k\u00fcrzester Pfade Algorithmus, minimaler Spannbaum, \u2026), jeweils kombiniert mit einem cleveren Twist. Programmiert wird in C\/C++ oder Java mit den jeweiligen Standard-Libraries als Starthilfe.<\/p>\n

Mir lief es gut, die ersten f\u00fcnf Probleme wurden auf Anhieb \u2018accepted\u2019. Doch bei der DP-Aufgabe (Dynamische Programmierung) schlich sich ein kleiner Fehler ein: Ziel war es zu z\u00e4hlen, wie viele Spielverl\u00e4ufe ein Fussballspiel mit einem Endresultat von X:Y bei Z F\u00fchrungswechseln haben kann. Schliesslich fand ich den Bug und es reichte mir f\u00fcr den zweiten Platz, sodass ich mich mit den beiden Mathematik-Studenten Nikola Djokic und Johannes Kapfhammer f\u00fcr das erste ETH-Team qualifizierte. F\u00fcr das zweite Team qualifizierten sich Kieran Nirkko (D-INFK), Jan Wilken D\u00f6rrie (D-INFK) und Marco Keller (D-ITET).<\/p>\n

Team-Training: Kondition und Technik
\n<\/strong>Nun galt es, aus Einzelk\u00e4mpfern ein Team zu formen. Fortan stand uns zu dritt nur noch ein Computer zur Verf\u00fcgung, sodass wir uns gut absprechen mussten, wer wann was codet und debugt, ohne dass sich sechs H\u00e4nde um die Tastatur streiten.<\/p>\n

W\u00e4hrend einer Woche \u00fcbten wir t\u00e4glich von 10 bis 15 Uhr. Die Trainings wurden organisiert von der VIS-ACM-Kommission in Zusammenarbeit mit Maxim Buzdalov und Fedor Tsarev (ihres Zeichens ACM ICPC World Champions von 2009 respektive 2008) von der University of Information Technologies, Mechanics and Optics (ITMO) in St. Petersburg. Die ITMO hat in den letzten paar Jahren die ACM ICPC Szene dominiert und die j\u00e4hrlichen Trainings mit ihnen sind f\u00fcr die ETH Teams immer sehr f\u00f6rdernd und fordernd zugleich. Sie haben einen grossen Teil zu den regionalen Erfolgen der letzten Jahre beigetragen. W\u00e4hrend der Trainings sahen wir jeweils die Einsendungen der russischen Teams wie sie an den Contests geschahen, und konnten uns so virtuell mit ihnen messen.<\/p>\n

An manchen Tagen lief es super – an anderen weniger. Das bin\u00e4re Grading ist da gnadenlos. Solange die Einsendung nicht alle Testf\u00e4lle korrekt und schnell l\u00f6st, gibt es keinen Punkt. Nicht jeder hat eine so einfache Strategie wie das russische Top-Team letztes Jahr: \u201eFirst, each of us solved three tasks. Then we solved the last one together.\u201c<\/p>\n

\"Nebelmeer<\/a>
Nebelmeer beim Start in Z\u00fcrich<\/figcaption><\/figure>\n

\u252c\u00edHola Valencia!<\/strong><\/p>\n

Zuversichtlich und auch ein wenig aufgeregt bestiegen wir das Flugzeug und freuten uns darauf, f\u00fcr ein letztes Wochenende dem Z\u00fcri-Nebel nach Valencia zu entfliehen.<\/p>\n

Nach der Ankunft im Hotel erkundeten wir die Altstadt Valencias. Vorbei an der Stierkampfarena und der Kathedrale begaben wir uns auf die Suche nach Churros, einem spanischen frittierten Geb\u00e4ck, das man in heisse Schokolade tunkt. Zum Abendessen trafen wir uns mit den beiden Teams der EPFL, um eine grosse Auswahl an Tapas zu teilen.<\/p>\n

Der Samstag war dann der Vorbereitung auf den kommenden Wettbewerb gewidmet. Austragungsort des Southwestern Europe Regional Contest (kurz SWERC [2]) war die Universitat Politecnica de Valencia. 44 Teams aus Spanien, Frankreich, Portugal, Italien, Israel und der Schweiz waren angereist. Nach der Registrierung vertrieben wir uns die Zeit mit Karten spielen und erh\u00f6hten so die Anzahl D-INFK-Doktoranden, die Jassen und Tichu beherrschen. Nach den Er\u00f6ffnungsansprachen folgten die beiden obligaten Vortr\u00e4ge: Ein Professor des dortigen Instituts erkl\u00e4rte uns den Unterschied zwischen SaaS (Software as a Service) und PaaS (Platform as a Service), bevor uns eine Facebook-Ingenieurin ihr Code-Review-System erl\u00e4uterte. Am Nachmittag folgte ein Testlauf, damit wir das Wettbewerbs-System auf Herz und Nieren pr\u00fcfen konnten. Und um am n\u00e4chsten Tag richtig fit zu sein, liess unser Team gar das noble Contest-Dinner aus, um richtig ausgeschlafen zu sein.<\/p>\n

\"Team\"<\/a>
ETH-Team w\u00e4hrend dem Probe-Contest<\/figcaption><\/figure>\n

Der Contest
\n<\/strong>Jetzt galt es ernst. Wir joggten zur Uni um richtig wach zu werden und nutzen die letzten zehn Minuten vor dem Start um alles aufzusetzen. Nikola codete schon mal den Maximum Flow auf Vorrat, denn der kommt doch sowieso immer dran – er sollte Recht behalten.<\/p>\n

Die zehn Aufgaben waren spannend und herausfordernd. Wir berechneten die aktuellsten Themen aus der Blogosph\u00e4re, die Parit\u00e4t der Anzahl Nullen von n!, einen optimalen Stundenplan und vieles mehr. Nach vier von f\u00fcnf Stunden schwebten \u00fcber unserem Monitor sechs Ballone und wir lagen in F\u00fchrung. Nur das erste Team der Universitat Polit\u00e8cnica de Catalunya (kurz UPC [3]) hatte bis dahin ebensoviele Aufgaben gel\u00f6st.<\/p>\n

W\u00e4hrend der letzten Stunde blieb die Rangliste eingefroren. Wir sahen nicht mehr woran die anderen Teams noch arbeiteten und somit blieb es spannend bis am Schluss. Wir l\u00f6sten kurz darauf ein siebtes Problem, doch am achten bissen wir uns die Z\u00e4hne aus. Es galt einen planaren Graphen mit vier Farben zu f\u00e4rben [4]. Ein simples Backtracking war zu langsam und so versuchten wir es auch noch randomisiert. Gl\u00fccklicherweise hatte ich in der Vorlesung \u00fcber randomisierte Algorithmen von Prof. Angelika Steger gerade k\u00fcrzlich von einer Abwandlung von Sch\u00f6nings 3-SAT-Algorithmus auf F\u00e4rbeprobleme geh\u00f6rt. Wir kombinierten beides, optimierten und schickten mit diversen Random Seeds ein, bis 24 Sekunden vor Schluss die 16. Einsendung akzeptiert wurde.<\/p>\n

Auch das UPC-Team hatte insgesamt acht Probleme gel\u00f6st, sodass wir auf dem zweiten Platz der Schlussrangliste zu liegen kamen. Damit haben wir uns, zusammen mit dem UPC-Team, f\u00fcr das Weltfinale qualifiziert. So d\u00fcrfen wir n\u00e4chsten Sommer ins russische Jekaterinburg reisen, um dort die ETH und damit S\u00fcdwesteuropa zu vertreten.<\/p>\n

Insgesamt fiel die Schweizer Bilanz \u00e4usserst erfreulich aus: Drei der insgesamt zw\u00f6lf Medaillens\u00e4tze gingen in die Schweiz. Die ETH holte Gold und Bronze auf den Pl\u00e4tzen 2 und 12 und die EPFL gewann eine Silbermedaille mit Platz 5 und verpasste Bronze mit Platz 13 nur haarscharf. Grund genug f\u00fcr eine feines Essen in der Stadt: In einem Felsenkeller wurde uns beste spanische Ente serviert.<\/p>\n

\"Seaside\"<\/a>
Die ETH-Delegation am Mittelmeer: v.l.n.r. Daniel Graf, Kieran Nirkko, Akaki Mamageishvili, Jan Wilken D\u00f6rrie, Nikola Djokic, Johannes Kapfhammer, Marco Keller, Jan H\u2500\u00e0z\u253c\u00e9a<\/figcaption><\/figure>\n

Meer und Architektur
\n<\/strong>Bis zum R\u00fcckflug blieben uns noch ein paar Stunden. F\u00fcr einen Spaziergang an den Strand reichte es allemal. Zum Baden war das Mittelmeer schon etwas zu kalt, aber es war ideal zum Jassen im Sand. Auf dem Weg zum Flughafen machten wir noch einen kurzen Abstecher zur Ciudad de las Artes y de las Ciencias. Dieser moderne Museumskomplex steht im Flussbett des in den 1990er Jahren trocken gelegten R\u00edo Turia. Entworfen wurden die extravaganten Geb\u00e4ude vom valencianischen Architekten Santiago Calatrava, welcher \u00fcbrigens an der ETH Z\u00fcrich Bauingenieurwesen studierte und promovierte. Besonders bekannt sind seine skelettartigen Tragwerke und andere der Natur entlehnte Formen.<\/p>\n

\"Valencia\"<\/a>
Palau de les Arts Reina Sof\u00eda und L\u2019Hemisf\u00e8ric zwei der Geb\u00e4ude der Ciudad de las Artes y de las Ciencias<\/figcaption><\/figure>\n

Fazit
\n<\/strong>Wir hatten ein tolles Wochenende, viel Spass und erfreuliche Resultate. An dieser Stelle m\u00f6chten wir uns ganz herzlich bei unseren Coaches Jan H\u2500\u00e0z\u253c\u00e9a und Akaki Mamageishvili und bei allen weiteren fleissigen Mitglieder der ACM-VIS-Kommission [5] bedanken, welche unsere Teilnahme erst erm\u00f6glichten.<\/p>\n

Wenn du interessiert bist, n\u00e4chstes Jahr selbst mitzumachen oder mitzuhelfen, kontaktierst du am besten das ACM-Komitee unter acm@vis.ethz.ch. Es lockt eine Reise an den SWERC 2014 in Porto!<\/p>\n

Links:
\n<\/strong>[1] http:\/\/icpc.baylor.edu
\n[2] http:\/\/swerc.eu
\n[3] http:\/\/www.upc.edu
\n[4] http:\/\/en.wikipedia.org\/wiki\/Four_color_theorem
\n[5] http:\/\/www.vis.ethz.ch\/en\/about\/committees\/acm<\/p>\n","protected":false},"excerpt":{"rendered":"

Daniel Graf Programmieren als Wettbewerb? Die ACM (association for computing machinery) k\u00fcrt neben dem Turing Award Gewinner jedes Jahr auch das Team der besten Informatikstudierenden im algorithmischen Programmieren. Dies im Rahmen des ICPC, dem International Collegiate Programming Contest [1]. J\u00e4hrlich nehmen weltweit Tausende von Dreierteams an regionalen Wettbewerben teil und k\u00e4mpfen um einen der begehrten … <\/p>\n

Continue reading “SWERC 2013 Valencia Report”<\/span><\/a><\/p>\n","protected":false},"author":44384,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-332","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/blogs.ethz.ch\/acmicpc\/wp-json\/wp\/v2\/posts\/332","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ethz.ch\/acmicpc\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ethz.ch\/acmicpc\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/acmicpc\/wp-json\/wp\/v2\/users\/44384"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/acmicpc\/wp-json\/wp\/v2\/comments?post=332"}],"version-history":[{"count":0,"href":"https:\/\/blogs.ethz.ch\/acmicpc\/wp-json\/wp\/v2\/posts\/332\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.ethz.ch\/acmicpc\/wp-json\/wp\/v2\/media?parent=332"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/acmicpc\/wp-json\/wp\/v2\/categories?post=332"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/acmicpc\/wp-json\/wp\/v2\/tags?post=332"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}