TOPC 程式競賽命題須知

tags: TOPC ICPC Competitive Programming

要繳交的檔案與資訊

• 題目為英文，但如果沒有信心可以用中文敘述。建議使用 LaTeX，如有使用特別的 package 請先詢問，非 LaTeX 會盡量幫忙轉。

  1. Problem statement (statement.tex)
  2. Input Format (input.tex)
  3. Output Format (output.tex)
  4. Technical Specification (spec.tex)
  5. (Optional) Hint (hint.tex)
  6. (Optional) Note (note.tex)
  7. 範例檔連結
     • 範例是交大競技程式設計用的考題模板，日後會改為比賽用的。
     • 建議安裝 TeX live 進行編譯，在 tex 使用 make 即可生成 main.pdf
     • tex/A, …, tex/H 目錄下為題目檔案範例
     • main.tex 中，\problem{A}{Area}{2}{512} 可以指定以 A 目錄下的資料來生成題目，題目名稱為 Area，時間限制為 2 seconds，記憶體限制為 512 megabytes。

• DOMjudge格式之測試資料與範例程式

  1. data/sample 下放範例測試資料，會顯示在題面上，必須以 .in 命名輸入，以 .ans 命名輸出檔，主檔名必須成對，如 1.in 配 1.ans。可多檔案。
  2. data/secret 下放祕密測試資料，不會顯示在題面上，必須以 .in 命名輸入，以 .ans 命名輸出檔，主檔名必須成對，如 secret.in 配 secret.ans。建議採多檔案，單一檔案單一測試資料。
  3. submissions/accepted 下放範例解答程式。
  4. (Optional) submissions/wrong_answer 下放輸出錯誤的範例程式。
  5. (Optional) submissions/time_limit 下放超時的範例程式。
  6. (Optional) submissions/memory_limit 下放記憶體超量的範例程式。
  7. 範例檔連結

• 除了題目本身之外，

  1. Source: 題目來源
  2. Limits: 時間限制與記憶體使用量限制
  3. Brief desciption of the solution
  4. (Optional) Brief description of the tests
  5. Estimate of the difficulty
     • Very hard (0~3%)
     • Hard (3~20%)
     • Medium (20~50%)
     • Easy (50%~80%)
     • Very easy (80%~97%)
     • Registration (97~100%)

題目來源

不要求完全使用原創題目，但請大家盡可能標示題目來源，如原創、來自書籍、網站、論文等等，參考自網站的題目請加上修改程度，以便我們判斷題目是否適合直接使用，或是需要進行修改。

題目敘述

• 請盡量控制在兩頁以內，理想情境是statement.tex的篇幅不要超過一頁。
• 請適度包裝題目，盡量避免簡單裸題跟難度全在閱讀的題目。
• 請避免特定族群能比較快理解題目內容的題面，如西洋棋、圍棋、數獨、麻將等等。
• 請盡量避免會冒犯到特定族群的內容。
• 如果題目難度較高但有 Closed-form solution 的話，請在解法文件說明。

資源限制

根據 ICPC World Finals 的規定，C / C++ / Java / Kotlin 均需要能通過，因此時間與記憶體的限制需要仔細設置。

• 時間限制：至少一秒鐘，原則上為C/C++範例程式的5倍，Java/Kotlin範例程式的2倍。
• 記憶體限制：通常不限制，太嚴格可能會無法妥善設置。
• 其他限制：
  • 編譯後的檔案大小可有全域性限制，可限制但不宜過嚴
  • 編譯時間有全域性的限制，建議不要限制
  • 編譯時記憶體使用量有全域性限制，建議不要限制
  • 不建議出實做需要至少 500 行程式碼的題目。

輸出入

• 請不要出只要輸出答案的題目。
• 請盡量使用單純的輸出入格式，除非跟題目核心概念有關。
• 除非必要，請不要在測試資料裡面放 trailing space 或空白行。
• 測試資料組數不超過30個時，請盡量使用一檔案一組測試資料的格式。
• 單一檔案有多筆測試資料時，請在輸入檔的第一行指定測試資料個數。
  • 請不要使用 EOF 結尾、0結尾、或是特殊字串結尾的格式。
• 關於特定形式的測試資料，如祕密測試資料中沒有，且與解題手法有關，請在題敘說中說明。如果在測試資料中有，則可說明也可不說明。
  • 如一個平面幾何題，測試資料中沒有三點共線，且會影響到解題方法的設計，就需要在題敘說明「沒有三點共線」。如果有三點共線的測試資料，可以自由選擇是否說明。
  • 如果是屬於需要說明的情形，賽中被詢問時，需要正確回應。
• 如果輸出值是一個浮點數，則必須標示所需的精確度。
  • DOMjudge 會提供 special judging
  • 除非答案唯一，否則不建議寫「輸出到小數下第幾位」
• 測試資料大小請先控制在輸出輸入單一檔案128MB以下，總體測試資料請控制在 256MB 以下，如果非得出超過，請先與題組負責人聯繫。

特殊判定

通常我們會使用 DOMjudge 內定的檢查程式來判斷輸出是否與答案相符，如果內定的就夠用，可跳過本節。

如果需要自己來寫，請務必確認以下條件：

1. 能透過程式的 argument 取得對應資料的檔案名稱。
2. 在答案正確時，程式的 return code 是 42："Answer to the Ultimate Question of Life, the Universe, and Everything"
3. 在答案錯誤時，程式的 return code 是 43。
4. 不可以有其他的 return code ，包括程式被弄當時。
5. 範例稍後再補。

範例解答

• 請適度撰寫註解。
• 請避免針對特定測試資料進行最佳化，除非是顯而易見的極端測試資料。
• 適用於所有測試資料的最佳化，如輸出入、資料結構實做等等，在命題實務上均可運用。但使用多個最佳化技巧時，請謹慎評估執行時間上限，以免 Kotlin 與 Java 在時限無法通過。