Hồi năm ngoái, bạn tôi đi phỏng vấn cho vị trí phát triển phần mềm của một “big corp” bên Nhật. Trong quá trình phỏng vấn, bên đó có đưa ra một đề bài yêu cầu bạn tôi đưa ra thuật giải. Nếu giải được thì với hồ sơ của mình, bạn tôi hoàn toàn có thể đậu phỏng vấn và trải nghiệm môi trường của một trong những công ty công nghệ lớn nhất Nhật Bản ngay tại Tokyo.
Đây là một trong những bài tin xưa như Trái Đất và bất kỳ cuốn cẩm nang "300 bài code thiếu nhi" nào cũng sẽ đề cập đến. Nhưng bạn tôi thì làm gì chịu luyện đề trước khi đi phỏng vấn, thế là không làm được. Một hôm, nó đề cập bài này với tôi. Cảm thấy hình như chúng tôi đã giải bài này từ hồi cấp 3, tôi và nó ngồi nhắn tin cả tiếng đồng hồ quyết tâm giải được.
Lưu ý: Những đoạn code trong bài đều là mã giả, sử dụng ký hiệu toán học, không phải của cụ thể một ngôn ngữ lập trình nào.
*Rất mong ban quản trị có thể đưa công cụ viết code nào đó vào trong text editor của Spiderum để nơi đây thực sự có thể trở thành một nơi dành cho mọi người viết.

ĐỀ BÀI

Cho một khu vườn có N cái cây, mỗi cái cây có chiều cao A[i]. Tìm số lần tỉa cây ít nhất để có một khu vườn cao thấp xen kẽ. N có thể lên tới 1.000.000 (cây), giá trị Ai thuộc tập số nguyên integer [-2^29, 2^29 – 1] (cm).
Đề bài trong buổi phỏng vấn
Trong tin học có một dạng các bài toán gọi là Giải thuật tham lam (Greedy algorithm), nghĩa là sẽ không có phương thức tổng quát hay quy trình chung để giải. Việc giải bài toán hoàn toàn phụ thuộc vào kỹ năng giải quyết vấn đề của người làm. Những bài toán này là công cụ tốt để kiểm tra kỹ năng giải quyết vấn đề của ứng viên khi phỏng vấn (thực chất là một cách kiểm tra chỉ số IQ trá hình của các công ty công nghệ). Bài toán phía trên thuộc dạng bài này.
Đầu tiên có thể nhận xét ngay: với N lớn như vậy thì thuật toán cần có độ phức tạp O(n) hoặc cùng lắm là O(nlogn) nếu không thì thời gian để máy tính tìm ra đáp án sẽ là rất rất lâu. Như vậy, lý tưởng nhất là tìm được cách giải chỉ sử dụng một vòng lặp. Điều này tương đương với việc đi từ đầu vườn đến cuối vườn, đi đến cây nào là biết ngay cần phải cắt cây đó bao nhiêu cm.
Điều này gần như không tưởng. Bởi vì theo trực giác, khi muốn quyết định một điều gì đó (ở đây là tỉa cây) thì ít nhất ta phải có một cái nhìn tổng quan về bối cảnh trước. Bài toán này lại yêu cầu ra quyết định tỉa cây hiện tại khi chưa biết bất kỳ điều gì về những cái cây phía trước.
Chính vì vậy, nhận xét sau đây là vô cùng quan trọng nếu muốn làm tiếp: Chỉ cần xét cắt hay không cắt, không cần xét xem phải cắt bao nhiêu.
Nhận xét này được rút ra từ một quá trình suy nghĩ quy nạp:
1, Nếu có hai cây {3,3} thì ta sẽ muốn cắt thành {3,2} hoặc {3,1} hoặc {1,3} hoặc {2,3} – chỉ cắt một cây, chứ không phải {2,1} hoặc {1,2} – phải cắt hai cây.
2, Nếu có ba cây {3,3,3} thì ta sẽ muốn cắt thành {3,2,3} hoặc {3,1,3} – 1 lần cắt cây ở giữa.
3, Nếu có ba cây {3,3,2} thì ta sẽ muốn cắt thành {3,1,2} – 1 lần cắt cây ở giữa.
Vậy là: Cần giữ nhiều cây không cắt nhất có thể. Muốn vậy thì chỉ cần xét những cây ở giữa, cắt nó về một chiều cao an toàn để đảm bảo không cao hơn 2 cây hai bên, tạo thành từng cặp ba {cao, thấp, cao} hoặc {thấp, cao, thấp}. Chiều cao an toàn này bằng A[i] = min(A[i-1],A[i+1])-1 (thấp hơn 2 cây hai bên).
Như vậy, có thể đưa ra ngay một vài ý tưởng cho thuật giải. Chúng tôi lần lượt đi qua các cách giải sau đây.

CÁCH PHÀM PHU TỤC TỬ: CỨ THẾ MÀ DUYỆT O(2^N)

Đây là phương pháp huyền thoại cho mọi bài toán tin. Không cần suy nghĩ, không cần đắn đo, không cần lao tâm khổ trí, tất cả những gì cần làm là để cho máy tính thử mọi trường hợp, trường hợp nào thỏa mãn thì chọn. Bởi vì máy tính có khả năng tính toán hàng nghìn tỷ phép tính trên giây, nên cách này hoàn toàn khả thi cho những trường hợp bộ số nhỏ.
Để lập trình thuật giải này, có thể tạo một mảng mới gọi là mảng chose[1..n]. Trong đó chose[i] = 0 nghĩa là không cắt cây ở vị trí i, chose[i] = 1 nghĩa là cắt cây ở vị trí i.
Sau đó, làm một hàm đệ quy “chose_tree_to_cut” để máy sinh ra tất cả các trường hợp cho mảng chose này.
Def chose_tree_to_cut(index): \ for i = 0 -> 1: \ chose[index] = i \ if index = n: \ test_configuration() \ else: \ chose_tree_to_cut(index+1)
Hàm trên sẽ sinh ra mọi trường hợp của chose, và đưa tất cả trường hợp này vào một hàm kiểm tra “test_configuration”. Trong hàm kiểm tra sẽ kiểm tra xem với cách chọn hiện tại thì các cây có thỏa mãn yêu cầu cao thấp xen kẽ không, nếu có thì đếm số cây được chọn để cắt. Nếu số cây phải cắt ít hơn phương án tốt nhất, thì cập nhật phương án hiện giờ trở thành phương án tốt nhất.
Thuật toán này là thuật toán sẽ cho ra kết quả chính xác. Nhưng độ phức tạp sẽ là O(2^n) và chiếm dụng một lượng bộ nhớ khổng lồ. Với n = 1.000.000 chắc chắn sẽ bị stack overflow (tràn bộ nhớ), hoặc nếu bạn có bộ nhớ vô hạn thì cũng phải cần đợi vô hạn thời gian để thuật toán trả về kết quả.

CÁCH LÀM CỦA DỊ NHÂN: CHUYỂN SỐ NHỊ PHÂN SANG THẬP PHÂN ĐỂ DUYỆT O(2^N)

Cách trên không ổn, chúng tôi bàn cách khác. Có một thủ thuật để giảm bộ nhớ chiếm dụng của các thuật toán đệ quy, đó là biến các trạng thái nhị phân thành trạng thái thập phân.
Ví dụ: mảng chose[1..n] là một bộ số kiểu 011010101, có thể chuyển sang hệ thập phân là 213.
Như vậy, thay vì phải chạy hàm đệ quy “chose_tree_to_cut” khủng khiếp ở trên thì bây giờ chỉ cần chạy 1 vòng for từ 1 đến 2^n là đủ để duyệt mọi trường hợp của chose. Các bước như sau:
B1: Sinh ra mọi trường hợp của chose dưới dạng thập phân
for i = 0 -> 2^n: \ convert_decimal_binary(i)
B2: Chuyển số thập phân sang số nhị phân.
Trong hàm chuyển “convert_decimal_binary” sẽ biến số i (tương trưng cho trạng thái hiện giờ của mảng chose) thành một số nhị phân. Ví dụ: 213 sẽ thành 011010101, nghĩa là chose[1] = 0, chose[2]=1, chose[3]=1… Đến đây chúng ta sẽ có các mảng chose tương tự như cách phía trên.
B3: Cho mảng chose hiện tại vào hàm “test_configuration” để kiểm tra và cập nhật kết quả tốt nhất.
Thuật toán này thì sẽ không làm tràn bộ nhớ vì không có hàm đệ quy. Tuy nhiên, vòng lặp for từ 0 đến 2^n vẫn có độ phức tạp O(2^n). Cách này vẫn không ổn.

SỰ BẾ TẮC

Sau khi nghĩ ra 2 cách trên, vốn là hai cách rất tự nhiên nhưng không thể chạy với bộ số lớn của đề bài, chúng tôi chìm vào bế tắc.
Chúng tôi có thử thiết lập công thức quy hoạch động cho bài toán nhưng không được. Quy hoạch động có thể hiểu đơn giản là làm ngược lại thuật toán đệ quy: Nếu đệ quy là thuật toán top-down (từ trên xuống) – giải quyết bài toán mẹ bằng cách đẻ ra các bài toán con, thì quy hoạch động là thuật toán bottom-up (từ dưới lên) – dự trù các bài toán con trước, sau đó ghép lại thành bài toán mẹ. Cách này thì không phải lúc nào cũng làm được, nhưng một khi đã làm được thì có thể đảm bảo chương trình chạy mướt mườn mượt như được tra Castrol Power 1, và nếu là học sinh thì có thể đảm bảo cho bạn ít nhất là giải 3 Quốc gia.
Nhưng không được thì vẫn là không được. Tôi bắt đầu nghi ngờ bản thân. Lúc này, thằng bạn đã động viên tôi một vài câu, nhắc nhở về một quá khứ tươi đẹp.
Bất ngờ thay, sức mạnh tình bạn đã phát huy tác dụng. Sau khi nhận được lời động viên từ bạn mình, tôi đã nghĩ ra được cách làm.

EUREKA! CÁCH LÀM O(N)!

Bí quyết ở đây là thay vì sử dụng một lối tiếp cận “cá nhân hóa” cho từng cây – cân nhắc chiều cao của nó cùng với chiều cao của các cây bên cạnh để quyết định số phận xem có mang đi cắt tỉa hay không, thì cần sử dụng một lối tiếp cận “bao cấp” hơn. Mọi kế hoạch đều được quy định sẵn, những vị trí đã được thiết lập từ trước, cá nhân chỉ có lựa chọn thay đổi chính mình để trở thành bánh răng trong bộ máy đó hoặc bị đào thải.
Tương tự vậy, trong bài toán này, cần xác định trạng thái cuối cùng của vườn cây từ trước, rồi mới ép buộc từng cây thay đổi cho phù hợp với vị trí đứng của nó.
Lý do mà chúng tôi không xem xét tới cách này từ đầu là vì sợ không khả thi. Ví dụ như {2,3,3,3} có phương án tối ưu là tỉa cây thứ 3 xuống còn 2, trở thành {2,3,2,3}; nhưng nếu sử dụng cách ép buộc mà không xác định đúng trạng thái cuối cùng từ đầu thì có thể cho ra kết quả đi xa ra khỏi trạng thái tối ưu. Ví dụ nếu tôi xác định trạng thái cuối cùng của khu vườn là {cao,thấp,cao,thấp} thì {2,3,3,3} phải trở thành {2,1,3,2}, nghĩ là phải tỉa cây số 2 và số 4, không phải tối ưu.
Nếu áp dụng lối tiếp cận ép buộc như vậy thì tôi phải hoạch định được trạng thái tối ưu ngay từ ban đầu. Nhưng làm sao có thể thiết lập được trạng thái tối ưu ấy từ ban đầu cơ chứ?
Hay là… có thể?
Đúng là có thể thật. Khác với nền kinh tế với hàng trăm biến phải xem xét, khu vườn này chỉ có một đống cây vô tri cần cắt tỉa. Trạng thái cuối cùng của nó chỉ có 2 mà thôi!
Hoặc là:
Thấp-cao-thấp-cao-thấp-cao…
Hoặc là:
Cao-thấp-cao-thấp-cao-thấp…
Không thể có trạng thái thứ ba. Đến đây kết hợp với nhận xét từ ban đầu “chỉ cần xác định cây cần cắt, không cần xác định cần cắt bao nhiêu”, thì bài toán đã tự động được giải. Các bước như sau:
B1: Tạo 2 mảng biểu diễn 2 trường hợp:
Config_1[1..n] = {0,1,0,1,0,1…}
Config_2[1...n] = {1,0,1,0,1,0…}
Trong đó 0 là thấp, 1 là cao.
B2: Xác định cây cần cắt tỉa.
Bằng cách so sánh nó với hai cây hai bên và trạng thái muốn đạt được.
If (Config_1[i] = 0) and ((A[i] > A[i-1]) or (A[i] > A[i+1]): \ A[i] = min(A[i-1],A[i+1])-1 \ Chose[i] = 1
Đến đây bạn phải thì thầm với cây i: "Cây i à, số phận bắt cậu phải thấp hơn hai cây hai bên, chịu khó tý nhé!"
B3: Chạy lần lượt 2 vòng lặp for từ đầu đến cuối, đếm xem số cây cần cắt cho từng trường hợp.
B4: So sánh 2 trường hợp, xem trường hợp nào cần cắt ít hơn thì chọn trường hợp đó.
Vậy là xong! Sau khi giải được, thằng bạn tôi nổi điên nổi khùng vì bài dễ vậy mà lúc đó không nhớ ra. Tôi thì thấy rất vui vì kỹ năng của mình chưa quá mai một.
Thôi, đến giờ vào học rồi. Hy vọng bài này lọt vào sự quan tâm của ai đó.