Editorial for SGAME6

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

<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>

$\color{#ff7500}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}$ $\color{#ff7500}{\text{Và sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu với thuật của mình và thu được bài học cho mình}}$ $\color{#ff7500}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}$ [ở đây](https://www.facebook.com/SPectiar2k/)

<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}}}}$

C++

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}}}}$

C++

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;
}

Comments

There are no comments at the moment.

Editorial for SGAME6

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

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

\(\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}}}}\)

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

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

\(\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}}}}\)

Comments