(1) Thuật toán tự nhiên

Trước tiên ta có nhận xét rằng nếu biết trước hai vị trí cây đổ trên lưới, ta có thể xác định được vector hướng của bước nhảy của ếch và do đó sẽ xác định được đường thẳng này có tạo thành một đường ếch hay không (xem hình 1).

Thuật toán kiểm tra này sẽ có độ phức tạp là O(N). Thật vậy giả sử p_A, p_B là hai điểm đã cho và V(p_A,p_B) là vector tạo bởi hai điểm trên, với mỗi điểm P thuộc tập các vị trí cây lúa đổ ta chỉ việc kiểm tra xem vector V(P,p_B) có song song và bằng vector V(p_A,p_B) hay không mà thôi. Như vậy với thuật toán tự nhiên này chúng ta duyệt tìm trên tất cả các cặp điểm của toàn bộ N vị trí đã cho của cây đổ với độ phức tạp là O(N²) và sử dụng cách làm trên để tìm ra lời giải bài toán. Tổng hợp cách giải này yêu cầu thời gian tính toán là O(N³).

(2) Thuật giải ″tập con thẳng hàng với khoảng cách bằng nhau″.

ý tưởng của thuật giải này rất đơn giản: chúng ta tìm cách so sánh các bộ 3 điểm thẳng hàng và đều nhau (p_A,p_B,p_C). Các bộ 3 điểm ″thẳng-đều″ này chính là cái lõi của các đường ếch mà chúng ta cần tìm (xem hình 2).

Ta xây dựng một Đồ thị vô hướng G với các đỉnh là cặp điểm (p_X,p_Y) từ tập các vị trí cây đổ (đồ thị sẽ có O(N²) đỉnh) như sau: với mỗi bộ 3 điểm thẳng đều (p_A,p_B,p_C) ta thiết lập hai đỉnh (p_A,p_B), (p_B,p_C) cho đồ thị G và một cạnh nối từ đỉnh (p_A,p_B) với đỉnh (p_B,p_C). Như vậy mỗi cạnh nối của đồ thị sẽ phải tương ứng với một đường ếch (bởi vì đã có tối thiểu 3 vị trí!). Như vậy các thành phần liên thông của đồ thị này chính là các đường ếch cực đại và vấn đề còn lại là tìm ra số phần tử của thành phần liên thông lớn nhất của đồ thị mà thôi. Nhận xét rằng mỗi đỉnh của đồ thị này chỉ có thể nối tối đa với 2 cạnh, do đó số cạnh của đồ thị này cũng là đại lượng O(N²). Vậy thuật toán tìm miền liên thông cực đại cũng phải là O(N²).

Vấn đề còn lại bây giờ là liệu có thể tìm kiếm nhanh các bộ 3 điểm thẳng đều (p_A,p_B,p_C) được hay không để khởi tạo đồ thị G? Nếu việc tìm này không nhanh thì ý tưởng thuật toán sẽ thất bại.

Cách thứ nhất chúng ta sử dụng thêm một mảng 2 chiều kích thước NxN để lưu trữ dữ liệu các vị trí cây đổ: giá trị của mảng M(x,y) = k > 0 nếu và chỉ nếu (x,y) là toạ độ của cây đổ thứ k (như vậy mảng M sẽ là mảng hầu như bằng 0). Với mỗi cặp (p_A,p_B) giá trị của p_C chỉ phải tìm tại đúng 1 vị trí có thể trong mảng M, do đó việc tìm các bộ 3 điểm thẳng đều theo cách trên chỉ tốn O(N²) thời gian (duyệt theo p_A và p_B). Tuy nhiên phương án trên sẽ cần bộ nhớ vượt quá N² và theo đầu bài thì có thể lên tới 5000x5000, sẽ vượt quá 64M là yêu cầu của đề bài. Ta cần xử lý mẹo tại đây: do mảng M bao gồm hầu hết là 0 nên ta có thể sử dụng kỹ thuật băm để lưu trữ mảng này. Tuy nhiên cách làm này sẽ không qua được các Test ″xấu″.

Cách thứ hai, ta tiến hành sắp xếp toàn bộ các vị trí cây đổ theo một thứ tự nào đó (chẳng hạn sắp xếp theo thứ tự tăng dần của tọa độ hàng, sau đó tọa độ cột). Các bộ 3 điểm thẳng đều sẽ được tìm kiếm bằng cách duyệt theo các bộ điểm p_A,p_B,p_C với điều kiện p_A < p _B < p _C. Cách làm này trên thực tế sẽ có thời gian tính toán rất nhanh, gần như tuyến tính với O(N²) và không cần sử dụng thêm bộ nhớ.

Bài 2: UTOPIA

(Dựa theo Jung-Hum Park và Ian Munro − các tác giả của đề bài được lựa chọn tại IOI 2002 với vài nhận xét bổ xung của người biên soạn bài viết này).

Trước tiên hãy chứng minh rằng bài toán trên (với mảng 2 chiều) sẽ suy được dễ dàng từ bài toán 1 chiều sau đây:

Bài toán chọn dãy 1 chiều:

Cho trước N số nguyên dương khác nhau và N dấu (là + hoặc -). Khi đó tồn tại một hoán vị của N số trên và sau khi đặt các dấu vào trước các số này, ta thu được dãy {Xi} sao cho với mọi k thì sẽ cùng dấu với giá trị dấu thứ k.

Chứng minh từ bài toán 1 chiều trên suy được bài toán UTOPIA của chúng ta. Thật vậy sau khi nhập vào 2N mã số nguyên dương khác nhau, ta tách tập này thành 2 phần bằng nhau (một cách bất kỳ!), mỗi tập con chứa đúng N số. Gọi các tập con này là A và B. Sau khi đã nhập N số hiệu miền ta tách mỗi miền này theo hai giá trị dấu (d_X, d_Y) theo sơ đồ dấu của đề bài (hình 3).

Như vậy ta thu được hai dãy dấu bao gồm N phần tử, ứng với các giá trị dấu của dãy miền nhập vào. Gọi hai tập dấu này là S_X, S_Y.

Bây giờ ta áp dụng bài toán chọn dãy 1 chiều trên cho các tập dãy và dấu độc lập, lần lượt áp dụng cho (A, SX) và (B, SY). Để có được đáp số ta chỉ việc ghép các hai dãy số tìm được theo từng cặp giá trị lần lượt.

Lời giải của bài toán chọn dãy 1 chiều

Ta sẽ chỉ ra một cách xây dựng lần lượt dãy số {X_i} thỏa mãn điều kiện đầu bài.

Trước tiên ta có định nghĩa sau: Dãy số X={X_a, X_a+1,...., X_b} với a<=b được gọi là dãy đổi dấu đơn điệu nếu thỏa mãn các điều kiện sau:

(i) dãy là đơn điệu tăng nếu so sánh giá trị tuyệt đối:

|X_a| < |X_a+1| <..... < |X_b|

(ii) các phần tử của dãy đổi dấu tuần tự: X_i luôn khác dấu với X_i+1.

Dễ thấy rằng nếu X={X_a, X_a+1, ...., X_b} là một dãy đổi dấu đơn điệu thì các dãy con dạng X′ = {X_a, X_a+1,...., X_k} và X″={X_k,X_k+1,....,X_b} cũng là đổi dấu đơn điệu.

Bài toán suy từ 2 mệnh đề sau:

Mệnh đề 1: Giả sử X={X_a, X_a+1,...., X_b} là một dãy đổi dấu đơn điệu. Khi đó X_b sẽ cùng dấu với tổng X_a + X_a+1 +.... + X_b.

Chứng minh: Không mất tổng quát giả sử X_b >0 (dương). Ta xét 2 trường hợp:

Trường hợp 1: dãy X có số chẵn phần tử. Khi đó theo định nghĩa ta sẽ có X_a+1, X_a+3,...., Xb là dương. Các tổng con X_a + X_a+1, X_a+2 + X_a+3, ...., X_b-1+X_b sẽ là dương. Từ đó suy ra tổng X_a + X_a+1 +.... + X_b cũng dương.

Trường hợp 2: dãy X có lẻ các phần tử. Khi đó X_a, X_a+2,...., X_b-2, X_b sẽ là dương. Các tổng con X_a, X_a+1 + X_a+2,...., X_b-1 + X_b cũng sẽ dương, vậy suy ra tổng X_a + X_a+1 + .... + X_b cũng dương. Mệnh đề 1 được chứng minh.

Giả sử ta có dãy số X={X_a, X_a+1, ...., X_b} và dãy các dấu S={S_a, S_a+1,..., S_b}. Ta nói dãy X tương thích với dãy dấu S nếu các tổng con X_a + X_a+1 +.... + X_k sẽ có dấu giống S_k với mọi k.

Mệnh đề 2: Giả sử X = {X_a, X_a+1,...., X_b} là một dãy đổi dấu đơn điệu và S = {S_a, S_a+1,..., Sb} là một dãy các dấu. Giả sử Xb cùng dấu với Sb. Khi đó tồn tại một hoán vị của X là dãy X′={X′_a, X′_a+1,...., X′_b} tương thích với S.

Chứng minh: Ta chứng minh mệnh đề 2 bằng qui nạp theo k là số phần tử của X. Với k=1 thì không cần chứng minh gì cả. Giả sử bây giờ k≥2.

Đặt S₁ = S - {S_b}, vậy S₁ = {S_a, S_a+1,..., S_b-1}. Ta xét 2 trường hợp sau:

Trường hợp 1: X_b cùng dấu với S_b-1. Đặt X₁ = X-{X_a}. Vậy X_1</SUB>={Xa+1,Xa+2,....,Xb}. Đặt T=Xa.

Trường hợp 2: Xb khác dấu với Sb-1 hay Xb-1 cùng dấu với Sb-1. Đặt X1 =X-{Xb}. Vậy X1</SUB>={Xa,Xa+1,...,Xb-1}. Đặt T=Xb.

Trong cả hai trường hợp dễ thấy X1 là dãy đổi dấu đơn điệu và có phần tử cuối cùng cùng dấu với Sb-1. áp dụng qui nạp suy ra tồn tại một hoán vị X′1 của X1 là tương thích với S1. Đặt X′={X′1,T}, khi đó X′ là hoán vị của X có tổng các phần tử cùng dấu với Sb (theo mệnh đề 1) và có dãy con X′1 tương thích với S1, do đó sẽ tương thích với S. Mệnh đề được chứng minh.

Chú ý: từ cách chứng minh mệnh đề trên suy ra thuật giải tuyến tính để tìm ra hoán vị X′. Ví dụ với X={-3,+5,-7,+9} và S={+,-,-,+} ta có:

- Tách phần tử:

S1 = {+,-,-}, khác dấu, X1 = {-3,+5,-7}

S2 = {+,-}, cùng dấu, X2 = {+5,-7}

S3 = {+}, khác dấu, X3 = {+5}

- Ghép phần tử:

X′1 = {+5}

X′2 = {+5,-7}

X′3 = {+5,-7,-3}

X′4 = {+5,-7,-3,+9}

Quay lại lời giải bài toán chọn dãy 1 chiều: giả sử dãy dấu ban đầu là S1,S2,...,SN. Ta sắp xếp dãy N mã số nguyên dương ban đầu theo thứ tự tăng dần và đặt các dấu +, - trước chúng sao cho dãy này trở thành một dãy đổi dấu đơn điệu và phần tử cuối cùng cùng dấu với SN. Theo mệnh đề 2 tồn tại một hoán vị của dãy trên là tương thích với dãy dấu S và đó chính là dãy số cần tìm.

Bài 3: XOR

(Dựa theo Jung-Gun Lim và Chong-Dae Park − tác giả của bài toán được đề nghị cùng với một vài nhận xét của người biên soạn bài viết này).

Trước tiên chúng ta cần định nghĩa và phân biệt khái niệm điểm lưới và ô lưới. Điểm lưới là điểm giao của các đường lưới. Ô lưới là vùng diện tích giới hạn bởi các đường lưới. Như vậy mỗi ô lưới sẽ bị chặn bởi 4 điểm lưới (xem hình 4).

Với mỗi điểm lưới p, ta định nghĩa giá trị ic(p) (ic-value) như sau: ic(p)=1 khi và chỉ khi điểm p tiếp giáp với một số lẻ ô lưới màu đen, ngược lại ta định nghĩa ic(p)=0. Nếu ic(p)=1 ta nói p là điểm góc (imagecorner). ý nghĩa của khái niệm này là dễ hiểu: điểm lưới p là điểm góc (ic=1) nếu trên màn hình đen trắng, p nằm tại một ″góc″ của hình ảnh (xem hình 5).

Các mệnh đề sau là quan trọng cho việc tìm thuật giải của bài toán.

Mệnh đề 1: Hình ảnh là toàn trắng khi và chỉ khi không có điểm góc.

Mệnh đề này là hiển nhiên.

Như vậy để tìm lời giải bài toán chúng ta đi ngược từ hình ảnh đã cho. Nhiệm vụ của ta là tìm một dãy các biến đổi XOR để cuối cùng thu được hình ảnh không có điểm góc nào cả.

Mệnh đề 2: Giả sử toán tử XOR(L,R,T,B) được thực hiện và Q là hình chữ nhật xác định vùng tác động của toán tử này. Gọi a,b,c,d là các điểm lưới tại vị trí góc trái trên, trái dưới, phải trên, phải dưới của Q. Khi đó toán tử XOR(L,R,T,B) sẽ thay đổi giá trị ic của các điểm lưới a,b,c,d và không làm thay đổi giá trị này của tất cả các điểm lưới còn lại.

Chứng minh: Tước tiên xét ic của các điểm a,b,c,d. Dễ thấy rằng với tác động của XOR tương ứng, chỉ có đúng một ô lưới kề với các điểm a,b,c,d là thay đổi màu, do đó giá trị ic của các điểm này sẽ thay đổi. Bây giờ ta xét các điểm còn lại:

- Các điểm bên ngoài Q: do không bị tác động bới toán tử XOR, ic của các điểm này không thay đổi.

- Các điểm nằm trên cạnh (và bên trong cạnh) của Q. Các điểm này kề với 2 ô lưới của Q, do đó sẽ có 2 ô kề bị đổi màu và do đó ic không thay đổi.

- Các điểm nằm bên trong Q. Các điểm này có 4 ô kề nằm trong Q bị thay đổi màu, do đó ic cũng không thay đổi. Mệnh đề được chứng minh.

Kết quả của mệnh đề 2 chỉ ra rằng mỗi lần áp dụng toán tử XOR thì số lượng điểm góc của hình ảnh sẽ giảm tối đa là 4.

Mệnh đề 3: Nếu hình ảnh không là toàn trắng thì sẽ tồn tại 3 điểm góc tạo thành 3 đỉnh của một hình chữ nhật trên lưới.

Chứng minh: Cách tìm 3 điểm góc như sau. Chúng ta xuất phát từ một ô lưới đen ở hàng trên cùng và tận cùng bên phải của hàng này. Đó là điểm góc thứ nhất. Xuất phát từ điểm này chúng ta đi xuống và đi sang trái, chắc chắn sẽ tìm được thêm 2 điểm góc nữa và 3 điểm này tạo thành 3 đỉnh của một hình chữ nhật.

Mệnh đề 4: Từ một hình ảnh không toàn trắng ban đầu bao giờ cũng tìm được một toán tử XOR sao cho sau khi áp dụng cho hình này, số điểm góc sẽ giảm đi 2 hoặc 4.

Thật vậy theo mệnh đề 3 ta luôn tìm được một hình chữ nhật với tối thiểu 3 điểm góc tạo thành hình chữ nhật. áp dụng toán tử XOR với hình chữ nhật này. Theo mệnh đề 2 thì sau toán tử này chỉ có 3 điểm góc trên và đỉnh (điểm lưới) còn lại là bị thay đổi giá trị ic. Trường hợp cả 4 đỉnh là điểm góc thì số điểm góc giảm đi 4, trường hợp chỉ có 3 điểm góc thì số điểm góc sẽ bị giảm 3 nhưng tăng 1 vì đỉnh còn lại sẽ trở thành điểm góc và do đó tổng thể số điểm góc giảm 2. Mệnh đề được chứng minh.

Từ kết quả của mệnh đề 4 chúng ta tìm được một thuật giải đơn giản cho bài toán XOR như sau.

Thuật toán 2-tối ưu cho bài toán XOR:

Liên tục áp dụng các biến đổi XOR với hình ban đầu sao cho sau mỗi bước số điểm góc giảm 2 hoặc 4. Sau một số hữu hạn bước số điểm góc trở về 0 và ta thu được hình ảnh toàn trắng. Thuật toán này đảm bảo rằng số lần gọi XOR sẽ chắc chắn nhỏ hơn 2 lần số lần gọi XOR của phương án tối ưu và do đó thuật toán được gọi là 2-tối ưu.

Lập kế hoạch theo khối

Lời giải IOI 2002:
Batch Scheduling - Lập kế hoạch theo khối
(Đề bài Batch Scheduling IOI-2002 đã đăng tải trong TH&NT tháng 10-2002)
Trước tiên ta nhắc lại một số nét chính về yêu cầu của bài toán: Cần phân hoạch (batch) các công việc J₁, J₂,..., J_n thành các nhóm liên tục dạng (J₁,.., J_k1), (J_k1+1, ..., J_k2),....(J_ks+1,..., J_n) sao cho tối ưu hóa hàm giá thành chi phí thực hiện các công việc trên.
Hàm chi phí có dạng:

ở đây O_k là thời gian thực hiện xong công việc k (tính từ thời điểm 0 - bắt đầu thực hiện toàn bộ các công việc), F_k là hệ số chi phí cho công việc k.
Thời gian tính để hoàn thành công việc O_k, k=1, 2,..., n được tính như sau:
Nếu (J_x, J_x+1,...., J_x+k) là một nhóm trong phân hoạch thì toàn bộ các công việc của nhóm sẽ có cùng thời gian thực hiện được tính theo công thức sau:

Ở đây, T_k là thời gian cho phép thực hiện công việc k, S - thời gian chờ đợi để khởi động các công việc trong một nhóm (batch), t - thời gian bắt đầu thực hiện batch trên.
Do đó tổng chi phí cho các công việc trong nhóm (J_x, J_x+1,...., J_x+k) sẽ tính bởi công thức sau:

Như vậy, tổng (1) sẽ bao gồm các số hạng có dạng (3).

Yêu cầu của bài toán gợi ý cho chúng ta sử dụng Qui hạch động để giải quyết. Các bước triển khai cụ thể như sau:
Gọi C_i là chi phí minimum cho tất cả các phân hoạch theo lô của các công việc J_i, J_i+1,..., J_n tính từ thời gian 0. Khi đó dễ thấy
C_n = (S+T_n)F_n (4)
C_n+1 = 0 (4')
và C₁ chính là ẩn số cần tìm. Để tìm được các giá trị C_i chúng ta cần thêm một đại lượng nữa.
Với i< k gọi C_i (k) là chi phí minimum để thực hiện các công việc J_i, J_i+1, ..., J_n tính từ thời gian 0 với điều kiện lô đầu tiên đã được chọn là (J_i, J_i+1, ..., J_k-1). Khi đó rõ ràng ta có:

Ta sẽ tìm cách phân tích và tính toán với C_i(k).Với lô đầu tiên đã được chọn là (J_i, J_i+1, ..., J_k-1), thời gian để thực hiện mỗi công việc của nhóm này (tính từ 0) sẽ như nhau và bằng t = S + T_i + T_i+1 +....+ T _k-1. Chi phí cho việc thực hiện xong các công việc tại lô đầu tiên này sẽ là t(F_i + F_i+1 +... + F_k-1). Sau khi thực hiện xong lô đầu tiên (J_i, J_i+1, ..., J_k-1), công việc còn lại là phân hoạch các công việc còn lại J_k, J_k+1,..., J_n thành các nhóm con và thực hiện. Nếu tính từ thời gian 0 thì chi phí toàn bộ cho các công việc này tối thiểu sẽ là C_k. Do thời gian dùng để thực hiện các công việc J_k, J_k+1, ..., J_n luôn tại thời điểm sau t, do đó chi phí cho các công việc này luôn phải cộng thêm với t(F_k + F_k+1 +... + F_n). Do vậy tổng hợp các phân tích trên ta có công thức sau cho việc tính toán với C_i(k).
C_i(k) = t(F_i + F_i+1 +... + F_k-1) + C_k + t(F_k + F_k+1 +... + F_n) với t = S + T_i + T_i+1 +....+ T_k-1.
Tóm lại ta có đẳng thức sau liên kết giữa C_i(k) và C _k .
C_i(k) = C_k + (S + T_i + T_i+1 +....+ T_k-1)(F_i + F_i+1 +....+ F_n) (6)
.
Chú ý rằng với i=n, k=n+1 công thức (6) trở thành: C_n(n+1) = C_n+1 + (S+T_n)F_n
Vì với 1 công việc J_n chỉ có 1 cách phân hoạch duy nhất nên C_n = C_n(n+1) và do đó ta có
C_n = C_n+1 + (S+T_n)F_n, đây chính là đẳng thức (4) nếu chú ý đến (4').
Từ các đẳng thức (6), (4) và (5) ta suy ra thuật giải tìm C₁ như sau (qui hoạch động):
Algorithm 1 (thời gian tính O(n²)).
C_n+1 = 0; //gán giá trị ban đầu
For i:=n downto 1 do
begin
C_min = 0;
for k:=i+1 to n+1 do
begin
C_i(k) = C _k + (S + T_i + T_i+1 +....+ T_k-1)(F_i + F_i+1 +....+ F_n);
If C_min > C_i(k) then C_min = C_i(k);
end;
C_i = C_min;
end;
Output(C₁);
Với cách giải như trên, bạn sẽ vượt qua được 17/20 test của ban giám khảo. Với 3 test còn lại chúng ta cần một thuật giải tốt hơn.
Bây giờ chúng ta sẽ phân tích tiếp công thức (6) và chứng tỏ rằng chỉ cần thuật toán tuyến tính là có thể tính được C₁. Tác giả của thuật giải này là P. Brucker, đăng trên tạp chí Discrete Applied Mathematics, N^o62, 1995.

Mệnh đề 1

Thật vậy từ (6) áp dụng cho C_i(k) và C_i(l) ta có:
C_i(l) - C_i(k) = C_l - C_k + (T_k + T_k+1 +...+ T_l-1)(F_i + F_i+1 +.... + F_n) = C_l - C_k + (T_k + T_k+1 +...+ T_l-1)f(i) = (T_k + T_k+1 +...+ T_l-1)(f(i) - g(k,l))
Vậy rõ ràng là C_i(l) > C_i(k) khi và chỉ khi f(i) > g(k,l). đpcm.
Mệnh đề 2

Thật vậy so sánh g(j,k) và g(k,l) với f(i) ta thấy chỉ có thể một trong 3 khả năng sau:
(a) f(i) ≤g(j,k)≤ g(k,l)
(b) g(j,k) ≤ f(i) ≤g(k,l)
(c) g(j,k) ≤ g(k,l)≤ f(i)
Các trường hợp (a) và (b) suy ra f(i) ≤ g(k,l) vậy theo mệnh đề 1 thì C_i(k) ≥ C_i(l).
Trường hợp (c) suy ra g(j,k) ≤ f(i) vậy theo mệnh đề 1 suy ra C_i(k) ≥ C_i(j).
Đó chính là điều phải chứng minh (đpcm).
Mệnh đề 2 cho ta một nhận xét quan trọng là chìa khóa cho lời giải mới của bài toán: Nếu như chúng ta có với j, k, l nào đó thỏa mãn thì C_i(k) hoàn toàn không cần dùng đến khi tính toán C_i, theo công thức (5) vì khi đó ta sẽ dùng C_i(l) hoặc C_i(j). Do vậy trên thực tế việc tính toán có thể lược bớt và do đó tăng tốc độ lời giải bài toán.
Để áp dụng được nhận xét trên, chúng ta phải đưa vào xét một dãy 'hàng đợí sau
Q = (I_r, I_r-1,...., I₂, I₁) thỏa mãn các điều kiện sau:
I_r < I_r-1 <.... < I₂ < I₁ <=n+1
g(I_r,I_r-1) > g(I_r-1,I_r-2) > .... > g(I₂,I₁)
Hàng đợi Q được đưa vào để trợ giúp việc tính toán các giá trị C_i dựa trên nhận xét đã nêu trên. Vì sao lại gọi là 'hàng đợí thì ngay bây giờ các bạn sẽ rõ. Với hàng đợi Q ta gọi I_r là 'đuôí và I₁ là 'đầú của Q. Bây giờ thuật toán 1 sẽ được cải tiến như sau với sự trợ giúp của hàng đợi Q.
C_n+1 = 0; //gán giá trị ban đầu
For i:=n downto 1 do
begin
Xây dựng hàng đợi Q;
Tính toán C_i;
end;
Như vậy hàng đợi Q sẽ được tính toán lại tại mỗi thời điểm, phụ thuộc vào biến chạy i. Ta sẽ xây dựng Q thỏa mãn các điều kiện sau (phụ thuộc vào i):
1. i < I_r < I_r-1 <.... < I₂ < I₁ ≤n+1 (9)
2. g(I_r,I_r-1) > g(I_r-1,I_r-2) > .... > g(I₂,I₁) > f(i) (10)
3. Với mọi h≤i, k >h, C_h(k) sẽ lớn hơn hoặc bằng C_h(I_t) với I_t nằm trong Q. (11)
Mệnh đề sau chứng tỏ rằng hàng đợi Q với các tính chất trên chính là hàng đợi mà chúng ta cần xây dựng để tính được C_i.
Mệnh đề 3
Giả sử Q là hàng đợi thỏa mãn các điều kiện (9), (10) và (11) khi đó
C_i(I₁) = min{C_i(k), k =i+1,i+2, ..,n+1}, hay nói cách khác C_i = C_i(I₁).
Chứng minh: Điều kiện (10) với mệnh đề 1 cho ta
C_i(I_r) > C_i(I_r-1) > .... > C_i(I₁).
Cùng với điều kiện (11) và bất đẳng thức trên suy ra C_i(k) ≥C_i(I₁) với mọi k > i. Từ đó suy ra ngay
C_i(I₁) = min{C_i(k), k =i+1,i+2,..,n+1}, vậy C_i = C_i(I₁) và đó là đpcm.
Để hoàn thiện lời giải, chúng ta chỉ còn cần chứng minh rằng sau mỗi bước (khi tính toán C_i) ta có thể xây dựng được Q (từ hàng đợi Q đã có sẵn) bằng cách chèn thêm hoặc xóa bớt các phần tử của Q sao cho thỏa mãn các điều kiện đã nêu trong mệnh đề 3.
Q sẽ được xây dựng theo qui trình sau đây:
// Giá trị khởi tạo ban đầu của Q chỉ gồm 1 phần tử
Q = {n+1}
// Với i - hiện thời, i < I_r. Trước khi tính C_i.
1. Điều chỉnh đầu của Q: xóa bớt một số phần tử đầu của Q.
Tính f(i).
Nếu f(i) ≥ g(I₂,I₁) thì với mọi h ≤i ta có f(h) ≥ f(i) ≥g(I₂,I₁) do đó theo mệnh đề 1 ta có C_h(I₁) ≥ C_h(I₂), do đó I₁ có thể loại khỏi Q mà không ảnh hưởng đến tính chất (11) của Q. Ta tiếp tục quá trình trên, xóa bớt các phần tử thuộc bên phải của Q cho đến khi hoặc Q còn lại một phần tử hoặc tồn tại ≥1 thỏa mãn
g(I_r,I_r-1) > g(I_r-1,I_r-2) >.... > g(I_t+1,I_t) > f(i). Khi đó Q sẽ vẫn thỏa mãn (9), (10) và (11).
// Với i hiện thời. Sau khi tính C_i. Chuẩn bị cho bước tiếp theo.
2. Bổ xung i vào đuôi của Q sau khi đã điều chỉnh cái đuôi này.
Giả sử g(i,I_r) ≤ g(I_r,I_r-1) khi đó theo mệnh đề 2 ta có: với mọi h ≤i, ta sẽ có
C_h(I_r) ≥ C_h(i) hoặc C_h(I_r) ≥C_h(I_r-1). Do vậy sau khi bổ sung i vào đuôi của Q thì I_r sẽ thừa và ta có thể loại bỏ I_r mà phần còn lại của Q sau khi đã bổ sung i sẽ thỏa mãn điều kiện (11).
Như vậy ta sẽ xóa bớt một số phần tử đuôi của Q và bổ sung i vào vị trí này sao cho thỏa mãn điều kiện (10) của hàng đợi như sau:
g(i,I_r) > g(I_r,I_r-1) >.....
Bây giờ ta có thể viết lại toàn bộ lời giải bài toán bằng thuật toán 2 như sau:
Algorithm 2 (thời gian tính O(n)).
C_n+1 = 0; //gán giá trị ban đầu.
// chỉ số đầu (b) và đuôi (e) của Q. Gán Q = {n+1}
// Q được lưu trong mảng Array[0..10000] of integer
b = 0;e = 0;Q[b] = n+1; Qlength = 1;
For i:=n downto 1 do
begin
while (Qlength>1) and (f(i) ≥g(Q[b+1],Q[b]) do
begin Qlength = Qlength-1;
b = b+1;
end; // Xóa đầu của hàng đợi Q.
C_i = C_i(Q[b]);
while (Qlength>1) and (g(i,Q[e]) ≤ g(Q[e],Q[e-1])) do
begin Qlength = Qlength-1;
e = e-1;
end; //xóa đuôi Q.
//bổ sung i vào đuôi Q.
e:=e+1; Q[e] = i; Qlength=Qlength +1;
end;
Mệnh đề 4
Thuật giải trên có độ phức tạp O(n).
Thật vậy trong quá trình xây dựng Q, mỗi giá trị i chỉ có thể đưa vào hoặc đưa ra khỏi Q tối đa là 1 lần, do đó tổng thời gian xây dựng Q chỉ có thể là 2n. Mệnh đề được chứng minh.