Một lớp học \(E\) chỉ thắng khi số lượng học sinh của lớp \(E\) chiếm hơn nửa số người tham gia.

Chứng minh trường hợp xấu nhất

Trong trường hợp xấu nhất, mọi lớp khác đều cùng hội đồng lớp \(E\), gọi lớp \(S\) là toàn bộ học sinh của các lớp \(E\) hợp lại.

Thế thì quá trình chơi sẽ chỉ có các trường hợp xảy ra như sau:

• Tới lượt của một bạn lớp \(S\) và bạn kế tiếp là lớp khác \(E\), thì sẽ bỏ lượt cho bạn tiếp theo cũng thuộc lớp \(S\)
• Tới lượt của một bạn lớp \(S\) và bạn kế tiếp là lớp \(E\), bạn đó sẽ loại một học sinh lớp \(E\) và lượt tiếp theo là của học sinh lớp \(E\)
• Tới lượt của một bạn lớp \(E\) và bạn kế tiếp là lớp khác \(S\), thì sẽ bỏ lượt cho bạn tiếp theo cũng thuộc lớp \(S\)
• Tới lượt của một bạn lớp \(E\) và bạn kế tiếp là lớp \(E\), bạn đó sẽ loại một học sinh lớp \(E\) và lượt tiếp theo là của học sinh lớp \(E\)
• Chỉ còn lại học sinh của lớp \(E\)

Và trong trường hợp xấu nhất này thì \(S\) cũng là người bắt đầu, và cứ mỗi \(2\) lượt thì \(S\) và \(E\) loại nhau \(1\) thành viên.

Mà ta có \(|E| > n - |E| = |S|\), nên sau \(2 \cdot |S|\) lượt thì \(|E| > |S| = 0\), hay lớp \(E\) là lớp duy nhất còn sót lại.

Một cách hiểu trực quan hơn là bài toán đưa một mảng \(n\) phần tử tối đa \(n\) phần tử khác nhau về thành dãy nhị phân, mỗi lần số \(0\) xoá số \(1\) thì số \(1\) xoá số \(0\) và ngược lại, nên kêt

Lưu ý

Đúng là có thể mỗi lớp có những chiến thuật khác nhau, tuy nhiên nếu nội bộ \(S\) không cùng thống nhất nhau mà lại có \(2\) lớp \(A, B \in S\) mà loại bỏ học sinh của nhau thì \(|S|\) sẽ giảm nhanh hơn nhiều nên \(E\) thắng nhanh hơn

Vì \(E\) đang chơi tối ưu nhất nên không dại gì phải bỏ lượt khi loại được một đối thủ bất kì, vì suy cho cùng dù có chọn loại học sinh của lớp nào trước thì lớp \(E\) vẫn bị các lớp còn lại hội đồng tấn công.

Trường hợp tốt nhất xảy ra khi mọi thành viên lớp \(S\) đều loại bỏ lẫn nhau và bỏ lượt khi gặp học sinh lớp \(E\).

Chứng minh trường hợp đặc biệt

• Trường hợp 1: Khi mọi người tham gia đều là lớp \(E\) thì họ nghiễm nhiên đã chiến thắng theo định nghĩa

• Trường hợp 2: Khi có lớp phá game bằng cách bỏ hết lượt chơi

Mặc dù bạn nghĩ nó là một lối chơi thú vị, khi mà ảnh hưởng tới lối chơi tối ưu của những team top đầu, bằng cách loại đi các team yếu không có khả năng chiến thắng.

Tuy nhiên, lớp \(E\) vẫn sẽ không bị ảnh hưởng bởi vì chiến thuật lớp \(E\) luôn loại đối thủ của mình bất chấp đối thủ có sử dụng chiến thuật nào đi nữa (lớp \(E\) không cần bỏ lượt vẫn tối ưu).

• Trường hợp 3: Không có lớp nào chiếm số áp đảo, thì không tồn tại một lớp luôn dành chiến thắng

Khi điều này xảy ra thì các lớp luôn có trường hợp thua hoặc có trường hợp lặp vô hạn do nếu loại bỏ đối thủ thì mình sẽ không tốt hơn top \(2\) được, ví dụ \(\{1, 2, 3\}\), nếu bạn loại \(1\) người thì người còn lại sẽ loại bạn để đạt top \(1\)

Và vì các lớp đều chơi tối ưu vì "Mọi người đều có tinh thần tham gia để đem về chiến thắng cho cả đội." nên không thể có trường hợp toàn bộ các lớp chung tay skip để cho một lớp duy nhất dành chiến thắng được.

Vậy nên với mỗi phần tử \(a_i\) trong đoạn \(a[l \ldots r]\) đang xét, ta cần phải tính hàm \(f(a_i) =\) số lần xuất hiện của \(a_i\) trong đoạn đó.

Nếu tồn tại \(a_i\) để \(f(a_i) > \left \lfloor \frac{r-l+1}{2} \right \rfloor\) là số thí sinh trong đoạn, thì lớp \(E = a_i\) chính là lớp duy nhất luôn dành chiến thắng, ngược lại không tồn tại lớp nào mà thắng trọn vẹn được cả, như đã chứng minh ở trên.

Có nhiều cách tính \(f(a_i)\) như sau:

• Tạo mảng \(b[l \ldots r] = a[l \ldots r]\) rồi sắp xếp \(b[]\) trong \(O(|b| \log |b|)\), lúc này các phần tử bằng nhau sẽ kề nhau nên cần tìm đoạn dài nhất có các phần tử bằng nhau. Ví dụ trong C++ có hàm std::sort

• Dùng các cấu trúc dữ liệu hỗ trợ việc sắp xếp hay duyệt các số theo thứ tự trong \(O(|b| \log |b|)\). Ví dụ trong C++ có std::priority_queue, std::set, std::map

• Dùng các cấu trúc dữ liệu kiểu mảng băm để đếm số phần tử trùng nhau std::hash, std::unordered_set, std::unordered_map

• Nén mảng \(a[1 \ldots n]\) (với từng số \(a_i\) lớn thứ \(p\) trong mảng sẽ gán lại thành \(p\)), và lưu vị trí xuất hiện của từng số \(a[i]\), khi truy vấn chỉ cần chặt nhị phân để đếm số phần tử trên đoạn \([l, r]\)

Gọi số chiếm hơn nửa lần xuất hiện của tập là số áp đảo, ta có các nhận xét như sau

• Nếu số \(x\) là số áp đảo thì mọi bit của \(x\) cũng áp đảo tại đó.
• Nếu tồn tại một số là số áp đảo, thì xác xuất để một số bất kì là áp đảo là hơn \(50\) %
• Tồn tại cấu trúc dữ liệu để nếu tồn tại phần tử áp đảo, thì luôn tìm được giá trị đó.
• Tồn tại cấu trúc dữ liệu để kiểm tra xem nửa trái, hoặc nửa phải, có phần tử áp đảo, hay cả hai đều không có.

Vậy bài toán này mình có nhiều các khai thác để giải bài

Ta có một nhận xét là, nếu một số xuất hiện hơn nửa số lần, và tồn tại số \(b = b_0\) để nó không áp đảo với bit thứ \(b_0\) của các số trong tập, thì số đó không phải là số áp đảo.

Vậy ta biến bài toán thành các bài toán độc lập nhau, mỗi bài toán xét trên số bit thứ \(b = 0 \rightarrow 60\) và tìm xem số áp đảo tại \(b\) là \(x_b = 0\) hay \(x_b = 1\). Khi này kết quả bài toán là \(\Sigma x_b \times 2^b\)

Giờ thì bài toán lại trở về các số \(0\) và \(1\), thế để kiểm tra xem số áp đảo là màu nào, thì ta có thể sử dụng quy hoạch động (không cập nhật) hoặc Fenwick Tree (có thể cập nhật) trong \(O(n \log n)\) cho đơn giản, ngắn và hằng số thấp.

Sau đó khi tính kết quả thực tế của bài toán, ta phải kiểm tra lại xem nếu nó xuất hiện quả nửa số phần tử trong mảng chưa, nếu đúng là thế thì nó là số áp đảo.

Để kiểm tra số lần xuất hiện của một số trên đoạn, ta có thể lưu các vị trí xuất hiện của số đó trong mảng và sử dụng chặt nhị phân để tìm chặn trên chặn dưới.

Cách này sẽ có độ phức tạp là \(O(n \log n \times \log_2 a)\) với \(a\) là giới hạn của các giá trị trong mảng và \(n\) là số phần tử trong mảng.

Ví dụ

• Số \(1\) là số áp đảo trong tập \(\{1\}\) vì nó là phần tử duy nhất
• Số \(2\) không phải là số áp đảo trong tập \(\{1, 2\}\) vì xét bit tại \(b = 0\) (cơ số \(2^0 = 1\)) ta có cả hai bit đều không phải là bit áp đảo trong dãy \(\{1, 0\}\)
• Số \(3\) không phải là số áp đảo trong tập \(\{1, 2, 3, 3\}\) vì nó xuất hiện không quá nửa lần.
• Số \(5\) không phải là số áp đảo trong tập \(\{1, 2, 3, 3, 5, 5, 5\}\) vì xét bit tại \(b = 2\) (cơ số \(2^2 = 4\)) ta có cả hai bit đều không phải là bit áp đảo trong dãy \(\{0, 0, 0, 0, 1, 1, 1\}\)
• Số \(8\) không phải là số áp đảo trong tập \(\{1, 2, 3, 3, 5, 5, 5, 8, 8, 8, 8, 8\}\) vì xét bit tại \(b = 0\) (cơ số \(2^0 = 1\)) ta có cả hai bit đều không phải là bit áp đảo trong dãy \(\{1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0\}\)
• Số \(7\) là số áp đảo trong tập \(\{1, 3, 3, 5, 5, 5, 7, 7, 7, 7, 7, 7, 7\}\) vì số \(7_{10} = 111_{2}\) áp đảo trên từng hệ nhị phân của nó, và nó xuất hiện hơn nửa số lần.

Ta có nhận xét là nếu một số là số áp đảo, thì nó phải xuất hiện hơn một nửa số lần, nên nếu ta bốc ngẫu nhiên một số bất kì thì phải có hơn \(50\)% xác xuất là bốc trúng số cần tìm.

Ví dụ

• Số \(1\) là số áp đảo, và duy nhất xuất hiện trong tập \({1, 1}\) nên xác xuất xuất hiện là \(100\)% > \(50\)%
• Số \(27\) là số áp đảo, và xuất hiện \(5\) lần trong tập \(\{2, 7, 27, 27, 27, 27, 27, 69, 420\}\) nên xác xuất xuất hiện là \(\frac{5}{9} = 0.555555556 > 50\)%
• Số \(2\) không phải là số áp đảo vì nó không hề xuất hiện trong tập \({1, 3, 5, 7, 9}\) nên xác xuất xuất hiện là \(0\)% < \(50\)%
• Số \(7\) không phải là số áp đảo vì nó xuất hiện không quả nửa số lần trong tập \(\{2, 7\}\), xác xuất xuất hiện là \(50\)% nhưng chưa hơn nửa.

Vậy với mỗi \(i = 1 \rightarrow n\) ưu vị trí xuất hiện của \(a_i\), ta bốc thử \(k\) lần số \(a_i\) ngẫu nhiên trên \(a[l \ldots r]\) và đếm số lần xuất hiện của \(a_i\).

Gọi tập \(S_x = \{p_1, p_2, \ldots, p_q\}\) là tập các vị trị mà ở đó \(a[p_i] = x\), thế thì để đếm số \(a_i\) trong đoạn \(a[l, r]\) ta chỉ cần đếm số \(p_i\) trong đoạn \([l, r]\)

Ta có thể đếm bằng chặt nhị phân đơn giản

Nếu với mọi \(a_i\) ta có tập \(S_x\) được sắp xếp tăng dần, thì nó tồn tại hàm đơn điệu $f(n) = $ số phần tử \(p_i \leq n\) như sau

Ví dụ với mảng \(S_x = \{1, 2, 3, 5, 8\}\) ta có:

Vậy ta chỉ cần chặt nhị phân là tìm được đoạn \(l \leq p_{x} < p_{x+1} < \ldots < p_{y} \leq r\) thì số phần tử giá trị đó xuất hiện là \(y - x + 1\), ngược lại là \(0\).

Lưu ý cẩn thận vị trí \(p_i < 0, p_i = x, p_i = y, p_i > y\) và cẩn thận với cách bạn code là mảng bắt đầu từ \(0\) hay từ \(1\)

Trong C++ có hàm lower_bound() sẽ giúp bạn tìm được \(x\) và hàm upper_bound() giúp bạn tìm được \(y + 1\) đơn giản như sau

int countOccurence(const vector<long long> &S, int l, int r) { /// S = Tập p[i] độ dài q
    return (l > r) ? 0 : (upper_bound(S.begin(), S.end(), r) - lower_bound(S.begin(), S.end(), l));
}

Cách này sẽ có độ phức tạp là \(O(k \times \log n)\) với \(k\) chính là số lần chọn ngẫu nhiên \(a_i\), nếu xác xuất mỗi số bạn bốc trúng là đều nhau thì xác xuất để thuật đưa ra kết quả sai mỗi lần chọn \(a_i\) là \(\epsilon = \frac{1}{2^k}\)

Ghi chú

Nén mảng \(a[1 \ldots n]\) về thành mảng \(a'[1 \ldots n]\) sao cho \(a[i]\) chính là số lớn thứ \(a'[i]\) trong \(a[1 \ldots n]\). Bằng cách này thì độ phức tạp nhanh hơn nhưng có thể không đáng kể.

Ngoài ra cũng có thể tối ưu độ phức tạp lên \(O(k \times \log \sqrt{n})\) nhưng không đáng kể, vì hằng số bù lại vào cũng như nhau.

Mình dùng Segment Tree cơ bản, mỗi nút sẽ coi như đại diện cho một đội tốt nhất hiện tại, chỉ chứa hai thông tin là <mã màu áo> và <số thành viên>

Ý tưởng của mình là, nếu \(2\) bạn có cùng màu áo thì hợp \(2\) team với nhau, ngược lại thì từng cặp thành viên của hai nhóm sẽ bị loại dần tới khi chỉ còn một bên.

struct Node<int color, int count>

Node operator + (const Node &A, const Node &B) {
    if (A.color == B.color) return Node(color, A.cnt + B.cnt);
    if (A.cnt > B.cnt) return Node(A.color, A.cnt - B.cnt);
    if (A.cnt < B.cnt) return Node(B.color, B.cnt - A.cnt);
    return Node(any color, cnt = 0);
}

Nếu bạn duyệt từng team một từ \(a[L], a[L + 1], \ldots\) duyệt sang dần tới \(\ldots, a[R - 1], a[R]\) thì có \(2\) trường hợp có thể xảy ra

• \(a_i = color\) là số áp đảo
• Không có số áp đảo trên đoạn này

Chứng minh trực tiếp

Trên đoạn thì có nhiều màu áo khác nhau, người thứ \(i\) có màu áo \(a_i\)

Hãy giả sử là giờ chúng ta solo theo kiểu một đấu một với nhau.

Thế thì rõ ràng là khi hai nhóm cùng màu áo thì hợp lại với nhau để trở nên mạnh mẽ hơn

if (A.color == B.color) return Node(color, A.cnt + B.cnt);

Ngược lại nếu khác màu áo thì team nào đông thì thắng

if (A.cnt > B.cnt) return Node(A.color, A.cnt - B.cnt);
if (A.cnt < B.cnt) return Node(B.color, B.cnt - A.cnt);
return Node(any color, cnt = 0);

Nhưng như đã nhắc tới ở subtask \(1\), nếu màu áo \(E\) nào đó mà áp đảo, thì cho dù trong trường hợp xấu nhất là bị chơi hội đồng, và các lớp liên minh với nhau thành màu áo \(S\) nào đó, thì ta vẫn có \(|E| > n - |E| = |S|\)

Nên sau mỗi lần đấu đá nhau do khác màu áo, thì \(E\) mất \(x\) người cũng làm \(S\) mất \(x\) người. Nên sau khi toàn bộ các nhóm đấu nhau, thì \(S\) sẽ bị bay màu trước, bởi vì tại \(x = |S|\), có \(|E| - x > |S| = 0\)

Tuy nhiên, nếu không có màu áo áp đảo, thì kết quả trả về sẽ là một \(a_i\) ngẫu nhiên nào đó trên đoạn \(a[l \ldots r]\) hoặc là có giá trị <count> $ = 0$, nên vẫn cần phải kiểm tra lại bằng cách chặt nhị phân số vị trí của \(a_i\) trong đoạn \([l, r]\)

Tuy nhiên, bài toán ta đang xét có phẩn tổng quát hơn, đó là chúng ta sẽ sử dụng cấu trúc dữ liệu cây để giải bài nhanh hơn.

Chứng minh trên vẫn đúng, xong phải cẩn thận kẻo suy xét những vấn đề không cần thiết làm trực giác ta cảm giác nó không đúng lắm.

Ví dụ: Sau một quá trình đấu đá nhau trên cây nhị phân, còn lại \(2\) đỉnh là \(\text{<color }= E\text{, count }= X\text{>}\) với \(\text{<color }= S\text{, count }= Y\text{>}\) làm sao để chứng minh là khi biết \(E\) là phần tử áp đảo thì chắc chắn hệ quả \(X > Y\) phải thoả.

Chứng minh trên cây

Trong trường hợp xấu nhất mà ta xét, thì các lớp luôn liên minh với nhau để hội đồng nhóm áp đảo.

Nhưng trên cái cây của mình, mình không thể biết được ai là áp đảo cho tới khi đấu với nhau, nên sẽ có những lúc đấu đá nội bộ.

Thế nên cái cây chỉ là một trong các cách ghép cặp các team đấu đá với nhau, nên dù đảo đi đảo lại hay thế nào đi nữa, thì trong trường hợp xấu nhất (ví dụ xen kẽ \(E S E S E \ldots E S E\)) thì \(E\) sẽ luôn tồn tại cuối cùng nếu nó thực sự áp đảo.

Và tất nhiên nếu có giá trị khác may mắn chui qua được, thì vẫn phải qua bước kiểm tra số phần tử của nó ở trên đoạn \([l, r]\) nên nó vẫn đúng.

Còn về tại sao \(X > Y\) luôn đúng khi \(E\) áp đảo thì, trong trường hợp xấu nhất (tức là thay đổi cây tính toán một cách tuỳ ý sao cho \(E\) bị thiệt hại nhiều nhất), ta vẫn có \(X \geq X_{min} > Y_{max} \geq Y\).

Chứng minh phản chứng

Gọi \(K[x] = y\) nghĩa là \(x\) bị loại bởi \(y\) trong quá trình hợp cây lên.

Ban đầu thì có thể khởi tạo \(K[x] = x\) hoặc số nào đó khác đoạn \([L \ldots R]\)

struct Emilia {
    int color;
    vector<int> member;
};

thế thì cái hàm hợp \(2\) nút của chúng ta sẽ được viết lại thành như sau

Emilia Merge(Emilia L, Emilia R) {
    if (L.color == R.color) {
        R.emplace_back(L.cbegin() , L.cend());
        return L;
    }
    if (L.member.size() == R.member.size()) {
        return trash_value;
    }
    if (L.member.size() < R.member.size()) {
        swap(L, R);
    }
    for (; R.size(); L.pop_back(), R.pop_back()) {
        K[L.back()] = R.back();
        K[R.back()] = L.back();
    }
    return L;
}

Giả sử \(Emilia\) là tập áp đảo, có mã màu là \(E\), và \(e_i\) là các thành viên của lớp \(E\) trên đoạn đang xét.

Thế thì ta phản chứng bằng cách giả sử \(K[e_i] \neq E\ \forall\ e_i \in {Emilia}\), nghĩa là hàm phải trả về giá trị khác \(E\) \(\dagger\)

Mà vì ta đấu đá lẫn nhau kiểu qua lại nên \(K_A = B \Leftrightarrow K_B = A\), tức là không thể tồn tại \(K_X = Y \rightarrow K_Y \neq X\) \(\ddagger\)

Gọi \(K_{ed}\) là tập các bạn \(e_i\) đã bị loại và \(K_{er}\) là tập các bạn đã loại \(e_i\).

Vì \(\dagger\) và \(\ddagger\) nên \(K_{ed} \cap K_{er} = \emptyset\)

Mà ta cũng có \(K[K_A] = A\) nên \(|K_{ed}| = |K_{er}|\)

Mà vì như ta đã giả sử từ \(\dagger\) là mọi \(e_i\) đều sẽ bị loại, nghĩa là \(|K_{ed}| = |E|\)

Vậy thì ta có \(|K_{ed} \cup K_{er}| = |K_{ed}| + |K_{er}| - |K_{ed} \cap K_{er}| = |E| + |E| - |\emptyset| = 2 \cdot |E|\)

Mà ban đầu ta đã định nghĩa \(E\) là phần tử áp đảo nên \(|E| > (r - l + 1) - |E| \Leftrightarrow 2 \cdot |E| > (r - l + 1)\) (mâu thuẫn)

Suy ra điều phải chứng minh.

Giống như cách trên, nhưng thay vì kiểm tra lại số lần xuất hiện của một phần tử mà sống sót cuối cùng (để xem nó áp đảo thật sự hay không), thì mình có thể sử dụng Persistent Segment Tree để lưu lại lịch sử của cây để đếm số lần xuất hiện trên đoạn.

Ta có thể tạo một cây gồm các dữ liệu như sau

long long top; // tổng số phần tử trên cây
long long lhs[LIM << 5]; // lhs[id] = nhánh trái của nút
long long rhs[LIM << 5]; // rhs[id] = nhánh phải của nút
long long ver[LIM << 5]; // ver[id] = phiên bản hiện tại của nút
long long sum[LIM << 5]; // sum[ver[r]] - sum[ver[l-1]] = đếm số lần xuất hiện trên đoạn phiên bản [l, r] (sau lần update cuối là l-1)

Thế thì tại mỗi bước, mình kiểm tra xem nhánh trái, hay nhánh phải, có tồn tại một phần tử mà số lần xuất hiện của nó là hơn \(k = \left \lfloor \frac{r - l + 1}{2} \right \rfloor\) hay không, nếu có thì đi vô nhánh đó.

Nhưng cững có thể là cả \(2\) nhánh đều không có phần tử áp đảo, lúc đó mình sẽ dừng đi sâu hơn vào cây và trả về kết quả là một giá trị đặc biệt.

int query(int lt, int rt, int l, int r, int k)
{
    if (l == r) return l; /// Đã tìm được phần tử đó
    int m = (l + r) >> 1; /// Cây nhị phân thì chặt giữa thôi :3
    if (k < sum[lhs[rt]] - sum[lhs[lt]]) return query(lhs[lt], lhs[rt], l, m+0, k); /// Kiểm tra nếu nhánh trái có phần tử áp đảo trong đoạn đệ quy tiếp theo [l \ldots r] = [lhs[l] \ldots lhs[r]]
    if (k < sum[rhs[rt]] - sum[rhs[lt]]) return query(rhs[lt], rhs[rt], m+1, r, k); /// Kiểm tra nếu nhánh phải có phần tử áp đảo trong đoạn đệ quy tiếp theo [l \ldots r] = [rhs[l] \ldots rhs[r]]
    return 0; /// Không có phần tử áp đảo, trả về giá trị đặc biệt, giả sử mọi a[i] > 0
}

Mình chỉ tạo đỉnh mới khi cập nhật điểm

void update(long long pre, long long &cur, int l, int r, int p)
{
    /// Tạo đỉnh mới
    cur = ++top;
    lhs[cur] = lhs[pre];
    rhs[cur] = rhs[pre];
    sum[cur] = sum[pre] + 1;
    if (l == r) {
        return;
    }

    int m = (l + r) >> 1; 
    if (p <= m) {
        update(lhs[pre], lhs[cur], l, m+0, p); /// Nhánh trái
    } else {
        update(rhs[pre], rhs[cur], m+1, r, p); /// Nhánh phải
    }
}

Còn để xử lí dữ liệu thì có nhiều cách, bao gồm cả cách nén giá trị lại, \(b_p\) là số lớn thứ \(p\) trong \(a[1 \ldots n]\)

cin >> n >> q;
for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    b[i] = ++a[i]; /// Shift to 1-based
}

sort(b + 1, b + n + 1);
int m = unique(b + 1, b + n + 1) - (b + 1);
for (int i = 1; i <= n; ++i) {
    a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
    update(ver[i-1], ver[i], 1, m, a[i]);
}

Để giải subtask \(3\), thì ngoài cách sử dụng Persistent Lazy Segment Tree, bạn có thể dùng thuật toán chia căn để giải quyết, còn cập nhật và tính toán kết quả của một khối to có thể sử dụng một trong \(4\) ý tưởng của subtask \(2\) là được.