# Solution Sơ loại OLP MTTN 2023 (Chuyên Tin)

## B1: TEAMBUILDING
Tóm tắt: Đếm số cách chia mảng $a$ thành các nhóm liên tiếp. Mỗi nhóm thỏa mãn abcxyz.

---

### Sub 1: $n \le 20$
Có $n$ người thì sẽ có $n-1$ "khoảng trống" để ta đặt/ không đặt "vách ngăn" vào. Mỗi cách đặt như vậy là một cách chia nhóm.
Ví dụ:
[Hình vẽ] (soon^TM)
Quay lui $O(2^n)$

---

### Sub 2: $n \le 500$
Cài chưa chuẩn ?

### Sub 3: $n \le 5000$
Đặt $f(i)$ là số cách để chia $i$ người đầu.
Từ $f(i)$ ta cập nhật $f(j)$ với $j > i$. Thêm một nhóm $i+1, i+2, i+3, ..., j$. Nếu được thì $\texttt{f(j) += f(i)}$


(Nguyễn Minh Huy, A5 K37 LQĐ)

---

## B2: FRUITMARKET

Tóm tắt: Hoa sẽ đi mua quả theo vòng tròn: mỗi tiệm mua $\le 1$ quả xong rồi qua tiệm tiếp theo. Dừng lại khi không đủ tiền mua quả rẻ nhất.

**Bước 1:** Tính xem thử Hoa đã đi được bao nhiêu vòng trước khi $m<$ tổng?
Đặt $S$ là tổng dãy $a$. Số vòng $= [m / S]$.
Giả sử sau khi mua các vòng thì còn dư $m'$ tiền.

### Thuật trâu:
Mô phỏng lại toàn bộ quá trình mua hàng của Hoa.

for (int i = 1; m >= Min; i++) {
    if (i > n) i = 1;
    if (m >= a[i]) {
        m -= a[i];
        ans++;
    }
} 

### Sub 1: $n = 2$
Có các giai đoạn:
- Còn đủ tiền mua $2$ quả
- Chỉ đủ tiền mua quả rẻ nhất
- Thiếu tiền

Dùng phép chia để xem mỗi giai đoạn xảy ra trong bao lâu (bao nhiêu vòng?)

### Sub 2: $a_1 \le a_2 \le ... \le a_n$
Tính mảng tiền tố (prefix-sum).
Mô phỏng lại các vòng đi chợ của Hoa.
Do $a$ tăng dần nên những loại quả được mua sẽ là những quả ở các quầy đầu tiên.
Do đó chỉ cần TKNP để xác định là mua tới quả nào thì hết tiền, xong lại bắt đầu vòng mới.

// Credit: OLP4CT587
void sub2()
{
    int res = 0;
    //prefix-sum
    for (int i = 1; i <= n; i++)
        a[i] += a[i - 1]; //trở thành tổng i số đầu tiên
    
    while (m >= a[1])
    {
        int k = upper_bound(a + 1, a + 1 + n, m) - a - 1;
        //upper_bound: tìm vị trí đầu tiên > hẳn m
        // lại -1 đi để ra vị trí cuối cùng <=
        res += (m / a[k]) * k;
        m = m % a[k];
    }
    cout << res;
}

### Sub 3: $m \le \min a\cdot 10^6$
Đáp án chắc chắn $\le 10^6$. Tuy nhiên nếu cày trâu như trên thì sẽ TLE (theo lí thuyết) vì có trường hợp quả rẻ nhất nằm ở một vị trí duy nhất, và ta phải chạy for hết $n$ phần tử mới tìm được quầy rẻ đó để mua.
VD:

n = 1e5, m = 1e18
a[i] = 10^9 với mọi i, ngoại trừ tại vị trí i = ? thì a[i] = 1

Ý tưởng:
http://online.vku.udn.vn/src/88371

Dùng DSU, tính mảng $nxt(i)$ là vị trí tiếp theo trên vòng tròn mà $\le m$ (số tiền còn hiện tại)


### Sub 4:
### Đơn giản
Thuật toán sau mô phỏng lại thuật trâu:
Code trên của: baoduong23042007
Giải thích: Vòng lặp `while` bên ngoài thực hiện rất ít lần, vì câu lệnh `m %= sum` sẽ giảm $m$ đi ít nhất $2$ lần (nếu `m > sum`).
Nếu `m < sum` thì phần "cày trâu" sẽ giảm $m$ đi xuống rất bé ?

### Phức tạp
(Chưa kiểm chứng được đúng sai nhưng thấy có một số thí sinh code BIT)
Xét $O(n)$ thời điểm đặc biệt: ngay khi $m$ giảm xuống bé hơn giá trị lớn thứ $i$ trong dãy $a$.
Quầy hàng nào đắt hơn $m$ thì ta "xóa" nó đi.
Về ý tưởng thì vẫn dùng phép chia (đi thành nhiều vòng) giống subtask 1, cho tới khi $m$ bé hơn mốc tiếp theo.
Vậy việc cần quan tâm là xét trong một đoạn liên tiếp sẽ có bao nhiêu số chưa bị "xóa"
Có cần BIT hay không?

## B3: DISTANCE
Tóm tắt: Cho cây $n$ đỉnh. Có $k$ đỉnh đặc biệt. Hỏi khoảng cách từ $u$ tới đỉnh đặc biệt gần nhất ($\neq u$) là bao nhiêu?

### Sub 1: $n \le 200$
Thuật $O(n^2):$ Tính trước k/cách giữa mọi cặp đỉnh trên cây (BFS/DFS), lưu vào mảng.
Sau đó chạy `for` $n^2$ để tìm cà phê gần nhất.

### Sub 2: $n \le 10^5, k \le 50$

Với mỗi $u$, ta duyệt qua $k$ đỉnh đặc biệt, cần lấy k/cách từ $u$ tới đỉnh đó.
Vậy lúc đầu cần tính trước bằng cách BFS/DFS từ mỗi một trong $k$ đỉnh.
Hoặc: dùng LCA để tính (phức tạp).

ĐPT: $O(nk)$

### Sub 3 + 4:
Làm chưa tối ưu la

http://online.vku.udn.vn/src/89811
QHĐ trên cây. DFS 2 lần để tính hai loại khoảng cách:
- từ nút con cháu cập nhật lên $u$
- từ nút tổ tiên (nằm ngoài cây gốc $u$) cập nhật cho $u$.

Đặt `dp_down[u], dp_up[u]` lần lượt là k/c loại 1,2 ở trên.

Khoảng cách loại 1 tính được bằng dfs thông thường. Gọi dfs để tính `dp_down` của những nút con cháu trước, sau đó gán `dp_down[u] = max(dp_down[v] + w)`.
https://viblo.asia/p/quy-hoach-dong-tren-cay-LzD5d9B4KjY

Khoảng cách loại 2 phải tính ngược lại một chút. Tận dụng khoảng cách loại 1, và kết quả từ các nút cha & tổ tiên ta cập nhật cho các nút con cháu.

Có hai trường hợp:
- `dp_up[v] = dp_up[u] + w` (từ nút tổ tiên của $u$ cập nhật cho $v$)
- Từ một nhánh khác trong cây con gốc $u$, gọi là $v_2$, cập nhật cho $v$. Ta có `dp_up[v] = dp_down[v2] + w2 + w1` (từ nút $v_2$, đi theo hai cạnh để tới $u$, rồi tới $v$)

Nếu nhóm biểu thức trên lại, ta thấy cần lấy $\max$ của tất cả `dp_down[.] + w[.]` của những nhánh khác $v$.

#### Sub 3:
Ta lưu hết vào một `multiset`, khi duyệt tới nhánh hiện tại thì xóa nó đi để tính, xong lại thêm vào. ĐPT $O(n\log)$
#### Sub 4:
Cần tìm $\max$ mọi nhánh còn lại nhanh hơn. Có thể:
- Hướng 1: Làm giống prefix-sum
- Hướng 2: Lưu lại hai giá trị bé nhất.

## B4: CARDGAME

### $O(n^2)$
Thử hết mọi đoạn con (chạy for $l,r$), lấy tổng đoạn trừ max

### Full (idea)

Giả sử $a_i$ lớn hơn mọi số trong đoạn $[l,r]$ (dùng stack/ gì đó để tìm l min, r max).

Tính prefix-sum thôi: Lấy max của S từ i tới r, trừ cho min của S từ l-1 tới i-1.

Segment Tree