Phân tích: Erdős–Szekeres

Thu thập thông tin

Mấu chốt của bài toán này là trích xuất càng nhiều thông tin càng tốt từ các dãy \(A[i]\) và \(B[i]\). Chúng ta sẽ thu thập thông tin dưới dạng các bất đẳng thức giữa các phần tử khác nhau của dãy \(X\).

Đầu tiên, nhận thấy rằng nếu chúng ta có hai chỉ số \(i < j\) và \(A[i] \ge A[j]\), thì \(X[i] > X[j]\). Thật vậy, nếu ngược lại \(X[i] < X[j]\), thì dãy con tăng độ dài \(A[i]\) kết thúc tại \(X[i]\) có thể được kéo dài bằng cách thêm \(X[j]\) vào cuối để có được một dãy con tăng kết thúc tại \(X[j]\), và khi đó ta sẽ có \(A[j] \ge A[i] + 1\). Điều này cho phép chúng ta thêm một số bất đẳng thức mà \(X\) phải thỏa mãn. Chúng ta có thể thêm các bất đẳng thức tương tự cho \(B\) — nếu \(i < j\) và \(B[i] \le B[j]\), thì \(X[i] < X[j]\).

Tuy nhiên, những bất đẳng thức này là chưa đủ để khôi phục \(X\). Ví dụ, nếu ta lấy \(A[i] = i + 1\) và \(B[i] = N - i\), ta không thu được bất đẳng thức nào để xem xét, nhưng đồng thời không phải mọi hoán vị \(X\) đều hoạt động. Vấn đề là trong khi chúng ta biết cần làm gì với \(X\) để không có dãy con nào dài hơn tồn tại, chúng ta vẫn cần đảm bảo rằng các dãy con đủ dài có tồn tại.

Điều này tương đối đơn giản để thực hiện. Nếu \(A[i] > 1\), thì dãy con tăng kết thúc tại \(X[i]\) được hình thành bằng cách kéo dài một dãy nào đó có độ dài \(A[i] - 1\). Điều này có nghĩa là \(X[i]\) phải lớn hơn \(X[j]\) đối với một số \(j < i\) có \(A[j] = A[i] - 1\). Tập hợp các bất đẳng thức trước đó đảm bảo rằng trong số tất cả các \(j\) như vậy (tức là \(j < i\) và \(A[j] = A[i] - 1\)), phần tử có \(X[j]\) nhỏ nhất là \(j\) lớn nhất. Do đó, chỉ cần tìm \(j\) lớn nhất với \(j < i\) và \(A[j] = A[i]-1\) rồi thêm \(X[j] < X[i]\) vào tập bất đẳng thức của chúng ta. Chúng ta lại làm điều tương tự cho \(B\) (với \(B[j] = B[i] - 1\) và \(j < i\), ta có \(X[j] > X[i]\)).

Sử dụng thông tin

Lưu ý rằng các bất đẳng thức chúng ta có thực sự đủ để đảm bảo rằng bất kỳ dãy \(X\) nào thỏa mãn chúng sẽ dẫn đến \(A\) và \(B\) mà chúng ta mong muốn. Khá dễ dàng để kiểm tra tập bất đẳng thức thứ nhất đảm bảo các giá trị \(A\) và \(B\) sẽ không lớn hơn mong muốn, trong khi tập bất đẳng thức thứ hai đảm bảo chúng sẽ đủ lớn.

Bây giờ chúng ta đã đưa bài toán về việc tìm hoán vị nhỏ nhất về mặt từ điển thỏa mãn một tập hợp các bất đẳng thức cho trước. Để tìm kết quả nhỏ nhất về mặt từ điển, trước hết chúng ta quan tâm đến việc giảm thiểu giá trị đầu tiên trong \(X\). Để đạt được mục tiêu này, chúng ta chỉ đơn giản là duyệt qua tất cả các bất đẳng thức mà giá trị đầu tiên trong \(X\) phải thỏa mãn (tức là duyệt qua tất cả các phần tử mà chúng ta biết là nhỏ hơn, sau đó là tất cả các phần tử nhỏ hơn các phần tử đó, v.v.). Chúng ta có thể làm điều này bằng cách sử dụng DFS. Sau khi biết có bao nhiêu phần tử của \(X\) phải nhỏ hơn \(X[0]\), chúng ta có thể gán giá trị nhỏ nhất có thể (số lượng này + 1) cho \(X[0]\). Bây giờ chúng ta cần gán các số nhỏ hơn \(X[0]\) cho tất cả các phần tử này, theo cách nhỏ nhất về mặt từ điển.

Lưu ý rằng cách chúng ta thực hiện việc gán này sẽ không ảnh hưởng đến các phần tử khác (vì tất cả chúng đều sẽ lớn hơn \(X[0]\), và do đó cũng lớn hơn mọi thứ chúng ta gán ngay bây giờ). Do đó, chúng ta có thể gán tập hợp các phần tử này sao cho nó nhỏ nhất về mặt từ điển. Điều này có nghĩa là lấy phần tử sớm nhất trong số các phần tử này và lặp lại quy trình tương tự một cách đệ quy (tìm tất cả các phần tử nhỏ hơn nó, gán giá trị thích hợp, đệ quy). Lưu ý rằng khi một số giá trị đã được gán, chúng ta cần tính đến điều đó khi gán các giá trị mới (ví dụ, nếu chúng ta đã gán 1, 3 và 10; và bây giờ chúng ta biết rằng một phần tử chúng ta đang xem xét lớn hơn 4 phần tử khác, giá trị nhỏ nhất chúng ta có thể gán cho nó là 7).

Một quy trình đệ quy như vậy sẽ cho phép chúng ta giải quyết bài toán. Đối với mỗi phần tử, chúng ta sẽ duyệt qua đồ thị các bất đẳng thức để tìm tất cả các phần tử nhỏ hơn nó (thời gian \(O(M)\) nếu chúng ta thực hiện DFS, trong đó \(M\) là số lượng bất đẳng thức), sau đó xem giá trị nhỏ nhất có thể gán là bao nhiêu (\(O(N)\) với tìm kiếm tuyến tính, cũng có thể giảm xuống \(O(\log N)\) nhưng không cần thiết), và đệ quy. Điều này cho chúng ta thời gian \(O(N^3)\) trong trường hợp xấu nhất — đủ tốt cho Small dataset, nhưng rủi ro cho Large dataset.

Nén thông tin

Theo quy trình chính xác ở trên, chúng ta có thể kết thúc với \(O(N^2)\) bất đẳng thức. Điều này sẽ là quá nhiều đối với chúng ta (ít nhất là đối với Large dataset), vì vậy chúng ta sẽ nén lại một chút.

Vấn đề nằm ở các bất đẳng thức loại thứ nhất — đối với các chỉ số nhỏ hơn một \(i\) cho trước, có thể có nhiều chỉ số có \(A\) lớn hơn hoặc bằng \(A[i]\). Tuy nhiên, một mẹo chúng ta có thể sử dụng là chỉ lấy một bất đẳng thức — tìm \(j < i\) lớn nhất với \(A[j] = A[i]\), và chỉ chèn bất đẳng thức \(X[j] > X[i]\).

Bất kỳ \(k < j\) nào khác với \(A[k] = A[i]\) sẽ được suy ra từ tính chất bắc cầu — sẽ có một chuỗi các chỉ số với \(A\) bằng \(A[i]\) kết nối \(k\) với \(i\). Bất kỳ \(k\) nào với \(A[k] > A[i]\) cũng sẽ được suy ra, vì \(X[k]\) sẽ phải lớn hơn một số \(X[l]\) với \(A[l] = A[i]\) và \(l < k\) (và do đó \(l < i\)). Điều này có nghĩa là chúng ta có thể giảm tập hợp các bất đẳng thức xuống còn \(O(N)\), có nghĩa là mỗi bước duyệt DFS sẽ chỉ mất thời gian \(O(N)\), và giải pháp cho toàn bộ bài toán sẽ chạy trong \(O(N^2)\).

Sự thật thú vị: Bài toán này cũng có thể được giải trong \(O(N \log N)\). Bạn có thể tìm ra cách không?

Dựa trên phân tích chính thức của Google Code Jam.