Tutorial — Sign Inversion

Hãy xem xét sự thay đổi của tổng tất cả các phần tử trong mảng sau mỗi thao tác biến đổi. Mỗi lần đảo dấu của hai phần tử liên tiếp, tổng của mảng sẽ thay đổi một lượng như thế nào?

Mỗi thao tác chỉ làm tổng mảng thay đổi một lượng bằng $0$, $+4$ hoặc $-4$. Do đó, giá trị tổng $S$ khi chia cho $4$ lấy dư $S \bmod 4$ là một đại lượng bất biến qua mọi bước biến đổi.

Tổng mục tiêu bằng $0$ là một số chia hết cho $4$, vì vậy điều kiện cần và đủ để giải bài toán là tổng ban đầu $S$ phải thỏa mãn $S \bmod 4 = 0$. Bạn chỉ cần tính tổng $S$ của mảng ban đầu và kiểm tra điều kiện này trong thời gian $O(n)$ cho mỗi test case.