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 (x_i,y_i) và (x_j,y_j) đều có cây, và (x_i,y_i) nằm trái dưới (x_j,y_j) 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(x_i,y_i) + F(x_j,y_j) - F(x_i,y_j) - F(x_j,y_i) + 1.
Nếu (x_i,y_i) nằm trái trên (x_j,y_j) thì số cây của có công thức gần tương tự:
F(x_j,y_i) + F(x_i,y_j) - F(x_j,y_j) - F(x_i,y_i) + 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(n²). Chi phí không gian tối đa là O(n²) (để tính F(x_i,y_j) 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à (x_i,y_i), ta chỉ cần biết F(x_i,*), F(*,y_i), F(x_j,y_j) 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(n²).
Giả sử (x₀,y₀) là tọa độ điểm xuất phát của sứ giả Hermes với (x₀,y₀)=(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à (x₁,y₁), (x₂,y₂),..., (x_N,y_N). Gọi các điểm này P₀, P₁,.., P_N.
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 x_i và y_j.
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í P₁, P₂,..., P_i và kết thúc đứng tại vị trí (x_i,y_j). 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í P₁, P₂,..., P_i và kết thúc đứng tại vị trí (x_j,y_i).
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à v₁,v₂... v_n, 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 E_i = v_i-v_i-1 = (a_i,b_i), coi v₀ = v_n. Đặt u_i = UCLN(a_i,b_i), chúng ta đưa vector E_i về vector cơ sở e_i = (a_i/u_i,b_i/u_i). Dãy các vector {u_i e_i} được gọi là dãy vector cạnh của P, vector e_i gọi là cạnh cơ sở. Ta kí hiệu {e_i} 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 {k_ie_i}, trong đó i=1,2,..n, k_i 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ử {e_i}.
Tạo dãy C các vector cạnh dạng C_i = {k_i e_i}:1≤ k_i ≤ k, trong đó k = max UCLN(a_i, b_i). 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 m²/2 các phần tử có dạng k_ie_i+k_je_j.
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 C_i, C_j, C_l, C_t của A sao cho C_i + C_j + C_l + C_t = 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(m⁴).
Cải tiến hơn, với mỗi phần tử D_i của D, ta kiểm tra các phần tử D_j sao cho D_i + D_j = 0. Do D sắp xếp theo tọa độ x nên ta có thể tìm kiếm nhị phân D_j (hoành độ x của D_j là số đối của hoành độ x của D_i). Độ phức tạp chỉ còn (m²log(m²)).
Để tìm đa giác con A 3 đỉnh (tam giác) ta cần tìm 3 vector cạnh C_i, C_j, C_t của A sao cho C_i + C_j + C_t = 0. Duyệt mọi nhóm 3 phần tử của C ta mất chi phí cỡ O(m³).
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.logm²).
Để tìm đa giác con A 2 đỉnh (đoạn thẳng) ta cần tìm 2 vector cạnh C_i, C_j của A sao cho C_i + C_j = 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(m²). 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ử a_i... a_j 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(n³).
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(n²).
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 g_i. Gọi là n_i là số cây bách của g_i và v_i là số cây ôliu. Nếu g_i là cánh đồng thì v_i = n_i, còn nếu là dải đất thì v_i = n_i-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à n_i và giá trị là v_i, 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 - n_i) + v_i).
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(N³) và chi phí không gian O(N²).

Hướng dẫn giải đề thi IOI 2004