Thuật giải tối ưu theo phương pháp quy
hoạch động như sau:
Gọi F(x,y) là số cây có trong hình chữ nhật
(0..x)*(0..y). Ta có thể tính F(x,y) với chi phí thời gian O(n).
Nếu tại hai
điểm (xi,yi) và (xj,yj) đều có cây,
và (xi,yi) nằm trái dưới (xj,yj) thì
số cây của hình chữ nhật có hai đỉnh là hai điểm trên có thể tính bằng công
thức:
F(xi,yi) + F(xj,yj) -
F(xi,yj) - F(xj,yi) + 1.
Nếu
(xi,yi) nằm trái trên (xj,yj) thì số
cây của có công thức gần tương tự:
F(xj,yi) +
F(xi,yj) - F(xj,yj) -
F(xi,yi) + 2
Chú ý là tại hai đỉnh còn lại đều không
có cây, theo cách trồng của Artemis.
Thuật toán của chúng ta như sau: với
mỗi cây tại điểm (x,y), coi nó là một đỉnh của hình chữ nhật cần cắt và duyệt
qua mọi cây là một đỉnh để tính số cây trong hình chữ nhật đó bằng các công thức
trên.
Thuật toán có chi phí thời gian là O(n2). Chi phí không
gian tối đa là O(n2) (để tính F(xi,yj) với mọi
cặp (i,j) là chỉ số các điểm trồng cây.
Ta có thể giảm chi phí không gian
xuống còn O(n) nếu để ý rằng khi cố định một đỉnh là
(xi,yi), ta chỉ cần biết F(xi,*),
F(*,yi), F(xj,yj) là đủ để tính mọi hình chữ
nhật nhận đỉnh đó làm đỉnh trên phải (cả 3 đều có thể lưu trữ bằng các mảng 1
chiều).
Bài 2: Thần Hermes
Sau đây là lời giải với độ phức
tạp O(n2).
Giả sử (x0,y0) là tọa độ điểm
xuất phát của sứ giả Hermes với (x0,y0)=(0,0). Các vị trí
cần gửi thông điệp theo thứ tự tiếp theo lần lượt là
(x1,y1), (x2,y2),...,
(xN,yN). Gọi các điểm này P0, P1,..,
PN.
Trước tiên ta nhận thấy rằng để tối ưu quãng đường đi được,
sứ giả Hermes sẽ luôn phải dịch chuyển giữa các điểm có toạ độ là các giá trị
nguyên xi và yj.
Ta gọi A[i,j] là quãng đường đi ngắn
nhất của sứ giả xuất phát từ điểm ban đầu P0, lần lượt đã gửi được thông điệp
cho các vị trí P1, P2,..., Pi và kết thúc đứng
tại vị trí (xi,yj). Tương tự gọi B[i,j] là quãng đường đi
ngắn nhất của sứ giả xuất phát từ điểm ban đầu P0, lần lượt đã gửi được thông
điệp cho các vị trí P1, P2,..., Pi và kết thúc
đứng tại vị trí (xj,yi).
Hình vẽ dưới cho ta hình dung
được quãng đường mô tả bởi A[i,j] và B[i,j].
Dễ dàng chứng minh được các
công thức sau đây:
Các giá trị ban đầu:
A[0,j] = d(x0,xj) = |xj - x0|
B[0,j] = d(y0,yj) = |yj - y0|
Các giá trị tiếp theo:
A[i+1,j] =
min{A[i,j]+d[xi,xi+1], B[i,i+1]+d[yi,yj]}
B[i+1,j] = min{B[i,j]+d[yi,yi+1],
A[i,i+1]+d[xi,xj]}
Đáp số của bài toán chính là minj {A[n,j],B[j,n]}
Bài 3: Đa giác (Polygon)
Ta giả sử đa giác P có N đỉnh là
v1,v2... vn, các đỉnh được liệt kê theo chiều
thuận.
Ta gọi vector (a,b) là vector cơ sở nếu không có điểm nguyên nào nằm
trên nó. Tức là UCLN(a,b)=1.
Các cạnh của P có thể biểu diễn bằng các vector
Ei = vi-vi-1 = (ai,bi),
coi v0 = vn. Đặt ui =
UCLN(ai,bi), chúng ta đưa vector Ei về vector
cơ sở ei = (ai/ui,bi/ui).
Dãy các vector {ui ei} được gọi là dãy vector cạnh của P,
vector ei gọi là cạnh cơ sở. Ta kí hiệu {ei} là E(P).
Ta có bổ đề sau: Một cạnh cơ sở của P=A+B phải là cạnh cơ sở của A hoặc của
B. Nếu cạnh đó không phải là cạnh cơ sở thì nó là tổng của 2 cạnh song song: một
của A và một của B.
Từ đó ra rút ra kết luận quan trọng: A là đa giác được
dùng để tạo nên P qua phép cộng Minkowski khi và chỉ khi dãy vector cạnh cơ sở
của A là tập con của dãy vector cạnh cơ sở của P, tức là dãy vector cạnh của A
có dạng {kiei}, trong đó i=1,2,..n, ki nguyên
và có thể bằng 0, thoả mãn điều kiện: tổng các vector đó phải bằng 0 (thì mới
tạo thành đa giác được).
Thuật toán của chúng ta tiến hành như sau:
Tạo
dãy E các vector cạnh cơ sở của P. E có n phần tử {ei}.
Tạo dãy C
các vector cạnh dạng Ci = {ki ei}:1≤
ki ≤ k, trong đó k = max UCLN(ai, bi). Số phần
tử của dãy C tối đa là m=kn.
Tạo dãy D có các phần tử là tổng của 2 phần tử
của dãy C. Như vậy D gồm tối đa m2/2 các phần tử có dạng
kiei+kjej.
Sắp xếp dãy C và dãy
D tăng dần theo toạ độ x.
Để tìm đa giác con A 4 đỉnh (tam giác) ta cần tìm
4 vector cạnh Ci, Cj, Cl, Ct của A
sao cho Ci + Cj + Cl + Ct = 0. Tìm
bằng cách xét tất cả các nhóm 4 phần tử của C ta mất chi phí cỡ
O(m4).
Cải tiến hơn, với mỗi phần tử Di của D, ta kiểm
tra các phần tử Dj sao cho Di + Dj = 0. Do D
sắp xếp theo tọa độ x nên ta có thể tìm kiếm nhị phân Dj (hoành độ x
của Dj là số đối của hoành độ x của Di). Độ phức tạp chỉ
còn (m2log(m2)).
Để tìm đa giác con A 3 đỉnh (tam
giác) ta cần tìm 3 vector cạnh Ci, Cj, Ct của A
sao cho Ci + Cj + Ct = 0. Duyệt mọi nhóm 3 phần
tử của C ta mất chi phí cỡ O(m3).
Ta có thể cải tiến bằng cách
với mỗi một phần tử của C, ta tìm kiếm nhị phân một phần tử của D để có tổng
bằng 0. Độ phức tạp được rút xuống còn O(m.logm2).
Để tìm đa giác
con A 2 đỉnh (đoạn thẳng) ta cần tìm 2 vector cạnh Ci, Cj
của A sao cho Ci + Cj = 0. Xét tất cả các cặp phần tử của
C ta được kết quả với chi phí thời gian cỡ O(m2). Nếu dùng tìm kiếm
nhị phân, chi phí chỉ còn là O(mlogm)
Nếu lưu trữ các phần tử của C,D bằng
bảng băm (hash table, với hàm băm là toạ độ x), các thao tác tìm kiếm chỉ mất
chi phí O(1), chúng ta còn cải thiện được hơn nữa.
Sau khi tìm được A, ta có
thể tìm được B một cách khá dễ dàng.
Ngày 2, IOI 2004
Bài 1: Empodia
Ta có một số nhận xét sau về một đoạn
khung (framed interval):
Giả sử phần tử đầu là x, phần tử cuối là y thì y =
x + L - 1, trong đó L là số phần tử của đoạn.
Tất cả các phần tử trong đoạn
là duy nhất và chứa tất cả các điểm nguyên thuộc [x,y].
x là phần tử nhỏ
nhất đoạn, y là phần tử lớn nhất đoạn.
Dựa vào các nhận xét đó, ta có thể
duyệt qua mọi cặp (i,j) của dãy input để kiểm tra xem đoạn gồm các phần tử
ai... aj có phải là đoạn khung (framed interval) không,
nếu phải thì nó có phải là đoạn khung tối đại (empodio) không? Thuật toán này có
độ phức tạp O(n3).
Người ta còn chứng minh được rằng: điểm đầu và
cuối của một đoạn đóng tối đại không nằm trong một đoạn đóng tối đại khác.
Do đó ta có thuật toán đơn giản hơn như sau: với mỗi phần tử i, ta tìm đoạn
đóng tối đại lớn nhất có điểm đầu là phần tử i. Nếu phần tử cuối của đoạn đóng
đó là j thì đoạn đóng tối đại tiếp theo sẽ bắt đầu từ phần tử j+1. Thuật toán
này có độ phức tạp O(n2).
Bài 2: Người nông dân (Farmer)
Phương pháp quy hoạch động.
Ta coi cánh đồng và dải đất
như nhau. Như vậy sẽ có M+K cánh đồng hay dải đất, gọi chung gi. Gọi
là ni là số cây bách của gi và vi là số cây
ôliu. Nếu gi là cánh đồng thì vi = ni, còn nếu
là dải đất thì vi = ni-1.
Như vậy ta có bài toán xếp
balô: có N=M+K đồ vật, đồ vật i có trọng lượng là ni và giá trị là
vi, hãy chọn một số đồ vật sao cho tổng trọng lượng - Q và tổng giá
trị là lớn nhất. Thuật giải quy hoạch động có chi phí thời gian O(Q.N) và chi
phí không gian O(Q) theo công thức:
F(i,j)= max( F(i-1,j) , F(i-1,j -
ni) + vi).
Trong đó F(i,j) là số cây ôliu có được nếu
được chọn tối đa j cây bách trên i cánh đồng đầu tiên.
Bài 3: Phidias
Phương pháp quy hoạch động.
Gọi A (x,y) là diện tích bị
lãng phí nếu cắt miếng đá hình chữ nhật có kích thước (1..x, 1..y). Nếu (x,y) là
kích thước một miếng đá cần cắt thì A (x,y)=0, ngược lại ta tạm gán A (x,y)=x*y.
Ngược lại, xét mọi nhát cắt dọc độ rộng c =1... x-1 và cắt ngang độ rộng c =
1..y-1. Ta có công thức quy hoạch động:
A (x,y) = min (A (x,y), A (c,y) + A
( x-c,y)) nếu c là lát cắt dọc
A (x,y) = min (A (x,y), A (x,c) + A (x,y-c))
nếu c là lát cắt ngang.
Thuật toán quy hoạch động có chi phí thời gian
O(N3) và chi phí không gian O(N2).