# [2023.02.18] 1st UCup, Stage 4: Ukraine

> The 1st Universal Cup. Stage 4: Ukraine.
> Contest link: https://qoj.ac/contest/1106

分工：
- 金刀：FGHIJKLMN
- 重諺：ABCDE
- 迺絜：打模板

> 先從 F 開始看起（加最少邊使二分圖不能三著色），發現他答案一定 $\le 5$ 感覺可以判 case。
> 接下來 G 是經典的 Hamiltonian Path 問題，不過他的 $n$ 到 $24$ 又要算出全點對的答案，算了一下發現 $\mathcal{O}(2^n n^2)$ 不會過就丟一邊。
> H 完全沒想法先丟一邊。
> I 看到了數字只會增加至多一，於是想說先在外圍墊一圈數字讓他一定會加一，然後再去數有幾種右上到左下的輪廓線。
>
> [name=SorahISA]

> 首先我打算先把題都看完，然後我大概看到 B 的時候發現計分板上 A 很多然開，於是就問了一下金刀，然後我就去寫 A 了
> [name=mmi366127]

> 接著重諺問我 A 直接 sort 是不是好的，不過想了一下之後看到範測 $(1, 2, 3, 4, 5)$ 是排成 $(2, 4, 5, 3, 1)$ 就知道想錯了，於是就直接 claim 由大到小左右交錯排就好。
>
> [name=SorahISA]

- 0:25 pA Accepted (+0)

> 我接到重諺丟過來的 E，並且把圖論題 FGH 丟給迺絜想。
> 迺絜提到最多只會切兩段，我用全部 xor $=0$ 的 case 反駁掉之後發現應該不會切到超過三段。分析了幾種 case 發現只有在 xor 只有不到兩種可能的時候會無解。
> 途中因為用 `set.contains()` 跟打錯字（`i+2` 打成 `i+1`）吃了一次 CE 還有一次 WA。
>
> [name=SorahISA]

- 0:37 pE Compile Error
- 0:37 pE Wrong Answer
- 0:38 pE Accepted (+1)

> 接著我繼續看題目，看一段時間才看懂 K，不過中間有穿插去想 F 和 I，然後 claim 了 K 是 SCC，但不確定是不是對的，所以就先去幫忙想 F 和 I。
> [name=mmi366127]

> 因為 F 的答案 $\le 5$，所以就打算一個一個 case 來判斷，之後因為「是二分圖」以及「$m \ge 2$」又把區間縮成 $[2, 4]$。
> 為了判斷答案是不是 $2$ 要找到有沒有 $K_{2,2}$ 存在，我們想了幾種方法：
> 1. 枚舉左邊每個點對，計算右邊交集，$\mathcal{O}(n^3 / 64)$ 太慢。
> 1. 因為之前印象中可以用 $\mathcal{O}(m \sqrt{m})$ 判斷 $4$-cycle，於是我就陷入了分塊地獄。
>
> [name=SorahISA]

> 然後金刀丟了 J 給我，我證了他的答案只會是 $-1$, $n-2$, $n-1$
和 $n$，然後我會判 $-1$ 和 $n$ 的 case，但是 $n-1$ 的 case 不好判，比單純的動態逆序數對還麻煩很多的感覺，就想找多一點性質來用。
> [name=mmi366127]

> 接著我想了想，覺得 K SCC 的想法應該是沒有錯，然後就開始實作了，然後就過了。
> [name=mmi366127]

- 1:36 pK Accepted (+0)

> 接著我看迺絜分析了 D，然後繼續看了一下 J 跟 I，接著他慢慢發現好像題目其實蠻梗的。然後金刀就把他 AC 了。
> [name=mmi366127]

> 我們想知道如果直接把 `dis[i][j] % 2 == 1` 的邊連起來會怎麼樣，最後發現這好像就是解。
> 我寫了一個爛爛對拍發現好像沒問題就傳上去 AC 了。
> 可惜迺絜大約三個小時後離開了，沒辦法看到這個 AC。
>
> [name=SorahISA]

> 如果一張圖是二分圖，那麼直接把`dis[i][j] % 2 == 1` 的邊連起來就做完了。
> 所以我就考慮一個奇環看看，結果發現要是有一個距離的 parity 不對，那個要是考慮加邊的話就勢必要改變一個原本沒有連邊的 parity。
> 反之，如果拔邊的話，因為在一個奇環上所以拔邊以後原本的 parity 關係也會被 flip。
> 根據上面這個觀察，不管怎樣直接連`dis[i][j] % 2 == 1` 的邊，然後驗證是否有解即可。
>
> [name=迺絜]

- 3:21 pD Accepted (+0)

> 接著我想了一個 F 的想法，把邊的 pair 用 sort 的，但被金刀發現 pair 數量太多，然後我又提出了可以用一個陣列去紀錄出現的 pair，然後金刀就發現其實最多只會有 $\mathcal{O}(n^2)$ 種 pair，所以複雜度最多 $\mathcal{O}(n^2)$，然後就做完了...
>
> [name=mmi366127]

- 3:36 pF Accepted (+0)

> 直到最後我把數字的格子畫出來，才發現這樣就等同於右上到左下的路徑記數，然後就把想法交給重諺做完了 .\_.
> 中途一直想要從左上往右下做類似輪廓線的東西，或是二維的直升機抓寶，燒雞 QQ
>
> [name=SorahISA]

> 接著我繼續想 J，但是沒有比較不毒瘤且沒有 TLE 風險的方法。然後就是用金刀的想法做 I 了，做一做就 AC 了
>
> [name=mmi366127]

- 4:45 pI Accepted (+0)

## 結果

- Rank: 102 / 169 (Mirror)
- AC: 6 / 14 (`A..DEF..I.K...`)
- Penalty: 881

## 燒雞

- 金刀：
- 感覺這場一直在嘗試 claim 東西，證明的時候也比較多在 brute force 看看有沒有反例，之後賽後補題應該多練習證明。