# Lời giải OLP SV'24
Link livestream lời giải:
- Bài 1 [Chuyên tin (path)](https://youtube.com/live/EC_HBv2QBmE?feature=share)
- Bài 1 [Không chuyên (string)](https://youtube.com/live/z-S7YbA7bUc?feature=share):
- [Bài 2,3 Không chuyên, bài 4 là bài 1 CT](https://youtube.com/live/jpu0aukHPGY?feature=share):

## Đố vui - string
**Đề bài:**
Cho một xâu $s$, tạo xâu $t = s + s$ sau đó chèn thêm một kí tự vào $t$ (ở vị trí bất kỳ) để tạo nên xâu $z$.
Cho xâu $z$, tìm xâu $s$, hoặc thông báo là (vô nghiệm, nhiều hơn 1 $s$ thỏa mãn)

### Subtask 2
Duyệt vòng lặp for để từ xâu $z$ tạo ra xâu $t$. $O(n)$
- Sau đó lấy nửa đầu của xâu $t$ để tạo ra xâu $s$. Kiểm tra chân phương, đề bảo gì làm nấy.
- Kiểm tra này hết $O(n)$ (cày trâu)

Lưu ý: `Multiple Solutions` cho test này "GKGKG" nhưng `GG` cho test này "GGGGG" (nghiệm khác nhau nếu xâu $s$ ban đầu là khác nhau)

ĐPT: $O(n^2)$

### Subtask 3
Mong muốn giảm ĐPT của bước kiểm tra xuống, không dùng vòng lặp for bên trong

Ý tưởng: Dùng Hash để so sánh nhanh hai substring trong xâu $s$

## Đăng ký học phần - credit
**Đề bài**: Cho $n$ môn học, độ khó $a_i$, số tín chỉ $b_i$. Chọn một tập hợp các môn học thỏa mãn:
- tổng $b$ được chọn $\ge C$
- hàm "độ biến động" đạt $\min$. Hàm này định nghĩa:
- Độ biến động bằng 

### First impressions
- Cần sắp xếp các môn học tăng dần theo $a$
- Nên chọn các môn học liên tiếp

1 3 5 7

### Subtask 1,2 (lý thuyết là 40\% nhưng thực tế được 80\% số điểm)
- Duyệt 2 vòng lặp `for l` `for r` để chọn ra hai chỉ số $l,r$ là chỉ số đầu (trái) và cuối (phải) của một đoạn con liên tiếp các môn học (xét trong dãy môn học sau khi đã sắp xếp tăng dần theo $a$).
Vừa chạy for, ta vừa có thể tính được tổng số tín chỉ (tổng $b$ của các môn học được chọn) đồng thời tính hàm "độ biến động"

Độ phức tạp $O(n^2)$

### Subtask 3 (20\%)
Vì $b_i = 1$ nên cần chọn $\ge C$ môn học. Chọn đúng $C$ môn. Đương nhiên $C \le n$ thì mới có lời giải.

Ta cần chọn các đoạn liên tiếp, sao cho max (chênh lệch hai số liên tiếp trong đoạn) đạt min.

Tạo mảng $d_i = a_i - a_{i-1}$. Bài toán đưa về tìm min của một đoạn tịnh tiến (xem trên VNOI).

Đánh giá: Không phù hợp để code trong phòng thi, có thể có công dụng gợi ý?

### Subtask 4: (20\%) có $a_i \le 30$
Duyệt biến `ans` kết hợp với hai con trỏ

for (int ans = 1; ans <= 30; ans++) {
    for (int l = 1, r = 1; l <= n; l++) {
        r = max(r, l);
        while (r < n && a[r + 1] - a[r] <= ans) r++;
        // làm sao tính tổng b[ ] liên tiếp được nhanh ?
	}
}

### Subtask 5:
Chặt nhị phân đáp án (xem trên VNOI Wiki). Nhận thấy tính đơn điệu (tính tăng dần của biến ans). Khi độ biến động tăng thì số lựa chọn (lựa chọn = đoạn con các môn học liên tiếp) càng nhiều hơn.
Đặt hàm $f(x) = 0$ nếu như với độ biến động x = 0 thì không chọn được dãy các môn học liên tiếp có tổng tín chỉ lớn hơn bằng C
Ngược lại, nếu chọn được thì $f(x) = 1$

Hàm $f$ có dạng như sau:
`0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1`

Đặt hàm $g(x)$ là tổng số tín chỉ lớn nhất có thể của một dãy con liên tiếp các môn học thỏa mãn "độ biến động $\ge$ x"

Hàm $g$ tăng dần. Vì khi độ biến động cho phép $x$ tăng thì dãy chọn được càng lớn hơn.

Độ phức tạp: $O(n\log)$

## Ba số nguyên tố - prime
Kiến thức cần biết:
- Công thức đếm số lượng ước dựa vào dạng phân tích thừa số nguyên tố:
Số ước = Tích các (số mũ + 1)
Với $n = p_1 ^ {e_1} \times p_2 ^ {e_2} \times p_3 ^ {e_3}$, số ước $= (e_1 + 1) \times (e_2 + 1) \times (e_3 + 1)$ (tương tự với số $n$ có nhiều/ít thừa số hơn)
- Đệ quy quay lui, nhánh cận và thời gian chạy thực tế của các bài toán "duyệt trâu"

Nhận thấy số bé nhất $p_1 \le n^{1/3}$.
Sàng nguyên tố và chạy for các số nguyên tố nhỏ hơn căn bậc 3 n để chọn ra trước ba cơ số $p_1,p_2,p_3$.
Để tìm số mũ, chúng ta dùng kĩ thuật đệ quy quay lui + một số kĩ thuật để tối ưu hóa thời gian chạy (nhánh cận)
- Số mũ tối đa của $p_1$ là $\log_2{n} \le 63$. Tuy vậy, hàm mũ tăng rất nhanh.
- Suy ra, số mũ trung bình ta chạy tới rơi vào tầm 10-20.
- Hơn thế nữa, số lượng số nguyên tố nhỏ hơn $10^6$ chỉ tầm $50000$ (Source)[https://en.wikipedia.org/wiki/Prime_number_theorem].
- Như vậy, thuật toán với độ phức tạp $O(\text{num. of SNT} \times \text{exponents} ^ 3)$ có thể fit vào trong Time Limit.
**Do đó, có thể không cần phải backtrack mà chỉ cần chạy for và đặt câu lệnh (if tích lớn hơn n) break một cách đơn giản là đủ để AC**

Nếu làm ĐQQL, có thể tham khảo phương án tối ưu độ phức tạp như sau:
- Đầu tiên, vẫn chạy for để lấy ra ba cơ số là ba số nguyên tố, liên tiếp, đặt thành mảng `p[0], p[1], p[2]`
- `void backtrack(int i, int d, Int val) {` với ý nghĩa:
- Ta đang chọn số mũ cho `p[i]`
- $d$: số lượng ước của số ta đang xây dựng. Tức $d$ là tích các (số mũ +1) đã chọn (e[0], e[1], ... e[i]) là $d$. Tuy nhiên, vì sau cùng tích này phải bằng $k$ nên để tiết kiệm thời gian, tôi muốn trong mọi thời điểm $d$ phải là ước của $k$. Trong code thì mình code ngược lại một chút là mình lưu $\frac{k}{d}$.
- `val`: giá trị của số đang xây được, xét tới trước `p[i]`
- Nhánh cận là điều kiện được đặt vào cùng với đệ quy, để ngắt sớm các trường hợp (cấu hình) vô lý, giúp thời gian chạy thực tế nhanh hơn. Code tôi áp dụng các nhánh cận (branch & bound) như sau:
- ` if (val > n) return ;`
- ` if (k % (e+1) == 0) `

-- TO BE WRITING

## Đường đi - path