# Đề HSG9 - BRVT - 2019: Editorial

## Bài 1: Giá trị của biểu thức (8 điểm)

Tính $A = \frac xy - \left[ \frac{1}{1\cdot2} + \frac{1}{2\cdot3} + ... + \frac{1}{n\cdot(n+1)} \right]$ $\left( n \le 10^6 \right)$ và đưa ra kết quả là phân số tối giản.

### Brute - force:

Đặt hai biến làm tử số và mẫu số tương ứng là $nume$ và $deno$.

Ban đầu, khởi gán:

- $nume = x$.
- $deno = y$.

Sau đó ==duyệt tuần tự từ $1 \rightarrow n$== để tính $A$.

Công thức tổng quát để cộng hai phân số:

$$
\frac{a_1}{b_1} + \frac{a_2}{b_2} = \frac{a_1 \cdot b_2 + a_2 \cdot b_1}{b_1 \cdot b_2}
$$

Độ phức tạp thời gian: $O \left( n \right)$.

:::warning
Thuật toán trên có thể dẫn đến tràn số.
:::

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int x, y, n;
    cin >> x >> y >> n;
    
    long long nume = x, deno = y;

    for (int i = 1; i <= n; i++) {
        long long a2 = 1, b2 = 1LL * i * (i+1);
        nume = nume * b2 - a2 * deno;
        deno = deno * b2;

        long long t = __gcd(nume, deno);
        nume /= t;
        deno /= t;
    }

    cout << nume << " " << deno;
    
    return 0;
}

:::

### Accepted:

:::info
:information_source: Kiến thức toán học cần biết:
$$
\begin{flalign}
\frac {a}{n \cdot (n+a)} = \frac {1}{n} - \frac {1}{n+a} \\
\frac {1}{n \cdot (n+1)} = \frac {1}{n} - \frac {1}{n+1}
\end{flalign}
$$
:::

Ta biến đổi biểu thức trên đề bài như sau:

$$
\begin{flalign}
A &= \frac xy - \left( \frac{1}{1*2} + \frac{1}{2 \cdot 3} + \dots + \frac{1}{n \cdot (n+1)} \right) \\
&= \frac xy - \left[ \left( \frac{1}{1} - \frac{1}{2} \right) + \left( \frac{1}{2} - \frac{1}{3} \right) + \dots + \left( \frac{1}{n} - \frac{1}{n+1} \right) \right] \\
&= \frac xy - \left( \frac 11 - \frac{1}{n+1} \right) \\
&= \frac xy - \frac{n}{n+1} \\
&= \frac{x \cdot (n+1) - y \cdot n}{y \cdot (n+1)}
\end{flalign}
$$

Như vậy, ta có thể tính ngay đáp án của bài toán.

Độ phức tạp thời gian: $O \left( 1 \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long x, y, n;
    cin >> x >> y >> n;

    long long a = x * (n+1) - y * n;
    long long b = y * (n+1);

    long long t = abs(__gcd(a, b));
    a /= t;
        b /= t;

    if (b < 0) {
        a = -a;
        b = -b;
    }

    cout << a << " " << b;

    return 0;
}

:::

## Bài 2: Dãy con tăng (7 điểm)

Cho dãy số nguyên dương $A_1, A_2, A_3, \dots, A_n$. Đếm số lượng dãy con tăng trong dãy.

:::info
:information_source: Định nghĩa:

Dãy con: Một dãy số được hình thành bằng cách xóa một số phần tử (hoặc không xoá phần tử nào) trong dãy ban đầu và không làm thay đổi thứ tự của các phần tử còn lại.
**VD:** $3, 11, 4$ là một dãy con của dãy $3, 2, 11, 4, 5$.

${\sum_{i=a}^b i}$ : Tổng các số từ $a$ đến $b$

:::

### Brute - force:

==Quay lui== thử tất cả các dãy con.

Độ phức tạp thời gian: $O \left( 2^n \right)$.

### Accepted:

==Quy hoạch động cơ bản.==

Định nghĩa $dp_i$ là số cách tạo ra dãy con tăng **bắt buộc** kết thúc tại phần tử thứ $i$

- Khởi gán $dp_i = 1$ (Trường hợp dãy có một phần tử).
- Công thức quy hoạch động: $dp_i$ bằng tổng tất cả $dp_j$ với $j \lt i$ và $a_j \lt a_i$:

$$dp_i = {\sum_{j \lt i, \; a_j \lt a_i} dp_j}$$

- Kết quả: $dp_1 + dp_2 \; + \dots + \; dp_n$:

$$\sum_{i=1}^n dp_i$$

==**Lưu ý:**== Khi lấy kết quả phải trừ đi 1 vì trường hợp dãy có một phần tử không được tính.

Độ phức tạp thời gian: $O \left( n^2 \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 30;
int n, res, A[N+1], dp[N+1];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
		dp[i] = 1;

		for (int j = 1; j <= i-1; j++)
			if (A[j] < A[i]) dp[i] += dp[j];
	
		res += dp[i] - 1;
	}

	cout << res;

	return 0;
}

:::

## Bài 3: Xây cầu (5 điểm)

Cho dãy số nguyên dương $A_1, A_2, A_3, \dots, A_n$ và $B_1, B_2, B_3, \dots, B_m$ $\left( n, m \le 5 \cdot 10^3 \right)$. Xác định độ dài **dãy con chung dài nhất**.

### Accepted:

==Quy hoạch động cơ bản.==

Định nghĩa $dp_{i, j}$ là độ dài dãy con chung dài nhất khi xét $i$ phần tử đầu tiên của dãy $A$ và $j$ phần tử đầu tiên của dãy $B$.

- Khởi gán: $dp_{i, j} = 0$.
- Công thức quy hoạch động:
- $dp_{i, j} = \max \left( dp_{i-1,j}, dp_{i, j-1} \right)$: Giữ nguyên độ dài dãy con chung dài nhất đã có.
- Nếu $A_i = B_j$ thì $dp_{i, j} = \max \left( dp_{i,j}, dp_{i-1, j-1} + 1 \right)$: Có thể thêm cặp số $A_i, B_j$ vào dãy con chung dài nhất hiện đã có.
- Kết quả: $dp_{n, m}$.

Độ phức tạp thời gian: $O \left( n \cdot m \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 5e3;
int n, m, A[N+1], B[N+1], dp[N+1][N+1];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> A[i];

	cin >> m;
	for (int i = 1; i <= m; i++) cin >> B[i];

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			if (A[i] == B[j]) {
				dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
		    }
        }
    }

	cout << dp[n][m];

	return 0;
}

:::