# ***`CTB Training Contest 05 Solution`***
## *A. Connect*
**Author**: **[TrungnotChung](https://www.facebook.com/man.sup.9674)**
### Subtask 1
Sinh ra tất cả $\frac{n \cdot (n - 1)}{2}$ cạnh của đồ thị, kết hợp với $m$ cạnh ưu đãi ta có một danh sách cạnh.
Đến đây ta dùng thuật toán quen thuộc `tìm cây khung nhỏ nhất trên đồ thị bằng DSU` để tìm chi phí nhỏ nhất tạo giúp đồ thị liên thông.
### Subtask 2
Gọi $k$ là đỉnh có nhãn nhỏ nhất trong tất cả các đỉnh. Ta thấy $a_u$ + $a_v$ $\geq$ $a_k$ + $a_v$ với mọi $1$ $\leq$ $u$, $v$ $\leq$ n. Ngoài ra nếu ta chỉ dùng đúng $n-1$ cạnh nối từ đỉnh $k$ với tất cả các đỉnh $v$ $\neq$ $k$, đồ thị của ta vẫn đảm bảo liên thông. Do đó nếu ta không dùng thêm cạnh ưu đãi nào, ta luôn dùng đúng $n-1$ cạnh nối từ đỉnh $k$ tới các đỉnh còn lại. Nếu có nhiều đỉnh cùng có $a_i$ min, ta chọn đỉnh bất kì.

Từ nhận xét trên ta có thuật toán cải tiến từ subtask $1$ bằng cách thay vì tạo đủ $\frac{n \cdot (n - 1)}{2}$ cạnh của đồ thị, ta chỉ tạo $n-1$ cạnh nối từ đỉnh $k$ với tất cả các đỉnh $v$ $\neq$ $k$ vào trộn với $m$ cạnh ưu đãi và dùng thuật toán quen thuộc `tìm cây khung nhỏ nhất trên đồ thị bằng DSU` để tìm chi phí nhỏ nhất tạo giúp đồ thị liên thông.
### Code mẫu
- **[phanlong2811](https://www.facebook.com/phanlong2811)**: xem tại [đây](https://ideone.com/ILAQ4d).
- **[dquynh2811](https://www.facebook.com/D.QUYNH.28.11)**: xem tại [đây](https://ideone.com/EohY4X).

## *B. Round 1*
**Author**: **[dquynh2811](https://www.facebook.com/D.QUYNH.28.11)**
Với bài này, ý tưởng sẽ là duyệt từng thí sinh, kiểm tra xem trong các thí sinh còn lại có bạn nào **giỏi** hơn không.
### Subtask 1
Duyệt tất cả những thí sinh còn lại $\rightarrow$ **Độ phức tạp:** $O(N^2)$.
### Subtask 2
Với $N$ có giới hạn $10^5$, ta nghĩ tới **Độ phức tạp:** $O(NlogN)$. Gọi 3 môn thi lần lượt là $X, Y, Z$:

1. Đầu tiên ta sẽ *sort tăng dần* theo xếp hạng của $1$ trong $3$ môn. Ví dụ, *sort* theo môn $X$. Dễ thấy, sau khi sort, khi xét thí sinh $i$, các thí sinh có **tiềm năng giỏi hơn** $i$ chỉ có thể là các thí sinh từ $1$ đến $i - 1$.

2. Sau khi xử lý được điều kiện về môn $X$ ,điều kiện để các thí sinh $j$ $(1 \le j < i)$ giỏi hơn $i$ là : $Y_j<Y_i$ && $Z_j<Z_i$. Để kiểm tra trong độ phức tạp $O(logN)$ ta sẽ dùng `Fenwich Tree(BIT) / Segment Tree`.
Trên cây, giá trị của nút $Z_i$ sẽ được cập nhật bằng $Y_i$. Khi duyệt qua $i$, để kiểm tra xem có thí sinh nào giỏi hơn $i$ không, ta tìm giá trị nhỏ nhất của tất cả giá trị $Y_j$ của các nút $Z_j$ $(Z_j<Z_i)$, tạm gọi là $minY$.
- Nếu $minY < Y_i$ $\rightarrow$ tồn tại thí sinh giỏi hơn $i$.
- Ngược lại $\rightarrow$ **không** tồn tại thí sinh giỏi hơn $i$ $\rightarrow$ $ans$++.

### Code demo

//BIT.get(x) là hàm lấy giá trị min của các nút từ 1 đến x trên cây
//BIT.update(node, val) là hàm update giá trị của node bằng val
...
    sort(...) 
    for(i:1->n)
    {
        if(BIT.get(Z[i]) < Y[i]) ++ans; 
        BIT.update(Z[i], Y[i]);
    }
    ...

## *C. Round 2*
**Author**: **[dquynh2811](https://www.facebook.com/D.QUYNH.28.11)**
### Subtask 1
Ở mỗi nhóm, duyệt từng cặp thí sinh để kiểm tra $\rightarrow$ **ĐPT:** $O(T \times N^2)$.
### Subtask 2
$a_{i_y} - a_{i_x} = y - x$ $\Leftrightarrow$ $a_{i_y} - y = a_{i_x} - x$
$\rightarrow$ Duyệt từng nhóm, tại nhóm thứ $i$ thay thế giá trị của $a_{i_j}$ thành $b_j = a_{i_j} - j$ $(1 \le j \le N_i)$. Đến đây, bài toán cần xử lý đưa về đếm số cặp $(x, y)$ với $x < y$ sao cho $b_i = b_j$. Đây là bài toán cơ bản, có thể dùng đếm phân phối hoặc `map` nên chúng ta sẽ không giải thích sâu thêm.