# 秘密任務 - 題庫建立指南及檢討
[toc]

## 目標
## 一個題目需要...?
### 題敘
題敘是讓答題者了解此題目的的目標的部分，其必須盡量讓答題者能懂題目要求，更應藉由此部分讓答題者依照要求的規格輸出答案。
其可分為以下幾個部分：

#### 題目本身
通常答題者會希望於此看到生活化的例子，而不是直接擺出公式。通常 NP 題都會有對應的實際應用例子，例如 graph coloring 對應到的是 compiler 中的 registor allocation 問題
:::info
範例：
阿霆是一個電路設計師，在一塊電路板上有許多節點和可以製成電路的路徑，節點之間不一定直接相通，但必定有路徑可以讓節點之間形成通路，今天阿霆接到專案，專案指定電路板上有幾個一定得到達的節點，但由於刻製電路路徑皆是成本，專案特請阿霆於這些節點及路徑間找到一個最小成本的路線，且這個路線必須經過需要到達的節點組合。

上述的問題其實是要求各位於圖中找到最小的斯坦納樹，此即為斯坦納樹問題，是一個世界知名的 NP-hard 問題。
:::
#### 輸入說明
此部分用於表明程式所讀入的測資內容，有些資料庫已有既定格式也應於此段講述，必須清楚描述內容每行及每個數字代表意義。
:::info
範例：
史坦納樹問題使用 STP 資料格式作為輸入，則可參照其來源提供會用到的部分資料意義，範例如下：

輸入內容需注意以下：
- 每行為一個輸入單位
- 若該行的最前面有 # 則該行忽略
- 空白行忽略
- 每一個檔案的最開頭必為

33D32945 STP File, STP Format Version 1.0

參考: [steinlib](https://steinlib.zib.de/format.php)
:::
#### 輸出說明
分為兩個部分
* **程式輸出**用於表明每一筆測資期望的輸出，包括輸出格式、需不需要考慮順序以及浮點數精確度等限制。
* **驗證程式**則有以下幾種狀況需要顯示，除了以下狀況外不需要提供額外資訊給考生，並且遇到一筆測資錯誤即刻結束程式。
:::info
會有三種訊息：
`case i: File not existed!`
`case i: Accepted!`
`case i: Wrong Answer!`

範例：

case 1: Accepted!
case 2: Accepted!
case 3: Wrong Answer!

:::
### 限制
限制是為了表明測試資料的範圍，是讓答題者了解此題的測試目的重要區域，常見的限制有：
- 數字大小
- 測資內容數量
- 正負值
:::info
範例：
$\quad1 \leq$ $N$ $\leq 10^4$
$\quad1 \leq$ $p_i$, $w_i$ $< 2 ^ {64}$
$\quad0 \leq$ $W$ $\leq 10^7$
:::
### 測資
* GitHub 上有很多 NP 問題的 solver，通常都會附或 reference 有最佳解的 data set，可以直接在 GitHub 上搜尋會比在 Google 搜尋更有效率
* 除了已有最佳解的 data set 外，也可以自行生成資料，請注意測試 edge case 以及測資複雜度，以保證在考試時間內無法被暴力解答。
:::info
範例：
:::

### 現有測資
* [Graph data 討論串](https://cstheory.stackexchange.com/questions/739/data-for-testing-graph-algorithms)
* [SNAP: graph data generator](https://snap.stanford.edu/snap/index.html)
* NAS 上的 `home/題庫/dataset.txt` 有紀錄一些找到可用的

### 答案/最佳解
對於 NP 問題，由於已經確保在考試時間內無法得到最佳解，所以我們用一個比值來呈現作答情形。設計比值的原則為，若越靠近最佳解，比例考生得到的比例會越接近 1，越接近最差解或是我們另外取的 lower bound 的話就越接近 0。注意在算把職之前要先檢驗考生的答案是否為解答，如果不具作為解答的資格，則直接輸出 Wrong Answer! 並結束驗證
:::info
範例：
以 maximal independent set 為例，比值算法為 `(考生所找的 independentset 的大小) / 最大 set 大小`，最大 set 大小是自己跑出來的最佳解或是資料及提供的最佳解，真的跑不出最佳解可以自己寫一個已知最好的近似演算法求解 (需要先請老師認證)

輸出格式為 xx.xx%
:::

### Lower bound 下界/最差解
NP-Hard 的題目不一定每個算法都能求到最佳解，但通常會取得**近似解**， Lower bound 則是訂出了對於近似解的容許範圍，lower bound 通常要靠自己利用較差的解法運算取得，低於 lower bound 但符合規格的答案判斷為 0 分。lower bound 的選擇通常直接找老師討論，並使用該題的比值 $R$ 與比值下界 $L$ 進行正規化，正規化公式為 $max{(( R - L)/(1-L), 0)}$，視情形每個 case 逐一正規化或是平均完再正規化
:::info
範例：

std::cout << "Average of your_set_size / best_set_size: " <<  std::setprecision(2)  << std::fixed 
            << Ratio / TEST_COUNT * 100 << "%" << std::endl;
std::cout << "Formalized as " << std::setprecision(2)  << std::fixed
            << std::max((Ratio / TEST_COUNT - AVG_RATIO_LB) / (1 - AVG_RATIO_LB), 0.0) * 100 << "%"
            << std::endl;

:::

## 題目範本

### 題敘 latex 範本
- [史坦納樹問題](https://www.overleaf.com/2521816724mxzybhtmvycc)
### 題目相關 Code
參照 SIVSLAB FTP

## 20221119_測驗檢討記錄
### p1 01背包問題
### p2 著色問題
* datasets link http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html 因每個dataset的表現形式不同，需參考 http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf 轉換成統一的格式。
* 有一位考生表示verifier會產生inf是因為他的輸出錯誤所導致。
### p3 All pair shorest path
問題敘述不夠清楚，大致為以下幾點
* $a$ 與 $b$ 是否可以為同一人？
* 需不需要考慮由 $a$ 經過某一路徑後傳給 $a$ 本身？
* 測資有問題導致必須考慮
* 統計時的分母與分子定義不夠清楚
* 若 $a$ 走不到 $b$，是否需要統計入分母？
* 若 $a$ 走不到 $b$，距離是 0 還是無限大？
### p4 Set Cover
kind of easy, 適當 greedy 就會有 9x%

### p5 史坦納樹問題
- Lower bound 的運算式在出題後期才拔到 verifier 之外，是因為此題 lower bound 的運算實際運行需要花上 2 小時，故後將 lower bound 預先計算出來放入程式內運行。
- 考試期間有發現此題 verifier 出現問題，原因是驗證程式沒有考慮到考生答案與 lower bound 完全相同之狀況，導致程式出現 negative zero 而無法被程式中的條件式攔截，造成程式異常跳出。
- 若有執行起來應會有較花時間的解，我認為可以給學生一個解應該要有的時間參考依據，避免學生答此題花太久時間結果解在 Lower bound 之外。

### 考場及環境相關
* 考生進考場就必須將除了應試用具之外的東西放置於保管處
* 建議系辦請廠商把 wifi 介面卡拔掉，用不到
* 派送環境前應檢查我們測試的暫存檔也要清掉
* `bits/stdc++.h` 不在標準內，要使用必須啟用 g++ flag `-std=c++11`，所以正常來說不會編譯是沒問題的，要用的人要自己啟用 flag，所以沒有義務要幫他們解決無法使用該標頭檔的問題

---
## 考生回饋
A feedback: https://koyingtw.github.io/2022/11/20/%E6%88%90%E5%A4%A7%E8%B3%87%E5%B7%A5%E7%94%B2%E7%B5%84

另外聽到一些討論是一階使用 APCS 作為篩選標準為競技程式導向，二階卻不考競技程式的題目使得一階的篩選沒有意義。如果上機考內容不變，需要考慮調整一階篩選標準。測試環境的部份，可以考慮在考試題目說明中提示可以在 shell 中使用 redirect，將測資以 stdin 輸入給他們的程式，也可以 redirect stdout 為輸出檔，當天大部分人都是用讀檔或是複製貼上。我們提供的測資編碼也要注意，也不可以有不可顯示字元，verifier 可接受的編碼類型因為 windows 上的 compiler 預設是 UTF16LE 所以需要注意。若是使用伺服器驗證應該就沒有這類環境問題，也不須擔心 Linux 太易於 binary exploit verifier 而禁用，也不須不停測試 verifier 可不可以使用。