# ***`CTB Training Contest 04 Solution`***
# *A. DELTA*
## Tutorial
### Truy vấn thứ nhất
Đếm số dãy con liên tiếp chênh lệch không quá $\delta$
> Đây là 1 bài toán khá cơ bản, quen thuộc và dễ :))

Nhận thấy nếu đoạn $s \rightarrow t$ hiện tại thỏa mãn điều kiện thì mọi đoạn $x \rightarrow t$ với $(s \le x \le t)$ cũng đều thỏa mãn điều kiện.

Vậy nên, ta duyệt từ $1 \rightarrow n$. Với mỗi vị trí ta tìm điểm xa nhất về bên trái mà có điều kiện thỏa mãn. Việc này có thể làm nhờ `RMQ` và kĩ thuật `hai con trỏ`.

Ở đây chúng ta có thể chỉ việc tìm số dãy con liên tiếp có chênh lệch không quá k với đpt $O(NlogN)$ của thuật toán `RMQ`, tất nhiên, nếu dùng $O(N)$ của `deque` thì càng tốt.
### Truy vấn thứ hai
Đếm số dãy con không cần liên tiếp chênh lệch không quá $\delta$:
- Sắp xếp dãy theo thứ tự tăng dần.
- Duyệt vị trí $l$ là vị trí nhỏ nhất mà ta sẽ chọn trong tập con. Ta sẽ tìm được $r$ lớn nhất để $a_r - a_l \le \delta$. Khi đó thì ta thấy tập con của chúng ta sẽ chỉ chứa được các phần tử trong đoạn từ $l$ đến $r$. Do đó, ta cộng vào kết quả $2^{r-l}$ : Phần tử $a_l$ bắt buộc phải chọn do cách duyệt vị trí $l$. các phần tử từ $l+1$ tới $r$ có thể chọn hoặc không.

## Code demo
Như đã nói ở trên,truy vấn thứ nhất đây là 1 bài toán quen thuộc, ý tưởng này gặp ở khá nhiều bài:
* [VMQUABEO](https://oj.vnoi.info/problem/vmquabeo)
* [KDIFF](https://oj.vnoi.info/problem/kdiff)

Truy vấn thứ hai đã nếu rõ ý tưởng và cũng là 1 bài toán hết sức đơn giản.
> Vậy nên sẽ không có code demo hay là code mẫu :+1:
# *B. PUZZLES*

## Tutorial
### Subtask 1
Backtrack 2^n^ trạng thái chọn xâu. ĐPT $O(N \times 2^N)$.
### Subtask 2
Gọi `f[i][first][last]` là tổng độ dài **lớn nhất** đạt được nếu như ta chọn một số xâu ký tự, xâu cuối cùng đã chọn là $i$ (ta mới chỉ xét các xâu ký tự từ $1$ đến $i$ và xâu thứ $i$ chắc chắn được chọn), ký tự đầu tiên của xâu đầu tiên được chọn là $first$, và ký tự cuối cùng của xâu cuối cùng là $last$.
Tuy nhiên, ta biết do xâu thứ $i$ là xâu gần nhất ta đã chọn, nên $last$ = ký tự cuối cùng của xâu $s_i$. Do đó hàm QHĐ của chúng ta chỉ còn là `f[i][first]`.

Để tìm công thức truy hồi cho hàm QHĐ này, ta gọi $j$ là chỉ số của xâu được chọn liền trước xâu $s_i$. Khi đó, ký tự cuối cùng của xâu $s_j$ phải trùng với ký tự đầu tiên của xâu $s_i$. Nếu đều kiện này thỏa mãn, `f[i][first] = max(f[j][first] + |s_i|)`. ĐPT của công thức QHĐ này là $O(26 \times N ^ 2)$.
### Lý thuyết về Độ phức tạp trong thuật toán QHĐ
Độ phức tạp của một thuật toán QHĐ bao gồm 2 phần:
1. Số trạng thái của bảng QHĐ (trong bài này là $26\times N$)
2. Chi phí để tính toán một trạng thái (chi phí chuyển trạng thái, trong bài này là $N$).

**QHĐ xuôi:**

for (first: 'a' -> 'z') for (i: 1 -> n) for (j: i+1 -> n) 
	if (ký tự cuối của si trùng ký tự đầu của sj) 
           f[j][first] = max(f[j][first], f[i][first] + |sj|);

**QHĐ ngược:**

for (first: ‘a’ -> ‘z’) for (i: 1 -> n) for (j: 1 -> i-1)
	if (ký tự cuối cùng của sj trùng ký tự đầu của si) 
           f[i][first] = max(f[i][first], f[j][first] + |si|)

Để giảm độ phức tạp của một giải thuật QHĐ, ta cần phải giảm:
* (1) Số trạng thái của bảng QHĐ
* (2) Chi phí tính toán của một trạng thái.

Nếu muốn giảm số trạng thái của bảng QHĐ, ta chỉ có cách duy nhất là thiết kế lại toàn bộ hàm QHĐ. Tuy nhiên, nếu giảm (2) - chi phí tính toán của một trạng thái, thường có rất nhiều cách: lưu mảng phụ, mảng tiền tố, sử dụng CTDL... Mặc dù vậy, nếu dùng công thức QHĐ xuôi thì rất khó để giảm đpt do một trạng thái làm ảnh hưởng đến rất nhiều trạng thái khác. Vì vậy, công thức QHĐ ngược dễ tối ưu độ phức tạp hơn nhiều, vì có rất nhiều CTDL, kỹ thuật khác nhau có thể tính *tổng/max* trong thời gian ngắn.
### Subtask 4
Quay trở lại bài toán, từ công thức QHĐ ngược, ta thấy để tính `f[i][first]` ta cần tìm giá trị lớn nhất của các`f[j][first]` mà xâu $s_j$ kết thúc bởi ký tự đầu của xâu $s_i$. Do đó, ta sử dụng mảng phụ `maxF[last][first]` là giá trị lớn nhất của `f[j][first]` với các xâu $s_j$ kết thúc bởi ký tự $last$. Khi tính xong mảng này, ta có:

f[i][first] = maxF[ký tự cuối cùng của si][first] + |s_i|.

## Code demo

string words[N];
int n, result;
int f[N][26], maxF[26][26];

memset(f, -0x3f, sizeof f);
memset(maxF, -0x3f, sizeof maxF);
for (int i = 1; i <= n; i++) 
       maximize(f[i][words[i].front()], words[i].size());

for (int i = 1; i <= n; i++) {
	// tính mảng f[i] dựa theo mảng phụ maxF
	for (first: ‘a’ -> ‘z’)
		maximize(f[i][first], maxF[words[i].front()][first] + words[i].size());

	if (first == words[i].back()) 
           result = max(result, f[i][first]);
	
	// cập nhật lại mảng maxF sau khi đã tính được f[i]
	for (first: ‘a’ -> ‘z’)
		maximize(maxF[words[i].back()][first], f[i][first]);
}

# *C. Candy*
## Tutorial
### Subtask 1
Với ràng buộc nếu từ đỉnh $u$ có thể đi đến đỉnh $v$ thì dữ liệu đảm bảo từ đỉnh $v$ không có đường đi tới đỉnh $u$, đồ thị của ta có dạng một `DAG` và mỗi cạnh của chúng ta chỉ có thể đi qua một lần duy nhất. Bài toán bây giờ trở thành tìm đường đi có tổng trọng số lớn nhất trên `DAG`.

for(những đỉnh v có cạnh nối trực tiếp từ u)
    dp[u] = max(dp[u] , dp[v] + số kẹo được rải trên cạnh (u , v)).

### Subtask 2+3
Bây giờ ta xét xem trong trường hợp nào thì cạnh ($u$, $v$) có thể được đi qua nhiều lần. Khi đó đồ thị của chúng ta tồn tại đồng thời cả đường đi từ $u$ đến $v$ và đường đi từ $v$ đến $u$ nên $u$ và $v$ thuộc chung một thành phần liên thông mạnh. Khi đó để số kẹo lấy được là nhiều nhất, ta cứ đi qua cạnh $(u, v)$ cho đến khi số kẹo trên cạnh này = $0$. Vậy chúng ta có thể nhặt được bao nhiêu kẹo từ cạnh $(u, v)$ như vậy?. Ta chuẩn bị trước mảng c với ý nghĩa:
$c[i] = 1 + 1 + 2 + 1 + 2 + 3 + ... + 1 + 2 + 3 + ... + i. c[i] = c[i-1] + \frac{i \cdot (i - 1)}{2}$.
Gọi $w$ là số kẹo ban đầu trên cạnh $(u,v)$, lần thứ $i$ đi qua đây, số kẹo trên cạnh này sẽ còn $max(0, w - \frac{i \cdot (i - 1)}{2})$, do đó chúng ta có thể dùng thuật toán chặt nhị phân số lần **tối đa** mà chúng ta có thể đi qua đây mà vẫn nhặt được kẹo, gọi số lần đó là $t$, khi đó số kẹo mà chúng ta có thể nhặt được ở đây bằng $t \cdot w - c[t-1]$. Do $w \le 10^8$ nên mảng $c$ của chúng ta chỉ cần tính đến $10^4$ là đủ.

Bây giờ chúng ta dùng thuật toán `Tarjan` để nén đồ thị thành các *siêu đỉnh*, mỗi đỉnh là một thành phần liên thông mạnh. Hai đỉnh của siêu đồ thị này có cạnh nối khi ở đồ thị ban đầu có một đỉnh $u$ thuộc đỉnh thứ nhất và đỉnh $v$ thuộc đỉnh thứ hai. Khi đó ta được một siêu đồ thị có dạng là DAG. Với mỗi đỉnh $u$ của siêu đồ thị này, ta có $sum[u] =$ tổng số kẹo nhặt được trên mọi cạnh nối giữa các cặp đỉnh cùng thuộc siêu đỉnh này. Khi đó ta có công thức QHĐ như sau:

for(những đỉnh v có cạnh nối trực tiếp từ u)
    dp[u] = max(dp[u] , dp[v] + số kẹo được rải trên cạnh (u , v) + sum[u]).

Với subtask $2$, mỗi cạnh chúng ta chỉ có thể nhặt kẹo được 1 lần nên không cần chặt nhị phân.

Ngoài thuật toán chặt nhị phân, do $t$ tối đa của mỗi cạnh chỉ lên đến $10^4$, chúng ta có thể sort các cạnh theo trọng số tăng dần và dùng thuật toán `hai con trỏ` để tìm $t$.

## Code demo

int par[N]; //đánh dấu chỉ số tpltm của từng đỉnh
void dfs(int u) //Tarjan liệt kê tpltm
{
    ...
}

ll go(int u) // Hàm QHĐ bằng đệ quy có nhớ
{
     ...
}

int main() 
{
    ... // Input
    memset(f, -1, sizeof f); // Khởi tạo mảng QHĐ chuẩn bị cho quá trình đệ quy có nhớ
    for(int i = 1 ; i <= n ; ++ i)
        if(đỉnh i chưa được xét) dfs(i);
    ... // Xây siêu đồ thị mới từ các tpltm
    printf("%lld\n", go(comp[S])); // Gọi hàm QHĐ với siêu đỉnh chứa đỉnh s của đồ thị ban đầu
}