Đề - Đáp án Tin học 10 - Bài 3 - Olympic 30/4/2012 - Đoạn hoán vị

Cho dãy số A gồm N số nguyên dương a1, a2,.., aN, mỗi phần tử chỉ xuất hiện đúng 1 lần. (1<=N, ai<=10^5).
YC: Hãy tìm đoạn dài nhất gồm các phần tử trong dãy trên tạo thành một hoán vị các phần tử của tập {1, 2,..., K} (1<=K<=N). Nếu không tìm dc thì trả về 0, ngược lại trả về vị trí bắt đầu imax và độ dài dmax.
Ví dụ:

PASWAP.INP	PASWAP.OUT
7 10 9 3 4 1 2 8	3 4

Lời giải O(N^3)
procedure try;
var i,j
begin
   for i...
       for j...
           if isOK(i,j) then update; //O(N)
Hai vòng lặp for có dpt O(N^2), kiểm tra xem đoạn a[i],.. a[j] có thỏa mãn hoán vị có dpt O(N). Đpt tổng thể là O(N^3).

Lời giải O(N^2)
Bằng cách kết hợp cấp số cộng, tổng tích lũy, chi phí kiểm tra isOK(i,j) chỉ còn O(1).

Lời giải O(NlogN)
Kết hợp Binary Search.