Editorial for posprod: Tích dương

Hiểu bài toán

Cho một dãy số nguyên $A$ có $N$ phần tử. Ta có thể thực hiện phép biến đổi 'đảo dấu' một phần tử bất kỳ (thay $x$ bằng $-x$) với chi phí 1 lần biến đổi cho mỗi phần tử. Mục tiêu là thực hiện ít phép biến đổi nhất để dãy thu được có tích của mọi cặp phần tử bất kỳ đều dương. Điều này tương đương với việc toàn bộ dãy phải cùng dấu (tất cả dương hoặc tất cả âm) và không được chứa số 0. Ta cần tìm số lần đổi dấu ít nhất để đạt được trạng thái này, hoặc in ra -1 nếu không thể.

Các cách tiếp cận

Cách Quyết định theo đa số

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int cnt_pos = 0, cnt_neg = 0;
    int has_zero = 0;
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        if (x == 0) has_zero = 1;
        else if (x > 0) cnt_pos++;
        else cnt_neg++;
    }

    if (has_zero) {
        printf("-1");
    } else {
        // Nếu muốn toàn bộ dương: cần đổi dấu tất cả số âm (cnt_neg lần)
        // Nếu muốn toàn bộ âm: cần đổi dấu tất cả số dương (cnt_pos lần)
        // Chọn cách ít tốn kém nhất
        if (cnt_pos < cnt_neg) printf("%d", cnt_pos);
        else printf("%d", cnt_neg);
    }
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Đây là cách tiếp cận trực quan nhất. Để mọi cặp số có tích dương, dãy số phải cùng dấu. Do đó, ta có 2 lựa chọn:

1. Biến đổi dãy thành toàn số dương: Số lần đổi dấu bằng số lượng số âm hiện tại ($cnt_{neg}$).
2. Biến đổi dãy thành toàn số âm: Số lần đổi dấu bằng số lượng số dương hiện tại ($cnt_{pos}$). Ta chọn phương án có số lần đổi dấu ít hơn. Nếu dãy chứa số 0, không thể biến đổi để thỏa mãn điều kiện (vì tích với 0 luôn bằng 0), nên trả về -1.

Cách Thống kê và so sánh

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    int pos = 0, neg = 0;
    bool zero = false;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x == 0) zero = true;
        else if (x > 0) pos++;
        else neg++;
    }

    if (zero) {
        cout << -1 << endl;
    } else {
        cout << min(pos, neg) << endl;
    }
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Hàm số này thực hiện logic tương tự như cách tiếp cận trước nhưng sử dụng biến đếm tích hợp sẵn và thư viện chuẩn. Logic cốt lõi là:

• Nếu có số 0: Không thể thực hiện được -> -1.
• Nếu không có số 0: Số lượng thay đổi tối thiểu là số lượng phần tử ít hơn giữa hai nhóm dương và âm. Ví dụ: 3 số dương, 2 số âm thì đổi 2 số âm thành dương là ít nhất (hoặc đổi 3 số dương thành âm, nhưng 2 < 3 nên chọn 2).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Điều kiện 'tích mọi cặp đều dương' ngụ ý dãy phải đồng nhất về dấu (hoặc tất cả dương, hoặc tất cả âm) và không chứa 0.
• Số lần đổi dấu để đưa một dãy về 'toàn dương' chính là số lượng phần tử âm ban đầu. Tương tự cho 'toàn âm'.
• Bài toán quy về bài toán tìm min(cntpos, cntneg) nếu không có số 0.

Lỗi thường gặp

• Bỏ qua trường hợp dãy chứa số 0 (phải trả về -1).
• Sử dụng phép so sánh sai (ví dụ dùng dấu '>' thay vì '>=' có thể không ảnh hưởng kết quả nhưng logic phải rõ ràng: chọn số lượng phần tử ít hơn để đổi dấu).