Phân tích

Bài toán này cho phép chúng ta tự do trong cách tiếp cận, vì chỉ cần đưa ra bất kỳ dãy chiều cao nào khớp với dữ liệu đầu vào là được. Dưới đây là một trong những giải pháp khả thi.

Đầu tiên, hãy lưu ý rằng nếu từ đỉnh \(3\) chúng ta thấy đỉnh \(7\) là cao nhất, thì từ các đỉnh \(4, 5\) và \(6\), chúng ta chắc chắn không thể nhìn xa hơn đỉnh \(7\). Điều này là do các đỉnh này phải nằm dưới đường thẳng nối đỉnh \(3\) và đỉnh \(7\), và không có đỉnh nào sau đỉnh \(7\) nằm trên đường thẳng đó (nếu không nó sẽ trông cao hơn từ đỉnh \(3\)). Nếu điều kiện này không được thỏa mãn, chúng ta có thể kết luận là "Impossible".

Ý tưởng thuật toán

Chúng ta có thể xây dựng chiều cao bằng cách sử dụng đệ quy hoặc xử lý theo từng khoảng.

1. Bắt đầu với đỉnh \(1\), sau đó đi đến đỉnh cao nhất nhìn thấy từ nó, rồi đỉnh cao nhất nhìn thấy từ đỉnh đó, v.v. Gán cho tất cả các đỉnh trong chuỗi này chiều cao tối đa là \(10^9\). Lưu ý chuỗi này chắc chắn kết thúc tại đỉnh \(N\).
2. Bây giờ, xét tuần tự đỉnh đầu tiên \(A\) mà chúng ta chưa gán chiều cao. Vì đây là đỉnh chưa gán đầu tiên, nên đỉnh trước đó (\(A-1\)) chắc chắn đã được gán. Gọi \(B\) là đỉnh trông cao nhất từ \(A-1\). Chúng ta biết rằng chuỗi các đỉnh cao nhất bắt đầu từ \(A\) phải kết thúc hoặc đi qua \(B\) - nó không thể nhảy qua \(B\) vì toàn bộ chuỗi phải nằm dưới đường thẳng nối \((A-1)\) và \(B\). Nếu chuỗi này nhảy qua \(B\), ta trả về "Impossible".
3. Giả sử đường thẳng nối \((A-1)\) và \(B\) có độ dốc \(T\). Cách xây dựng của chúng ta sẽ đảm bảo \(T\) là một số nguyên (độ dốc của đường thẳng đầu tiên là \(0\)). Chúng ta muốn tất cả các đỉnh trong chuỗi bắt đầu từ \(A\) nằm trên một đường thẳng đi qua đỉnh \(B\) và có độ dốc \(T+1\). Điều này xác định duy nhất chiều cao của các đỉnh trong chuỗi.
4. Làm như vậy không phá hỏng những quan hệ nhìn thấy đã xây dựng trước đó, vì toàn bộ đường thẳng mới nằm dưới đường nối \((A-1)\) với \(B\). Trong chuỗi mới, đối với mỗi đỉnh, đỉnh trông cao nhất sẽ là đỉnh kế tiếp của chuỗi: mọi đỉnh trong chuỗi cùng nằm trên một đường thẳng, không có đỉnh nào đã được gán chiều cao nằm xen giữa \(A\) và \(B\), còn mọi đỉnh sau \(B\) đều vô hình vì chúng nằm dưới đường nối \((A-1)\) với \(B\), và do đó càng nằm dưới đường nối \(A\) với \(B\) — đường sau có độ dốc lớn hơn.

Chứng minh tính đúng đắn

Tại bất kỳ thời điểm nào của quá trình xây dựng:

• Nếu giả định các đỉnh chưa xây dựng không gây cản trở (ví dụ: có chiều cao bằng \(0\)), thì với mỗi đỉnh đã xây dựng, đỉnh trông cao nhất chính là đỉnh chúng ta mong đợi.
• Với bất kỳ đỉnh \(A\) đã xây dựng nào, hoặc \(A+1\) cũng đã được xây dựng, hoặc không có đỉnh nào giữa \(A\) và đỉnh nhìn thấy từ \(A\) được xây dựng chiều cao.
• Việc thêm một chuỗi mới vẫn duy trì các bất biến này; bởi vậy, khi quá trình kết thúc, mọi quan hệ nhìn thấy đều đúng.

Do đó, phép dựng hoạt động. Ta tăng độ dốc thêm một sau mỗi chuỗi, nên cuối cùng độ dốc không vượt quá \(N\). Vì thế, chiều cao nhỏ nhất có thể xuất hiện là \(10^9-N^2\); mọi chiều cao đều dương.

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