計算機協會 國際大學生程式設計競賽 Association of Computing Machinery International Collegiate Programming Contest （ACM-ICPC）

Presentation on theme: "計算機協會 國際大學生程式設計競賽 Association of Computing Machinery International Collegiate Programming Contest （ACM-ICPC）"— Presentation transcript:

1 計算機協會 國際大學生程式設計競賽 Association of Computing Machinery International Collegiate Programming Contest （ACM-ICPC）

2 ICPC宗旨: 腦力之戰 (Battle of the Brains)
目的: 促進國際各大學學生之間的交流。 提供學生一個機會，在有限的時間之內，藉由解決精心設計的複雜難題，以鍛鍊和展現其本身解決問題、程式設計，以及團隊合作的能力。 發現和培養計算機科學頂尖學生。

3 歷史 競賽的歷史可以上溯到1970年，當時在美國德克薩斯農工大學(The Agricultural and Mechanical College of Texas)舉辦了首屆比賽，其主辦單位為the Alpha Chapter of the UPE Computer Science Honor Society。 競賽很快得到美國和加拿大各大學的積極響應。1977年，在計算機協會(Association of Computing Machinery, 簡稱ACM)的計算機科學會議期間舉辦了首次ACM主辦的總決賽，並演變成為目前的一年一屆的多國參與的國際性比賽。 電腦協會(Association of Computing Machinery, 簡稱ACM)是一個世界性的電腦從業員專業組織，創立於1947年，是世界上第一個科學性及教育性電腦學會。

4 歷史 (續) 1997年IBM開始贊助賽事，自此賽事規模增長迅速，當年總共有來自560所大學的840支隊伍參加比賽。而到了2004年，一共有840所大學的4109支隊伍參加比賽，並以每年10-20%的速度增長。 1980年代，ACM將競賽的總部設在位於美國德克薩斯州的貝勒大學(Baylor University)。 1989年建立區域(regional)賽制度，區域賽的優勝隊伍才能參加世界總決賽。

5 歷史 (續) 1991年亞洲首支隊伍(台灣交通大學) 參加世界總決賽。 1995年首度舉辦亞洲區域賽，在台灣舉行，由國立政治大學舉辦。
2002年上海交通大學獲得中國隊伍首度世界總決賽冠軍。 2005 年上海交通大學第二度獲得世界總決賽冠軍。 2010 年上海交通大學第三度獲得世界總決賽冠軍。

6 歷史 (續) 2010年台灣大學獲得世界總決賽第三名。 2011 年浙江大學獲得世界總決賽冠軍。
2012 年上海交通大學獲得世界總決賽第四名。 2013 年上海交通大學獲得世界總決賽第二名。 2013年台灣大學獲得世界總決賽第四名。 2014年北京大學獲得世界總決賽第三名。 2014年台灣大學獲得世界總決賽第四名。

7 競賽規則 ICPC 共分兩個階段: 6個區域賽區 區域賽 (Regional Contest) 世界賽 (World Final)
北美 (North America) 南美 (Latin America) 歐洲 (Europe) 非洲 (Africa) 亞洲 (Asia) 南太平洋 (South Pacific)

8 競賽規則(續) 每年區域賽的日期大約是前一年的九月至十二月，世界賽則是在當年三月至四月舉行。
每年各區域賽有若干站區的比賽，根據各賽區規則，每站前若干名的學校自動獲得參加全球總決賽的資格。

9 競賽規則(續) ACM-ICPC以團隊的形式代表各學校參賽，每隊由3名隊員組成。
一個大學可以有多支隊伍參加區域賽，但只能有一支隊伍參加世界賽。

10 競賽規則(續) 隊員為大學學生，或精確的說是接受大學教育五年內學生(students who have had less than five years of university education before the contest)，一般而言，大一到碩一的學生都可參加。 參加過5次區域賽或參加過2次世界賽的學生不可再參賽。

11 競賽規則(續) 比賽期間，每隊使用1台電腦，在5個小時內使用C、C++或Java編寫程式解決7到10個問題。
參賽者可攜帶任何書籍(包括字典)、手冊、紙本的程式碼。但不可攜帶機器可讀寫的任何軟體或資料，亦不可攜帶自己的電腦、終端機、計算機、電子字典或PDA，並嚴禁使用行動電話及呼叫器，以免干擾其他隊伍作答。

12 競賽規則(續) 程式完成之後提交裁判以判定程式運行的結果。 每隊在正確完成一題後，將在其位置上升起一隻代表該題顏色的氣球。
判定運行結果可能為: 正確: Accepted (AC) 成功解出問題 錯誤: Wrong Answer (WA) 程式成功執行結束，但輸出的資料不正確

13 競賽規則(續) 判定運行結果可能為 格式錯誤: Presentation Error (PE) 程式輸出資料正確，但格式上有點小誤差 ，如多了一些空白或跳行等 編譯錯誤: Compile Error (CE) 程式編譯時產生錯誤 執行時期錯誤: Runtime Error (RE) 程式執行時產生錯誤，如記憶體段錯誤(segmentation fault)或浮點數例外(floating point exception)等 提交錯誤: Submission Error (SE) 提交程式時產生錯誤，如提交程序操作錯誤(題號、使用者ID、使用語言沒填好)，或是提交資料毀損等

14 競賽規則(續) 判定運行結果可能為 超時: Time Limit Exceeded (TLE) 程式執行超過限定時間(大部份程式執行時間限定為十秒) 超出記憶體使用限制: Memory Limit Exceeded (MLE) 程式使用記憶體超過限制 超出輸出限制: Output Limit Exceeded (OLE) 程式產生太多資訊，一般為程式進入無窮迴圈

15 競賽規則(續) 最後的獲勝隊伍為正確解答題目最多，且總使用時間最少者。 每道試題的「使用時間」將從競賽開始到試題解答被判定為正確為止。
其間每一次提交運行結果被判錯誤的話，將被加罰20分鐘使用時間；但是若某一道試題未被正確解答，則其加罰時間不採計。

16 競賽規則(續) 舉例: A、B兩隊都正確完成兩道題目 A隊於比賽開始後1:00和2:45正確提交兩題
B隊於比賽開始後1:20和2:00正確提交兩題，但B隊有一題提交了2次(錯誤一次)。 B隊總用時為1:20+2:00+0:20=3:40 B隊以總用時少而獲勝。

17 台灣地區比賽 由「全國大專電腦軟體設計競賽」參賽隊伍中，擇優推薦甲組六至八隊
報名參加「 ACM 亞洲區台灣賽區大學電腦程式設計競賽」，角逐台灣地區 ACM 國際大學電腦程式設計競賽之決賽權，但各校不得超過兩隊。

18 獲勝秘訣 熟悉比賽使用之作業系統： 熟悉比賽使用之語言版本：
2014 World Final使用的作業系統為Fedora Core 4 Linux ，桌面為GNOME，編輯器為vi/vim、gvim、emacs、gedit 熟悉比賽使用之語言版本： 2014 World Final使用的語言為 Java: Version 1.7.0_25; OpenJDK Runtime Environment (IcedTea u ubuntu , OpenJDK 64-Bit Server VM (build 23.7-b01, mixed mode C/C++: GCC (Ubuntu/Linaro ubuntu5) 

19 獲勝秘訣 熟悉比賽使用之整合開發環境: 熟悉比賽使用之裁判程式: C/C++: CDT 8.2.1 under Eclipse 4.3.1
2014 World Final使用之整合開發環境為 Java: Eclipse 4.3.1 C/C++: CDT under Eclipse 4.3.1 熟悉比賽使用之裁判程式: Kattis contest control system 由瑞典皇家理工學院（英文名Royal Institute of Technology，瑞典語縮寫為KTH）所發展與維護。 PC2 (Programming Contest Control) system 由沙加緬度加州州立大學 (California State University, Sacramento)開發，在2008年之前的世界賽均採用這個系統，現今仍有許多人以此系統做為比賽訓練之用。

20 獲勝秘訣 培養團隊默契： 立定得分策略： 帶齊資料： 相互了解彼此的長處與短處 定好分工方式
因為ICPC賽事均以英文出題，因此至少一位隊員應積極培養英文閱讀能力。 立定得分策略： 先分工瀏覽全部試題，挑出有把握的題目，集中全力解決之 若手邊仍有一些可能解出的題目，則可以儘早放棄履遇挫折的題目。 帶齊資料： 參賽者可攜帶書籍、手冊、紙本的程式碼。但不可攜帶機器可讀寫的任何軟體或資料，亦不可攜帶自己的電腦、終端機、計算機、電子字典或PDA，並嚴禁使用行動電話及呼叫器，以免干擾其他隊伍作答。 記得帶一本好用的字典，以免無法理解題目。

21 獲勝秘訣 多準備並寫好常用的函式，或多使用內建函式庫或類別方法，以簡化程式設計並加速程式執行。 以下我們舉C++為例說明函式庫的使用。
C++ 語言除了提供C 語言的標準函式庫之外，還提供標準樣板函式庫(Standard Template Library, STL)。STL包含三個部份: 容器函式庫(containers library) 演算法函式庫(algorithms library) 迭代子函式庫(iterators library)

22 獲勝秘訣 容器函式庫(containers library): 提供不同的資料結構方便程式設計者使用，例如: vector、list, stack、set, hash_map, map, queue 及priority_queue 等。 演算法函式庫(algorithms library): 提供常用的資料結構操作，方便程式設計者使用，例如: find、sort、count 及copy 等。 迭代子函式庫(iterators library): 提供迭代中常用資料結構元素存取操作，方便程式設計者使用，例如: begin 及end 等。

23 獲勝秘訣 我們舉以下C++ 程式片段為例來看STL 的用法:

24 獲勝秘訣 多透過Online Judge進行題目練習 Universidad de Valladolid Online Judge
Ural State University Online Judge Tianjin University Online Judge Saratov State University Online Judge Sphere Online Judge ACM-ICPC Live Archive Around the World MIPT Online Judge Peking University Online Judge Zhejiang University Online Judge Harbin Institute of Technology Online Judge Fuzhou University Online Judge Online Problems Solving System

25 ACM 10041 Vito’s Family

26 題目: Background Problem
The world-known gangster Vito Deadstone is moving to New York. He has a very big family there, all of them living in Lamafia Avenue. Since he will visit all his relatives very often, he is trying to find a house close to them. Problem  Vito wants to minimize the total distance to all of them and has blackmailed you to write a program that solves his problem.

27 Input & output Input Output
The input consists of several test cases. The first line contains the number of test cases. For each test case you will be given the integer number of relatives r ( 0 < r < 500) and the street numbers (also integers) where they live ( 0 < si < ). Note that several relatives could live in the same street number. Output  For each test case your program must write the minimal sum of distances from the optimal Vito's house to each one of his relatives. The distance between two street numbers si and sj is dij= |si-sj|.

28 Sample input & output Sample Input  Sample Output  2 4

29 Lucky貓的 UVA（ACM）園地的翻譯 (http://luckycat.kshs.kh.edu.tw/)
維托家族 世界聞名的黑社會老大Vito Deadstone要搬到紐約來了。在那裡他有一個大家族，並且他們都住在Lamafia大道上。因為Vito時常要拜訪所有的親戚，他想要找一間離他們最近的房子，也就是說他希望從他的家到所有的親戚的家的距離的和為最小。 他恐嚇你寫一個程式來幫助幫助他解決這個問題。

30 Lucky貓的 UVA（ACM）園地的翻譯 (http://luckycat.kshs.kh.edu.tw/)
Input 輸入的第一列有一個整數代表以下有多少組測試資料。 每組測試資料一列，第一個整數 r（0 < r < 500），代表他親戚的數目。接下來的r個整數s1,s2,......sr為這些親戚房子的門牌號碼（0 < si <30000）。 注意：有些親戚的門牌號碼會相同。

31 Lucky貓的 UVA（ACM）園地的翻譯 (http://luckycat.kshs.kh.edu.tw/)
Output 對每一組測試資料，輸出從他的新家到所有的親戚的家的距離的和為最小為多少。2個門牌號碼si、sj的距離為si-sj的絕對值。

32 題目建模(抽象的重新描述問題) 給定一個陣列 A[i], i = 0,…,n 找出 k, 使得 S= 的值最小 輸出此最小值S

33 作法簡介 找出中位數(median)為所選整數，再計算所有元素與中位數的差的總和即為解答 給定一個陣列 A[i], i = 0,…,n -1
當 n 為奇數時，中位數為 A[n/2]; 當 n 為偶數時，中位數為 (A[(n − 1)/2] + A[(n + 1)/2])/2 。 不過因為題目的輸出為所有元素與中位數的差的總和，因此我們不論選中位數、A[(n − 1)/2]或是A[(n + 1)/2] 所得到的輸出結果都相同。 當 n 為偶數時， A[(n + 1)/2]=A[n/2]。因此，我們以 A[n/2] 為所選整數，如此不管 n 為奇數或是偶數都可以產生正確解答。

34 中文Java程式碼: Vito.java

35 Java程式碼: Vito1.java

36 C++程式碼: Vito.cpp

37 C++程式說明 以上Vito.cpp程式中，我們使用C++ 語言 STL 的vector 集合變數(collection variable)解題。 我們並使用執行速度比sort 函式還快的nth_element 函式來找出中位數。 透過使用nth_element(begin, begin+n, end) 函式呼叫，可以使排序為n 的元素處於位置n(排序從0 開始計算)，並且比這個元素小的元素都排在這個元素之前，比這個元素大的元素都排在這個元素之後，但是這個元素前後的元素並未依序排列。 透過使用sort(begin, end) 函式呼叫，可以將所有的元素依序排序，因此排序為n 的元素自然會處於位置n。

38 C++程式說明(續) 一般而言，排序演算法的時間複雜度為O(s log s)，而nth_element 函式的時間複雜度為O(s)，其中s為輸入規模(input size)，也就是需要處理的元素總個數。 (一般輸入規模使用n 來表示，在此處我們使用s 來表示以避免與nth_element 函式中的n 產生混淆。)

39 UVa Judge 操作畫面 UVa Judge由西班牙 University Valladolid維護，是最古老也是最知名的Online Judge。 題庫目前約有4000多題，除了收集自行舉辦比賽的題目之外，也收錄ACM ICPC與世界各地重大程式設計比賽題目。 有許多相關書籍與相關網站: Steven S. Skiena and Miguel Revilla, Programming Challenges, Elsevier, 2003.  Lucky貓的ACM園地、Lucky貓的 ACM 中譯題目 Mirror

40

41

42

43

44

45

46

47

48

49

50

51

52

53 Q&A