Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
Diễn đàn arrow Thư viện arrow Đề thi arrow IOI (thi quốc tế) arrow Hướng dẫn giải đề thi IOI 2004
Hướng dẫn giải đề thi IOI 2004 In E-mail
(13 votes)
Người viết: Thầy Nguyễn Thanh Tùng   
21/04/2008

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


Nguyễn Thanh Tùng

Ngày 1 - IOI 2004
Bài 1: Nữ thần Artemis
Bài toán có thuật giải đơn giản nhưng độ phức tạp thời gian lớn là: xét mọi hình chữ nhật có 2 đỉnh là 2 cây i và j, đếm số cây trong hình chữ nhật đó (bằng các phép so sánh toạ độ đơn giản) và chọn hình chữ nhật tối ưu. Dễ thấy độ phức tạp thời gian của thuật giải là O(n3) và độ phức tạp không gian là O(n) (chỉ dùng lưu toạ độ các điểm trồng cây).

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).

 
Tiếp >