# CF 479 Div 3

## A
Đề bảo sao làm vậy (for, if).
Vì có dòng này "Đề đảm bảo rằng kết quả luôn luôn là số dương." nên yên tâm làm.

## B
Cần tính số lần xuất hiện của mỗi cặp?
Có thể đếm phân phối. Tuy nhiên do không phải là số nên hơi khó đếm. Dùng map là dễ code nhất
Hướng khác: chạy trâu $O(n^2)$ để đếm.
### Hướng 1
Lưu ý: Code sau chỉ chạy được với `C++ 17` (do vòng `for` ở cuối)

### Hướng 2
Code của binhan (sau khi sửa)

## C
Sắp xếp tăng dần. Ta sẽ muốn $x$ lớn hơn $k$ giá trị nhỏ nhất.
Tuy nhiên cần xét các trường hợp $-1$.

### $k = 0$
Cần có $x < \min a$. Nên lấy $x = \min a - 1$
Vậy sẽ không được khi $\min a = 1$, lúc đó cần lấy $x \le 0$ (không dương)

### $a[k] = a[k+1]$
(đánh số từ $1$)
Chọn kiểu gì cũng có $x> \,\, k+1$ số trong dãy $a$

## D
Nhận thấy chỉ có chia $3$ và nhân $2$ nên bậc của $3$ giảm dần và bậc của $2$ tăng dần.
**Bước 1**: Phân tích mỗi số ra TSNT. Giả sử với số $a_i$ bậc 3 là $b_i$, bậc 2 là $c_i$
**Bước 2**: Sắp xếp theo tiêu chí: $b$ giảm, rồi tới $c$ tăng.
**Bước 3**: Kiểm tra, nếu thỏa 2 điều kiện sau là ok :
- $b_i - 1 \le b_{i+1}$
- $c_i + 1 \ge c_{i+1}$
- Có chính xác một dấu $=$ xảy ra trong 2 BĐT trên (số phép biến đổi là $1$)

## E
Dùng BFS/ DFS để lấy ra các TPLT.
Ngoài ra, cần đếm xem mỗi TPLT chứa bao nhiêu cạnh? Nếu một TPLT chứa $v$ đỉnh và $v$ cạnh thì nó ~~chính~~ **chưa chắc** đã là chu trình.
Xét trường hợp sau:
Có $4$ đỉnh và $4$ cạnh nhưng không phải chu trình.
Vậy cần xét **bậc** của mỗi đỉnh nữa
Có thể làm như sau:

const int N = 2e5 + 50;
int component_id; //tăng lên mỗi khi gặp TPLT mới
int count_edges[N], count_nodes[N], count_ok[N];
vector<int> neighbor[N];

bool visit[N];
void dfs(int u) {
    if (visit[u]) return ;
    visit[u] = true;
    count_edges[component_id] += neighbor[u].size();
    count_nodes[component_id] += 1;
    if (neighbor[u].size() == 2)
        count_ok[component_id] += 1;
    for (auto v : neighbor[u]) dfs(v);
}

int main() {
    dfs(u); //với mỗi u từ 1 tới n, nhớ tăng component_id lên
    for (int i = 1; i <= component_id; i++) {
        count_edges[i] /= 2; //mỗi cạnh (u,v) cộng 2 lần vào mảng này
        if (count_edges[i] == count_nodes[i] && count_ok[i] == count_nodes[i]) {
            cout << "This is a cycle! (containing " << i << "\n";
        }
    }
}

## F
Ý tưởng tương tự bài toán LIS, nhưng đơn giản hơn, vì giá trị đứng trước giá trị $v$ chỉ là $v-1$ chứ không bao gồm toàn bộ các số $1 \rightarrow v-1$ như bài gốc.
Chạy $i$ từ $1$ tới $n$.
Xét $j<i$, $j$ lớn nhất mà $a_j + 1 = a_i$ (dùng `map`). Vậy $f_i = f_j + 1$
Trường hợp gốc $f_i = 1$