Tích số

Nguồn: CLUE OJ – Chương 14: Cửa sổ trượt + Tham lam Độ khó: Dễ Tham lam Chẵn lẻ

Đề bài

Bạn được cho một dãy số gồm $n$ số nguyên $a_1, a_2, \ldots, a_n$. Một thao tác được ghi nhận khi bạn tăng hoặc giảm giá trị của bất kỳ số $a_i$ nào trong dãy lên 1 đơn vị (tức là $a_i = a_i + 1$ hoặc $a_i = a_i - 1$), và bạn có thể lặp đi lặp lại thao tác này vô số lần. Thầy giáo muốn bạn thực hiện các thao tác tăng giảm giá trị đó để thu được một dãy số mới sao cho tích của các phần tử trong dãy số mới bằng 1.

Ví dụ với $n = 3$ và dãy $[1, -3, 0]$, ta có thể tăng 2 lần số $-3$ (tức $a_2$) để trở thành $-1$ và giảm 1 lần số $0$ (tức $a_3$) để trở thành $-1$. Lúc này ta thu được dãy mới $[1, -1, -1]$ có tích bằng 1. Như vậy bạn mất tổng cộng 3 thao tác. Có nhiều cách khác nhau để dãy mới có tích bằng 1, tuy nhiên không tồn tại cách nào ít hơn ba thao tác.

Yêu cầu: cho dãy $a$ gồm $n$ số nguyên, hãy tìm chi phí (số thao tác) ít nhất để biến đổi dãy $a$ thành dãy mới có tích các phần tử bằng 1.

Dữ liệu:

• Dòng đầu là số nguyên dương $n$.
• Dòng thứ 2 gồm $n$ số nguyên $a_i$ $(-10^9 \le a_i \le 10^9)$, mỗi số cách nhau bởi một dấu cách.

Kết quả: chi phí ít nhất để biến đổi dãy số đã cho thành dãy có tích các phần tử bằng 1.

Giải thích ví dụ:

• Ví dụ 1: đổi $-1$ thành $1$ hoặc đổi $1$ thành $-1$, chi phí 2 thao tác.
• Ví dụ 2: đổi $-5$ thành $-1$ (4 thao tác), $-3$ thành $-1$ (2 thao tác), $5$ thành $1$ (4 thao tác), $3$ thành $1$ (2 thao tác) và $0$ thành $1$ (1 thao tác). Tổng là 13 thao tác.

Ràng buộc: 20% test đầu có $n \le 20$; 30% test tiếp theo có $n \le 10^4$; 30% test tiếp theo có $n \le 10^5$; 20% test cuối có $n \le 10^6$.

Ví dụ 1 – input

2
-1 1

Ví dụ 1 – output

2

Ví dụ 2 – input

5
-5 -3 5 3 0

Ví dụ 2 – output

13

Lời mở đầu

Bài này nhìn thì có vẻ phải thử rất nhiều cách biến đổi, nhưng chỉ cần một nhận xét nhỏ về tích bằng 1 là mọi thứ trở nên đơn giản: mỗi số chỉ có 2 lựa chọn, và ta chọn tham lam lựa chọn gần nhất, cuối cùng sửa lại một chút về chẵn lẻ. Mình sẽ đi từ cách vét cạn (ăn 20% điểm) tới cách tham lam $O(n)$ full điểm.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởng±1 + chẵn lẻCách 1vét cạn 2ⁿCách 2tham lam O(n)

Bộ testBộ test chính thức có gì?

Bộ test có 100 test, chia đúng theo 4 mức ràng buộc của đề:

Test	n	$a_i$ nhỏ nhất	$a_i$ lớn nhất	Số test có lẻ số âm	Số test có số 0	Đáp án
1–20	2 … 20	-30	30	11/20	4/20	2 … 302
21–50	10.000	-999.984.034	999.970.018	20/30	0/30	641.320.646.159 … 718.381.215.198
51–80	100.000	-999.997.475	999.998.561	18/30	0/30	6.670.250.465.734 … 6.893.214.159.194
81–100	1.000.000	-999.998.937	999.999.144	10/20	0/20	67.547.516.106.515 … 68.273.299.616.001

Vài điều đáng chú ý:

• Test 1, 2 chính là 2 ví dụ của đề; test 1–20 có $n$ lần lượt từ 2 tới 20 và $|a_i| \le 30$.
• Chỉ có 4 test (2, 11, 19, 20) chứa số 0; các test lớn không có số 0 nào. Có 57 test có số lượng số âm lẻ và không có số 0 – đó là những test bắt buộc phải cộng thêm 2 ở bước sửa chẵn lẻ. Quên bước này là sai khoảng một nửa bộ test.

Đối chiếu ràng buộc của đề với test thật và số test đúng của từng cách:

Subtask	Đề ghi	Test thật	Cách 1 vét cạn $2^n$	Cách 2 tham lam
20%	$n \le 20$	1–20	20/20	20/20
30%	$n \le 10^4$	21–50	0/30	30/30
30%	$n \le 10^5$	51–80	0/30	30/30
20%	$n \le 10^6$	81–100	0/20	20/20

Nhớ dùng long long

Mỗi số có thể tốn tới gần $10^9$ thao tác, $n = 10^6$ số thì tổng chi phí cỡ $10^{15}$ – đáp án lớn nhất trong bộ test là 68.273.299.616.001. Biến tổng chi phí bắt buộc phải là long long.

Ý tưởngMỗi số về 1 hoặc −1, rồi sửa chẵn lẻ

Nhận xét 1. Tích của các số nguyên bằng 1 thì mỗi số phải là $1$ hoặc $-1$ (nếu có số nào có trị tuyệt đối $\ge 2$ thì tích có trị tuyệt đối $\ge 2$; có số 0 thì tích bằng 0). Hơn nữa số lượng số $-1$ phải là số chẵn.

Nhận xét 2. Đưa $a_i$ về giá trị $t$ tốn đúng $|a_i - t|$ thao tác. Nếu không lo chuyện chẵn lẻ, mỗi số cứ về giá trị gần nó nhất:

• $a_i > 0$: về $1$, tốn $a_i - 1$.
• $a_i < 0$: về $-1$, tốn $-1 - a_i$.
• $a_i = 0$: về $1$ hay $-1$ đều tốn $1$ – số 0 là "con bài linh hoạt".

Nhận xét 3 (sửa chẵn lẻ). Nếu số lượng số âm là lẻ thì sau bước trên ta có lẻ số $-1$ → tích bằng $-1$. Khi đó:

• Nếu có ít nhất một số 0: cho số 0 đó về phía ngược lại (tốn vẫn là 1) → không mất thêm gì.
• Nếu không có số 0: phải đổi "phe" một số. Với số dương $a$ đổi từ đích $1$ sang $-1$ tốn thêm $|a + 1| - |a - 1| = 2$; với số âm cũng y hệt, thêm 2. Vậy cộng thêm 2.

Thuật toán tham lam

Đáp án $= \sum$ (khoảng cách từ $a_i$ tới $1$ hoặc $-1$ gần nhất) $+\ 2$ nếu (số lượng số âm lẻ và không có số 0).

Em nhập dãy số rồi bấm Tiếp để xem từng số được đưa về đâu và lúc cuối có phải "trả thêm" 2 thao tác không:

Dãy a:

Ví dụ nhanh:

Cách 1Vét cạn dấu – 20% điểm

Theo nhận xét 1, mỗi số chỉ có 2 đích là $1$ hoặc $-1$. Với $n \le 20$ ta thử hết $2^n$ cách gán dấu bằng một số nhị phân mask: bit thứ $i$ bằng 1 nghĩa là $a_i$ về $-1$. Chỉ xét các mask có số bit 1 chẵn (số lượng $-1$ chẵn), tính tổng $|a_i - t_i|$ và lấy nhỏ nhất.

C++▶ Chạy tay từng dòng codeCách 1: thử mọi cách gán dấu bằng mask, chỉ nhận mask có chẵn bit 1.

Dữ liệu vào (stdin) – sửa thoải mái2 -1 1

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. __builtin_popcount(mask) đếm số bit 1 của mask, tức số lượng phần tử về $-1$. Lẻ thì bỏ qua.
2. (mask >> i & 1) lấy bit thứ $i$ của mask.
3. Cách này không cần nghĩ gì về tham lam, rất hợp để kiểm tra lại cách 2 trên các test nhỏ.

Không gian$O(n)$

Thời gian$O(2^n \cdot n)$

Kết quả chạy thật: bản C++ đúng 20/100 test (sai/quá thời gian ở test 21–100), test đúng chạy lâu nhất 0.02s. Bản Python: bản Python đúng 19/100 test (sai/quá thời gian ở test 20–100), test đúng chạy lâu nhất 0.77s. Đúng trọn subtask 1 (test 1–20); từ test 21 với $n = 10^4$ thì $2^n$ là con số khổng lồ nên không thể chạy được (thậm chí 1 << n với $n \ge 31$ còn bị tràn số, chương trình in ra kết quả sai hoặc chạy quá giờ).

Cách 2Tham lam O(n) – Full điểm

Làm đúng như phần ý tưởng: đọc tới đâu xử lý tới đó, cộng chi phí đưa về $\pm 1$ gần nhất, đếm số âm và số 0, cuối cùng sửa chẵn lẻ.

C++▶ Chạy tay từng dòng codeCách 2: đưa mỗi số về ±1 gần nhất, cuối cùng sửa chẵn lẻ.

Dữ liệu vào (stdin) – sửa thoải mái5 -5 -3 5 3 0

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Số 0 được cộng 1 thao tác và đếm vào zero; ta chưa cần quyết định nó về $1$ hay $-1$.
2. Dòng if (neg % 2 == 1 && zero == 0) cost += 2; là chỗ hay quên nhất: ví dụ 1 của đề $[-1, 1]$ có tổng khoảng cách bằng 0 nhưng đáp án là 2 chính là nhờ dòng này.
3. Không cần lưu mảng: bộ nhớ $O(1)$.

Không gian$O(1)$

Thời gian$O(n)$

Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.11s. Bản Python: bản Python đúng 100/100 test, test đúng chạy lâu nhất 0.41s.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Test đúng lâu nhất	Ghi chú
1. Vét cạn dấu $O(2^n \cdot n)$	C++	20/100	0.02s	Chỉ chạy được $n \le 20$
	Python	19/100	0.77s	Như bản C++ nhưng chậm hơn
2. Tham lam $O(n)$	C++	100/100	0.11s	Full điểm
	Python	100/100	0.41s	Full điểm

Ghi chú của mình: thời gian trong bảng là thời gian CPU đo trên máy của mình (giới hạn 1 giây). Cách tham lam ở đây đúng vì mỗi số được chọn độc lập, ràng buộc duy nhất giữa các số là chẵn lẻ của số lượng $-1$, và cái giá để sửa chẵn lẻ luôn là 0 (có số 0) hoặc đúng 2 (không có số 0).

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇