# Solution for VOI 22-23
> Chưa chắc là tôi đã đủ trình nghĩ & code được những điều này trong phòng thi.
\- Lê Tăng Phú Quý

>Tham khảo thêm lời giải chất lượng từ [VNOI](https://www.facebook.com/vnoi.wiki/videos/1264715667813041)

## Bài 1: Chuỗi ADN
### Đề bài
Điền vào các vị trí `?` để đạt được độ đa dạng lớn nhất.
Độ đa dạng: Số lượng xâu con "phức tạp"
Xâu con phức tạp: xâu con chứa $\ge$ hai loại kí tự khác nhau
Xâu ban đầu chỉ chứa $A,T,G,X,?$

### Subtask 1: $n \le 10$
Duyệt vét cạn mọi trường hợp bằng đệ quy quay lui $O(4^n)$.

### Subtask 2: $n \le 20$
Tính độ đa dạng bằng cách lấy tổng tại từng vị trí $i$.
Giả sử có một xâu hoàn chỉnh (không có `?`), đặt $l_i = j$ là vị trí gần nhất về bên trái mà $S_j \neq S_i$. Độ đa dạng $=\sum l_i$
Từ đó có thể đặt trạng thái QHĐ: $dp(i,a,t,g,x)$ là xét tới kí tự thứ $i$, ta đã điền sao đó để vị trí của các chữ $A,T,G,X$ gần nhất là tại $a,t,g,x \le i$ thì tổng độ đa dạng bằng bao nhiêu?
ĐPT: $O(n^5)$ hoặc $O(n^6)$

### Subtask 3: $n \le 5000$
Vẫn ý tưởng tính độ đa dạng bằng $l_i$, tuy nhiên ta sẽ khéo hơn một chút.
Đặt $dp(i,c)$ là xét trong tiền tố độ dài $i$ của $S$, sao cho $S_i$ được điền $c$ (tức nó phải $=c$ hoặc $=?$ lúc đầu).
Ý tưởng chuyển trạng thái: Mỗi lần, ta sẽ thêm hẳn một đoạn liên tiếp các kí tự giống nhau, và $\neq c$. Dễ thấy $l_j$ của các vị trí được điền tiếp theo bằng đúng $i$,
Giả mã:

for (int i = 0; i <= n; i++)
    for (char c in {'A', 'T', 'G', 'X'})
        for (int j = i+1; j <= n; j++)
            for (char c2 in {'A', 'T', 'G', 'X'} \ {c})
                if (đoạn [i+1..j] chỉ chứa ? hoặc c2)
                    tối ưu dp[j][c2] theo dp[i][c] + (j-i) * i

ĐPT $O(n^2)$. Nếu cài khéo có thể giảm hằng số (chỉ `for c` 1 lần thay vì 2 lần chẳng hạn).

### Subtask 4: $n \le 10^5$
ĐPT $O(n\log)$ dễ đoán.
Nếu biết nhiều kĩ thuật, thí sinh có thể nhìn vào công thức ở subtask 3 và nghĩ ngay tới cách dùng Convex Hull Trick để cập nhật $dp[j]$ mà không cần chạy `for j`. Tuy nhiên, độ phức tạp về kiến thức lẫn cài đặt đều vượt quá phạm vi bài 1 của đề vòng 1.
Mong được chia sẻ thêm về cách làm tinh tế nào đó ăn được subtask này.

### Subtask 5: $n \le 10^6$
Tiến xa hơn một bước nữa, ta nhận thấy để một xâu kết thúc tại $i$ có độ đa dạng nhỏ nhất, thì nên làm cho đoạn liên tiếp kết thúc tại $i$ càng dài càng tốt? (cần chứng minh)
Sơ lược về tính đúng đắn:
- Nhận thấy $dp(i)$ đồng biến với $i$ (xâu càng lớn - độ đa dạng càng cao)
- Biểu thức $j(i-j)$ (giả sử ta chọn $j<i$ là một vị trí trước đó mà $S_j \neq S_i$) là parabol hướng xuống, đạt $\min$ tại hai đầu ($j$ bé nhất hoặc lớn nhất)

Có nhận xét này, để tính $dp(i)$ tối ưu ta chỉ cần biết $O(1)$ vị trí $j$ trước đó mà không cần `for`.
Để xác định là $j$ nào thì xử lý được trong $O(n)$ hoặc $O(n\log)$ bằng đếm phân phối hoặc CTDL.

## Bài 2: Thu nhập ổn định
### Đề bài
Cho một dãy $A$ có $n$ phần tử. Sau mỗi lượt, ta gán $A_i^{(t)} = \max(A_{[L_i..R_i]}^{(t-1)})$.
Hỏi cần bao nhiêu lượt (tìm $t \min$) để $A$ "hội tụ" (không đổi giá trị so với phiên bản trước, hay $A^{(t)} = A^{(t-1)}$)

### Subtask 1: $n \le 500$
Ta cày trâu. Mỗi lượt, ta sẽ tính $\max$ và có $A^{(t)}$ trong $O(n^2)$
Số lượt tối đa là $O(n)$ $(*)$ nên ĐPT là $O(n^3)$.
Chứng minh $(*):$ Mất tối đa $n-1$ lượt để $A_i^{(t)} = A_j^{(0)}$ (giá trị của $A_j$ lúc đầu cập nhật tới $A_i$) với $i,j$ bất kì. Dấu bằng xảy ra với test sau:
- $A_i^{(0)} < A_{i+1}^{(0)}$
- $L_i = i, R_i = i+1$

### Subtask 2: $A_i^{(50)} = A_i^{(49)}$
Tức là $t \le 50$. Nếu tìm được cách tính $A^{(t)}$ từ $A^{(t-1)}$ hiệu quả hơn $O(n^2)$, cụ thể là trong độ phức tạp $T(n)$, thì bài toán có thể giải quyết được trong ĐPT: $O(50 \times T(n))$
- Nếu dùng Segment Tree hoặc dùng các cây khác của C++ STL thì $T(n) = O(n\log n)$
- Có thể dùng [Deque tìm max đoạn tịnh tiến](https://vnoi.info/wiki/algo/data-structures/deque-min-max.md) để đạt được $T(n) = O(n)$

### Subtask 3: $\sum_{i=1}^{N} R_i-L_i \le 10^6$
Subtask này có cách tiếp cận khá độc đáo.
Với mỗi $j \in [L_i, R_i]$, ta thêm cung có hướng $j \rightarrow i$.
Sau đó, duyệt các đỉnh theo trọng số giảm dần. Với trọng số $w$, ta thêm tất cả đỉnh $u$ có $A_u^{(0)} = w$ vào queue ban đầu và BFS.
Do ta duyệt theo trọng số giảm dần, những đỉnh đã thăm trước đó (với các $w'$ lớn hơn) không cần thăm lại ở lượt này nữa.
ĐPT $O(n + \sum (R_i - L_i))$

### Subtask 4: Nếu $L_i < L_j$ thì $R_i \le R_j$
Chưa biết làm

### Subtask 5: Bài gốc
Ta thêm vào các đỉnh "ảo", đại diện cho nhiều nút. Dựa trên cấu trúc của Segment Tree, có thể tạo ra $O(n)$ đỉnh ảo là đủ để biểu diễn bất kì đoạn $[L,R]$ nào.
Với đoạn $[L_i, R_i]$, ta phỏng theo hàm `query` của IT để chia nó thành $O(\log)$ nút quản lý các đoạn liên tiếp. Sau đó nối các cung $u \rightarrow i$ với *trọng số* $1$.
Riêng với các cung của cây IT (nối từ nút con lên nút cha), trọng số là $0$.
Vậy cần áp dụng thuật toán [BFS 0/1](https://cp-algorithms.com/graph/01_bfs.html).
ĐPT cuối: $O(n\log)$

## Bài 3: Năng lượng tối thiểu
### Đề bài
Tìm khoảng cách xa nhất từ một ô **bất kì** tới một trạm điện. Có $Q$ truy vấn thêm/ bớt trạm.
Bảng gồm $W \le 15$ dòng và $L \le 10^9$ cột. Lúc đầu có $N (N \le 5 \cdot 10^4)$ trạm. Giới hạn $Q:Q \le 10^5$.

### Sub 3: $Q,L,N \le 200$
Với mỗi truy vấn, ta duyệt qua toàn bộ bảng $W \times L$ và các trạm điện để mô phỏng.
Duyệt qua toàn bộ ô $(r,c)$. Với mỗi ô, ta lại duyệt qua $O(N+Q)$ trạm điện để tính khoảng cách gần nhất. Đáp án sẽ là ô có khoảng cách lớn nhất.
ĐPT $\mathcal{O}(Q\cdot WL\cdot(N+Q))$
Có thể tối ưu ĐPT bằng cách tiền xử lý. Vì đã biết trước các ô là trạm điện trong ở $\ge 1$ trong $Q+1$ tình huống, ta chỉ cần tính khoảng cách một lần lúc đầu và lưu vào mảng, thay vì phải duyệt qua toàn bộ trạm với mỗi truy vấn. Xét ĐPT của:
- tiền xử lý: $\mathcal{O}(WL\cdot(N+Q))$
- trả lời truy vấn: $\mathcal{O}(Q \cdot (N+Q))$

### Sub 5: $L \le 10^4, Q \le 100$

Xét một ô $(r,c)$ bất kì, để tìm khoảng cách ngắn nhất từ ô đó tới một trạm bất kì, thay vì BFS từ $(r,c)$, ta có thể thêm tất cả trạm vào `queue` rồi BFS (BFS đa nguồn tương tự Subtask 3 bài 2).
ĐPT: $\mathcal{O}(Q\cdot(N+Q + W \cdot L))$

### Sub 1: $W = 1$
Nhận thấy cần tính *"Khoảng cách xa nhất giữa cặp trạm liền kề"*.
Xét khoảng cách giữa:
+ Hai trạm liên tiếp
+ Trạm gần biên nhất với biên (trái/phải).

Dùng `set` để quản lý những vị trí có trạm, và dùng `multiset` để quản lý khoảng cách.

### Sub 2: $W = 3$
Làm khá giống sub 1, tuy nhiên với mỗi dòng ta sẽ có một `set` riêng để lưu vị trí trạm.
Khi thêm/xóa trạm $(r,c)$, cần duyệt qua cả $3$ dòng và tìm trên đó những trạm nào có tọa độ cột gần $c$ nhất. Từ đó tính được khoảng cách.
Khi một trạm thay đổi, cần phải tính lại khoảng cách của toàn bộ trạm "gần" đó (có tọa độ cột gần nhất, xét từng dòng)
Vậy, tại mỗi trạm cần quản lý thêm khoảng cách của tất cả những trạm "gần" nó.

### Sub 4: $Q = 1$
Nhận thấy bài toán có tính chất "tăng": càng nhiều năng lượng lúc đầu thì robot càng có khả năng hơn để đi tới trạm điện $\Rightarrow$ ta nghĩ đến TKNP trên đáp án.
Với khoảng cách $d$, cần kiểm tra xem: Có tồn tại ô nào mà khoảng cách từ nó tới mọi trạm điện là $>d$ không?
Mỗi trạm tạo 1 vùng.
Cộng đoạn liên tiếp. Duyệt theo W. Sweepline. Cần tìm cách khử log của sắp xếp. $\rightarrow$ Nén số từ trước + prefix-sum.

### Full
[Lời giải của GS.PVH](https://docs.google.com/document/d/1EIj69K7G__fdjztjUmJ9KPAKBRWv5_dUQ3bdZ1-B4fI/edit?fbclid=IwAR0OysN9cyh6XKriusDNB_rE_6Beh5lApJElaCBgnWD70ImuOL8dBa71fhg)

Để giải quyết bài toán kiểm tra ở trên, ta có nhận xét, với ô $(r,c)$ nằm giữa 2 cột A và B (tức A <= c <= B), k/c từ ô (r, c) tới trạm gần nhất bên trái là $\text{Left}(r) + c - A$, k/c từ ô (r, c) tới trạm gần nhất bên phải là $\text{Right}(r) + B - c$. Từ đó, ta thấy rằng, nếu $\max(0, T - \text{Left}(r) + 1) + \max(0, T - \text{Right}(r) + 1) \ge B - A + 1$ thì mọi ô trên hàng r giữa 2 cột A và B đều có k/c tới trạm gần nhất <= T. Ngược lại, nếu max(0, T - Left(r) + 1) + max(0, T - Right(r) + 1) < B - A + 1 thì tức là còn một ô nào đó k/c tới trạm gần nhất > T, và khi đó khoảng cách T là không đủ để bao hết mọi ô.

ĐPT của thuật toán trên là $O((N + Q) * W * (log(N + Q) + W*log(W))$. Có một số cải tiến có thể khả thi cho thuật toán này (mà mình chưa nghiên cứu kỹ):

## Bài 4: Nhà gỗ
- Sắp xếp tăng dần
- Lấy đoạn liên tiếp để xây
- Vì hoán vị các nhà sẽ TLE nên dùng QHĐ bitmask

## Bài 5: Thiết bị thông minh
TKNP & sweep-line
(tôi không phải Madara Trần)

## Bài 6: Canh tác lương thực
### Đề
Knapsack trên cây + rất nhiều hệ số riêng
### Sol
$f[u][s]:$ chi phí thấp nhất để cây con gốc $u$ có sản lượng $= s$ tấn. (nếu $s > S$ thì coi như là $s = S$).
Công thức: $f[u][s] = \min \sum f[v][s'] +k_u^2 c_u$ với $k_u=s-\sum s', k_u \le q_u$

### Sub 1: $q = 1$, mọi cạnh nối $1$
Bài toán cái túi. Mỗi "vật" (thửa ruộng) có trọng số là $c_i$, giá trị là $w_i$.

### Sub 2: $n,s \le 500$
Kết hợp thành Knapsack trên cây với ĐPT $O(n \times s^2)$ như trên.

### Sub 3: $q = w = 1$
Ta thấy $f[u][s]$ chính là $\sum c_v$ với các $c_v$ nhỏ nhất, $v$ thuộc cây con gốc $u$, thỏa điều kiện $(w_{parent} = 0 \Rightarrow w_{child} = 0)$
Cách làm như trên, nhưng để ý ĐPT: Khi duyệt tới nhánh $v$, ta chỉ chạy $s'$ tới $\le cnt_v$ (với $cnt_v=$ số nút trong cây con gốc $v$).
Do đó ĐPT tổng cộng là $O(n^2)$
*Lí giải:* Khi gặp con $v$ của $u$ và duyệt $s'$ để cập nhật QHĐ, việc đó giống như ta đang xét từng nút trong cây con gốc $v$, và chắp nối nó vào đỉnh $u$ (cây gốc $u$)

### Sub 4: $q = 1$
Vẫn dùng thuật toán như subtask 2, ta đạt được ĐPT $O(s^2)$.
Chuyển trạng thái: Khi thêm một nhánh của

### Sub 5: Mọi cạnh chứa $1$
$f(s) + k^2 * c(k) -> f(s + kw)$
chia căn?