---
type: slide
---

<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) 生出不同的測資

產生出 t = 10, l = 1, r = 2, type = random 的測資
![](https://i.imgur.com/gohkJno.png =420x)

----

可以根據不同傳進去的參數去產出想要的測資，這個是比較簡單題目的，通常會分一堆case
大概平均都會寫個百行
像是圖論題目來說，可能就要分有自環、重邊、仙人掌圖、菊花圖、樹、單環、鍊不連通圖...等等case去分別產出
所以...要生出好測資很難 QQ

---

## Validator

驗證你產出來的測資 Test input 是符合題目測資限制範圍的

以下為題目 [Frozen Scoreboard](https://codeforces.com/gym/369935/problem/F) 的 Validator
![](https://i.imgur.com/SfCywcZ.png)

----

判斷是否符合題目限制，以 Frozen Scoreboard 這題為例
- 輸入的 n 在 1-1000
- 輸入的 時間為2位數且都是 0-9
- 每一題的 CORRECT 數量最多只出現一次
- 狀態只有 CORRECT, WRONG-ANSWER...等
以上等等

可以用正則表達式判斷是否符合輸入限制
記得每個空白、換行以及 EOF 都要判斷

----

## Validator 常用函式

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 之後產出來的結果
因此要用同一種參數 後面要多加一些額外的參數

![](https://i.imgur.com/7kzb2Zq.png)

以上為使用 gen 這個 generator 產出 n 為 xxx v 為 xxx.. 的測資

----

範例測資以及一些特殊測資也可以直接上傳檔案

如果是範例測資記得在 Use in statement 打勾

![](https://i.imgur.com/2LNBMj0.png)

---

## Stresses

對拍
可以用 generator 產出指定範圍的測資，用兩個程式(一個為AC code,另一個假解) 去跑測資
會不斷產random測資直到找到一組測資，使得對出來的答案不同或者使得TLE為止，可以把對拍到的加進去測資裡

![](https://i.imgur.com/9mJE7mE.png)

以上圖為例產出 n 在 30-40之間的 ... 等參數，後面的 Countertest 是一筆找到錯的測資

---

## Invocation

會跑指定的solution以及指定的測資，會跑出所有結果可以看是否符合預期

![](https://i.imgur.com/9QaGzTb.png)

而可以發現結果有些底色為藍色或橘色
是提示執行時間與題目時間限制(TL)相近

![](https://i.imgur.com/8CFZ0qF.png)


橘色代表執行時間與TL相差在兩倍以內，藍色為在三倍以內
Polygon 會希望你設的TL與正解的code應該設在兩倍以上否則或時間卡太緊很危險
以及如果應該TLE的程式碼只差在兩倍以內也怕會被剪枝過

---

## Packages

題目都產好之後如果要放 domjudge 等，先 commit 後就可以按 package 打包下來記得按 full 才會有完整測資
如果是用 windows 系統就按 windows
而如果有上面的 test, solution, validator 沒處理好的他不會讓你 package
一定要先確保都處理完才能用

![](https://i.imgur.com/MCqS3dg.png)

打包下來後可以使用 [p2d](https://github.com/rjalfa/polygon2domjudge) 轉檔後
就可以直接丟 domjudge 的 problem achieve 了
記得 special judge 等要額外處理，細節會在 domjudge 教學那邊再介紹

---

## 總結
以上為大概介紹，基本上出題需要的功能都有了

### 優點
- 題目品質佳
- 上傳至 domjudge 或 codeforces 方便
### 缺點
- 處理的時間比較多

----

## 注意事項

1. 更新題目前先 Update Working Copy
2. 每次更新完題目都要記得 Commit Changes
3. 在 Manage access 把隊友以及我加進去

![](https://hackmd.io/_uploads/H1cE5ELMa.png)

----

## 目標

每隊出一題，範圍如下

- 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   前產生假解唬爛、增強測資