# Đề HSG9 - BRVT - 2018: Editorial

[toc]

## Bài 1: Sắc hoa (8 điểm)

Có $n$ $(n \le 32)$ loại hoa, loại hoa thứ $i$ có chu trình nở hoa là $a_i$ $(1 \lt a_i \le 100)$ ngày. Xác định ngày đầu tiên cả $n$ loại hoa cùng nở.

### Accepted:
Dễ dàng nhận thấy ngày mà tất cả loài hoa cùng nở phải là bội chung của $A_1, A_2, ..., A_n$.

Do đó đáp án là $\text{BCNN} \left( A_1, A_2, ..., A_n \right) = \text{BCNN} \left( \text{BCNN} \left( \dots, A_{N-1} \right), A_N \right)$.

Để lập trình tính $\text{BCNN}$ nhanh, ta sử dụng công thức sau:

$$
\text{BCNN} \left( a, b \right) = \frac{a \cdot b}{\text{UCLN} \left( a, b \right)}
$$

:::success
:::spoiler Code

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

int main() {
    int n, res;
    cin >> n >> res;
    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        
        res = res * x / __gcd(res, x);
    }

    cout << res;

    return 0;
}

:::

## Bài 2: Dãy ngoặc đúng (7 điểm)

Đếm số dãy ngoặc đúng có độ dài $n$ $(n$ chẵn, $2 \le n \le 26)$.

### Brute - force:

==Quay lui đơn thuần==, thử mọi cách đặt dấu ngoặc đóng và dấu ngoặc mở vào từng vị trí, sau đó kiểm tra dãy ngoặc có phải dãy ngoặc đúng hay không.

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

### Accepted:

Cần đặt thêm **nhánh cận** vào thuật toán quay lui brute-force (chỉ thử các trường hợp có thể thỏa điều kiện).

:::info
**nhánh cận** trong thuật toán quay lui được hiểu là những điều kiện để dừng hàm quay lui sớm hơn bình thường hoặc chỉ duyệt qua những trường hợp đúng, nhằm tránh việc duyệt qua những trường hợp thừa (chắc chắn sai). Từ đó giảm thời gian chạy chương trình đáng kể.
:::

==Nhánh cận được đặt trong bài trên như sau:==
- Duy trì một biến $sum$, ban đầu $sum = 0$.
- Mỗi khi đặt dấu `(` thì $sum$ trừ 1 đơn vị, dấu `)` thì $sum$ cộng 1 đơn vị.
- ==**Nhận xét:**== Trong quá trình quay lui, bất cứ khi nào $sum \lt 0$ (nghĩa là có tồn tại dấu đóng ngoặc khi chưa mở ngoặc trước đó) thì cách xếp ngoặc đang thực hiện là không đúng $\rightarrow$ **Không quay lui tiếp trường hợp này.**

Độ phức tạp thời gian: $O \left( Catalan_{\frac n2} \right)$ với $Catalan_{\frac n2}$ là [số Catalan](https://www.wikiwand.com/vi/articles/S%E1%BB%91_Catalan) thứ $\frac n2$.
:::info
:information_source: Số Catalan

- Số Catalan là đáp án của nhiều bài toán đếm, tiêu biểu là bài toán **số dãy ngoặc đúng độ dài $n$** (bài toán kể trên).
- Công thức tính số Catalan thứ $N$:

$$
Catalan_n = \frac{1}{n + 1} \cdot C^n_{2n} = \frac{(2n)!}{(n+1)! \cdot n!} = \frac{(n+2)\cdot(n+3) \dots (2n)}{n!}
$$
:::

:::success
Bài toán này cũng có thể được giải bằng ==số Catalan== nói trên.
:::

:::success
:::spoiler Code

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

const int N 1000006;
int n;
long long sum, res;

void Try (int pos) {
    for (int i = -1; i <= 1; i += 2){
        sum += i;
        
        if (sum < 0){
            sum = 0;
            continue;
        }
        
        if (pos == n && sum == 0) {
            res++;
        }
        if (pos < n) {
            Try(pos+1);
        }
        
        sum -= i;
    }
}

int main() {
    cin >> n;
    
    Try(1);
    cout << res;

    return 0;
}

:::

## Bài 3: Pháo đài (5 điểm)

Có $n$ pháo đài $\left( n \le 2 \cdot 10^4 \right)$, $d_i$ là khoảng cách đồng thời cũng là chi phí kết nối của hai pháo đài $i$ và $i+1$ $\left( i \lt n, \; 0 \lt d_i \le 10^6 \right)$.

Tìm chi phí nhỏ nhất sao cho mỗi pháo đài đếu được kết nối với ít nhất một pháo đài khác. Biết tồn tại một pháo đài đặc biệt $K$ không cần kết nối với bất kỳ pháo đài nào.

### Accepted:

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

Định nghĩa $dp_i$ là chi phí nhỏ nhất để kết nối $i$ pháo đài đầu tiên lại với nhau (chỉ được sử dụng đúng i pháo đài đầu tiên).

Khởi gán:
$$
dp_1 =
\left \{
\begin{array}{rcl}
0 & \mbox{khi} & k = 1 \\
\infty & \mbox{khi} & k \not = 1
\end{array} \right.
$$

> Nếu $k = 1$ $\rightarrow$ Pháo đài $1$ không cần kết nối.

> Nếu $k \not = 1$ $\rightarrow$ Không có cách nào để kết nối pháo đài $1$ chỉ với duy nhất pháo đài $1$.

Công thức quy hoạch động:
$$
dp_i=
\left \{
\begin{array}{rcl}
\min \left[ dp_{i-1} , \left( dp_{i-1}, dp_{i-2} \right) + d_{i-1} \right] & \mbox{khi} & i = k \\
\min \left( dp_{i-1}, dp_{i-2} \right) + d_{i-1} & \mbox{khi} & k \not = 1
\end{array} \right.
$$

> Nếu $i \not = k$ $\rightarrow$ Vì chỉ được dùng $i$ pháo đài đầu tiên, ta chỉ có thể kết nối pháo đài $i-1$ với pháo đài $i$.
> Tuy nhiên, có hai trường hợp như sau:
> - Pháo đài $i-2$ có kết nối với pháo đài $i-1$.
> - Pháo đài $i-2$ không kết nối với pháo đài $i-1$.

> Nếu $i = k$ $\rightarrow$ Có thêm lựa chọn không kết nối pháo đài thứ i, do đó ta thử lấy $dp_{i-1}$.

:::success
:::spoiler Code

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

const int N = 2e4;
const long long MX = 1e18;
int n, k, d[N+1];
long long dp[N+1];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n-1; i++) {
        cin >> d[i];
    }

    if (k == 1) {
        //Nếu k = 1 tức là pháo đài 1 không cần kết nối
        dp[1] = 0;
    }
    else {
        //Nếu k != 1 tức là chỉ với pháo đài 1 nó không thể kết nối
        //Do đó chi phí sẽ là oo (vô cực) <=> Không thể kết nối
        dp[1] = MX;
    }

    dp[2] = d[1];
    for (int i = 3; i <= n; i++) {
        if (i == k) {
            dp[i] = min(dp[i-1], min(dp[i-1], dp[i-2]) + d[i-1]);
        }
        else {
            dp[i] = min(dp[i-1], dp[i-2]) + d[i-1];
        }
    }

    cout << dp[n];

    return 0;
}

:::