Post on 25-Feb-2021
transcript
Tobias FriedrichFSU Jena
Worldwide Programming ContestsEin Insider-Report
19.01.2004 T. Friedrich 2
Inhalt
Offline Contests• Bundeswettbewerb Informatik• ACM ICPC
Online Contests• Valladolid Online Judge• TopCoder
VergleichBeispielaufgaben
19.01.2004 T. Friedrich 3
Inhalt
Offline Contests• Bundeswettbewerb Informatik• ACM ICPC
Online Contests• Valladolid Online Judge• TopCoder
VergleichBeispielaufgaben
19.01.2004 T. Friedrich 4
Bundeswettbewerb Informatik
nur für Jugendliche bis 21 Jahre1. Runde: 5 leichte Aufgaben (zu Hause)2. Runde: 3 schwere Aufgaben (zu Hause)3. Runde: Kolloquium (30 Besten)
Preise: Geld, Sachpreise,Sprachreisen, Stipendien
19.01.2004 T. Friedrich 5
Bundeswettbewerb Informatik
Aus den Endrundenteilnehmern werden Teamsfür internationale Wettkämpfe gestellt:
• IOI (International Olympiad in Informatics)
• CEOI (Central European Olympiad in Informatics)
• BOI (Baltic Olympiad in Informatics)
19.01.2004 T. Friedrich 6
BWInf – Teilnehmerzahlen
Entwicklung seit 1984:
0
500
1000
1500
2000
2500
3000
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
19.01.2004 T. Friedrich 7
BWInf – Teilnehmerzahlen
Rückläufige Entwicklung seit 1997:1200
1000
800
600
400
200
0
2003
2002
1997
1998
1999
2000
2001
19.01.2004 T. Friedrich 8
Inhalt
Offline Contests• Bundeswettbewerb Informatik• ACM ICPC
Online Contests• Valladolid Online Judge• TopCoder
VergleichBeispielaufgaben
19.01.2004 T. Friedrich 9
ACM - Association for Computing Machinery
älteste und größte Informatik-Gesellschaftgegründet 1947≥ 75.000 Mitglieder weltweit≥ 25 Zeitschriften≥ 100 Tagungen/JahrACM Digital LibraryACM Press Books (gemeinsam mit AddisonWesley und Longman Publishing Company)
19.01.2004 T. Friedrich 10
ACM-Publikationen (Auswahl)Communications of the ACM (CACM)Computers in Entertainment (CIE)Computing ReviewsComputing SurveysJournal of the ACM (JACM)Transactions on Architecture and Code Optimization (TACO)Transactions on Computational Logic (TOCL)Transactions on Computer-Human Interaction (TOCHI)Transactions on Computer Systems (TOCS)Transactions on Database Systems (TODS)Transactions on Embedded Computing Systems (TECS)Transactions on Graphics (TOG)Transactions on Information and System Security (TISSEC)Transactions on Information Systems (TOIS)Transactions on Internet Technology (TOIT)Transactions on Mathematical Software (TOMS)Transactions on Modeling and Computer Simulation (TOMACS)IEEE/ACM Transactions on Networking (TON)Transactions on Programming Languages and Systems (TOPLAS)Transactions on Software Engineering and Methodology (TOSEM)
19.01.2004 T. Friedrich 11
ACM International CollegiateProgramming Contest (ICPC)
Veranstaltet von der ACM
Ursprung: 1970 in Texas als Lokaler Wettbewerb der Upsilon Pi Epsilon (ΥΠΕ) Computer Science Honor Society
seit 1977 mehrstufiger US-Wettbewerb
seit 1980 weltweit
seit 1997 IBM Hauptsponsor
19.01.2004 T. Friedrich 12
ACM ICPC – Entwicklung
seither kontinuierlicher Wachstum derTeilnehmerzahlen (30% p.a.):
19.01.2004 T. Friedrich 13
27th ACM ICPC 2002/2003
23.000 Studenten
3.850 Teams
1.329 Universitäten
106 Regional Contests
68 Länder
6 Kontinente
1 Weltmeister
19.01.2004 T. Friedrich 14
ACM ICPC – Ablauf
100.000 Studenten
3.850 Teams
70 Teams
Local Contest
Regional Contest
World Final
Erst- und ggf. Zweiplazierte kommen weiter
beste Studenten bilden Team
19.01.2004 T. Friedrich 15
ACM ICPC – Ablauf Regional Contest
Lesen/Überlegen
Programmieren
Submitten
19.01.2004 T. Friedrich 16
ACM ICPC – Jenaer Teilnahmen
1994 ETH Zürich, Schweiz
2000 Freiburg, Deutschland
2001 Porto, Portugal
2002 Warschau, Polen
2003 Paris, Frankreich
19.01.2004 T. Friedrich 17
ACM ICPC Weltmeister 2003
Warsaw University (Poland), Beverly Hills
19.01.2004 T. Friedrich 18
ACM ICPC Weltmeister 1984
University of Alberta (Canada), Atlantic City Playboy Club
19.01.2004 T. Friedrich 19
ACM ICPC World Finals
2004 Prague, Czech Republic2003 Beverly Hills, CA, USA
Winner: Warsaw University, Poland2002 Honolulu, Hawaii
Winner: Shanghai JiaoTong University, China2001 Vancouver, Kanada
Winner: St. Petersburg State University, Russia2000 Orlando, Florida, USA
Winner: St. Petersburg State University, Russia
19.01.2004 T. Friedrich 20
ACM ICPC – Wordfinals Prizes
1st (World Champion): $10.000
2nd-4th (Gold Medaille): $3.000
5th-8th (Silber Medaille): $2.000
9th-12th (Bronze Medaille): $1.000
+ Stipendien
+ “Ruhm und Ehre“
19.01.2004 T. Friedrich 21
ACM ICPC – Deutsche Teilnehmer
Ulm München
Erlangen
Jena
Bruchsal
Oldenburg Bremen
Darmstadt
Lübeck
Karlsruhe
Deutsche Universitäten bei den ACM ICPC Regionals 2003
19.01.2004 T. Friedrich 22
ACM ICPC – Deutsche Teilnehmer
Ulm (7) München (2)
Erlangen (1)
Jena (3)
Bruchsal (1)
Oldenburg (5) Bremen (1)
Darmstadt (1)
Lübeck (1)
Karlsruhe (3)
Deutsche Universitäten bei den ACM ICPC Regionals 2003
In Klammern: Anzahl der gelösten Aufgaben
19.01.2004 T. Friedrich 23
Inhalt
Offline Contests• Bundeswettbewerb Informatik• ACM ICPC
Online Contests• Valladolid Online Judge• TopCoder
VergleichBeispielaufgaben
19.01.2004 T. Friedrich 24
Valladolid Online Judge Problemset
betrieben an der Universidadde Valladolid (Spanien) von Prof. Miguel Revilla auf acm.uva.esüber 1200 Probleme online24h Judge, Online-Contestsanalog an anderen Unis:
Ural State Univ acm.timus.ru (282)Saratov State Univ acm.sgu.ru (225)Zhejiang Univ acm.zju.edu.cn (1065)
19.01.2004 T. Friedrich 25
Valladolid Online Judge Problemset
19.01.2004 T. Friedrich 26
Valladolid Online Judge – Contest
19.01.2004 T. Friedrich 27
Valladolid Online Judge – Contest
19.01.2004 T. Friedrich 28
Valladolid Online Judge – Contest
19.01.2004 T. Friedrich 29
Valladolid Online Judge – Contest
19.01.2004 T. Friedrich 30
Valladolid Online Judge – Contest
19.01.2004 T. Friedrich 31
Valladolid Online Judge – Contest
19.01.2004 T. Friedrich 32
Valladolid Online Judge – Herkunftgelöste Probleme Nutzer pro
Rang Land Nutzer pro Nutzer 1 Mio Einwohner1 Taiwan 5474 16 2422 Bangladesh 5232 17 383 China 4548 11 44 USA 3826 6 135 Russia 1965 13 14
7 Poland 1270 14 338 Canada 970 12 30
6 Brazil 1936 12 11
9 Indonesia 942 15 410 Hong Kong 921 20 12511 India 853 4 1
13 Spain 756 6 1914 Singapore 668 18 145
12 South Korea 758 14 16
15 Portugal 556 12 5516 Germany 547 19 717 Japan 536 20 418 France 532 6 919 Mexico 473 4 520 Romania 469 6 21
19.01.2004 T. Friedrich 33
Valladolid Online Contests
C++
Pascal
CJava
verwendete Programmiersprachen in Online-Contests80%
60%
40%
20%
0%2001 2002 2003
19.01.2004 T. Friedrich 34
Inhalt
Offline Contests• Bundeswettbewerb Informatik• ACM ICPC
Online Contests• Valladolid Online Judge• TopCoder
VergleichBeispielaufgaben
19.01.2004 T. Friedrich 35
TopCoder.com
Gründung 2001 von Jack Hughes36.000 Mitglieder aus ≥150 Länderje Monat 1.300 neue Mitglieder300% mehr Teilnehmer bei Online-Wettbewerben 2002 (im Vergleich zu Vorjahr) Jack Hughes
19.01.2004 T. Friedrich 36
TopCoder – Sponsoren
19.01.2004 T. Friedrich 37
TopCoder – Aktivitäten
Contests• Single Round Matches (SRM)• Tournaments• „Powered by TopCoder™“ Competitions• Private Label Competitions
Development• Software Components• Application Development
19.01.2004 T. Friedrich 38
TopCoder – Contests
„My adrenalinewas flowing
and I really gotabsorbed in
the problems“
Zitat von TopCoder-Member „dmwright“
19.01.2004 T. Friedrich 39
TopCoder – Contests
„My adrenalinewas flowing
and I really gotabsorbed in
the problems“ Daniel WrightEarnings: $157.196
19.01.2004 T. Friedrich 40
TopCoder – Single Round Match
1. Coding Phase (75 min)
2. Intermission (5 min)
3. Challenge Phase (15 min)
4. Automated Testing Phase (≈5 min)
19.01.2004 T. Friedrich 41
TopCoder – Single Round Match
19.01.2004 T. Friedrich 42
TopCoder – Single Round Match
19.01.2004 T. Friedrich 43
TopCoder – Single Round Match
19.01.2004 T. Friedrich 44
TopCoder – Single Round Match
19.01.2004 T. Friedrich 45
TopCoder – Single Round Match
19.01.2004 T. Friedrich 46
TopCoder – Single Round Match
19.01.2004 T. Friedrich 47
TopCoder – Single Round Match
19.01.2004 T. Friedrich 48
TopCoder – Single Round Match
19.01.2004 T. Friedrich 49
TopCoder – Single Round Match
19.01.2004 T. Friedrich 50
TopCoder – Mitgliederentwicklung
Wachstum der Mitgliederzahl seit März 2001:
0
5000
10000
15000
20000
25000
30000
Mar'01 May JulJul Mar Mar MayMay
Professionals: 11,532
Students: 15,663
Total Members:
27,195 (as of May 31st)
Sep Nov Jan'02 Sep Nov Jan'03
19.01.2004 T. Friedrich 51
TopCoder – aktive MitgliederMehrheitlich aus den USA: 3268 Students, 2065 Professionals.Die übrigen Mitglieder verteilen sich wie folgt:
400
350
300
250
200
150
100
50
0
Canad
a
India
China
United K
ingdom
Austra
liaGer
man
y
Russian
Feder
ation
Sweden
Roman
ia
Brazil
Professionals
Students
19.01.2004 T. Friedrich 52
TopCoder – Mitgliederverteilung
Verteilung der Top20 bei der TopCoder Open 2003:
19.01.2004 T. Friedrich 53
TopCoder – Tournaments
Ablauf TopCoder Open:
1. Online rounds
2. Onsite rounds
2 Qualification rounds4 Elimination rounds
Semifinal roundChampionship round
19.01.2004 T. Friedrich 54
TopCoder Open
Onsite:1st place: $50,0002nd place: $15,0003rd place: $5,0004th place: $3,0005th-16th (Semifinalists): $1,000 each
Online:Online Round #4: $100 each (50x)Online Round #3: $50 each (100x)Online Round #2: $25 each (200x)
19.01.2004 T. Friedrich 55
TopCoder Open – The Winner
19.01.2004 T. Friedrich 56
TopCoder – Tournaments
Ablauf TopCoder Collegiate Challenge:
1. Online rounds
2. Onsite rounds (24 finalists)
Februar/März 2004
April 2004 in Boston, USA
19.01.2004 T. Friedrich 57
TopCoder Collegiate Challenge
2004 – Ein Jenaer???
19.01.2004 T. Friedrich 58
TopCoder – Sprachen
C++116.000h online
C#6.000h online
Java161.500h online
Professionals70,607 hrs
Students90,934 hrs
Professionals34,254 hrs
Students81,971 hrs Professionals
3,875 hrs
Students2,209 hrs
Zeitraum: 2.12.2001-31.5.2003
19.01.2004 T. Friedrich 59
Inhalt
Offline Contests• Bundeswettbewerb Informatik• ACM ICPC
Online Contests• Valladolid Online Judge• TopCoder
VergleichBeispielaufgaben
19.01.2004 T. Friedrich 60
Vergleich
Teamwork Teams von je 3 Studenten nur Einzelkämpfer
Teilnehmer nur Studenten 42% Professionals, 58% Studenten
Dauer 5 Stunden 75min (Stress!!)
Aufgaben neun gleichgewichtete drei in versch. Schwierigkeitsstufen
Response sofort am Ende
Häufigkeit einmal im Jahr jede Woche (Single Round Matches)
Preisgeld Weltmeister $10.000 bis zu $100.000 (Tournament)
Code bleibt geheim anschließend einsehbar
Peer Review nein ja, inkl. "Challenge Phase"
Sprachen C, C++, Pascal, Java C++, Java, C#, VB.Net
Chat persönlich online
Offline (ACM ICPC) Online (TopCoder)
19.01.2004 T. Friedrich 61
Inhalt
Offline Contests• Bundeswettbewerb Informatik• ACM ICPC
Online Contests• Valladolid Online Judge• TopCoder
VergleichBeispielaufgaben
19.01.2004 T. Friedrich 62
Arten von Aufgaben
Graphenprobleme (kürzeste Weg, MST, Zyklus)
Backtracking (8-Damen-Problem, Springertour)
Geometrie (Konvexe Hülle, Schnitte)
Dynamische Programmierung (Rucksackproblem)
Zahlentheorie (Primzahlen, Teilersummen, Zerlegungen)
Parser/Compilerbau (arith. Auswertung, TeX-Quotes)
Sonstige
19.01.2004 T. Friedrich 63
Beispiel 1: Simple Calculator
Problem StatementA simple calculator accepts the following kinds of strings as input:
1) NUM+NUM 2) NUM-NUM 3) NUM*NUM 4) NUM/NUM
where NUM is a positive integer, between 1 and 10000 inclusive that can contain leading zeros. Return the value produced by the given expression. Here +,-,*, and / denote addition, subtraction, multiplication and division respectively. All operations are done on integers, so "5/3" returns 1.
19.01.2004 T. Friedrich 64
Beispiel 1: Simple Calculator
Definition
Class: SimpleCalculatorMethod: calculateParameters: StringReturns: intMethod signature: int calculate(String input)(be sure your method is public)
19.01.2004 T. Friedrich 65
Beispiel 1: Simple Calculator
Examples
0) "5/3" Returns: 1Remember integer division is used, so results are truncated.
1) "15*3" Returns: 45
2) "1-10000" Returns: -9999Negative results are allowed.
3) "17+18" Returns: 35
4) "00018/0009" Returns: 2The long way of writing 18/9.
19.01.2004 T. Friedrich 66
Beispiel 1: Simple Calculator
Solution (Java)public class SimpleCalculator {
public int calculate(String input) {String[] nums = input.split("[+*-/]");char op = input.charAt(nums[0].length());int x = Integer.parseInt(nums[0]),
y = Integer.parseInt(nums[1]);if (op == '+') return x+y;if (op == '-') return x-y;if (op == '*') return x*y;if (op == '/') return x/y;return 0;
}}
19.01.2004 T. Friedrich 67
Beispiel 2: Farey sequences
Problem Statement
A fraction h/k is called a proper fraction if it lies between 0 and 1 and if h and k have no commonfactors. For any natural number n≥1, the Fareysequence of order n, Fn, is the sequence of all proper fractions with denominators which do not exceed ntogether with the "fraction" 1/1, arranged in increasing order. So, for example, F5 is thesequence:
1 1 1 2 1 3 2 3 4 1-, -, -, -, -, -, -, -, -, -.5 4 3 5 2 5 3 4 5 1
19.01.2004 T. Friedrich 68
Beispiel 2: Farey sequences
Problem StatementF1 =[0/1, 1/1]F2 =[0/1, 1/2, 1/1]F3 =[0/1, 1/3, 1/2, 2/3, 1/1]F4 =[0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1]F5 =[0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1]F6 =[0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1]
Fn =[0/1, 1/n, ... ..., (n-1)/n, 1/1]
k
geg.: (n,k)ges.: kter Bruch in Folge Fn
19.01.2004 T. Friedrich 69
Beispiel 2: Farey sequences
Input/Output
For a given n, you are to find the kth fraction in thesequence Fn. Input consists of a sequence of linescontaining two natural numbers n and k, 1≤n≤1000 and ksufficiently small such that there is the kth term in Fn. For each line of input print one line giving the kth element of Fnin the format as below.
5 55 15 95 10117 348288 10000
1/21/54/51/19/10978/197
input output
19.01.2004 T. Friedrich 70
Beispiel 2: Farey sequences
Solution (C++)struct bruch {private:int zaehler, nenner;public:bruch(int zaehler, int nenner) {
this->zaehler=zaehler;this->nenner=nenner;
}inline bool operator<(const bruch& b) const {
return (zaehler*b.nenner < b.zaehler*nenner);}inline friend ostream& operator<<(ostream& os, const bruch& s) {
return os << s.zaehler << "/" << s.nenner;}
};
19.01.2004 T. Friedrich 71
Beispiel 2: Farey sequences
Solution (C++)
int main() {int n, k;while (cin >> n >> k) {
vector<bruch> num;for (int nenner=1; nenner<=n; nenner++)
for (int zaehler=1; zaehler<=nenner; zaehler++)if (ggt(nenner,zaehler)==1)
num.push_back(bruch(zaehler,nenner));nth_element(num.begin(), num.begin()+(k-1), num.end());cout << num[k-1] << endl;
}}
19.01.2004 T. Friedrich 72
Beispiel 2: Farey sequences
Solution (C++)int ggt(int a, int b) { return b ? ggt(b,a%b) : a; }int main() {int n, k;while (cin >> n >> k) {
vector<bruch> num;for (int nenner=1; nenner<=n; nenner++)
for (int zaehler=1; zaehler<=nenner; zaehler++)if (ggt(nenner,zaehler)==1)
num.push_back(bruch(zaehler,nenner));nth_element(num.begin(), num.begin()+(k-1), num.end());cout << num[k-1] << endl;
}}
19.01.2004 T. Friedrich 73
Beispiel 2: Farey sequences
Statistik
Total submissions 996Accepted 585Presentation Error 1Wrong Answer 80Runtime Error 101Time Limit Exceeded 110Memory Limit Exceeded 19Output Limit Exceeded 1Compile Error 98Restricted Function 1
19.01.2004 T. Friedrich 74
Zusammenfassung
wichtigste Wettbewerbe: BWInf, ICPC, Valladolid, TopCoder
zu gewinnen: Ruhm, Geld, Job, Spaß
zu erlernen: (Programmier-)Sprachen, Algorithmen, SWT, Tricks
kennenzulernen: interessante Teilnehmer
Vielen Dank fürIhre Aufmerksamkeit!
Worldwide Programming ContestsEin Insider-Report
Fragen ?
Worldwide Programming ContestsEin Insider-Report
Wichtige Adressen
Worldwide Programming ContestsEin Insider-Report
ICPC: www.acm.org/contest
psc.informatik.uni-jena.de/ICPC.htm
Valladolid: acm.uva.es/problemset
TopCoder: www.topcoder.com
E-Mail: T.Friedrich@uni-jena.de
19.01.2004 T. Friedrich 78
TopCoder – Professionals