<button style="text-align:center; font-size:30px; color:none; background:none; border:none; padding:0; position:relative; left:38.5%;">
\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.9}}}}}\)
</button>

<button style="text-align:center; font-size:30px; color:none; background:none; border:none; padding:0; position:relative; left:38.5%;">
\(\color{orange}{\text{Mục lục}}\)
</button>

\(\color{#300000}{\text{1. Hint <Trâu>}}\)

• \(\color{#903030}{\text{<Cày trâu>}}\) Duyệt qua từng dãy con và kiểm tra xem dãy đó có thỏa hay không.

Gọi tập \(S\) là một tập các phần tử thỏa màn yêu cầu đề bài. Thì cần xóa \(n - |S|\) phần tử

Thì kết quả cần tìm là \(res = n - max(|S|)\)

\(\color{#c01515}{\text{1. Approach <Cày trâu> <Bitmasking>}}\)

• \(\color{#f03030}{\text{<Cày trâu> <Bitmasking>}}\) Xét từng trạng thái hiện tại là dãy nhị phân \(mask\)

Có \(mask = x_0 \times 2^0 + x_1 \times 2^1 + \dots + x_{n - 1} \times 2^{n - 1}\) với \(xi = 1\) là tồn tại phần tử thứ \(i\) trong mảng \(a[]\)

Gọi mảng \(b[]\) là tập hợp các phần tử \(a[i]\) có \(x_i = 1\)

Kiểm tra tính hợp lệ bằng cách duyệt \(\forall x, y \in b[]\) có \(|x - y| \notin \{1, 8, 9\}\)

Trong các mảng \(b[]\) hợp lệ thì \(res = n - max(b.size)\)

• \(\color{#f03030}{\text{<Phân tích độ phức tạp> }}\) Độ phức tạp \(O(2^n \times n^2)\)

Số lượng tập cần duyệt qua là \(O(2^n)\)

Duyệt lấy các phần tử cho mảng \(b[]\) là \(O(n)\)

Chi phí kiểm tra là \(O(n^2)\)

\(\color{#88B4B4}{\text{1. Code tham khảo(TLE) }}\): Cày trâu, Bitmasking

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(2^n \times n^2)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n)\ \color{#7f5f3f}{\text{memory}}}}\)

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    int res = n;
    int lim = 1 << n;
    for (int mask = 0; mask < lim; ++mask)
    {
        vector<int> b;
        for (int i = 0; i < n; ++i)
            if (mask & (1 << i))
                b.push_back(a[i]);

        bool SEQ189 = true;
        int m = b.size();
        for (int x : b)
            for (int y : b)
                for (int d : {1, 8, 9})
                    if (x - y == d)
                        SEQ189 = false;

        if (SEQ189) res = min(res, n - m);
    }

    cout << res;
    return 0;
}

\(\color{#300000}{\text{2. Hint <Quy hoạch động>}}\)

• \(\color{#903030}{\text{Nhận xét (Sắp xếp): }}\) Thứ tự các phần tử được chọn không quan trọng, chỉ quan trọng \(|a_i - a_j| \in \{1, 8, 9\}\) hay không

Ta có thể sắp xếp mảng để tiện tính toán

• \(\color{#903030}{\text{Nhận xét (Nén mảng): }}\) Nếu \(S\) là một tập thỏa mãn tối ưu và \(a_i \in S\) thì mọi \(a_j = a_i\) \((j \neq i)\) đều thuộc tập \(S\)

Nên ta chỉ cần các phần tử phân biệt, gọi \(b_i\) là giá trị này và \(c_i\) là số lần xuất hiện số đó

• \(\color{#903030}{\text{Nhận xét (Bitmasking): }}\) Khi lấy lần lượt các phần tử \(x\) tăng dần. Mình chỉ quan tâm các thằng \(y \in S\) mà \(x - y \leq 9\) để kiểm tra \(S\) có thể thêm \(x\) hay không

Ngoài việc lưu một tập tối đa \(9\) phần tử, mình có thể dùng \(mask\) để đánh dấu sự tồn tại của nó như cách trên

• \(\color{#903030}{\text{Nhận xét (Đệ quy có nhớ): }}\) Gọi \(magic(int\ i)\) là độ dài tập tối ưu xét tới \(i\)

Nếu ta bỏ qua thằng \(b_i\), kết quả tối ưu sẽ là \(magic(i + 1)\)

Nếu ta lấy thằng \(b_i\), kết quả tối ưu sẽ là \(magic(i + 1) + c_i\)

\(\color{#c01515}{\text{2. Approach <Quy hoạch động>}}\)

• \(\color{#f03030}{\text{<Đệ quy có nhớ>}}\)

Gọi \(S[]\) là một mảng đánh dấu với \(S[p] = 1\) là tồn tại phần tử \(b_p\). Ta có thể tính được \(mask\) là 9 thằng cuối của \(S[]\)

Gọi \(f[i][mask]\) là mảng quy hoạch động. Nếu \(f[i][mask]\) đã được tính thì trả về kết quả luôn

Gọi \(ok = true\) là mình có thể lấy được phần tử \(b_i\) đang xét. Sau đó duyệt \(\forall \{t \in \mathbb{N}, t \in [i - 9; i)\ \}\) nếu \(\exists S[t] = 1\) để \(b_i - b_t \in \{1, 8, 9\}\) thì \(ok = false\)

Tính \(A = magic(i + 1)\) là khi không lấy \(b_i\).

Nếu \(ok = true\) thì ta sẽ lấy \(b_i\). Ta đánh dấu \(S[i] = true\) sau đó tính \(B = magic(i + 1)\) và cuối cùng đánh dấu lại \(S[i] = false\)

Kết quả \(f[i][mask] = max(A, B)\)

• \(\color{#f03030}{\text{<Phân tích độ phức tạp> }}\) \(O(n \times 2^9)\)

Chi phí chuyển: \(O(9)\)

Số trạng thái: \(O(n) \times O(2^9)\)

\(\color{#009933}{\text{2. Code tham khảo(Accepted) }}\): Đệ quy có nhớ, Bitmasking

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n \times 2^9)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n \times 2^9)\ \color{#7f5f3f}{\text{memory}}}}\)

#define all(x) (x).begin(), (x).end()
template<typename T> void maximize(T &res, T val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, T val) { if (res > val) res = val; }

int n;
vector<int> b, c;
vector<vector<int> > f;
bitset<2000> S;
bool i189(int x) { return (x == 1) || (x == 8) || (x == 9); }
int magic(int i = 0) {
    if (i >= b.size()) return 0;

    int mask = 0;
    int low = max(0, i - 10);
    for (int t = low; t < i; ++t)
        mask |= (S[t] << (t - low));

    int &res = f[i][mask];
    if (res != -1) return res;
    res = magic(i + 1);

    bool ok = true;
    int lim = max(0, i - 9);
    for (int t = i - 1; t >= lim; --t)
        if (S[t] && i189(b[i] - b[t]))
            { ok = false; break; }

    if (ok)
    {
        S[i] = true;
        maximize(res, magic(i + 1) + c[i]);
        S[i] = false;
    }

    return res;
}

int main()
{
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;

    sort(all(a));
    int res = 0, cnt = 0, pre = -1;
    for (int cur : a)
    {
        if (cur != pre)
        {
            b.push_back(cur);
            c.push_back(1);
            cnt++;
        }
        else cnt++, c.back()++;
        pre = cur;
    }
    f.assign(n + 1, vector<int>((1 << 10) + 1, -1));
    res += cnt - magic();

    cout << res;
    return 0;
}