---
title: 競程一期中題解
tags: Editorial
image:
---

# 2022 Spring NYCU CP1 Midterm Exam -- Editorial

[TOC]

:::spoiler Problems
{%pdf https://docdro.id/IcylOn8 %}
:::

:::spoiler Rankings
:::

## Problem A -- A Monad Is a Monoid in the Category of Endofunctors

###### Problem Setter: 黃克崴

:::spoiler Editorial
根據題敘找出符合定義的元素。
:::

:::spoiler Code (Python)

n = int(input())
op = [list(map(int, input().split())) for _ in range(n)]

for i in range(n):
    if all(op[i][j] == j + 1 == op[j][i] for j in range(n)):
        identity = i + 1
print(identity)

invertible = []
for i in range(n):
    if any(op[i][j] == op[j][i] == identity for j in range(n)):
        invertible.append(i + 1)
print(*invertible)

:::

:::spoiler Code (C++)

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n = 0;
    cin >> n;

    vector op(n + 1, vector(n + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> op[i][j];
        }
    }

    int identity = 0;
    for (int i = 1; i <= n; i++) {
        bool is_identity = true;
        for (int j = 1; j <= n; j++) {
            if (op[i][j] != j || op[j][i] != j) {
                is_identity = false;
            }
        }
        if (is_identity) {
            identity = i;
        }
    }
    cout << identity << '\n';

    for (int i = 1; i <= n; i++) {
        bool is_invertible = false;
        for (int j = 1; j <= n; j++) {
            if (op[i][j] == identity && op[j][i] == identity) {
                is_invertible = true;
            }
        }
        if (is_invertible) {
            cout << i << ' ';
        }
    }
    cout << '\n';
}

:::

## Problem B -- Balanced Students

###### Problem Setter: 黃克崴

:::spoiler Editorial
將所有學生的分數 pair $(c_i, m_i)$ 依照 $c_i$ 排序後，他們的 Chinese ranking 會是 $n, n-1, \dots, 2, 1$。同理，依照 $m_i$ 排序後，他們的 Math ranking 會是 $n, n-1, \dots, 2, 1$。根據這兩種排序找出位置相同的學生數量即是答案。
總時間複雜度與排序的時間複雜度相同（通常是 $O(n \log n)$）。
:::
:::spoiler Code (Kotlin)

data class Student(val c_score: Int, val m_score: Int)

fun main() {
    val n = readLine()!!.toInt()
    val scores = List<Student>(n) {
        val (c, m) = readLine()!!.split(" ").map{it.toInt()}
        Student(c, m)
    }
    val c_rank = scores.sortedWith(compareBy({it.c_score}))
    val m_rank = scores.sortedWith(compareBy({it.m_score}))
    val ans = c_rank.zip(m_rank).count{(c, m) -> c == m}
    println(ans)
}

:::
:::spoiler Code (C++)

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<pair<int, int>> scores;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        scores.emplace_back(x, y);
    }

    auto sx = scores;
    auto sy = scores;

    sort(sx.begin(), sx.end());
    sort(sy.begin(), sy.end(),
         [](const auto &a, const auto &b) { return a.second < b.second; });

    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (sx[i] == sy[i]) {
            ans++;
        }
    }

    cout << ans << endl;
}

:::

## Problem C -- Counting Pairs That Satisfy Some Random Requirements

###### Problem Setter: 郭軒語

:::spoiler Editorial
我們嘗試算出所有不符合第二個條件的 pair 以後，再從 $\frac{n(n-1)}{2}$ 裡面去扣。

不符合第二個條件有兩種可能：$a_j - a_i > j - i$ 和 $a_i - a_j > j - i$。整理一下式子可以得到 $a_j - j > a_i - i$ 和 $a_i + i > a_j + j$，兩個都可以用算 inversion pair 的方式算出分別符合這兩個條件的有幾個 pair。
:::

:::spoiler Code

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
using pii = pair<int, int>;

int64_t count_pairs(vector<int> &a, int l, int r) {
  if (r <= l + 1)
    return 0LL;
  int m = (l + r) >> 1;
  int64_t ans = count_pairs(a, l, m) + count_pairs(a, m, r);
  int idxr = m;
  for (int i = l; i < m; i++) {
    while (idxr < r && a[idxr] <= a[i])
      idxr++;
    ans += (r - idxr);
  }
  inplace_merge(a.begin() + l, a.begin() + m, a.begin() + r);
  return ans;
}

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int &i : a)
    cin >> i;
  vector<int> tmp(n);

  int64_t ans = n * 1LL * (n - 1) / 2;
  for (int i = 0; i < n; i++)
    tmp[i] = a[i] - i;
  ans -= count_pairs(tmp, 0, n);
  for (int i = 0; i < n; i++)
    tmp[i] = a[i] + i;
  reverse(tmp.begin(), tmp.end());
  ans -= count_pairs(tmp, 0, n);
  cout << ans << '\n';
}

:::

## Problem D -- Deja Vu

###### Problem Setter: 郭軒語

:::spoiler Editorial
以下都令 $val(l,r) = \max\limits_{l \leq i \leq r} a_i - |b_l - b_r|$。

考慮分治。令 $f(L,R)$ 代表滿足 $L \leq l < r \leq R$ 的 $(l,r)$ 中 $val(l,r) = k$ 的數量。假設 $mid$ 是 $[L,R]$ 區間中最大值所在處，則 $f(L,R)$ 由以下三種可能組成

* $f(L,mid-1)$
* $f(mid+1,r)$
* $val(l,r) = k$，其中 $L \leq l \leq mid, mid \leq r \leq R, l \neq r$

在計算 $f(L,R)$ 過程中，同時維護一個 set 和一個 map，set 存所有 $(a_i,i)$ 的 pair，map 存 $b_i$ 到 $i$ 的 count。 (set 的部分可以使用區間資料結構取代，例如 sparse table 或線段樹。)

* 用第一個 set 可以求出 $mid$ 所在。這樣可以把當前區間切成兩半。
* 把兩半中長度比較短的另外開 set 跟 map，把屬於這個短區間的 $(a_i,i)$ 和 $b_i$ 取出分別放入新開的兩個 set 跟 map。在這裡因為啟發式合併所以每個 element 最多只會被移動 $\mathcal{O}(\log n)$ 次，所以這一步貢獻整體時間複雜度是 $\mathcal{O}(n \log^2 n)$。
* 現在我們已經固定 $\max\limits_{l \leq i \leq r} a_i$ 的值了，我們嘗試算出 $|b_l - b_r| = k - \max\limits_{l \leq i \leq r} a_i$ 的有多少。這可以在取出短區間的值的時候順便算出來。
* 接下來遞迴下去算 $f(L,mid-1)$ 和 $f(mid+1,r)$。

整題時間複雜度 $\mathcal{O}(n \log^2 n)$。
:::

:::spoiler Code

#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;
using pii = pair<int, int>;

vector<int> a, b;
int k;

// [l,r)
int64_t solve(int l, int r, set<pii> &s, map<int, int> &cnt) {
  // if len <= 1 then return
  if (l >= r)
    return 0LL;

  // find max and max_idx. Calculate target difference
  auto [max, max_idx] = *prev(s.end());
  int target = max - k;
  if (target < 0)
    return 0LL;

  // declare base ans and shorter side set/map
  int64_t base_ans = 0;
  set<pii> ss;
  map<int, int> scnt;

  // count the pairs that one index is max_idx
  s.erase({max, max_idx});
  cnt[b[max_idx]]--;
  if (cnt.find(b[max_idx] + target) != cnt.end())
    base_ans += cnt[b[max_idx] + target];
  if (target != 0 && cnt.find(b[max_idx] - target) != cnt.end())
    base_ans += cnt[b[max_idx] - target];

  // determine which side is shorter
  bool left_shorter = false;
  if (max_idx - l < r - max_idx)
    left_shorter = true;

  // count other pairs and split set and map into two
  int sl, sr; // range of the shorter side
  if (left_shorter)
    sl = l, sr = max_idx;
  else
    sl = max_idx + 1, sr = r;
  for (int i = sl; i < sr; i++) {
    s.erase({a[i], i});
    cnt[b[i]]--;
    ss.insert({a[i], i});
    scnt[b[i]]++;
  }
  for (int i = sl; i < sr; i++) {
    if (cnt.find(b[i] + target) != cnt.end())
      base_ans += cnt[b[i] + target];
    if (target != 0 && cnt.find(b[i] - target) != cnt.end())
      base_ans += cnt[b[i] - target];
  }

  // solve problem recursively
  if (left_shorter)
    return solve(l, max_idx, ss, scnt) + solve(max_idx + 1, r, s, cnt) +
           base_ans;
  else
    return solve(l, max_idx, s, cnt) + solve(max_idx + 1, r, ss, scnt) +
           base_ans;
}

int main() {
  int n;
  cin >> n >> k;
  a.resize(n), b.resize(n);
  for (int &i : a)
    cin >> i;
  for (int &i : b)
    cin >> i;

  set<pii> s;        // (a_i, i)
  map<int, int> cnt; // count for each number

  for (int i = 0; i < n; i++) {
    s.insert({a[i], i});
    cnt[b[i]]++;
  }
  cout << solve(0, n, s, cnt) << '\n';
}

:::

## Problem E -- Even More Pair Counting Problems?

###### Problem Setter: 黃克崴

:::spoiler Hint
若 $A_y$ 表示序列 $a$ 中 $y$ 的數量，$B_z$ 表示序列 $b$ 中 $z$ 的數量，則對於某個值 $c$，滿足 $a_i + b_j = c$ 的 $(i, j)$ 數量為
$$
\sum_{y+z=c} A_y \times B_z
$$
:::
:::spoiler Editorial
令 $N$ 表示所有序列中最大的元素。考慮多項式 $f(x) = A_0 + A_1 x + A_2 x^2 + \dots + A_N x^N$ 以及 $g(x) = B_0 + B_1 x + B_2 x^2 + \dots + B_N x^N$。他們的乘積是
$$
\begin{split}
f(x) \times g(x) &= \sum_{i=0}^N \sum_{j=0}^N A_i \times B_j x^{i+j} \\
&= \sum_{k=0}^{2N} x^k \sum_{i+j=k} A_i \times B_j
\end{split}
$$
所以 $f(x) \times g(x)$ 的 $c$ 次係數即是滿足 $a_i + b_j = c$ 的 $(i, j)$ 數量。算出乘積後，對於每個 $c_k$ 將乘積的 $c_k$ 次係數相加即是答案。

總時間複雜度為 $n + N \log N$（使用 FFT 做多項式乘法），或是 $n + N^{\log_23}$（使用 Karatsuba）。
:::
:::spoiler Code (FFT)

#include <cmath>
#include <complex>
#include <iostream>
#include <vector>

using namespace std;

using c = complex<double>;
using poly = vector<c>;
constexpr double pi = 3.141592653589793238;

constexpr int N = 1 << 19;

// recursive fast fourier transform
void fft(poly &a, bool inv) {
    int n = a.size();
    if (n == 1) {
        return;
    }
    poly a0(n / 2), a1(n / 2);
    for (int i = 0; i < n / 2; i++) {
        a0[i] = a[i * 2];
        a1[i] = a[i * 2 + 1];
    }
    fft(a0, inv);
    fft(a1, inv);
    double arg = pi * 2 / n * (inv ? -1 : 1);
    complex<double> w(1), wn(cos(arg), sin(arg));
    for (int i = 0; i < n / 2; i++) {
        a[i] = a0[i] + w * a1[i];
        a[i + n / 2] = a0[i] - w * a1[i];
        w *= wn;
    }
    if (inv) {
        for (int i = 0; i < n; i++) {
            a[i] /= 2;
        }
    }
}

// multiply two polynomials of degree N - 1
poly multiply(poly f, poly g) {
    int n = N;
    f.resize(n);
    g.resize(n);
    fft(f, 0);
    fft(g, 0);
    poly res;
    for (int i = 0; i < n; i++)
        res.push_back(f[i] * g[i]);
    fft(res, 1);
    return res;
}

int main() {
    int n;
    cin >> n;

    poly a(N), b(N);

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a[x] += 1;
    }
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        b[x] += 1;
    }

    poly d = multiply(a, b);

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        ans += round(d[x].real());
    }
    cout << ans << '\n';
}

:::
:::spoiler Code (Karatsuba)

#include <iostream>
#include <vector>

using namespace std;

constexpr int N = 1 << 18;

// karatsuba algorithm
vector<long long> multiply(vector<long long> f, vector<long long> g) {
    int n = f.size();
    vector<long long> res(2 * n);
    if (n <= 32) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                res[i + j] += f[i] * g[j];
            }
        }
        return res;
    }
    int k = n / 2;
    vector<long long> f0(k), f1(k), g0(k), g1(k);
    for (int i = 0; i < k; i++) {
        f0[i] = f[i];
        f1[i] = f[i + k];
        g0[i] = g[i];
        g1[i] = g[i + k];
    }
    vector<long long> a = multiply(f0, g0);
    vector<long long> b = multiply(f1, g1);
    for (int i = 0; i < k; i++) {
        f0[i] += f1[i], g0[i] += g1[i];
    }
    vector<long long> c = multiply(f0, g0);
    for (int i = 0; i < n; i++) {
        res[i] += a[i];
        res[i + n] += b[i];
        res[i + k] += c[i] - a[i] - b[i];
    }
    return res;
}

int main() {
    int n;
    cin >> n;

    vector<long long> a(N), b(N);

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a[x] += 1;
    }
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        b[x] += 1;
    }

    vector<long long> d = multiply(a, b);

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        ans += d[x];
    }
    cout << ans << '\n';
}

:::

## Problem F -- Function With Hashing Functionality

###### Problem Setter: 郭軒語

:::spoiler Editorial
$n$ 個 pair 當中，令 $a_i = \lfloor \frac{x_i}{2^{32}}\rfloor, b_i = x_i \bmod 2^{32}$，則可以知道 $h'(a_i) = h(x_i) \bmod 2^{32}, h'(b_i) = \lfloor \frac{h(x_i)}{2^{32}}\rfloor$。

用一個類似紅黑樹的資料結構紀錄所有知道的 $h'(\cdot)$ 值，之後每筆詢問就能根據公式推算出答案。可以使用各自語言中實作好的資料結構，例如在 C++ 中可以使用 `std::map`, 而在 Python 中可以使用 `dict`。

注意到因為這題是使用 hexadecimal number 做輸出入，所以也可以用字串處理的方式做 mapping。
:::

:::spoiler Code

#include <iostream>
#include <map>

using namespace std;

int main() {
  int n, q;
  cin >> n >> q;
  map<string, string> hf;
  for (int i = 0; i < n; i++) {
    string x, y;
    cin >> x >> y;
    hf[x.substr(0, 8)] = y.substr(8, 8);
    hf[x.substr(8, 8)] = y.substr(0, 8);
  }
  while (q--) {
    string x;
    cin >> x;
    if (hf.find(x.substr(0, 8)) == hf.end() ||
        hf.find(x.substr(8, 8)) == hf.end()) {
      cout << "-1\n";
    } else {
      cout << hf[x.substr(8, 8)] + hf[x.substr(0, 8)] << '\n';
    }
  }
}

:::

## Problem G -- Grievous Light Bulb Decoration

###### Problem Setter: 范釗維

:::spoiler Hint 1
一個區間 $[L, R]$ 可以被選的前提是 $|\{a_L, a_{L+1}, \ldots, a_R\}| \le k$。
:::

:::spoiler Hint 2
對每個左界 $L$，都可以找到一個最大的右界 $R$ 使得 $R = n$ 或 $|\{a_L, a_{L+1}, \ldots, a_R\}| = k$。
而且只要 $L$ 遞增，$R$ 也會跟著遞增。
:::

:::spoiler Editorial
用 two-pointer 維護 $L$、$R$，時間複雜度 $\mathcal{O}(n)$。
~~不要吃毒寫二分搜 la~~
:::

:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int N, K; cin >> N >> K;
    
    vector<int> A(N);
    for (int &x : A) cin >> x, --x;
    
    int type = 0, ans = 0;
    vector<int> cnt(N, 0);
    for (int L = 0, R = 0; R < N; ++R) {
        type += (cnt[A[R]]++ == 0);
        while (type > K) type -= (--cnt[A[L]] == 0), ++L;
        if (R-L+1 > ans) ans = R-L+1;
    }
    cout << ans << "\n";
}

int32_t main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    
    int t; cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    
    return 0;
}

:::

## Problem H -- Harmonic Heap Merging

###### Problem Setter: 范釗維

:::spoiler Hint
回顧之前學 Disjoint Set 的時候講到的「啟發式合併」。
:::

:::spoiler Editorial
合併兩個 heap 的時候把 size 小的丟到 size 大的，這樣每個元素至多只會被丟 $\mathcal{O}(\log q)$ 次。
需要用到的空間再開就好。
如果你使用的資料結構是 `std::set` 或 `std::priority_queue`，時間複雜度就是 $\mathcal{O}(q \log^2 q)$。

另一種解法是寫一個可併堆 or 左偏樹（詳見 pbds），可以達到 $\mathcal{O}(q \log q)$ 的時間複雜度。
:::

:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

template <typename T> using prior = priority_queue<T, vector<T>, greater<T>>;

#define ee emplace
#define SZ(x) ((int)(x).size())

int32_t main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    
    int N, Q; cin >> N >> Q;
    int tok = 0;
    
    vector<prior<int>> heaps(2*Q);
    map<int, int> inv;
    
    auto _create = [&](int x) {inv[x] = tok, heaps[tok].ee(x), ++tok;};
    auto _add = [&](int x, int to) {inv[x] = to, heaps[to].ee(x);};
    
    for (int q = 1; q <= Q; ++q) {
        string op; cin >> op;
        
        if (op == "merge") {
            int x, y; cin >> x >> y;
            if (!inv.count(x)) _create(x);
            if (!inv.count(y)) _create(y);
            if (inv[x] == inv[y]) {cout << -1 << "\n"; continue;}
            prior<int> &px = heaps[inv[x]], &py = heaps[inv[y]];
            if (SZ(px) < SZ(py)) {while (SZ(px)) _add(px.top(), inv[y]), px.pop();}
            else                 {while (SZ(py)) _add(py.top(), inv[x]), py.pop();}
            cout << SZ(heaps[inv[x]]) << "\n";
        }
        
        else if (op == "take") {
            int x; cin >> x;
            if (!inv.count(x)) {cout << x << "\n"; continue;}
            int val = heaps[inv[x]].top(); heaps[inv[x]].pop();
            _create(val);
            cout << val << "\n";
        }
    }
    
    return 0;
}

:::

:::spoiler Code using pbds

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;

template <typename T> using prior = __gnu_pbds::priority_queue<T, greater<T>, __gnu_pbds::pairing_heap_tag>;

struct DSU {
    vector<int> p;
    
    void init(int N) {
        p.resize(N), iota(begin(p), end(p), 0);
    }
    
    int Find(int x) {return x ^ p[x] ? p[x] = Find(p[x]) : x;}
    int Union(int x, int y) {x = Find(x), y = Find(y); return x ^ y ? p[y] = x, 1 : 0;}
};

int32_t main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    
    int N, Q; cin >> N >> Q;
    int tok = 0;
    
    DSU dsu; dsu.init(2*Q);
    vector<prior<int>> heaps(2*Q);
    unordered_map<int, int> inv;
    
    auto _create = [&](int x) {inv[x] = tok, heaps[tok].push(x), ++tok;};
    
    for (int q = 1; q <= Q; ++q) {
        string op; cin >> op;
        
        if (op == "merge") {
            int x, y; cin >> x >> y;
            if (!inv.count(x)) _create(x);
            if (!inv.count(y)) _create(y);
            x = dsu.Find(inv[x]), y = dsu.Find(inv[y]);
            if (x == y) {cout << -1 << "\n"; continue;}
            heaps[x].join(heaps[y]), dsu.Union(x, y);
            cout << heaps[dsu.Find(x)].size() << "\n";
        }
        
        else if (op == "take") {
            int x; cin >> x;
            if (!inv.count(x)) {cout << x << "\n"; continue;}
            x = dsu.Find(inv[x]);
            int val = heaps[x].top(); heaps[x].pop();
            _create(val);
            cout << val << "\n";
        }
    }
    
    return 0;
}

:::

## Problem I -- Interval Deletion

###### Problem Setter: 黃克崴 & 范釗維

:::spoiler Hint 1
固定 $c$ 的話你會做嗎？

顯然 $a_1$ 一定要被一個區間蓋到，所以就先選 $[a_1, a_1 + c]$。
顯然 $a_{x = \arg\min_k\{a_k > a_1 + c\}}$ 一定要被一個區間蓋到，所以就再選 $[a_x, a_x + c]$。
顯然 $a_{y = \arg\min_k\{a_k > a_x + c\}}$ 一定要被一個區間蓋到，所以就再選 $[a_y, a_y + c]$。
以此類推，greedy 的取就好。
:::

:::spoiler Hint 2
如果 $c$ 是一個解，那對於 $c' > c$ 的 $c'$ 也是一個解。
:::

:::spoiler Editorial
對答案二分搜，找到第一個符合條件的 $c$。
:::

:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int INF = 1'000'000'000;

int32_t main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    
    int N, K; cin >> N >> K;
    
    vector<int> A(N);
    for (int &x : A) cin >> x;
    
    auto calc = [&](int len) -> bool {
        int cnt = 0, lst = 0;
        for (int x : A) {if (x > lst) lst = x + len, ++cnt;}
        return (cnt <= K);
    };
    
    int lo = 0, hi = INF, mi;
    while (lo < hi) {
        mi = (lo + hi) >> 1;
        if (calc(mi)) hi = mi;
        else          lo = mi + 1;
    }
    cout << lo << "\n";
    
    return 0;
}

:::