# TIOJ 爛測資補修計畫 鑑於 TIOJ 上許多題目測資太爛（有些甚至無法驗證解的正確性）， 請各位在寫到測資爛的題目時來這裡回報，某個人會盡可能改善他們。 目前的計畫是一題一題修，盡可能在 TIOJ 低峰時 Rejudge。 ## 測資報修格式 爛測資分為兩種： 1. 壞掉的測資 如輸入 $m$ 條邊實際上卻不足 $m$ 條、題目限制輸入 $\le 10 ^ 5$ 卻超出 `long long` 等較嚴重的問題，會**導致正確的程式碼無法通過**的問題。 例如：1709。 這類題目經回報會先打上 `broken` 的標籤。 2. 太弱的測資 如卡不掉假解、輸入量太小等較不嚴重的問題。 例如：1807。 如果要報修，請提供「題號、原因、Submission 編號、此 Submission 問題詳細說明」，如： - 1807 原因：測資範圍明顯有問題，且無法驗證解的正確性 Submission 編號：208419 Submission 問題：只驗證輸入邊數是否大於完全圖卻通過所有測資。 其中，有問題的 Submission 可能是正解卻被排除（測資生爛），或是假解卻沒有被卡掉。 請在「Submission 問題」裡註明這筆假解的錯誤處、或是你是怎麼驗出測資錯的。 請注意，**確認自己的解沒有意外 bug**再丟上來，這不是 debug 板。 被回報為「太弱的測資」的題目不一定會修。 ## 要如何（在看不到測資的情況下）確認問題？ 請善用 `<cassert>` 裡的 `assert()`，有時可以驗出測資根本生不夠輸入等問題。 ## 我有其他問題 qwq 請私訊 `FHVirus` 或其他認識的 Admin。 聯絡方式： - froghackervirus@gmail.com - Instagram: @FH.Virus - Discord: FHVirus #4823 --- ## 「已經修正／補強的題目」 - 1877 2022/08/01 已修正：題敘修正為長度 $\leq N/2$，測資修正與加強 - 1391 & 1392 2022/08/01 已修正：題敘修正為 $1\leq T\leq 100$ - 1406 2023/09/15 已修正：增強測資，感謝 YiaHong 提供 hack --- ## 「壞掉的測資」回報區 - 1709 原因：測資點 #8 #9 #12 輸入邊數不足。 Submission 編號：258223 Submission 問題：經 Assert 驗得上述問題。 - 1249 原因：測資點 #5 #6 #8 #9 有重複測資，與題意「沒有兩個人帳號一樣」矛盾 Submission 編號：259515 Submission 問題：經 Assert 驗得上述問題 ((原本用`set`寫，後來改成`multiset`就過了 - 2115 原因：測資錯了，NPSC 官解是錯的 Submission 編號：178534 Submission 問題：他可以找到比官解還好的解，經下載 NPSC 測資後輸出構造後確認定是合法的，不確定每一筆錯的是不是都有打贏，但至少現在的測資應該不是對的 - 1879 原因：經管理員查看第 8 號測資邊數不足 - 1305 原因：測資與輸入範圍不符 Submission 編號：296344 Submission 問題：在測資 #5 #7 assert 出 insert 次數超過 $10^4$ 次 - 1405 原因：測資不合題意 Submission 編號：310724 Submission 問題：在測資 #18 assert 出輸入的排列不是 self-inverse，違反光的可逆性。 註 1：可和 AC 的 310725 對照。 註 2：這題用 `ios::sync_with_stdio(false);` 會拿到 WA，建議修正或加註警語。 - 1726 原因：測資和輸入範圍不符 Submission 編號：321963 Submission 問題：在測資 #5 #6 #7 assert 出不符合 $1\leq C_i \leq N$ - 1228 原因：時限變太小 Submission 問題：每筆測資時限 1000 ms，但可以從其他 submission 中知道在時限還沒變小以前可 AC 的做法執行時間會超過 1000 ms，現在上傳會 TLE --- ## 「太弱的測資」回報區 - 1807 原因：測資範圍明顯有問題，且無法驗證解的正確性 Submission 編號：208419 Submission 問題：只驗證輸入邊數是否大於完全圖卻通過所有測資。 - 1236 原因：使用不完整的最大流模板依然可以過 Submission 編號：256219 Submission 問題：`add` 裡面反向邊的 index 錯誤，應 +1 - 1253 原因：除了第一筆，其他都只有一筆測資 Submission 編號：258269 Submission 問題：我沒給ans++都能過第一筆之外的 - 1590 原因：測資實際上遠小於題目限制 Submission 編號：247255 Submission 問題：原題的限制下開值域大小的陣列應該會MLE，但只要把陣列開小一點就能過了 <!-- comment: 我沒看這裡列的題目，但就我所知好像有些題目是故意擺弱的測資，雖然這可能不是一件好事，不過不知道有沒有考慮過這件事呢? --> <!-- comment: 感謝提醒，在開修之前我會先注意一下這件事的 >< --> - 1399 原因：無法卡掉複雜度不正確的解 Submission 編號：253845 Submission 問題：題目要求應為 $O(nT)$，但 $O(n^2 \log T)$ 也會過，還比 $O(nT)$ 快許多。 - 1178 原因：無法卡掉不正確的解 Submission 編號：262500 Submission 問題：題目說「所謂凸包上的頂點，指的是轉折處(邊上的點不算)。」可是如果把邊上的點也算進去還是可以過。 - 1798 測資實際上遠小於題目限制 Submission 編號：271426 Submission 問題：陣列開5e5也能過 - 2205 測資太爛 - 1410 原因：題目值域實際上只有 $\le 10^5$ - 1811 原因：暴力找轉移點會過 Submission 編號：290166 - 1902 原因：$O(N^2+Q)$ 會過 Submission 編號：238873 - 1049 原因：沒有卡好邊界 Submission 191290 303047 都會過 - 1412 原因：無法卡掉假解 Submission 編號：308055 && 308074 Submission 問題：判斷函式中應回傳sum >= k * m，但回傳sum >= k也會AC - 2226 原因：subtask沒有卡掉漏判edge case的解 Submission 編號：343271 Submission 問題：沒判斷k=0的情況可以拿57分
Last changed by  
 
FHVirus
背包問題比 FFT 難 QWQ

Read more

Notes for FFT Course

:::success source: MIT OCW 6.046 2015 spring ::: Polynomials $$ \begin{align} A(x) &= a_0x^0 + a_1x^1 + \cdots + a_{n-1}x^{n-1} \ &= \sum_{k=0}^{n-1}a_kx^k \ &= <a_0, a_1, \cdots, a_n-1>

8/12/2022
計算幾何＆其他

by FHVirus 閒聊時間 大綱 暖身題 一些基本的運算 凸包 多邊形面積

6/4/2022
蛋餅已經在 ISSC 電爆我了 QQ 題解

題目背景 總之有點背包問題？一開始還被 youou 說題目太簡單了。 Subtask 也幾乎都是亂來的： Subtask 1 是 8e7 提議說要不要出一個所有拉麵都一樣重的 Subtask，但是好像有更好撈分的所以就這樣吧。 Subtask 2 理論上是可以枚舉所有子集之類的，但是 Subtask 2 ~ 4 其實都是同一個解法。 Subtask 5 是卡輸入輸出，防破台用（惡趣味）。 測資也總共才十一筆，希望是沒有人唬爛過的啦 ><

4/26/2022
TIOJ ApfCon 2022 Editorial

pA Setter: 8e7 首殺: apf22_011 (2022-03-31 17:15:34) 就是Wordle啦 上傳一個五個小寫英文字母的合法單字，用verdict看結果。 WA: 非法輸入 AC: 綠色 RE: 黃色

4/26/2022
Read more from FHVirus
Published on HackMD