Dãy hài hòa

Nguồn: CLUE OJ – Map/Set Độ khó: Dễ map đếm tần suất Sắp xếp

Đề bài

Dãy hài hòa là một dãy thỏa mãn điều kiện giá trị lớn nhất và giá trị nhỏ nhất của dãy khác nhau đúng bằng 1.

Cho mảng số nguyên có $N$ phần tử $(1 \le N \le 10^6)$ và giá trị các phần tử trong đoạn $[-10^9, 10^9]$. Kết quả cần in ra độ dài của dãy hài hòa con dài nhất có thể.

Input gồm có 2 dòng, dòng đầu tiên là số $N$. Dòng thứ hai gồm $N$ số nguyên mỗi số cách nhau 1 khoảng trắng.

Output gồm 1 dòng duy nhất là độ dài của dãy hài hòa con dài nhất có thể.

Giới hạn: thời gian 1 giây, bộ nhớ 256 MB.

Subtask:

• 30% điểm đầu tiên có $N \le 10^3$.
• 30% điểm tiếp theo có $N \le 10^4$.
• 30% điểm tiếp theo có $N \le 10^5$.
• 10% điểm cuối cùng có $N \le 10^6$.

Ví dụ 1 – input

8
1 3 2 2 5 2 3 7

Ví dụ 1 – output

5

Ví dụ 2 – input

4
1 2 3 4

Ví dụ 2 – output

2

Giải thích ví dụ 1: dãy hài hòa con dài nhất có 5 phần tử là $\{3, 2, 2, 2, 3\}$.

Giải thích ví dụ 2: có 3 dãy con hài hòa có 2 phần tử: $\{1, 2\}$, $\{2, 3\}$, $\{3, 4\}$.

Lời mở đầu

Đọc kỹ ví dụ 1 các bạn sẽ thấy dãy $\{3, 2, 2, 2, 3\}$ lấy các phần tử ở vị trí 2, 3, 4, 6, 7 – bỏ qua số 5 ở giữa. Vậy "dãy con" ở đây không cần liên tiếp, chỉ cần chọn ra một số phần tử (giữ thứ tự hay không cũng không quan trọng vì ta chỉ quan tâm max và min). Hiểu được điều này thì bài trở nên rất gọn: chỉ cần đếm số lần xuất hiện của mỗi giá trị – đúng sở trường của map.

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, 4 subtaskÝ tưởngCặp x, x + 1Cách 1O(N²)Cách 2mapCách 3Sắp xếpTổng kếtKết quả chạy thật

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

Bộ test có 100 test:

Test	N	Giá trị	Số giá trị khác nhau	Số lần lặp nhiều nhất	Đáp án
1–20	2 – 15	-10 … 11	2 – 12	1 – 3	0 – 5
21–30	1.000	-999.469.154 … 998.281.780	671 – 851	11 – 22	19 – 43
31–60	10.000	-999.866.656 … 999.884.963	7.220 – 7.571	74 – 96	139 – 175
61–90	100.000	-999.999.557 … 999.987.796	59.553 – 60.283	685 – 760	1.357 – 1.458
91–100	1.000.000	-999.998.512 … 999.998.765	409.663 – 411.288	6.825 – 6.990	13.571 – 13.850

• Có 3 test đáp án bằng 0 (test 6, 7, 9): không có 2 giá trị nào hơn kém nhau đúng 1, nên không có dãy hài hoà nào. Code phải in 0 chứ không được in 1 (một phần tử đơn lẻ có max − min = 0, không phải 1).
• Từ test 21, các số trải từ $-10^9$ tới $10^9$ nhưng phần lớn là số có trị tuyệt đối nhỏ (kiểu phân bố "logarit"), nên vẫn có nhiều cặp $x, x + 1$ và nhiều số lặp lại. Cẩn thận: $x + 1$ với $x = 10^9$ vẫn vừa int.

Subtask	Điều kiện	Các test	Cách ăn được
1 (30%)	$N \le 10^3$	1 – 30	Cách 1, 2, 3
2 (30%)	$N \le 10^4$	31 – 60	Cách 1, 2, 3
3 (30%)	$N \le 10^5$	61 – 90	Cách 2, 3
4 (10%)	$N \le 10^6$	91 – 100	Cách 3 (cách 2 sát giới hạn)

Ý tưởngmax − min = 1 nghĩa là chỉ có 2 giá trị x và x + 1

Nếu một dãy có min $= x$ và max $= x + 1$ thì mọi phần tử của nó nằm trong $[x, x + 1]$, mà là số nguyên, nên chỉ có thể bằng $x$ hoặc $x + 1$, và phải có mặt cả hai. Muốn dãy dài nhất thì ta lấy hết các phần tử bằng $x$ và bằng $x + 1$:

Công thức

$$\text{ans} = \max_{x \text{ mà } cnt[x] > 0 \text{ và } cnt[x+1] > 0} \big( cnt[x] + cnt[x + 1] \big)$$ Không có cặp nào thì đáp án là 0.

Ví dụ 1: $cnt[1] = 1$, $cnt[2] = 3$, $cnt[3] = 2$, $cnt[5] = 1$, $cnt[7] = 1$. Các cặp hợp lệ: $(1, 2) \to 4$, $(2, 3) \to 5$. Cặp $(5, 6)$, $(7, 8)$ không có vì thiếu 6, 8. Đáp án là 5. Em nhập dãy rồi bấm Tiếp để xem:

Dãy a:

Ví dụ nhanh:

Cách 1Thử mỗi phần tử làm min, đếm lại cả mảng – O(N²)

Với mỗi $a[i]$, coi $x = a[i]$ là min, ta duyệt lại toàn bộ mảng đếm số phần tử bằng $x$ (c0) và bằng $x + 1$ (c1). Chỉ cập nhật đáp án khi c1 > 0.

C++▶ Chạy tay từng dòng codeCách 1: coi a[i] là min, đếm lại cả mảng số lượng a[i] và a[i] + 1.

Dữ liệu vào (stdin) – sửa thoải mái8 1 3 2 2 5 2 3 7

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Điều kiện c1 > 0 rất quan trọng: nếu thiếu, dãy gồm toàn số $x$ có max − min $= 0$ cũng bị tính, sai ở các test đáp án 0.
• Chỉ cần xét $x$ là min (cặp $x, x + 1$), không cần xét cặp $x - 1, x$ vì cặp đó sẽ được tính khi duyệt tới phần tử bằng $x - 1$.

Không gian$O(N)$

Thời gian$O(N^2)$

Kết quả chạy thật: bản C++ đúng 60/100 test (Subtask 1: 30/30, Subtask 2: 30/30, Subtask 3: 0/30, Subtask 4: 0/10). Với $N = 10^4$ là $10^8$ phép so sánh, chạy tối đa 0.13 giây; từ $N = 10^5$ ($10^{10}$ phép) thì quá thời gian.

Cách 2map đếm tần suất – O(N log N)

Thay vì đếm lại mỗi lần, ta đếm 1 lần cho tất cả bằng map<int, int> cnt. Rồi duyệt từng giá trị $x$ trong map, tìm xem $x + 1$ có trong map không bằng cnt.find(x + 1).

C++▶ Chạy tay từng dòng codeCách 2: map đếm tần suất, với mỗi khoá x tìm x + 1.

Dữ liệu vào (stdin) – sửa thoải mái8 1 3 2 2 5 2 3 7

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Dùng find chứ không dùng cnt[x + 1] để kiểm tra: toán tử [] sẽ tự chèn thêm khoá $x + 1$ với giá trị 0 vào map ngay trong lúc đang duyệt map – vừa sai logic vừa tốn bộ nhớ.
• Vì map đã sắp xếp khoá tăng dần, ta còn có thể so trực tiếp với phần tử kế tiếp (next(it)) thay vì find. Đó chính là ý tưởng của cách 3.

Không gian$O(N)$

Thời gian$O(N \log N)$

Kết quả chạy thật: bản C++ đúng 98/100 test (Subtask 1: 30/30, Subtask 2: 30/30, Subtask 3: 30/30, Subtask 4: 8/10). Subtask 3 chỉ mất tối đa 0.08 giây, nhưng ở subtask 4 ($N = 10^6$, khoảng 410 nghìn giá trị khác nhau) thời gian CPU lên tới 1.07 giây – sát nút giới hạn 1 giây. Phần lớn thời gian là chèn vào cây của map.

Cách 3Sắp xếp rồi gom khối – O(N log N), hằng số nhỏ

Sau khi sắp xếp, các số bằng nhau nằm liền thành từng khối, và các giá trị khác nhau đi theo thứ tự tăng dần. Cặp $x, x + 1$ (nếu có) chắc chắn là 2 khối kề nhau. Vậy chỉ cần duyệt các khối, nhớ giá trị và kích thước của khối liền trước.

C++▶ Chạy tay từng dòng codeCách 3: sắp xếp, gom các khối bằng nhau, so khối với khối liền trước.

Dữ liệu vào (stdin) – sửa thoải mái8 1 3 2 2 5 2 3 7

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Vòng while(j < n && a[j] == a[i]) j++; đẩy $j$ tới hết khối hiện tại, nên khối là a[i..j-1] với kích thước c = j - i. Sau đó i = j nhảy sang khối mới, tổng cộng chỉ $O(N)$.
• prevCnt > 0 để bỏ qua khối đầu tiên (chưa có khối trước).
• sort trên mảng liên tục nhanh hơn nhiều so với chèn $10^6$ lần vào cây đỏ đen của map, nên cách này chạy thoải mái ở subtask 4.

Không gian$O(N)$

Thời gian$O(N \log N)$

Kết quả chạy thật: bản C++ đúng 100/100 test (Subtask 1: 30/30, Subtask 2: 30/30, Subtask 3: 30/30, Subtask 4: 10/10). Test lâu nhất chỉ 0.19 giây, nhanh gấp khoảng 6 lần so với cách 2 ở $N = 10^6$.

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

Mình chấm cả 3 cách (C++ và Python) trên toàn bộ 100 test với giới hạn 1 giây, đo thời gian CPU (máy chấm của mình lúc chạy đang khá tải, nên số liệu có thể chậm hơn máy chấm thật):

Lời giải	Subtask 1 test 1–30	Subtask 2 test 31–60	Subtask 3 test 61–90	Subtask 4 test 91–100	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	30/30	30/30	0/30	0/10	60/100	0.13s
Cách 1 – Python	30/30	0/30	0/30	0/10	30/100	0.20s
Cách 2 – C++	30/30	30/30	30/30	8/10	98/100	1.00s
Cách 2 – Python	30/30	30/30	30/30	10/10	100/100	0.85s
Cách 3 – C++	30/30	30/30	30/30	10/10	100/100	0.19s
Cách 3 – Python	30/30	30/30	30/30	0/10	90/100	0.15s

Ghi chú của mình: cả 3 cách đều cho đáp án đúng ở mọi test mà chúng chạy kịp (kể cả 3 test đáp án 0). Cách 3 là cách an toàn đạt trọn 100%. Python: cách 1 đúng 30/100, cách 2 đúng 100/100, cách 3 đúng 90/100 test; bản Python cách 2 dùng Counter (bảng băm), nhanh hơn hẳn bản Python cách 3 vì không phải sắp xếp và không có vòng while chạy từng phần tử.

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 😇