<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 的部分講解  ---- ## 常用符號 - $1\le n\ge 1$ ```$1\le n\ge 1$``` - $a^b$ ```$a^b$``` - $\sum_{i=1}^{j}\limits {t_i}$ ```$\sum_{i=1}^{j}\limits {t_i}$``` - $a_i$ ```$a_i$``` - $\to$ ```$\to$``` - $a\times b$ ```$a\times b$``` - $a\cdot b$ ```$a\cdot b$``` - $\sim$ ```$\sim$``` - $\sqrt{n}$ ```$\sqrt{n}$``` - $\neq$ ```$\neq$``` - $\in\notin$ ```$\in\notin$``` - $\frac{a}{b}$ ```$\frac{a}{b}$``` ---- ## 小規定 題目輸入範圍，放在輸入後面   --- ## Solution files 放你的 AC 程式碼，以及想測 TLE 或者 WA 等結果的可以分別上傳並標記不同結果 建議所有可能會出現的結果都要寫一份 code 以及假都要放上來測試  --- ## testlib.h 許多程式競賽的出題都會用到這個工具 [testlib.h](https://codeforces.com/testlib) 主要有以下四個功能 - Generator，產測資時用到 - Validator，驗證測資是否正確 - Interactor，互動題編寫 - Checker，寫 Special Judge --- ## Generator 通常測資不會直接上傳 .in .ans 等檔案，而會是寫一份產測資的 code polygon 會直接線上產測資 以下是題目 [Orz](https://codeforces.com/gym/369935/problem/J) 的 generator  程式碼中有 ```opt<type>``` ，代表讀入的測資大小 ---- generator 程式碼放在 Files -> Source Files  ---- ## Generate test 根據你的參數(以這題為例是 t,l,r,type) 生出不同的測資 ```gen -t -10 -l 1 -r 2 -type random > $``` (gen 為你的產測資檔案(gen.cpp)) 產生出 t = 10, l = 1, r = 2, type = random 的測資  ---- 可以根據不同傳進去的參數去產出想要的測資，這個是比較簡單題目的，通常會分一堆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 都要判斷 ---- ## Validator 常用函式 ```cpp= inf.readInt(1, 10, "n"); // 讀入一個大小為 1 到 10 之間的整數 inf.readInt(n, 1, 10, "a_i"); // 讀入 n 個大小為 1 到 10 之間的整數 string limit = "[a-zA-Z]{1," + to_string(n) + "}"; // 制定正規表達式 inf.readString(limit, "str"); // 讀入一個字串，並且要符合 limit 的正規表達式 inf.readSpace(); // 讀入空白 inf.readEoln(); // 讀入換行 inf.readEof(); // 結束輸入 ensuref(condition); // condition 為題目限制，如果不符合 validtor 會不通過 ``` --- ## 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 方便 ### 缺點 - 處理的時間比較多 ---- ## 注意事項 1. 更新題目前先 Update Working Copy 2. 每次更新完題目都要記得 Commit Changes 3. 在 Manage access 把隊友以及我加進去  ---- ## 目標 每隊出一題，範圍如下 - greedy - dp - binary search - two pointer - dsu - brute force - divide and conquer - pow - prime - dfs/bfs ---- ## 算分 占總成績 35% 每解出一題自己出的題目以外得 max($\lceil\frac{22}{n}\rceil, 4$)，最高得 22 分 自己出的題目，自己解出來拿 3 分 根據答對率最高可以拿到 10 分 (越低越高分) ---- ## useful tools - ```Graph Editor``` (for graph) https://csacademy.com/app/graph_editor/ - ```Geogebra``` (For Geometry) https://www.geogebra.org/calculator - ```draw.io``` (For draw figure) https://draw.io - ```latex cheat sheet``` https://wch.github.io/latexsheet/latexsheet.pdf ---- ## 題目想法 想完題目找 jakao 確認主題與難度 確定才開始出題 每題至少要驗 - AC - TLE - WA(special case, corner case) ---- ## 時限 11/10 前想完題 11/24 前測資、題序完成 12/01 前產生假解唬爛、增強測資