<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 <Bài toán con tương tự>}}\)

• \(\color{#903030}{\text{<Xét bài toán con> }}\) Sau khi mình lấy phần tử đầu. Thì mình lần lượt lấy 2 phần tử kề với phần tử trước đó. Vậy nếu duỗi cái hình tròn đó ra thành một đoạn thẳng, ta được một hàng đợi hai đầu mà ở đó mình hoặc là lấy thằng bên trái cùng, hoặc là lấy thằng bên phải cùng. Vậy phát biểu lại, ta có bài toán con: Nếu xét trên một hàng đợi hai đầu gồm \(n\) phần tử \(\{a_1, a_2, \dots, a_{n-1}, a_n\}\) và ta chỉ được lấy thằng bên trái cùng hoặc bên phải cùng rồi xóa nó và nhận số diểm tối ưu. Hãy tính giá trị tối đa của \(X - Y\) với \(X, Y\) là số số lẻ thằng thứ hai và thứ nhất lấy được khi cả 2 đứa chơi tối ưu.

\(\color{#c01515}{\text{1. Approach <Bài toán con tương tự>}}\)

• \(\color{#f03030}{\text{<Bài toán con>}}\) Với bài toán con về hàng đợi hai đầu và tính \(max(X - Y)\), bạn đọc có thể tham khảo ở đây

• \(\color{#f03030}{\text{<Nhận xét nhỏ>}}\) Ta chỉ quan tâm các số lẻ nên sẽ biến cả mảng \(a[]\) thành \((a_i = 1)\) khi \(a_i\) lẻ và \((a_i = 0)\) khi \(a_i\) chẵn. Điều này không ảnh hưởng bài toán nhưng lại có lợi trong việc tính toán

• \(\color{#f03030}{\text{<Bài toán chính>}}\) Ta sẽ nhân đôi mảng thành dãy \(A[] = \{a_1, a_2, \dots, a_{n - 1}, a_n, a_1, a_2, \dots, a_{n - 1}, a_n\}\)

Tại mỗi vị trí \(p\) mà \(\{p \in \mathbb{N}, p \in [0, n)\ \}\) ta có được đoạn \(A[p + 1\dots p + n)\) là hàng đợi hai đầu sau khi bỏ \(a_p\) và duỗi ra

Ta sẽ xử lí từng đoạn con \(A[p + 1\dots p + n)\) của \(N\) ván chơi bằng deque trong \(O(n^2)\)

Gọi \(v[]\) là mảng nén của dãy \(A[]\) dựa theo Phép toán với ngăn xếp hai đầu

Ta có thể tính được \(d = X - Y\) từ mảng \(v[]\) và đếm được số lượng số lẻ trong đoạn \(v[]\) là \(t = X + Y\)

Gọi \(E\) là tính chẵn lẻ số bị bỏ đi, \(e = a[p + n - 1]\)

Từ \(d\) và \(t\) ta tính được \(X = \frac{t - d}{2}\) và \(Y = \frac{t + d}{2}\)

Nếu \(X + E > Y\) thì ta tăng biến đếm, là khi ông chủ thắng

\(\color{#009933}{\text{1. Code tham khảo<Accepted> }}\): CTDL, Deque, Tham lam, Concept, Two-pointers

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(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;
        x &= 1;
    }

    a.resize(n << 1);
    for (int i = 0; i < n; ++i) a[i + n] = a[i];
    vector<int> v(n - 1, false);

    int res = 0;
    for (int p = 0; p < n; ++p)
    {
        int m = n - 1;
        for (int i = 0, j = p; i < m; ++i)
        {
            v[i] = a[j++];
            for (; i >= 2 && v[i - 2] <= v[i - 1] && v[i - 1] >= v[i]; i -= 2, m -= 2)
                v[i - 2] = (v[i - 2] + v[i] - v[i - 1]);
        }

        int t = 0;
        for (int i = p; i < p + n - 1; ++i)
            if (a[i]) t++;

        int d = 0;
        for (int l = 0, r = m - 1, t = 1; l <= r; t = -t)
            d += t * (v[l] > v[r] ? v[l++] : v[r--]);

        int e = a[n - 1 + p];
        int x = (t - d) / 2;
        int y = (t + d) / 2;
        if (x + e > y) res++;
    }

    cout << res;
    return 0;
}

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

• Ta nhân đôi mảng và biến dãy về dãy nhị phân tương ứng vói tính chẵn lẻ của nó để tiện tính toán

• Ta sẽ xét trường hợp đặc biệt khi \(L = R\) và trường hợp thường khi \(L < R\) để suy ra công thức quy hoạch động

• Sau đó, khi có được \(f[L][R]\) là cách chơi tối ưu đoạn \([L; R]\), ta duyệt qua từng \(p\) thỏa \(\{p \in \mathbb{N}, p \in [0, n)\ \}\)

Vì nước đi đầu người chơi đầu chọn \(a_p\) nên sau đó người thứ hai chơi tối ưu \(f[L][R]\) với \([L; R] = [p + 1; p + n - 1]\)

\(\color{#c01515}{\text{2. Approach}}\)

• \(\color{#f03030}{\text{Nhận xét :}}\)

Ta chỉ quan tâm các số lẻ nên sẽ biến cả mảng \(a[]\) thành \((a_i = 1)\) khi \(a_i\) lẻ và \((a_i = 0)\) khi \(a_i\) chẵn. Điều này không ảnh hưởng bài toán nhưng lại có lợi trong việc tính toán

Khi bỏ phần tử \(a_p\), ta có thể duỗi hình tròn thành một hàng đợi hai chiều. Nên để tiện tính toán ta sẽ nhân đôi mảng thành dãy \(A[] = \{a_1, a_2, \dots, a_{n - 1}, a_n, a_1, a_2, \dots, a_{n - 1}, a_n\}\). Tại mỗi vị trí \(p\) mà \(\{p \in \mathbb{N}, p \in [0, n)\ \}\) ta có được đoạn \(A[p + 1\dots p + n)\)

• \(\color{#f03030}{\text{Trường hợp đặc biệt: }}\)

Khi \(L = R\) thì \(f[L][R] = A[L]\)

Vì \(a[i] = a[i + n]\) nên \(f[L][R] = f[L + n][R + n]\) \(\forall L = R\)

• \(\color{#f03030}{\text{Với các trường hợp thường: }}\)

Khi \(L < R\) thì ta có 2 lựa chọn, hoặc là lấy \(a[L]\) và đối thủ chơi tối ưu đoạn còn lại \(f[L + 1][R]\), ,hoặc là lấy \(a[R]\) và đối thủ chơi tối ưu đoạn còn lại \(F[L][R - 1]\)

Vậy ta sẽ chọn giá trị tối đa của 2 cách trên là nước đi tối ưu: \(f[L][R] = max(a[L] - f[L + 1][R], a[R] - f[L][R - 1])\)

• \(\color{#f03030}{\text{Duyệt các N ván chơi}}\)

Có \(D = a_p - f[p + 1][p + n - 1]\) là hiệu số lượng sổ lẻ người đầu - người thứ hai lấy được

Khi \(D > 0\) thì tăng biến đếm (người đầu lấy nhiều số lẻ hơn)

\(\color{#009933}{\text{2. Code tham khảo<Accepted> }}\): Quy hoạch động

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

const int INF = 1e9;
int main()
{
    int n;
    cin >> n;

    vector<int> a(n << 1);
    vector<vector<int> > f(n << 1, vector<int>(n << 1, -INF));
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        a[i]    = a[n + i]        = x & 1;
        f[i][i] = f[n + i][n + i] = x & 1;
    }

    for (int d = 1; d < n; ++d) 
        for (int l = 0, r = d; r < a.size(); ++l, ++r)
            f[l][r] = max(a[l] - f[l + 1][r], a[r] - f[l][r - 1]);

    int res = 0;
    for (int i = 0; i < n; ++i)
    {
        int l = i + 1, r = i + n - 1;
        if (a[i] - f[l][r] > 0) res++;
    }

    cout << res;
    return 0;
}