---
title: IOICamp 2023 Day 1 Contest Editorial
tags: editorial, competitive-programming
---
# IOIC 2023 Day 1 Contest Editorial
## pA 101. 這個魔法陣有夠煩（駭客題）
### Overview
要 hack 的 code 是個還算標準的圓線交點作法，詳細可以去看 IOIC 講義幾何的部分，這裡的 code 跟講義上的差異基本上只有:
* 我們是用包裝過的 `sqrt`，該函數嘗試處理遇到一個實際上要是 0 但因浮點數誤差而導致變成負很小數開根號的情況，因此若開完結果是 nan，則我們當作我們是因為餵給它負很小數而造成的，所以直接回傳 0
* 我們在判別浮點數大小關係時加入了 eps
看完要 hack 的 code 後，我們回頭確定一下題目要做的事情，它不僅僅是要我們構造出會錯的輸入，而是要讓輸出不是一些實數或 `"none"`
所以可以猜我們應該是要讓程式最後的輸出裡面有 nan 或 inf。
接下來的做法都考慮讓輸出 nan。
### Solution
#### All Zero
其實輸出
```
0 0 0 0
0 0 0
```
就會過了。
但是那是因為我題目限制忘記要求輸入是個合法的圓跟線了😭
賽中只有 Team 24 是用預期解通過這題的。
不過我們還是可以來檢視一下全 0 的時候會發生什麼事情。
因為全 0 ，所以直線退化成點了，也就導致在算圓心投影點的時候算出了 nan，而這個 nan 會被跟著塞進到 Sqrt 裡的 sqrt，並且經過 isnan，所以回傳 0，並落入 `interCircle` 中 `return {ft};` 的部分，然後我們就拿到了一個有 nan 的點了。
看起來很合理對吧?
但是如果你嘗試在 `Sqrt` 回傳 0 的部分印點東西，你會發現根本沒有東西被印出來，但是在 `Sqrt` 一進來的地方印 `x` 的話，可以發現 `x` 的確是 -nan，所以這表示我們上面的論述其實是錯的，只是剛好答對的。
那到底為什麼呢?
如果你嘗試把程式碼最上面 `#pragma GCC optimize("Ofast")` 拔掉，你就會發現現在的程式行為跟最一開始解釋的時候一樣了。
所以可以猜測是 `#pragma GCC optimize("Ofast")` 在搞怪。
在開了 `#pragma GCC optimize("Ofast")` 後會在多加入 fast-math 最佳化，而 fast-math 的一系列最佳化中包含了 finite-math-only 的最佳化，該最佳化會在假定所有運算都不會產生 NaN 與 Inf 的情況下做更多激進的最佳化，也因此導致 isnan 變成一個直接回傳 false 的函數，所以不會進去 `Sqrt` 裡面的那個 branch，而接下來的步驟就更會因為編譯器最佳化的細節不同而會造成不同行為，也因此較難分析，所以最後還是可能還是要回歸 proof by AC :P
但總而言之，在寫計算幾何題的時候雖然加 Ofast 可能會帶來不少的最佳化，但是也很有可能讓 debug 變得很困難，尤其是會不小心算出 NaN 或 Inf 的情況，因此建議不要隨手都幫 code 加 Ofast，以免 debug 很痛苦。
#### Construction
那所以正常的點跟線的話我們還有辦法構造出會壞的結果嗎?
仔細看 code 後發現我們會有 nan 產出的地方應該只剩下 sqrt 函數，而且前面我們已經知道 isnan 在 Ofast 下其實是假的，所以我們要做的事情就是想辦法餵負的東西到 sqrt 函數裡，然後剩下相信 GCC 會幫我們最佳化成我們想要的樣子。
觀察發現塞進 Sqrt 的東西其實有可能是負的，因為其實只有保證 dis <= r + eps，所以還是有可能 dis > r，因此我們就要來構造一個 r + eps >= dis > r 的輸入。
因為 dis 是投影點跟圓心的距離，所以代表我們要讓線跟圓不相交，但距離很近。
構法很多種，一種可能的構法就是把弄個半徑二的圓，然後再一條非常接近水平線的線讓它快要削到那個圓，例如穿過 $(1, 2)$ 與 $(10^9, 1)$ 的線。
或者你也可以例如強迫線的斜率是 1，然後用電腦努力爆搜滿足 $\lceil r \frac{\sqrt{2}}{2} \rceil - r \frac{\sqrt{2}}{2}$ 足夠小的 $r$ 之類的。
#### How to write code
不確定幾何講師會不會講，但是總之在寫幾何題的時候，雖然浮點數很方便，但是畢竟浮點數精度有限，所以還是要小心。
像是這種要算交點的題目，其實通常也都可以先用一些整數運算確認好交點數量，再下去直接求解，這樣就可以避免因為浮點數精度問題，導致比較兩數值時產生偏誤，進而導致程式出錯，或反而有更多的邊角狀況要處理。
有興趣的人可以確定一下自己真的會推全整數判斷圓與直線交點個數的式子😅。
## pB 180. 風のカタルシス（除蟲題）
把cmp改成clamp
## pC 193. 路徑規劃 Easy（除蟲題）
## pD 103. 路徑規劃 Hard（除蟲題）
## pE 128. 嵐珠的生日禮物 Mid（除蟲題）
## pF 104. 嵐珠的生日禮物 Hard（除蟲題）
## pG 105. 尤拉路徑（駭客題）
## pH 196. 尤拉路徑 Mid（除蟲題）
## pI 106. 尤拉路徑 Hard（除蟲題）
## pJ 129. 相親相愛挑戰 Mid（駭客題）
## pK 107. 相親相愛挑戰 Hard（駭客題）
## pL 127. 22/7 訓練計畫 Easy（除蟲題）
多輸入一些測資或是直接用看的應該可以發現算 hash 的時候算錯了，正確的方式應該是迴圈只能跑跟署名一樣長，但是這裡 code 只跑了 sizeof('a') 次，在 C++ 中也就是 1 次，所以我們需要想辦法修正他。
Edit Distance 是 4 的修正方式可以直接把 'a' 跟 'b' 改成 a 跟 b 即可，因為在前面有將 a 跟 b 都整個清零過，所以就算超過字串長度也只會拿到一堆 '\0'，而這在大部分的環境中經過 toupper [1] 後還會保證是 '\0'，而 0 的值有多少個都不影響我們特徵值的計算。
另外一個詭異的地方是題目要求每行開頭都輸出 `Case 0: `，但是原始的 code 是較正常會輸出 `Case %d:` 的版本，因次我們也要修正他。
因為輸入保證 $T$ 少於 100，所以我們可以歡樂的把 `kase` 除以 100 即會在每次都獲得 0。
一種 Edit Distance 是 0 的方式是直接在 `//**/` 中間插入空白變成 `/ /**/`，這樣 `//` 的第一個 `/` 就會是正常除法的 `/`，而後面的 `/` 則會與 `*` 結合成 `/*` 作為段落註解的開頭。
參考解答：
```cpp
#include <ctype.h> // toupper
#include <stdio.h>
#include <string.h> // memcpy
#define N 4
int T;
void solve() {
unsigned i;
char a[N * 2] = {};
char b[N * 2] = {};
struct T {
unsigned v, i;
} s1, s2;
scanf("%s%s", a, b);
s1.v = 0, s1.i = 1;
for (i = 0; i < sizeof(a); ++i)
s1.v = s1.v + (((unsigned)toupper(a[i])) << (i * 3));
s2.v = 0, s2.i = 2;
for (i = 0; i < sizeof(b); ++i)
s2.v = s2.v + (((unsigned)toupper(b[i])) << (i * 3));
if (s2.v < s1.v) {
memcpy(&s1, &s2, sizeof(T));
}
printf("%u %u\n", s1.v, s1.i);
}
int main() {
int kase;
scanf("%d", &T);
for (kase = 0; kase < T; ++kase) {
printf("Case %d: ",
kase / /*!*/ 100 /*?*/
);
solve();
}
return 0;
}
```
## pM 108. 22/7 訓練計畫 Hard（除蟲題）
出題的時候忘記 IOIC 趣味賽會忽視空白系列字元，導致貌似全部人都是非預期解過的😭。
順著 Easy 的版本我們知道我們需要減少修正特徵值計算時所耗費的 Edit Distance。
而大家的解應該都是基於 Ordinary multicharacter literal [2] 在有支援的情況下會是 int 型別的，這樣讓 `sizeof('a ')` 等價 `sizeof(int)`，而在大多數的環境下它都是 4，並且恰巧我們輸入的字串長度最多是 4，所以可通過此題。
如此的 Edit Distance 是 0。
參考解答：
```cpp
#include <ctype.h> // toupper
#include <stdio.h>
#include <string.h> // memcpy
#define N 4
int T;
void solve() {
unsigned i;
char a[N * 2] = {};
char b[N * 2] = {};
struct T {
unsigned v, i;
} s1, s2;
scanf("%s%s", a, b);
s1.v = 0, s1.i = 1;
for (i = 0; i < sizeof('a '); ++i)
s1.v = s1.v + (((unsigned)toupper(a[i])) << (i * 3));
s2.v = 0, s2.i = 2;
for (i = 0; i < sizeof(' b'); ++i)
s2.v = s2.v + (((unsigned)toupper(b[i])) << (i * 3));
if (s2.v < s1.v) {
memcpy(&s1, &s2, sizeof(T));
}
printf("%u %u\n", s1.v, s1.i);
}
int main() {
int kase;
scanf("%d", &T);
for (kase = 0; kase < T; ++kase) {
printf("Case %d: ",
kase / /*!*/ 100 /*?*/
);
solve();
}
return 0;
}
```
## pN 112. 20－不存在的SET－Easy（構造題）
特別感謝基礎數學講師許博翔的幫忙，有興趣了解相關理論細節的話可以找他。
以下將一個 anti-SET $S$ 變成裝向量而不是裝 index 比較方便理解，同時重新命名為 capset。
以下向量運算都在 $\mathbb{Z}_3^4$ 底下。
把範測的那一組 capset 所代表的向量全部平移一個 $b\in\mathbb{Z}_3^4$ 也會是一個 capset。$b$ 共有 $81$ 種，因此枚舉完所有的 $b$ 即可通過此題。
## pO 113. 20－不存在的SET－Mid（構造題）
先給一個重要的酷酷定理：
:::info
定理 1：對於任意兩個 capset $S,T$，存在一個**可逆矩陣** $A\in\mathcal{M}_{4\times 4}(\mathbb{Z}_3)$ 和一個向量 $b\in\mathbb{Z}_3^4$ 使得 $T=\lbrace Av+b\mid v\in S\rbrace$。
:::
證明：自己查 paper。
更正式的說，任兩個 capset 都是 affine equivalent。
以下我們定義 $AS+b=\lbrace Av+b\mid v\in S\rbrace$。
因此可以枚舉所有的 $A,b$ 然後判斷 $AS+b$ 是否為 capset，找到 $10^5$ 組相異的 capset 時就可以停止爆搜。
實作上可以用 `set<vector<int>>` 存 capset 方便去重。
注意枚舉 $A$ 的順序可能會影響找到答案的速度，當然也可以找到就打表，但理論上好好枚舉的話不需要打表。
## pP 114. 20－不存在的SET－Hard（構造題）
### Solution 1 (by 林煜傑)
我們延續 Mid 的做法。
對於一個 capset $S$，考慮他在 $\mathbb{Z}_3^4$ 底下的中心 $g_S=|S|^{-1}\sum_{v\in S} v$，不難發現如果 $T=AS+b$，則 $g_T=Ag_S+b$。注意到當我們固定 $A=I$(單位矩陣) 的話，有 $g_T=g_S+b$，換作是固定 $b=(0,0,0,0)$ 的話，有 $g_T=Ag_S$。
我們可以觀察出以下引理：
:::info
引理 1：對於一個 capset $S$，存在恰好一個 $b\in\mathbb{Z}_3^4$，使得"平移"後的 capset $T=S+b$ 的重心 $g_T=(0,0,0,0)$。
:::
:::info
引理 2：對於任兩個重心是 $(0,0,0,0)$ 的 capset $S,T$，如果**可逆矩陣** $A\in\mathcal{M}_{4\times 4}(\mathbb{Z}_3)$ 和向量 $b\in\mathbb{Z}_3^4$ 滿足 $T=AS+b$，則 $b=(0,0,0,0)$。
:::
引理 1 同時告訴我們對於兩個中心是 $(0,0,0,0)$ 的相異 capset $S,T$，不存在 $b_1,b_2\in\mathbb{Z}_3^4$ 使得 $S+b_1=T+b_2$。
綜合以上，我們可以想到以下找到所有 capset 的策略：
1. 找到所有重心是 $(0,0,0,0)$ 的 capset $S_1,S_2,\ldots,S_M$。
2. 對於每個 $S_i$，和每個 $b\in\mathbb{Z}_3^4$，輸出 $S_i+b$。
因為 $b$ 的種類有 $3^4=81$ 種，所以可以推得 $M=\frac{682344}{81}=8424$。輸出的部分很好處理，難是難在找到所有 $8424$ 個中心是 $(0,0,0,0)$ 的capset。
考慮 naive 的做法：先找到一組中心是 $(0,0,0,0)$ 的 capset $S$，接下來維護一個 `std::set`，枚舉所有 $A\in\mathcal{M}_{4\times 4}(\mathbb{Z}_3)$，如果 $A$ 是一個可逆矩陣，則把 $AS$ 丟進 `std::set`，一旦大小是 $8424$ 就終止。
根據官解，如果枚舉的順序是 $A$ 的每個元素按照 $2,1,0$ 的順序枚舉，則不到 $2$ 秒就能找完並輸出解。
### Solution 2 (by 吳柏燁)
注意，這是隨機解，我們不知道為什麼他這麼快，但它會過是事實。
我們用一個 `std::set` 來維護答案。
考慮以下步驟：
1. 隨機排序所有 $81$ 張卡所代表的個向量。
2. greedy 的把卡丟進一個集合 $S$ 裡，使得 $S$ 中的任三張卡都不形成 SET!
3. 如果 $|S|=20$，則執行 4.，否則回到 1.。
4. 將 $S$ 的四個維度進行重排成 $T_1,T_2,\ldots,T_{24}$，將所有 $T_i+b,b\in\mathbb{Z}_3^4$ 都扔進 `std::set` 中。
5. 如果 std::set 的大小是 $682344$ 就終止，否則回到 1.。
根據實測，本地 $30$ 秒左右就可以找到所有的 capset $^1$。不過不能直接打表，因為會 code length limit exceeded，所以必須要找到 $8424$ 個 capset 使得只用 $+b$ 平移就能產生出剩下的 capset。
根據 Solution 1 的分析，這其實很簡單，因為如果將 capset 當作節點，是否有平移關係當作邊，則這張圖會是由 $8424$ 個 clique 所組成。
所以隨便找一下並將該 $8424$ 個 capset 打表後就做完了。
$^1$ 這裡有個技術細節。為了加速，可以注意到一組 $20$ 個 $0$ 到 $80$ 之間數字可以一對一對應到 $0$ 到 $2^{81}-1$ 之間的數，所以 `std::set` 可以裝 `__int128` 來加速。
## pQ 110. 球球分教授（構造題）
首先觀察發現若定義 $f(x)$ 為第 $x$ 位教授的能力值，則 $f(x)$ 為一個 $x$ 的 $N$ 次多項式，另外題目同於：幫 $f(1), f(2), \ldots, f(2^{N + 1})$ 加上正負號使得全部加起來被 $M$ 整除。
而事實上 $M$ 是個幌子，我們可以透過數學歸納法證明對於任意 $N$ 次多項式 $f(x)$，必存在幫 $f(1), f(2), \ldots, f(2^{N + 1})$ 加上正負號的方法使得全部加起來總和為 $0$。
首先 $N = 1$ 將 $f(1), f(4)$ 取正，$f(2), f(3)$ 取負即可。
接著假設 $N = k$ 有解，當 $N = k + 1$ 的時候，定義 $g(x) = f(x) - f(x + 2^{k + 1})$，可以發現函數 $g(x)$ 為 $k$ 次多項式，且問題變成要將 $g(1), g(2), \ldots, g(2^{k + 1})$ 加上正負號使總和為 $0$，而這顯然就是 $N = k$ 的問題，所以根據數學歸納法也就證明完畢了。
因此可以簡單的從小的 $N$ 慢慢推廣到大的 $N$，另外這個想法也可以推出一個乾淨的構造法：根據 $x - 1$ 的二進位表示法 $1$ 個數的奇偶性分組即可。
## pR 120. IOICamp2023 的水題（構造題）
### Solution 1
枚舉所有 $1000$ 到 $9999$ 之間不是 $2400$ 的數字，找到一個解就輸出。
Time complexity: $O(9000)$
### Solution 2
不覺得 `IOICamp2023` 出現了若干次嗎？當然要 `IOICamp2023 will be amazing` 啊。
Time complexity: $O(1)$
## pS 149. 走蛋餅的路 Easy（8e7 題）
## pT 150. 走蛋餅的路 Mid（8e7 題）
## pU 130. 22/7 訓練計畫 Extreme（除蟲題）
這題的差異在於我們不採用 IOIC 趣味賽正常的 Edit Distance 計算方式了，我們這次連空白都會考慮進來，因此 Hard 版本的 Oridnary multicharacter literal 不能用了，但我們還是可以順著同樣的思路去解這題。
那要怎麼讓 `sizeof('a')` 是 4 呢?
如果仔細看 [2] 的話，會發現他說在 C 中 `sizeof('a')` 會是 4，所以我們就可以開心的直接把 `kase` 的部分修正好，然後選擇 C 語言傳到 Judge 上。
並獲得一個 WA!
在多看幾眼程式碼會發現 C 中的 `struct T` 型別除非有事先 `typedef` 過，不然都應該要用 `struct T` 來指涉，因此我們 `memcpy` 的 `sizeof(T)` 中的 `T` 現在變成指涉全域變數 `T`，也因此 `sizeof(T)` 變成 4，而導致複製時會沒把整個 struct 都複製好。
因此我們要找一個大小跟 `struct T` 一樣的東西來取代 `sizeof(T)` 中的 `T`，仔細看一看可以發現 `a` 或 `b` 都剛好大小是 `8`，與 `struct T` 的大小在絕大多數的情況下都一樣，所以我們直接把 `sizeof(T)` 改成 `sizeof(a)` 即可。
這樣搭配處理 `kase` 的方法就有一個 Edit Distance 1 的解答了。
參考解答：
```c
#include <ctype.h> // toupper
#include <stdio.h>
#include <string.h> // memcpy
#define N 4
int T;
void solve() {
unsigned i;
char a[N * 2] = {};
char b[N * 2] = {};
struct T {
unsigned v, i;
} s1, s2;
scanf("%s%s", a, b);
s1.v = 0, s1.i = 1;
for (i = 0; i < sizeof(a); ++i)
s1.v = s1.v + (((unsigned)toupper(a[i])) << (i * 3));
s2.v = 0, s2.i = 2;
for (i = 0; i < sizeof(b); ++i)
s2.v = s2.v + (((unsigned)toupper(b[i])) << (i * 3));
if (s2.v < s1.v) {
memcpy(&s1, &s2, sizeof(b));
}
printf("%u %u\n", s1.v, s1.i);
}
int main() {
int kase;
scanf("%d", &T);
for (kase = 0; kase < T; ++kase) {
printf("Case %d: ",
kase / /*!*/ 100 /*?*/
);
solve();
}
return 0;
}
```
### Extreme Extreme Version
這其實才是最初想出的題目，但是因為技術問題最後只放了前面的 Extreme 版本😰。
假設今天我們連換行都會算進 Edit Distance 的話其實還是有個 Edit Distance 1 的解答。
這次我們沿用前面修正特徵值計算的方式，而來想辦法減少處理 `kase` 所要花的 Edit Distance。
因為修正特徵值已經用掉 1 的 Edit Distance 了，我們現在不能再 Edit 了，因此剩下可以著手的點大概就剩 Compiler 了，仔細研究會發現 IOIC Judge 是支援 ANSI C 的，而且 ANSI C 是沒有段落註解的，所以其實 `kase` 那行在 ANSI C 下會直接被解釋成除以 100，於是我們就可以開心的用 ANSI C 傳這題，然後 AC !
參考解答：
```c
#include <ctype.h> // toupper
#include <stdio.h>
#include <string.h> // memcpy
#define N 4
int T;
void solve() {
unsigned i;
char a[N * 2] = {};
char b[N * 2] = {};
struct T {
unsigned v, i;
} s1, s2;
scanf("%s%s", a, b);
s1.v = 0, s1.i = 1;
for (i = 0; i < sizeof('a'); ++i)
s1.v = s1.v + (((unsigned)toupper(a[i])) << (i * 3));
s2.v = 0, s2.i = 2;
for (i = 0; i < sizeof('b'); ++i)
s2.v = s2.v + (((unsigned)toupper(b[i])) << (i * 3));
if (s2.v < s1.v) {
memcpy(&s1, &s2, sizeof(b));
}
printf("%u %u\n", s1.v, s1.i);
}
int main() {
int kase;
scanf("%d", &T);
for (kase = 0; kase < T; ++kase) {
printf("Case %d: ",
kase //*!*/ 100 /*?*/
);
solve();
}
return 0;
}
```
### References
[1] https://en.cppreference.com/w/cpp/string/byte/toupper
[2] https://en.cppreference.com/w/cpp/language/character_literal
Sign in with Wallet
Connect another wallet