# 2024 YCPC 解 by SorahISA

- [Contest Link](https://codeforces.com/contestInvitation/518b22b971a57def992bb054497007aa839488de)
- [Scoreboard](https://codeforces.com/spectator/ranklist/1032166ab4503d6e76067f596f25113c)

## Problem A. Trip Counting I <span class="medium pill">Medium</span>
> ###### Problem Setter: hank55663

補圖上數 $C_3$。

原圖上三個點如果有 $k$ 條邊 $\implies$ 補圖上有 $3-k$ 條邊。

- 有 $A_0 = \binom{n}{3}$ 個點 tuple 至少有 $0$ 條邊（任三點）；
- 有 $A_1 = m \cdot (n-2)$ 個點 tuple 至少有 $1$ 條邊（每條邊都往外找任意一個點）；
- 有 $A_2 = \sum_{i=1}^{n} \binom{\text{deg}(i)}{2}$ 個點 tuple 至少有 $2$ 條邊；
- 有 $A_3 = \# C_3$ 個點 tuple 是 $C_3$。

答案就是 $3! \cdot (A_0 - 3 A_1 + 3 A_2 - A_3)$。

https://github.com/OmeletWithoutEgg/ckiseki/blob/master/codes/Graph/CountCycles.cpp

TC：$\mathcal{O}(m \log m)$。

## Problem B. Trip Counting II <span class="hard pill">Hard</span>
> ###### Problem Setter: hank55663

數 $C_4$。

https://github.com/OmeletWithoutEgg/ckiseki/blob/master/codes/Graph/CountCycles.cpp

TC：$\mathcal{O}(m \log m)$。

## Problem C. Trip Counting III <span class="easy-medium pill">Easy Medium</span>
> ###### Problem Setter: hank55663

數 $C_5$。

注意 $n$ 跟 $m$ 很小，亂做就好。看起來大家都沒有通過閱讀測驗。

我的做法是枚舉三條相鄰邊 $(a, b), (b, c), (c, d)$ 然後計算 $a$ 跟 $d$ 共同鄰居扣掉 $b$ 跟 $c$ 的數量。

TC：$\mathcal{O}(m^3)$。

:::spoiler Code

void solve() {
    int N, M; cin >> N >> M;

    vector<pii> edges(M);
    vector<bitset<maxn>> adj_mat(N+1);
    for (auto &[u, v] : edges) {
        cin >> u >> v;
        adj_mat[u][v] = adj_mat[v][u] = 1;
    }

    vector cap(N+1, vector<int>(N+1, 0));
    for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) cap[i][j] = (adj_mat[i] & adj_mat[j]).count();

    ll ans = 0;
    for (int i = 0; i < M; ++i) for (int j = 0; j < M; ++j) for (int k = 0; k < M; ++k) {
        if (i == j or i == k or j == k) continue;
        auto [i1, i2] = edges[i];
        auto [j1, j2] = edges[j];
        auto [k1, k2] = edges[k];
        if (i1 == j1) swap(i1, i2);
        if (i2 == j2) swap(j1, j2);
        if (i1 == j2) swap(i1, i2), swap(j1, j2);
        if (j1 == k1) swap(j1, j2);
        if (j2 == k2) swap(k1, k2);
        if (i2 == j1 and j2 == k1 and i1 != k2) {
            ans += cap[i1][k2] - adj_mat[i2][k2] - adj_mat[i1][k1];
        }
    }
    cout << ans << "\n";
}

:::

## Problem D. Rearrangement <span class="easy pill">Easy</span>
> ###### Problem Setter: henotrix

經典 greedy 題，每個 column 由小排到大就是最佳解。

證明可以用 exchange argument 證。

:::spoiler Code

void solve() {
    int N, M; cin >> N >> M;

    vector arr(M, vector<int>(N, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) cin >> arr[j][i];
    }
    for (int j = 0; j < M; ++j) sort(ALL(arr[j]));

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j+1 < M; ++j) {
            ans += abs(arr[j][i] - arr[j+1][i]);
        }
    }
    cout << ans << "\n";
}

:::

## Problem E. Elimination Game <span class="easy pill">Easy</span>
> ###### Problem Setter: henotrix

觀察一下應該就能發現只要不是 $a = 0$ 或 $b = 0$ 就能讓任何數字留下來。

$a = 0$ 就只可能留最大的，vice versa。

:::spoiler Code

void solve() {
    int N, A, B, X; cin >> N >> A >> B >> X;

    if (A == N-1 and X != 1) cout << "No" << "\n";
    else if (B == N-1 and X != N) cout << "No" << "\n";
    else cout << "Yes" << "\n";
}

:::

## Problem F. Destroying Monsters <span class="easy-medium pill">Easy Medium</span>
> ###### Problem Setter: henotrix

經典 greedy，把 gun 依照左界排序。

:::spoiler Code

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> X(n);
    for (auto &x: X) cin >> x;
    vector<pair<int,int>> G(m);
    for (auto &[l,r]: G) cin >> l >> r;
    sort(ALL(X));
    sort(ALL(G), [&](auto a, auto b) {
        return a.first < b.first;
    });
    bool can = true;
    int ans = 0;
    for (int i = 0, j = 0; i < n; ) {
        int mx = -1;
        while (j < m and G[j].first <= X[i]) {
            mx = max(mx, G[j].second);
            j++;
        }
        if (mx < X[i]) {
            can = false;
            break;
        }
        ans++;
        while (i < n and X[i] <= mx)
            i++;
    }
    if (not can) ans = -1;
    cout << ans << endl;
}

:::

## Problem G. Graph Coloring Problem <span class="easy-medium pill">Easy Medium</span>
> ###### Problem Setter: henotrix

看限制可以大概感覺的出來要把邊由小到大加進去離線回答詢問。

只要一個 DSU 來維護最大連通塊大小就好了。

:::spoiler Code

struct Qry {
    int id, k, ans;
};

struct Edge {
    int u, v, w;
};

struct DSU {
    vector<int> ary;
    int mx = 1;
    DSU(int n): ary(n, -1) {}
    int find(int x) { return ary[x] < 0 ? x : ary[x] = find(ary[x]); }
    bool merge(int u, int v) {
        debug(u, v);
        u = find(u), v = find(v);
        if (u == v) return false;
        if (-ary[u] < -ary[v]) swap(u, v);
        ary[u] += ary[v];
        mx = max(mx,  -ary[u]);
        debug(mx);
        ary[v] = u;
        return true;
    }
    int mxsz() {
        return mx;
    }
};

signed main() {
    fast;

    int n, m, Q;
    cin >> n >> m >> Q;
    vector<Edge> edges(m);
    for (auto &[u,v,w]: edges) {
        cin >> u >> v >> w;
        u--; v--;
    }

    vector<Qry> qry(Q);
    for (int q = 0; q < Q; q++) {
        qry[q].id = q;
        cin >> qry[q].k;
    }

    sort(ALL(qry), [&](auto& x, auto& y) {
        return x.k < y.k;
    });

    sort(ALL(edges), [&](auto& x, auto& y) {
        return x.w < y.w;
    });

    DSU dsu(n);
    for (int q = 0, e = 0; q < Q; q++) {
        while (e < m and edges[e].w <= qry[q].k) {
            dsu.merge(edges[e].u, edges[e].v);
            e++;
        }
        debug(qry[q].id, dsu.mxsz());
        qry[q].ans = dsu.mxsz();
    }

    sort(ALL(qry), [&](auto& x, auto& y) {
        return x.id < y.id;
    });

    for (auto q: qry)
        cout << q.ans << '\n';

    return 0;
}

:::

## Problem H. Points Separation <span class="medium pill">Medium</span>
> ###### Problem Setter: henotrix

找 $(qx_i, qy_i)$ 跟凸包最短距離，然後答案就是中垂線。

最短距離要嘛是戳在一條邊上，要嘛是戳在一個點上。

範圍很小，$\mathcal{O}(nq)$ 都可以過，你知道怎麼算點到直線距離（或是你有模板又沒有抄爛）的話應該就能 AC 了。

## Problem I. LIS Decrement <span class="medium pill">Medium</span>
> ###### Problem Setter: henotrix

經典最小割題。

:::spoiler Code

/// 此處省略 Dinic 模板

signed main() {
    int n, ans = 0;
    cin >> n;
    
    vector<int> arr(n+2), dp(n+2), weight(n+2);
    for(int i=1;i<=n;i++)
        cin >> arr[i];
    arr[0] = 0, arr[n+1] = n+1;
    for(int i=1;i<=n;i++)
        cin >> weight[i], ans += weight[i];
    weight[0] = weight[n+1] = 2e9;
    arr[n+1] = n+1;
    for(int i=1;i<=n+1;i++)
        for(int j=0;j<i;j++)
            if(arr[j] < arr[i])
                dp[i] = max(dp[i], dp[j]+1);

    Dinic dinic;
    dinic.init(2*(n+2));

    for(int i=0;i<=n+1;i++)
        dinic.add_edge(2*i, 2*i+1, weight[i]);

    for(int i=0;i<=n+1;i++)
        for(int j=0;j<i;j++)
            if(dp[i] == dp[j]+1 and arr[j] < arr[i])
                dinic.add_edge(2*j+1, 2*i, 2e9);

    auto rrr = ans-dinic.max_flow(0, (n+1)*2+1);

    cout << rrr <<'\n';

    return 0;
}

:::

## Problem J. Randomized String Matching Algorithm <span class="medium-hard pill">Medium Hard</span>
> ###### Problem Setter: henotrix

把式子推一推就會發現你要處理每個位移的匹配位置數量，這是經典卷積題。

對每個字元分開做，把 $S$ 跟 $T$ 都當成一個只有 $0$ 跟 $1$ 的陣列，然後做 $S * \text{reverse}(T)$ 就好。

https://tioj.ck.tp.edu.tw/problems/1035

:::spoiler Code

/// 此處省略 NTT 模板（快速數論變換）
/// fpow(base, exp = MOD-2) 是快速冪 base^exp mod MOD

void solve() {
    string S, T; cin >> S >> T;
    int K; cin >> K;
    int N = ssize(S), M = ssize(T);
    int N_pow2 = (2 << __lg(N+1));

    vector<int> match(N-M+1, 0);
    for (char c = 'a'; c <= 'h'; ++c) {
        vector<int> a(N_pow2, 0), b(N_pow2, 0);
        for (int i = 0; i < N; ++i) a[i] = (S[i] == c);
        for (int i = 0; i < M; ++i) b[i] = (T[M-i-1] == c);

        NTT ntt;
        ntt(a, N_pow2, false);
        ntt(b, N_pow2, false);
        for (int i = 0; i < N_pow2; ++i) a[i] = (a[i] * b[i]) % MOD;
        ntt(a, N_pow2, true);

        for (int j = M-1; j <= N-1; ++j) match[j-(M-1)] += a[j];
    }

    int ans = 1;
    for (int i = 0; i <= N-M; ++i) {
        if (match[i] == M) continue;
        ans = ans * (1 - fpow(match[i], K) * fpow(fpow(M, K)) % MOD + MOD) % MOD;
    }
    cout << ans << "\n";
}

:::

## Problem K. King's Challenge <span class="hard pill">Hard</span>
> ###### Problem Setter: truckski

要算 $n! / (n-k)!$ 去掉結尾 $0$ 的末五位數。

先嘗試將答案表示為 $2^a \cdot 5^b \cdot c$ 的形式。

定義 $f_d(x)$ 代表 $d^{f_d(x)} \mid x!$ 但 $d^{f_d(x)+1} \nmid x!$。這可以在 $\mathcal{O}(\log_d x)$ 時間求出。

可得 $a = f_2(n) - f_2(n-k)$ 以及 $b = f_5(n) - f_5(n-k)$。

注意到 $\left( \prod_{\substack{1 \le x \le p-1 \\ x \bot p}} x \right)^2 \bmod p = 1$，因為每個數字可以跟他的 inverse 對上。這就代表說對任意 $x \in \mathbb{N}$，$[x, x + 2 \cdot 10^5)$ 跟 $10^5$ 互質的整數乘起來 $\!\!\bmod 100\,000$ 都是 $1$。

要計算 $c$ 就可以透過預處理 $[1, 2 \cdot 10^5]$ 前綴跟 $10^5$ 互質整數乘積來 $\mathcal{O}(1)$ 求得。

## Problem L. The Bag of Forgotten Coins <span class="easy pill">Easy</span>
> ###### Problem Setter: truckski

不能取相鄰數字的最大和，經典 DP。

用 $\text{dp}[i][0/1]$ 代表要不要取最後一個的總和最大值。

:::spoiler Code

void solve() {
    ll N; cin >> N;

    vector<ll> v(N);
    for (ll &x : v) cin >> x, x = max<ll>(x, 0);

    vector<ll> dp = v;
    for (int i = 1; i < N; ++i) {
        dp[i] = max(dp[i-1], (i >= 2 ? dp[i-2] : 0) + v[i]);
    }
    cout << *max_element(ALL(dp)) << "\n";
}

:::

## Problem M. The Tale of Professor Alya and the H-Index <span class="water pill">Water</span>
> ###### Problem Setter: truckski

int H = 0;
for (int i = 1; i <= n; ++i) {
    if (c[i] >= i) ++H;
}

<!-- below are css styles -->

<style>
.water {
background-color: blue;
color: white;
}
.easy {
background-color: green;
color: white;
}
.easy-medium {
background-color: PaleGoldenRod;
color: #1f2d3d;
}
.medium {
background-color: Gold;
color: white;
}
.medium-hard {
background-color: orange;
color: white;
}
.hard {
background-color: red;
color: white;
}
.pill {
display: inline-block;
border-radius: 5px;
padding: 5px 10px;
font-size: 16px;
}
.tag {
background-color: #e3e3e3;
padding: 0.5rem 0.8rem 0.5rem 1.5rem;
font-weight: bold;
border-radius: 0.5rem;
color: gray;
font-size: 14px;
}
.tag::before {
position: relative;
content: '#';
margin-left: -10px;
margin-right: 3px;
}
.warning {
color: white;
background-color: crimson;
font-weight: bold;
padding: 5px 10px;
border-radius: 5px;
}
.warning:hover {
background-color: gold;
color: black;
cursor: pointer;
}
.warning:hover::before {
position: absolute;
content: "Beware :D";
top: -150%;
left: 120px;
padding: 5px 10px;
background-color: white;
border-radius: 5px;
border: 1px solid gold;
}
</style>