<style> .reveal .slides { text-align: left; font-size:28px; } </style> # Polygon 網址：https://polygon.codeforces.com/ 建議要出題競賽程式的題目使用 polygon 出題，一開始是設計給 codeforces 用的出題網站。因為功能完整方便，許多主流比賽，包括IOI或者大學校內賽都題目都是使用 polygon 出題。 出好的題目可以下載套過一些套件轉檔成 domjudge 格式或者直接上傳至 codeforces。 Polygon 跟 Codeforces 帳號是獨立的 ---- ## 出題流程 主要有以下的內容 - Statement (題目) - 題序 - 輸入、輸出格式 - Solution files (各種結果的程式碼) - Generator (產測資的程式) - Tests (設定各種不同的參數、case，並用 generator 產出來) - Validator (驗證測資正確性的程式) - Checker (驗證輸出正確性的程式) --- ## Statement 題目題序(Legend)、輸入輸出格式、測資範圍(Input/Output format) 需要數學式等可以插入 latex ，用兩個錢字號($)包起來 題序中的 sample input/output 會在 tests 的部分講解  ---- 小規定 如果題目有很多變數，輸入範圍等等，請額外再後面一起放   --- ## Solution files 放你的 AC 程式碼，以及想測 TLE 或者 WA 等結果的可以分別上傳並標記不同結果 建議所有可能會出現的結果都要寫一份 code 以及假都要放上來測試  --- ## testlib.h 許多程式競賽的出題都會用到這個工具 [testlib.h](https://codeforces.com/testlib) 主要有以下四個功能 - Generator，產測資時用到 - Validator，驗證測資是否正確 - Interactor，互動題編寫 - Checker，寫 Special Judge --- ## Generator 通常測資不會直接上傳 .in .ans 等檔案，而會是上傳一個產測資的 code 他會直接線上產測資 以下是題目 [Orz](https://codeforces.com/gym/369935/problem/J) 的 generator  根據你的參數(以這題為例是 t,l,r,type 生出不同的測資) gen -t -10 -l 1 -r 2 -type random > $ (gen為你的產測資檔案(gen.cpp))  --- 可以根據不同傳進去的參數去產出想要的測資，這個是比較簡單題目的，通常會分一堆case 大概平均都會寫個百行 像是圖論題目來說，可能就要分有自環、重邊、仙人掌圖、菊花圖、樹、單環、鍊不連通圖...等等case去分別產出 所以...要生出好測資很難 QQ --- ## Validator 驗證你產出來的測資 Test input 是符合題目測資限制範圍的 以下為題目 [Frozen Scoreboard](https://codeforces.com/gym/369935/problem/F) 的 Validator  ---- 判斷是否符合題目限制，以 Frozen Scoreboard 這題為例 - 輸入的 n 在 1-1000 - 輸入的 時間為2位數且都是 0-9 - 每一題的 CORRECT 數量最多只出現一次 - 狀態只有 CORRECT, WRONG-ANSWER...等 以上等等 可以用正則表達式判斷是否符合輸入限制 記得每個空白、換行以及 EOF 都要判斷 --- ## Checker 驗證結果與正解是否一樣或符合答案 有幾個預設的 checker - 嚴格比對(fcmp) - 寬鬆比對(ncmp) - 判斷 yes/no 無視大小寫(nyesno) - 判斷答案在精度內(rcmp) 如果題目是 special judge 則需要自己寫 checker 可以參考 testlib.h ---- ## testlib.h for domjudge 如果題目是自己寫的 checker 要放到 domjudge 上面記得 testlib.h 要換成 for domjudge 的 https://github.com/cn-xcpc-tools/testlib-for-domjudge 否則會造成 Internal errors --- ## Tests 根據你的 Generator 給不同參數，產出可能造成 WrongAnswer, TimeLimitExceed 等等的測資 Tests 的測資是根據你的參數 Hash 之後產出來的結果 因此要用同一種參數 後面要多加一些額外的參數  以上為使用 gen 這個 generator 產出 n 為 xxx v 為 xxx.. 的測資 ---- 範例測資以及一些特殊測資也可以直接上傳檔案 如果是範例測資記得在 Use in statement 打勾  --- ## Stresses 對拍 可以用 generator 產出指定範圍的測資，用兩個程式(一個為AC code,另一個假解) 去跑測資 會不斷產random測資直到找到一組測資，使得對出來的答案不同或者使得TLE為止，可以把對拍到的加進去測資裡  以上圖為例產出 n 在 30-40之間的 ... 等參數，後面的 Countertest 是一筆找到錯的測資 --- ## Invocation 會跑指定的solution以及指定的測資，會跑出所有結果可以看是否符合預期  而可以發現結果有些底色為藍色或橘色 是提示執行時間與題目時間限制(TL)相近  橘色代表執行時間與TL相差在兩倍以內，藍色為在三倍以內 Polygon 會希望你設的TL與正解的code應該設在兩倍以上否則或時間卡太緊很危險 以及如果應該TLE的程式碼只差在兩倍以內也怕會被剪枝過 --- ## Packages 題目都產好之後如果要放 domjudge 等，先 commit 後就可以按 package 打包下來記得按 full 才會有完整測資 如果是用 windows 系統就按 windows 而如果有上面的 test, solution, validator 沒處理好的他不會讓你 package 一定要先確保都處理完才能用  打包下來後可以使用 [p2d](https://github.com/rjalfa/polygon2domjudge) 轉檔後 就可以直接丟 domjudge 的 problem achieve 了 記得 special judge 等要額外處理，細節會在 domjudge 教學那邊再介紹 --- ## 總結 以上為大概介紹，基本上出題需要的功能都有了 ### 優點 - 題目品質佳 - 上傳至 domjudge 或 codeforces 方便 ### 缺點 - 處理的時間比較多 ---- ## useful tools ### Graph Editor(for graph) https://csacademy.com/app/graph_editor/ ### Geogebra (For Geometry) https://www.geogebra.org/calculator ---- ## 注意事項 1. 更新題目前先 Update Working Copy (git pull) 2. 每次更新完題目都要記得 Commit Changes 3. 在 Manage access 把隊友以及我加進去 4. 預計下次上課 3/31 開始驗題，於這段時間好好產好測資