Bài 1: Trò chơi với dãy số
Phát biểu lại:
Cho hai dãy số nguyên có n phần tử b1, b2,..., bn và c1, c2,..., cn Yêu cầu: Chọn ra hai số nguyên từ hai dãy bi và cj sao cho |bi + cj| có giá trị nhỏ nhất. Giới hạn: n <= 105 Các số nguyên trong hai dãy đã cho có giá trị tuyệt đối không quá 109.
Thuật toán:
Sắp xếp lại hai dãy số theo thứ tự tăng dần.
Dùng hai biến chạy i và j. Biến i xuất phát từ đầu dãy b, biến j xuất phát từ cuối dãy c. Bước vào vòng lặp, ta xét giá trị bi + cj, chia ra hai trường hợp:
bi + cj >= 0: cần giảm j (vì nếu tăng giá trị i sẽ không thu được kết quả nhỏ hơn) bi + cj < 0: cần tăng i (vì nếu giảm giá trị j sẽ không thu được kết quả nhỏ hơn) Mã giả của bước 2 như sau:
i <- 1; j <- n; r <- oo; while (i<=n AND j>=1) do r=min(r, |bi + cj|) if (bi + cj >= 0) j <- j-1; else i<- i+1;           
return r; //r là kết quả cần tìm.
Thời gian thực hiện: Bước 1 (sắp xếp) có thời gian thực hiện O(nlogn). Bước 2 có thời gian thực hiện O(n) do hai biến chạy i và j dừng tại mỗi phần tử nhiều nhất một lần. Do đó toàn bộ thuật toán có thời gian thực hiện O(nlogn).
Nhận xét: sắp xếp lại dãy số và sử dụng biến chạy là kỹ thuật thường gặp khi xử lý dãy số. Thuật toán O(nlogn) trên đây đủ thời gian để đạt được trọn điểm qua các test. Dùng thuật toán O(n2) đơn giản: xét tất cả các cặp số, cũng có thể đạt được 60 điểm (theo đề bài đã nêu).
Bài 2: Lò cò
Ta đưa bài toán về dạng đồ thị: xem mỗi vòng tròn là một đỉnh của đồ thị. Đậy là một đồ thị có hướng và quy tắc xác định tập cạnh như sau: Nếu có 3 đỉnh i, j, k sao cho ai + aj = ak thì có cạnh (i, k) và cạnh (j, k). Nhận xét: đồ thị này không có chu trình, hay ta nói đồ thị có thứ tự topo. Bài toán trở thành một bài toán cơ bản: tìm đường đi dài nhất trên đồ thị có hướng không có chu trình. Một thứ tự topo hiển nhiên cho tập đỉnh chính là thứ tự tăng dần của các số. Xác định tập cạnh cho đồ thị cũng là một vấn đề quan trọng. Vì giới hạn số đỉnh là 1000 nên việc dùng vòng lặp O(n3) xét tất cả các bộ ba (i, j, k) để tìm tập cạnh của đồ thị là không khả thi. Ta sử dụng nhận xét đơn giản sau: nếu ai + aj > ak thì ai + aj’ > ak với  j’ > j. Từ đó có thuật toán sau:
Sắp xếp lại dãy số theo thứ tự tăng dần
Xác định tập cạnh của đồ thị. Mã giả của bước 2:
for i <- 1 to n-2 do t <- i+2; for j <- i+1 to n-1 do for k <- t to n do if ai + aj = ak xác định được cạnh (i, k) và (j, k) else if ai + aj < ak break; t=k;
Dùng phương pháp qhđ để tìm đường đi dài nhất trên đồ thị. Mã giả của bước 3:
r=-1; for i <- 1 to n do f[i]<-1; for j<-1 to i-1 do if ( (j, i) là cạnh) AND (f[j]+1>f[i]) f[i]<-f[j]+1; if (f[i]>r) r<-f[i];                      //r là kết quả
Thời gian thực hiện: Bước 1 có độ phức tạp O(nlogn). Trong bước 2, mặc dù có 3 vòng lặp, nhưng giá trị k sẽ luôn chỉ chạy qua dãy số đúng một lần (do mỗi lần được bắt đầu từ biến độc lập t), do đó bước 2 có độ phức tạp O(n2). Bước 3 cũng có độ phức tạp O(n2). Vậy tổng thời gian thực hiện của thuật toán là O(n2).
Nhận xét: bài toán này kết hợp giữa một bài tập cơ bản về đồ thị (tìm đường đi dài nhất trên đồ thị có hướng không có chu trình) và việc