# 出題工具教學 2024-03-04 @程式解題社 by 侯欣緯 ---- ## 為什麼你要學這個 因為你可能想要... - 當出程式題的助教 - ADA/DSA - 在系學會學術部的各種比賽出題 - 新生盃 ICPC/台清交 - 在程式解題社的各種比賽出題 - IOIC/將來可能出現的各種怪怪比賽 - 在其他比賽出題 - 全國模/自己高中的校內賽/... ---- ## 大綱 - 一道題目有什麼 - TPS 的基本使用 - 如何生測資：`jngen.h` - 如何寫 validator：`testlib.h` - 實作時間 - 以上東西的進階使用方法 - more about 出題 ---- ## 前置作業與先備知識 - 如果你是 Windows，要裝 WSL - 如果你是 Mac，我不會用 QQ - 會用一些基本的 Linux 指令 - 寫過 Online Judge 上的題目 - 有了會更好的技能 - 會一些演算法 - 看得懂 bash - 看得懂 Python --- # 一道題目有什麼 & 出題好習慣 ---- ## 參賽者看到的題目 - 題目敘述 - 測資 ---- ## 實際上的題目 - 題目敘述 - 測資 - **generator** - **validator** - **checker** - **solutions** - 標程、各種正解和假解 - 其他奇怪題型會有的東西 (?) ---- ## 題目敘述 - 問題描述、輸入輸出格式與限制、範例測資與說明、時間與記憶體限制、子題 - 題目敘述一定要嚴謹 - 輸入的所有東西都要有上下界限制 - 記得遵守格式要求 ---- 輸入輸出格式 - 視覺化版  <small>（2022 全國模 pC 頒獎音樂）</small> ---- 輸入輸出格式 - 純文字版  <small>（2024 IOICamp Day 5 pC 外星人的陰謀）</small> ---- ## 測試資料 - generator：用來生出測資 - validator：用來檢查測資是否符合輸入格式 - 不要照著 generator 寫 validator，要照著輸入格式寫！ ---- ## checker - 用來檢查答案是不是對的 - 通常會是直接看是不是和標程輸出一樣 - 嚴格比對：長得一模一樣 - 非嚴格比對：可以有多餘空格換行之類的 ---- ## solutions - 標程 - 其他的正解（不同作法、跑比較慢的） - 子題的解 - 各式各樣的假解 ---- ## 其他奇怪的東西 - grader - interactor ---- ## 常見 Online Judge - [TIOJ](https://github.com/TIOJ-INFOR-Online-Judge/tioj) - 程式解題社主要在用、新生盃 ICPC 會用 - [TIOJ Problem Tools](https://github.com/baluteshih/tioj-problem-tools/tree/main) - [CMS](https://github.com/cms-dev/cms) - 常見 OI 制比賽用 OJ，全國模跟資訊之芽會用 - [DOMjudge](https://github.com/DOMjudge/domjudge) - 常見 ICPC 制比賽用 OJ，台清交會用 - [Codeforces Polygon](https://polygon.codeforces.com/) - ~~很難用~~ - 其他各種牌子的 OJ - [ZeroJudge](https://github.com/jiangsir/ZeroJudge), [QDUOJ](https://github.com/QingdaoU/OnlineJudge), [Lyrio](https://github.com/lyrio-dev/lyrio) ... --- # TPS [**T**ask **P**reparation **S**ystem](https://github.com/ioi-2017/tps) ---- - 常用的出題工具 - 包辦幾乎整個題目需要的出題流程<span style="font-size: 15pt">吧</span> - IOI 在用的 - 所以某種程度上是為了 CMS 設計的 - repo 裡面有一些範例 - 有一個東西叫 [TPS - Web Interface](https://github.com/ioi-2017/tps-web)，有一些設定是給這個用的 - 但我沒有用過 ---- ### Installation ``` bash -c "$(curl -fsSL https://raw.githubusercontent.com/ioi-2017/tps/master/online-installer/install.sh)" ``` - 也可以 clone 下來後自己跑 `install.sh` - 在 Windows 怎麼用？WSL - 可能需要先裝一些東西，詳見 [document](https://github.com/ioi-2017/tps/tree/master/docs) - `apt install curl git python-is-python3 pip make g++ dos2unix` - `pip install psutil` - 建議裝 `dos2unix` 才不會發生怪怪換行問題 - 聽說 CRLF 在 CMS 真的會出包 - ~~不要 minor fix~~ ---- ### tps init - 一個題目會有一個資料夾 - 怎麼 init 一個題目的資料夾？ - 複製別人的來改 (?) - 你在出的比賽可能會有一個模板給你複製 - `tps init` ---- ### tps init ``` tps init <output-directory> [options] ``` - 在它的 repo 裡面有一個目錄 `task-templates`，裡面有一個叫 `default` 的 template ---- ### tps init: options 可能用到的 option： - `-T <task-template-dir>`，預設值是 `$TPS_TASK_TEMPLATES_PATH`，所以你可以在你的 `.*shrc` 裡加入 ``` export TPS_TASK_TEMPLATES_PATH=<你放 template 的地方> ``` - `-t <task-template-name>`，預設值是 `default` - 沒特殊需求的話，只要你先把 `$TPS_TASK_TEMPLATES_PATH` 設成 `tps/task-templates` 後就不用打 option ---- 他會問你一坨問題，大概像這樣  ---- ### Task Directory Structure 剛才生出的資料夾裡面會有 - problem.json：題目的基本資訊 - solutions.json：solution/ 裡面每個解預期的 verdict - subtasks.json：子題資訊 ---- - checker/ - gen/：放 generator 和其他跟生測資有關的東西的地方 - solution/ - statement/ - validator/ - scripts/：你用 `tps <command> ...` 時 `<command>.(sh|py)` 的所在地 ---- 做過一些事情後會有 - tests/：測資 - logs/：出錯了要去這裡找 log - sandbox/ ---- 有些題目可能還會有 - grader/ - public/ ---- 接下來我們會一邊試著出一題 A+B Problem 一邊介紹 TPS 基本的使用方式 輸入：$A$ 和 $B$，$1 \leq A,B \leq 2 \times 10^9$ 輸出：$A+B$ ---- ``` tps init -T ... aplusb ```  --- ## TPS: 各種 .json ---- ### problem.json ```json { "name": "aplusb", // 題目的代號 "code": "aplusb", // 通常會跟 name 一樣 "title": "A+B Problem", // 題目敘述上寫的題目名稱 "type": "Batch", "has_grader": false, "java_enabled": false, "python_enabled": false, "time_limit": 1.0, // sec "memory_limit": 2048, // MB "description": "Task description" } ``` <div style="font-size: 15pt"> 不重要小知識：<br/> <ol> <li> json 其實不支援註解，但不要在乎那麼多 (X)</li> <li> TPS exporter 只吃 name 不吃 code，TIOJ problem tools 只吃 code 不吃 name</li> <li> 寫 TPS 跟 CMS 的人很會取名字，TPS exporter 會把 name 放進一個叫作 code 的欄位，把 title 放進一個叫作 name 的欄位，從 code 讀出來的東西在 CMS 的 source code 裡叫作 name，從 name 讀出來的叫 title</li> </ol> </div> ---- ### Task Type CMS 有 4 種 Task type - Batch - Communication - TwoSteps - OutputOnly [CMS Task types](https://cms.readthedocs.io/en/latest/Task%20types.html) 今天只會講 Batch，通常也只會用這個 <div style="font-size: 15pt"> 不重要小知識：<br/> <ol> <li> 同樣的題目可以用不同的 Task type 實作，例如許多互動題會直接用 Batch 做，而不是 Communication，還有所有 TwoSteps 都可以用 Communication 做</li> <li>通常會用 Communication 是為了安全，而不用 Communication 是為了省 IO 的時間，CMS document 直接不建議用 TwoSteps</li> <li>在 Batch 跟參賽者 code 一起 compile 的那個檔案叫 grader.cpp，而在 Communication 叫 stub.cpp，這是為什麼你有時候會看到不同的檔名</li> </ol> </div> ---- ### solutions.json 其實寫在這的東西沒那麼重要 用 `tps invoke` 時如果這裡有寫它預期的結果 那麼最後會提示你是否符合預期 不過你這裡沒有設其實也不會怎麼樣 (?) （但有可能會有人不開心） （當然要記得 model solution） ``` { "correct1.cpp": { "verdict": "model_solution" } } ``` ---- ```json "<filename>.cpp": { "verdict": "<verdict>", "except": { "<subtask-name>": "<verdict>" } } ``` - 用來生 output 的解：`model_solution` - 其他所有 verdict： correct, time_limit, memory_limit, incorrect, runtime_error, failed, time_limit_and_runtime_error, partially_correct ---- ```json { "ac.cpp": { "verdict": "correct" }, "ac_fast.cpp": { "verdict": "model_solution" }, "tester_ac.cpp": { "verdict": "correct"}, "tester_ac_double.cpp": { "verdict": "correct" }, "double.cpp": { "verdict": "correct"}, "wa.cpp": {"verdict": "incorrect" }, "wa2.cpp": {"verdict": "incorrect" }, "bf.cpp": {"verdict": "time_limit", "except": {"samples": "correct", "bruteforce": "correct"}}, "vector.cpp": {"verdict": "time_limit", "except": {"samples": "correct", "bruteforce": "correct"}}, "nosort1.cpp": {"verdict": "time_limit", "except": {"samples": "correct", "bruteforce": "correct"}}, "nosort2.cpp": {"verdict": "time_limit", "except": {"samples": "correct", "bruteforce": "correct"}}, "tester_bruteforce.cpp": {"verdict": "time_limit", "except": {"samples": "correct", "bruteforce": "correct"}}, "tester_hulan.cpp": {"verdict": "time_limit", "except": {"samples": "correct", "bruteforce": "correct"}}, "tester_hulan_noofast.cpp": {"verdict": "time_limit", "except": {"samples": "correct", "bruteforce": "correct"}} } ``` <small>（2023 IOICamp Day 5 pC 三口羊之戰）</small> ---- ### subtasks.json ```json { "global_validators": ["validator.cpp"], "subtasks": { "samples": { "index": 0, "score": 0, "validators": [] }, "full": { "index": 1, "score": 100, "validators": [] } } } ``` ---- 一個 subtask： ```json "subtask-name": { "index": 1, "score": 87, "validators": [ "val1.cpp", "example.cpp" ] } ``` - index 是 0,1,2,... - 通常 0 是範測 - validators 是只會給這個子題的測資跑的 validator - 在 TIOJ 的 import 格式裡會多一項是 `"text": "..."`，會顯示在子題說明 <div style="font-size: 15pt"> 不重要小知識：<br/> <ol> <li>用 TPS exporter 輸出再在 CMS 匯入後 text 其實會被放進 scoring parameter 裡面，但我不知道是拿來幹嘛的</li> <li>index 0 實際上是 subtask 1</li> <li>如果你的 index 沒有照 0,1,2,... 打，其實在 TPS 裡不會怎麼樣，但其他要 parse 的 script 可能會生氣</li> </ol> </div> --- ## TPS: 常用指令 ---- 我們先把一些檔案隨便補起來 然後來試試看用指令 ---- `solution/correct1.cpp` ```cpp= #include<iostream> using namespace std; int main() { long long a, b; cin >> a >> b; cout << a + b << "\n"; return 0; } ``` ---- `validator/validator.cpp` ```cpp= #include "testlib.h" using namespace std; const int C = 2000000000; int main() { registerValidation(); inf.readInt(1, C, "A"); inf.readSpace(); inf.readInt(1, C, "B"); inf.readEoln(); inf.readEof(); return 0; } ``` ---- 我們先不改 generator `gen/data` ``` @subtask samples manual 1.in ``` `gen/manual/1.in` ``` 2000000000 1487634876 ``` ---- 然後我們就可以來試試看用指令了！ 先把測資生出來：`tps gen`  ---- - `tests/`：測資出現的地方 - `logs/`：log - 如果 val 沒有過，通常是有多/少換行空白 - 去看 log！ ---- 跑一個 solution：`tps invoke <file>`  ---- 試試錯的 solution？ ```cpp= // solution/wa.cpp #include<iostream> using namespace std; int main() { int a, b; cin >> a >> b; cout << a + b << "\n"; return 0; } ```  ---- 好用指令：`tps verify`  ---- 好用指令：`jq` 有時候 json 爛掉 tps 會直接不知道在幹嘛 :(  --- ## 測試資料 最困難的部分 ---- 測資怎麼可以只有一筆用手打的 `gen/data`：用來說每個子題有哪些測資、怎麼生 剛剛用的 `manual <file>`：用 `gen/manual` 裡的 `<file>` ---- ### gen/ 這個資料夾裡面的東西會有 - generator 們 - gen/data：描述測資的檔案 - manual/：放你手生測資的地方 ---- ``` @subtask samples manual 1.in manual 2.in manual 3.in manual 4.in @testset n20distinct gen 2 -1 gen 3 -1 gen 3 -1 3 gen 10 -1 gen 5 -1 gen 20 -1 gen 20 -1 0 gen 20 -1 10 gen 20 -1 20 @subtask n20 @include samples @include n20distinct gen 1 1 gen 2 1 gen 3 1 gen 3 2 gen 3 3 gen 20 20 gen 20 20 5 gen 20 20 10 gen 20 20 20 gen 20 1 gen 20 2 gen 20 3 gen 20 4 gen 20 5 @testset n1000distinct gen 100 -1 gen 500 -1 gen 1000 -1 gen 1000 -1 100 gen 1000 -1 500 gen 1000 -1 1000 gen 1000 -1 0 zisk gen 1000 -1 0 ziskzisk gen 1000 -1 0 ksiz gen 1000 -1 0 ksizksiz @subtask n1000 @include n20 @include n1000distinct gen 100 1 gen 100 2 gen 100 3 gen 100 4 gen 100 50 gen 100 20 gen 100 100 gen 1000 1 gen 1000 2 gen 1000 3 gen 1000 4 gen 1000 50 gen 1000 100 gen 1000 1000 gen 1000 500 gen 1000 100 100 gen 1000 1000 100 gen 1000 1000 500 gen 1000 1000 1000 @subtask distinct @include n20distinct @include n1000distinct gen 1000000 -1 gen 1000000 -1 0 ziskzisk gen 1000000 -1 0 kiszkisz gen 1000000 -1 1000 gen 1000000 -1 100000 gen 1000000 -1 1000000 @subtask full @include n1000 @include distinct gen 100000 1 gen 100000 10 gen 100000 100 gen 100000 1000 gen 100000 10000 gen 100000 100000 gen 1000000 1 gen 1000000 10 gen 1000000 100 gen 1000000 1000 gen 1000000 10000 gen 1000000 100000 gen 1000000 1000000 gen 1000000 1000000 100 gen 1000000 1000000 1000 gen 1000000 1000000 10000 gen 1000000 1000000 100000 gen 1000000 1000000 1000000 ``` <small>（2023 附中暑期培訓模競 1 pB 假消息）</small> ---- ``` @subtask samples manual 1.in gen 5 10 1 3 3 # blocks num block len ed con sep maxlen @subtask tree gen 400 399 1 200 3 1 gen 400 405 1 200 2 1 gen 400 400 101 300 5 1 gen 400 400 900000000 900000200 5 1 gen 400 1000 1 100 2 1 gen 400 1000 1 1000 3 1 gen 400 1000 1 1000000000 1000000000 1 @subtask scheduling blocks 50 6 6 8 2 1000000 3 2 blocks 50 6 5 8 2 1000000 3 2 blocks 30 10 10 15 2 1000 3 2 blocks 30 10 10 20 2 1000 3 2 blocks 30 10 10 10 2 1000 3 2 blocks 100 3 3 7 2 1000 2 2 blocks 100 3 4 7 2 1000 2 2 blocks 66 6 6 8 2 1000000 3 2 blocks 66 6 5 8 2 1000000 3 2 blocks 40 10 10 15 2 1000 3 2 blocks 40 10 10 20 2 1000 3 2 blocks 40 10 10 10 2 1000 3 2 gen 400 399 1 200 3 2 gen 400 405 1 200 2 2 gen 400 400 101 300 5 2 gen 400 400 900000000 900000200 5 2 gen 400 1000 1 100 2 2 gen 400 1000 1 1000 3 2 gen 400 1000 1 1000000000 1000000000 2 @subtask nnnmlogn blocks 10 5 4 7 1 1000 2 hack_wa2 8 0 hack_wa2 8 1 gen 50 49 1 30 2 gen 50 100 1 55 2 gen 50 100 1 30 3 gen 50 100 1 1000000000 1000000000 ca 50 100 @subtask nnmlogn @include nnnmlogn blocks 20 10 10 10 1 1000 2 blocks 10 20 20 20 2 1000 3 hack_wa2 33 0 hack_wa2 33 1 gen 200 199 1 120 3 gen 200 1000 1 100 2 gen 200 1000 1 1000 3 gen 10 1000 1 10 2 gen 200 1000 1 1000000000 1000000000 ca 199 1000 ca 200 1000 # blocks num block len ed con sep maxlen @subtask full @include tree @include scheduling @include nnmlogn ca 200 1000 blocks 50 6 6 8 2 1000000 3 blocks 50 6 5 8 2 1000000 3 blocks 30 10 10 15 2 1000 3 blocks 30 10 10 20 2 1000 3 blocks 30 10 10 10 2 1000 3 blocks 100 3 3 7 2 1000 2 blocks 100 3 4 7 2 1000 2 blocks 66 6 6 8 2 1000000 3 blocks 66 6 5 8 2 1000000 3 blocks 40 10 10 15 2 1000 3 blocks 40 10 10 20 2 1000 3 blocks 40 10 10 10 2 1000 3 hack_wa2 50 0 hack_wa2 50 1 gen 400 399 1 200 3 gen 400 405 1 200 2 gen 400 400 101 300 5 gen 400 400 900000000 900000200 5 gen 400 1000 1 100 2 gen 400 1000 1 1000 3 gen 400 1000 1 1000000000 1000000000 ca 399 1000 ca 400 1000 ``` <small>（2024 IOICamp Day 4 pF 又是城市規劃）</small> ---- - `@subtask <name>`：接下來的部分是一個子題，`name` 是你寫在 subtasks.json 的那個 - `@testset <name>`：接下來的部分是一個叫 `name` 的 testset - `@include <name>`：讓這個子題包含 `name`，可以是一個子題或 testset - **記得設子題 dependency** - `manual <file>`：`manual/<file>` - `<generator> <arguments>` ---- ### Generator - 就是用來生測資的東西 - 放在 `gen/XXX.cpp` - 可能會有很多個 - 寫在 `gen/data` 裡的 argument 會當成 generator 的執行參數 - 通常會用來寫一些變數的值、範圍（生子題的時候可以直接修改）等等 - generator 的輸出（stdout）就是測資 ---- 常被用來寫 generator 的 library 有 testlib 和 jngen 接下來我們會講 jngen ---- [jngen](https://github.com/ifsmirnov/jngen/) - 可以方便生許多東西的 library - 東西很雜，要自己看 document - [教學 by 蛋餅](https://omeletwithoutegg.github.io/2021/01/24/jngen/) ---- `gen/gen.cpp` ```cpp= #include <iostream> #include "jngen.h" using namespace std; int main(int argc, char* argv[]) { registerGen(argc, argv); int C = atoi(argv[1]); int a = rnd.next(1, C); int b = rnd.next(1, C); cout << a << " " << b << "\n"; } ``` ----  ---- 我們先來亂幫這個題目分一些子題 - (1%) $1 \leq A,B \leq 3$ - (39%) $1 \leq A,B \leq 10^9$ - (60%) 無額外限制 ---- `subtasks.json` ```cpp= { "global_validators": ["validator.cpp"], "subtasks": { "samples": { "index": 0, "score": 0, "validators": [] }, "water": { "index": 1, "score": 1, "validators": [] }, "int": { "index": 2, "score": 39, "validators": [] }, "full": { "index": 3, "score": 60, "validators": [] } } } ``` ---- `gen/data` ``` @subtask samples manual 1.in @subtask water gen 3 this gen 3 is gen 3 too gen 3 water @subtask int @include water gen 1000000000 remember gen 1000000000 to gen 1000000000 use gen 1000000000 long long @subtask full @include samples @include int gen 2000000000 ovo gen 2000000000 owo gen 2000000000 qwq ``` ----  好像不太對，怎麼只錯範測 ---- $A+B > 2147483647$ 的機率沒有非常高 <span style="font-size: 15pt">這裡不是數學課，絕對不是我不想算</span> ---- 生測資好習慣： - 確定有至少把所有想得到的假解都卡掉 - 可以多加幾個參數方便調範圍 - 不要太多個測資，judge 會哭 - 擅用一個檔案 $T$ 筆測資來加大測資筆數並控制檔案數量 - 種類數足夠少的話，可以用小測資來生過幾乎所有 case（小測資卡正確性） - 大測資用來卡時間，但要記得大測資多少也得卡正確性 - 可以注意一下不要讓人做子題的時候不小心拿到更多分數 --- ## Generator with jngen.h ---- ### Register ```cpp registerGen(argc, argv); parseArgs(argc, argv); ``` - 第一個是給 generator seed - 第二個是給 argument parser ---- ### [getopt](https://github.com/ifsmirnov/jngen/blob/master/doc/getopt.md) ```cpp // ./main 10 -pi=3.14 20 -hw hello-world randomseedstring int main(int argc, char *argv[]) { parseArgs(argc, argv); int n, m; double pi; string hw; n = getOpt(0); // n = 10 pi = getOpt("pi"); // pi = 3.14 n = getOpt(5, 100); // n = 100 as there is no option #5 pi = getOpt("PI", 3.1415); // pi = 3.1415 as there is no option "PI" getPositional(n, m); // n = 10, m = 20 getNamed(hw, pi); // hw = "hello-world", pi = 3.14 cout << (int)getOpt("none", 10) << endl; // 10 as there is no "none" option } ``` ---- 其實它有一些不太好用的地方 (?) 如果你有參數是填負數的話會被 parser 當成一個 option 然後你用 `getOpt(index)` 就拿不到了 所以也有些人會自己用 `atoi` （我都是這樣） ---- ### [random](https://github.com/ifsmirnov/jngen/blob/master/doc/random.md) - `rnd.next(l, r)`：$[l,r]$ 裡的隨機數字 - 你傳什麼型態就回傳什麼型態 - 也可以打 `rnd.next(n)`，這樣是 $[0,n)$ 內的數字 - `rnd.next(regex)`：符合 regex 的隨機字串 - `rnd.nextp(l, r, opt)`：隨機 pair $(x,y)$，`opt` 的選項有： - opair: $x \leq y$ - dpair: $x \neq y$ - `rnd.choice(container)`/`rnd.choice(l, r)`：容器裡拿一個東西 ---- ### rnd.wnext() ```cpp rnd.wnext(l, r, t) ``` - $t=0$：等同於 `rnd.next(l, r)` - $t>0$：`max(rnd.next(l, r), rnd.wnext(l, r, t - 1))` - $t<0$：`min(rnd.next(l, r), rnd.wnext(l, r, t + 1))` - 總之就是算 $|t|+1$ 次取最大/最小值 ---- ### More about random ```cpp registerGen(argc, argv); ``` 這個東西傳 argument 的目的是 argument 會被拿來當 random 的 seed 所以用一樣的 argument，生出來的測資是一樣的 ---- jngen 保證同樣的 seed 在不同裝置 random 出來的結果一樣 不一樣的例子： `uniform_int_distribution` 的實作在不同編譯器可能是不一樣的 ---- ### [array](https://github.com/ifsmirnov/jngen/blob/master/doc/array.md) - 蛤？為什麼 random 裡面沒辦法 shuffle 陣列 - `TArray<T>`：一個繼承自 `vector<T>` 的型態 - 為了方便，後面都寫 `Array`，實際上都可以換成其他的 `TArray<T>` ```cpp typedef TArray<int> Array; typedef TArray<long long> Array64; typedef TArray<double> Arrayf; typedef TArray<std::pair<int, int>> Arrayp; typedef TArray<TArray<int>> Array2d; ``` ---- ### Random array - `Array::random(size, ...)` - `Array::randomUnique(size, ...)` - `...` 的內容會被填在 `rnd.next(...)` - e.g. `Arrayp::random(10, 1, 10)`：長度為 10，數字在 $[1,10]$ 內的隨機 pair<int,int> 陣列 - `Array::id(size, start=0)`：$\{start,start+1,\dots,start+size-1\}$ ---- ### Methods of Array - `.shuffle()` / `.shuffled()` - `.reverse()` / `.reversed()` - `.sort()` / `.sorted()` - `.unique()` / `.uniqued()` - `.choice()` - `.choice(count)`：不重複 - `.choiceWithRepetition(count)`：重複 有 ed 沒 ed 的差別是，沒 ed 的會改原本的陣列，有 ed 的會回傳一個新的 ---- [print](https://github.com/ifsmirnov/jngen/blob/master/doc/printers.md)? ```cpp Array arr = {1, 2, 3}; cout << arr << "\n"; ```  ---- ### 樹與圖 [GenericGraph](https://github.com/ifsmirnov/jngen/blob/master/doc/generic_graph.md) 這個 class 是用來維護圖的 點是 0-indexed ---- ### random [tree](https://github.com/ifsmirnov/jngen/blob/master/doc/tree.md) - 你知道怎麼生一棵隨機的樹嗎？ ---- ### random [tree](https://github.com/ifsmirnov/jngen/blob/master/doc/tree.md) - `Tree::random(size)`：用隨機的 prufer sequence 生一棵樹 - `Tree::randomKruskal(size)`：隨機生一個邊的序列然後用類似 Kruskal 的方式加到樹上 - `Tree::randomPrim(size, elongation)`：  - 一般來說都會用 `randomPrim` 來控制樹的高矮胖瘦 ---- - 注意直接 random 出來的樹節點編號和邊的順序會有某種排序性質 (?)，要 `.shuffle()` / `.shuffled()` - 另外還有一些常見樹形狀的 generator，例如鏈、二元樹等 ---- ### random [graph](https://github.com/ifsmirnov/jngen/blob/master/doc/generic_graph.md) ```cpp auto g = Graph::random(10, 20).connected().allowMulti().g().shuffled(); Graph g2 = Graph::randomStretched(100, 200, 2, 5); cout << Graph::complete(5).allowLoops() << endl; ```  記得 shuffle！ ---- ### [print](https://github.com/ifsmirnov/jngen/blob/master/doc/printers.md) graph / tree ```cpp Graph g = Graph::random(4, 6).connected().allowMulti().g().shuffled(); cout << g.add1().printN().printM() << "\n"; ```  ---- ### 其他常用 (?) 的東西 - [geometry](https://github.com/ifsmirnov/jngen/blob/master/doc/geometry.md) - 生一堆點任三點不共線、凸包... - [prime](https://github.com/ifsmirnov/jngen/blob/master/doc/math.md) - 生質數 - [drawer](https://github.com/ifsmirnov/jngen/blob/master/doc/drawer.md) - 用來畫 svg 的東西，需要 debug 或放圖在題目裡的時候可以用 --- ## Validator with testlib.h ---- [testlib](https://github.com/MikeMirzayanov/testlib) - Polygon 在用的東西 - 所以他是為了 Polygon 設計的 - 可以用來寫 checker、validator、generator、interactor 等等 - 不過要注意 interactor 格式到處都不一樣 - 他的 repo 裡有一些範例可以看 - [Briefly about testlib.h](https://codeforces.com/testlib) - [Polygon 使用指北 by 林尚廷](https://hackmd.io/@omeletwithoutegg/HJtQcQ0vB) ---- 剛剛的例子 ```cpp= #include "testlib.h" using namespace std; const int C = 2000000000; int main() { registerValidation(); inf.readInt(1, C, "A"); inf.readSpace(); inf.readInt(1, C, "B"); inf.readEoln(); inf.readEof(); return 0; } ``` ---- 從輸入讀東西 ```cpp= // 輸入在 [l,r] 內的數 inf.readInt(l, r); inf.readLong(l, r); inf.readDouble(l, r); // 輸入一個等於 c 的字元 inf.readChar(c); // 輸入一個符合 regex 的字串 inf.readWord(regex); inf.readLine(regex); // 以上的參數可以多放一個字串，是讀進去的那個東西的名字 inf.readSpace(); inf.readEoln(); inf.readEof(); // 一定要有！ ``` ---- ensure ```cpp ensure(condition); ensuref(condition, message, ...); ``` ---- 一個簡單的例子 2022 全國模 pC Ceremony  ---- ```cpp #include "testlib.h" int main(int argc, char* argv[]){ registerValidation(argc, argv); int n = inf.readInt(3, 1000000); inf.readEoln(); for(int i = 1; i <= n; i++){ inf.readInt(1, n); if(i < n) inf.readSpace(); } inf.readEoln(); inf.readEof(); return 0; } ``` ---- 複雜的例子 IOIC 2023 5C 三口羊之戰  ---- ```cpp #include "testlib.h" // 模板請自己腦補 int district(Pt p){ return p.Y == 0 ? p.X < 0 : p.Y < 0; } bool comp(Pt a, Pt b){ if(district(a)) a = -a; if(district(b)) b = -b; return cross(a, b) > 0; } int main(int argc, char* argv[]){ registerValidation(argc, argv); int n = inf.readInt(1, 3000); inf.readEoln(); vector<Pt> kp(n + 1); vector<Pt> pnts; for(int i = 1; i <= n; i++){ kp[i].X = inf.readInt(0, 1000000000); inf.readSpace(); kp[i].Y = inf.readInt(0, 1000000000); inf.readEoln(); pnts.eb(kp[i]); } int m = inf.readInt(1, 1500); inf.readEoln(); vector<Line> wall(m + 1); for(int i = 1; i <= m; i++){ wall[i].X.X = inf.readInt(0, 1000000000); inf.readSpace(); wall[i].X.Y = inf.readInt(0, 1000000000); inf.readSpace(); wall[i].Y.X = inf.readInt(0, 1000000000); inf.readSpace(); wall[i].Y.Y = inf.readInt(0, 1000000000); inf.readEoln(); pnts.eb(wall[i].X); pnts.eb(wall[i].Y); } inf.readEof(); // 任兩道牆壁不相交 for(int i = 1; i <= m; i++){ for(int j = i + 1; j <= m; j++){ ensure(!intersect(wall[i], wall[j])); } } lsort(pnts); // 座標皆相異 for(int i = 0; i + 1 < SZ(pnts); i++){ ensure(pnts[i] != pnts[i + 1]); } // 任三點不共線 for(Pt i : pnts){ vector<Pt> tmp; for(Pt j : pnts){ if(i != j) tmp.eb(j); } sort(iter(tmp), [&](Pt a, Pt b){ return comp(a - i, b - i); } ); for(int j = 0; j + 1 < SZ(tmp); j++){ ensure(comp(tmp[j] - i, tmp[j + 1] - i) || comp(tmp[j + 1] - i, tmp[j] - i)); } } return 0; } ``` ---- Validator 好習慣 - 別忘了不只有數字範圍需要判，題目的所有限制都要判 - 寫 Validator 的原則是不要相信你的 generator 是對的 - 所以你不應該因為相信 generator 不會錯而懶得判某些不好判的東西 - 子題要有個別的 validator ---- 子題 validator validator 可以讀參數！ `validator/validator.cpp` ```cpp= #include "testlib.h" using namespace std; int main(int argc, char *argv[]) { int C = atoi(argv[1]); registerValidation(); inf.readInt(1, C, "A"); inf.readSpace(); inf.readInt(1, C, "B"); inf.readEoln(); inf.readEof(); return 0; } ``` ---- `subtasks.json` ```json { "global_validators": ["validator.cpp 2000000000"], "subtasks": { "samples": { "index": 0, "score": 0, "validators": [] }, "water": { "index": 1, "score": 1, "validators": ["validator.cpp 3"] }, "int": { "index": 2, "score": 39, "validators": ["validator.cpp 1000000000"] }, "full": { "index": 3, "score": 60, "validators": [] } } } ``` ---- （有一點重要的知識） tps init 出來的資料夾，裡面有三個地方有 `testlib.h` - `gen/` - `checker/` - `validator/` ---- [TPS 的 testlib](https://github.com/ioi-2017/tps/blob/master/extra-assets/testlib/testlib-cms.h) 是有修改過的版本 - 上面有一串註解說他改了什麼 - 大部分的用法都還是跟 Polygon 一樣 - 修改主要是為了讓 CMS 可以用 ---- - TPS：`0.9.21` - 最新的 `testlib.h`：`0.9.41` ---- 實際上 generator 和 validator 用的 `testlib.h` 是什麼版本基本上是沒差的 所以很多人會直接換成最新版，比較好用 ---- 但 checker 必須要搭配正確的 script 才能跑 而且可能要配合 judge 的格式 - CMS, TIOJ, Polygon checker 讀參數的順序都不一樣 - TIOJ Problem Tools 會硬塞一個 TIOJ 可以用的 testlib，跟你用的檔案沒關係 <div style="font-size: 15pt"> 真的不重要：<br/>三種 checker 參數順序<br/>（inf: 測資輸入, ans: 標程輸出, ouf: 參賽者輸出）<br/> <ol> <li>CMS: inf, ans, ouf</li> <li>Polygon: inf, ouf, ans</li> <li>TIOJ: ouf, inf, ans, ...</li> </ol> </div> --- ## 關於題目的更多事 ---- ### solution - 有一個資料夾專門拿來放各種解，當然不是只要放正解就好 - 卡假解不是寫幾個 generator 說「我卡掉了」就好，最好還是要自己寫一個確認真的不會過 - 還有其他版本的正解，例如不同作法或跑比較慢 ---- ### TL / ML - 通常 ML 都是一場比賽裡的題目都一樣 - 除非有題目要特別卡記憶體用太多的作法 e.g. 持久化線段樹 - 或記憶體需要特別多 - TL 則是依標程執行時間而定，通常至少會取標程的兩倍以上 - 要是你平常有壓常習慣 (?) 可能要再多一些 - 要丟上 judge 去測才會準 ---- ### 題目敘述 - 還有一個目錄叫 statement 耶，那是幹嘛的？ - 其實 TPS 不會幫你生題本，只是給你放檔案用的 - import 到 CMS 時會抓那個資料夾裡的所有 PDF，中文題本要叫 `zh_TW.pdf`~~，資芽都亂取，從來沒有對過~~ - 格式就依比賽而定 - 全國模/IOIC 使用的題本 script 還在改良中 (?) ---- ### 題敘注意事項 - 盡量寫清楚、嚴謹 - 輸入的所有變數都要有上下界 - 最好把所有限制寫在輸入限制裡，你寫 validator 的時候就可以直接看著寫 - 剩下就注意一下比賽的題敘規範，例如哪裡要不要句號 - [中文文案排版指北](https://github.com/sparanoid/chinese-copywriting-guidelines) ---- ### .gitignore 不要把 gen 出來的東西和 log 和 compile 完的執行檔 push 上去 如果你用 `tps init` 根目錄會有一個 `.gitignore` 不過它不會幫你 ignore 沒副檔名的執行檔 所以要自己注意如果你測試的時候有自己 compile 檔案 不要直接 `git add .` （我自己的編譯指令會加 `.exe`） ---- ### 本機 stack size 如果你用到遞迴的話，在你本機上可能會 stack overflow - Ubuntu: `ulimit -s unlimited` - Mac: 我不知道 ---- ### 一些網路上可以參考的東西 - [TPS samples](https://github.com/ioi-2017/tps/tree/master/samples) - APIO [2022](https://github.com/apio2022/apio2022_tasks) [2021](https://github.com/ia-toki/apio-2021) etc. - [twpca](https://www.twpca.org/) - 他們不是用 TPS 但還是可以看一下 ---- 不是啊好像還有很多東西沒講 接下來要講了 --- ## Checker ---- 相信大家剛剛就已經知道 checker 毛很多 畢竟 judge 要可以跑 請多參考你得到的出題指示 ---- 固定放在 `checker/checker.cpp` 通常會用 testlib [Checkers with testlib.h](https://codeforces.com/blog/entry/18431) [這裡](https://github.com/MikeMirzayanov/testlib/tree/master/checkers)有 Polygon 內建的 checker ---- TPS 裡的 default checker ```cpp #include "testlib.h" using namespace std; int main(int argc, char* argv[]) { registerChecker("TestTask", argc, argv); compareRemainingLines(); } ``` `registerChecker()` 和 `compareRemainingLines()` 是 TPS testlib 自己加的 ---- testlib wcmp.cpp ```cpp #include "testlib.h" using namespace std; int main(int argc, char *argv[]) { setName("compare sequences of tokens"); registerTestlibCmd(argc, argv); int n = 0; string j, p; while (!ans.seekEof() && !ouf.seekEof()) { n++; ans.readWordTo(j); ouf.readWordTo(p); if (j != p) quitf(_wa, "%d%s words differ - expected: '%s', found: '%s'", n, englishEnding(n).c_str(), compress(j).c_str(), compress(p).c_str()); } if (ans.seekEof() && ouf.seekEof()) { if (n == 1) quitf(_ok, "\"%s\"", compress(j).c_str()); else quitf(_ok, "%d tokens", n); } else { if (ans.seekEof()) quitf(_wa, "Participant output contains extra tokens"); else quitf(_wa, "Unexpected EOF in the participants output"); } } ``` ---- ### register checker ```cpp registerChecker("ProblemName", argc, argv); registerTestlibCmd(argc, argv); ``` - 在 main 的一開始要先把參數餵給 testlib - 上面是 TPS testlib.h 加的東西，他做的事情是 call `setName()`（也是 TPS 自己加的），然後再 call 下面那個，我不是很確定為什麼要這樣做 - 在 TPS 用下面那個也可以，甚至要傳上 CMS 也沒關係 ---- ### stream - `inf`：測資的輸入 - `ouf`：**待評測的輸出** - `ans`：測資的輸出 ---- - 限制可以不打，那樣就是沒有範圍 / pattern 限制 - 不符合限制的時候會 WA - 在 checker 裡面只有 ouf 是需要判正確性的，其他都不需要 - i.e. 只需要判斷 ouf 的正確性 - inf（測資輸入）的正確性在 validator 會檢查 - ans 的正確性你也可以判，爛掉的時候噴個 fail ---- - 範圍後面可以再放一個參數是那個東西的名字 - 會顯示在 checker 提供的訊息裡 - 一般來說參賽者是看不到的，可以當 debug 用 ---- ### quit ```cpp quit(verdict, message); quitf(verdict, message, ...); ``` - 將這筆 submission 判為 `verdict`，checker 提供的訊息是 `message` - verdicts: `_ok`, `_wa`, `_fail` ---- ### More about quit - `quit(...)` 是 `ouf.quit(...)` - 三個 stream 都可以 quit，如果是 `ans` 或 `inf` quit 就會是噴 fail（無論是哪種 verdict） - 可以用同一個 function 檢查 ouf 和 ans 的格式 ---- ### 部分給分 ```cpp quitp(x, message); ``` - 俗稱連續給分 - $x$ 是 $[0,1]$ 的浮點數，表示獲得的分數 / 總分 - verdict 會是 partially correct，所以如果你想要 verdict 是 correct 或 wrong answer，就要用 `quit(_ok/_wa, ...)` ---- ### 簡單提一下：Polygon 設部分給分  ```cpp quitp(s, message) ``` - $s$ 是一個**整數**，值是上一頁的 $100x$ - 沒錯他只能整數 % TODO: 確定這是不是過時資訊 ---- ### 部分給分 ```cpp quitp(x, message); ``` - 俗稱連續給分 - 在 TPS version，$x$ 是 $[0,1]$ 的浮點數，表示獲得的分數 / 總分 - verdict 會是 partially correct，所以如果你想要 verdict 是 correct 或 wrong answer，就要用 `quit(_ok/_wa, ...)` ---- ### 簡單提一下：Polygon 設部分給分  ```cpp quitp(s, message) ``` - $s$ 是一個**整數**，值是上一頁的 $100x$ - 沒錯他只能整數 % ---- ### 關 checker 在 problem.json 可以把 `has_checker` 設成 false 這樣驗答案的時候就是直接 diff 不過注意 judge 上沒 checker 時怎麼判會有所不同 上 TIOJ 的話有 checker 要記得把 `has_checker` 設成 true ---- ### checker 好習慣 - 讀 ouf 的輸入時**一定要加範圍** - 在最佳化答案且要輸出解的題目，如果參賽者答案比標程更好，噴 fail ---- ???  ---- ```cpp= #include "testlib.h" #include <set> #include <string> using ll = long long; void exit_WA() { quitf(_wa, "Wrong Answer"); } void exit_AC() { quitf(_ok, "Accept"); } void exit_PAR(double score) { // score should between 0 and 1 quitp(score, "Partially Correct"); } void check(bool res) { if (!res) exit_WA(); } int n, m; const ll MOD = 1000000007; int main(int argc, char *argv[]) { registerTestlibCmd(argc, argv); n = inf.readInt(); bool par = false; for(int i = 1; i <= n; i++){ ll dpans = ans.readLong(-1, LLONG_MAX); ll dpouf = ouf.readLong(-1, LLONG_MAX); if(dpans != dpouf) exit_WA(); if(dpans == -1) continue; ll cntans = ans.readLong(0, MOD - 1); ll cntouf = ouf.readLong(0, MOD - 1); if(cntans != cntouf) par = true; } if(par) exit_PAR(0.6); exit_AC(); } ``` <small>（2024 IOICamp Day 5 pC 外星人的陰謀）</small> ---- ```cpp= #include "testlib.h" #include <bits/stdc++.h> using namespace std; #define pb emplace_back #define iter(a) a.begin(), a.end() #define SZ(v) int(v.size()) using pii = pair<int, int>; void exit_WA(InStream &stream = ouf) { stream.quitf(_wa, "Wrong Answer"); } void exit_AC() { quitf(_ok, "Accept"); } void exit_PAR(double score) { // score should between 0 and 1 quitp(score, "Partially Correct"); } void check(bool res, InStream &stream = ouf) { if (!res) exit_WA(stream); } int n, m; struct edge{ int u, v, s, t; }; bool operator<(const edge& a, const edge& b){ return a.t < b.t; } bool operator>(const edge& a, const edge& b){ return a.t > b.t; } vector<edge> e; int readAns(InStream &stream) { int x = stream.readInt(0, n); string str = stream.readToken("[01]{" + to_string(m) + "}"); vector<vector<int>> g(n + 1); vector<int> ord; for(int i = 0; i < m; i++){ auto [u, v, s, t] = e[i]; if(str[i] == '1'){ g[u].pb(v); g[v].pb(u); ord.pb(i); } } auto check_scheduling = [&](vector<int> ord){ // O(N log N) sort(iter(ord), [&](int x, int y){ return e[x].s < e[y].s; }); int ptr = 0; priority_queue<edge, vector<edge>, greater<>> pq; for(int s = 1; ptr < SZ(ord) || !pq.empty(); ){ while(ptr < SZ(ord) && e[ord[ptr]].s == s){ pq.push(e[ord[ptr]]); ptr++; } if(pq.empty()){ s = e[ord[ptr]].s; continue; } if(pq.top().t < s) return false; pq.pop(); s++; } return true; }; check(check_scheduling(ord), stream); vector<bool> vst(n + 1); int cnt = 0; for(int v = 1; v <= n; v++){ if(vst[v]) continue; cnt++; queue<int> q; q.push(v); vst[v] = true; while(!q.empty()){ int now = q.front(); q.pop(); for(int i : g[now]){ if(vst[i]) continue; vst[i] = true; q.push(i); } } } check(cnt - 1 == x, stream); return x; } int main(int argc, char *argv[]) { registerTestlibCmd(argc, argv); n = inf.readInt(); m = inf.readInt(); for(int i = 0; i < m; i++){ int u = inf.readInt(); int v = inf.readInt(); int s = inf.readInt(); int t = inf.readInt(); e.pb(edge({u, v, s, t})); } int cnt_ans = readAns(ans); int cnt_ouf = readAns(ouf); if(cnt_ouf < cnt_ans) quitf(_fail, "the participant found a better solution"); else if(cnt_ouf > cnt_ans) exit_WA(); else exit_AC(); } ``` <small>（2024 IOICamp Day 4 pF 又是城市規劃）</small> --- ## 更多 TPS 使用技巧 ---- ```bash tps gen --help tps invoke --help ``` - `-t "..."` 省時間很好用 - `--no-tle` 看時間很好用 - 注意本機執行時間跟 judge 上有落差 ---- 編譯指令 - `gen/` 跟 `checker/` 跟 `validator/` 裡都有一個 `Makefile`，實際上是用它在編譯檔案 - 所以你可以自己改編譯指令，例如換 C++ 版本 - 有些舊版的模板會是 C++14 - ~~如果你還不會用 C++17 那你很老~~ - 你可能很好奇為什麼 `solution` 沒有，因為那個指令在 [compile_solution.sh](https://github.com/ioi-2017/tps/blob/master/scripts/internal/compile_solution.sh) - ~~TPS 很老~~ ---- 常見問題 - JSON 格式爛了 - `"text": "..."` 如果裡面有 `\leq` 之類的東西，斜線要記得用跳脫字元 - `"text": "$n \\leq 100$"` - `scripts/` 爛了 - 你是用 Mac - 我不會 ---- 關於 interactor - 剛剛一直沒有講到，因為這比 checker 更搞 - 我也沒什麼用過 QQ --- ## 牛刀小試 (?) ---- [可能沒有出得很好的範例](https://github.com/wiwiho/ntucpc-lecture-20240304) ---- ### 北極熊大遷徙研究 <small>NPSC 測機萬年老題</small> 輸入：一個整數 $0 \leq x \leq 2000$ 輸出：兩個整數 $a,b$，$0 \leq a,b \leq 1000$，$a+b=x$ ---- ### 你太矮了我看不到 <small>2023 YTP 國中組初賽 p3</small> 輸入：一個整數 $1 \leq N \leq 10^5$，然後一個序列 $b_1,b_2,\dots,b_N$ 滿足 - $b_i \leq b_{i+1}$ - $i \leq b_i \leq N$ 輸出：一個序列 $a_1,\dots,a_N$ 滿足 - $1 \leq a_i \leq N$ - $\forall i \neq j,\ a_i \neq a_j$ - $b_i = \max_{1 \leq k \leq i} \{a_i\}$ ---- ### [物種演化](https://drive.google.com/file/d/1jHYv58S_y31_k4oSi8u5CLXsDCOz2GJg/view?usp=sharing) <small>2019 北市賽 pD</small> 輸入：一棵 $1 \leq n \leq 10^5$ 個點的樹和 $1 \leq m \leq 2.5 \times 10^6$ 筆詢問，每筆詢問有兩個整數 $x_i,y_i$，滿足 $1 \leq x_i,y_i \leq n$ 輸出：對於第 $i$ 筆詢問，輸出樹上節點 $x_i$ 和 $y_i$ 的距離 ~~他為什麼可以把子題出那麼爛~~  ---- 挑戰題 (?) - 寫一個嚴格比對 checker - [2022 NPSC 高中組決賽 pF 城市規劃](https://tioj.ck.tp.edu.tw/problems/2310) - [題本](https://contest.cc.ntu.edu.tw/npsc2022/teamclient/final-sen.pdf) - [2021 附中校隊培訓模競 pD 足球場](https://tioj.ck.tp.edu.tw/problems/2221) - 這題的測資現在還是爛到暴力可以過的那種 - [題本](https://drive.google.com/file/d/1WUqrnkFigLmt9TWWLoGJRhd4-11EhB8I/view?usp=sharing)