Phân tích: Swinging Wild

Chuyển sang bài toán đồ thị

Để phân tích bài toán, hãy bắt đầu bằng việc mô tả trạng thái mà chúng ta có thể ở tại bất kỳ thời điểm nào trong quá trình băng qua đầm lầy. Dễ thấy rằng chúng ta cần hai thông tin để mô tả trạng thái này: chúng ta đang giữ sợi dây nào, và chúng ta đang giữ nó ở khoảng cách bao xa so với gốc.

Khi đã có mô tả như vậy, chúng ta có thể đóng khung bài toán thành bài toán tìm đường đi trong đồ thị. Chúng ta bắt đầu ở trạng thái \((0, d_0)\), và chúng ta muốn đến bất kỳ trạng thái \((i, p)\) nào mà \(p + d_i \ge D\) (để đơn giản, chúng ta cũng có thể thêm một sợi dây thứ \(N+1\) giả định tại nơi tình yêu của bạn đứng và yêu cầu chúng ta đạt đến trạng thái \((N, p)\) với bất kỳ \(p\) nào).

Các bước chuyển giữa các trạng thái (hay nói cách khác, các cạnh trong đồ thị) là các lần đu dây được phép. Nếu chúng ta hiện đang giữ dây \(i\) ở khoảng cách \(p\) tính từ gốc, chúng ta có thể đu đến bất kỳ dây \(j\) nào có gốc nằm trong khoảng \([d_i - p, d_i + p]\), và độ dài mới (khoảng cách từ gốc dây \(j\) mà ta nắm được) sẽ là giá trị nhỏ nhất của \(|d_i - d_j|\) và \(l_j\). Lưu ý rằng công dụng duy nhất của việc leo lên một sợi dây là để bắt một sợi dây khác vốn quá ngắn để nằm trong quỹ đạo đu của chúng ta - vì vậy chúng ta ngầm định bao gồm nó trong các bước chuyển được mô tả ở trên (và do đó không cần thêm các bước chuyển từ \((i, p)\) sang \((i, p-1)\)).

Giới hạn số lượng nút

Như đã mô tả, chúng ta có thể có một số lượng lớn các trạng thái (vì có rất nhiều độ dài dây có thể có). Một sự thật quan trọng cần nhận thấy là phần thứ hai của trạng thái (khoảng cách từ gốc) được xác định duy nhất bởi sợi dây trước đó mà chúng ta đã từ đó đến đây; và nó độc lập với việc trước đó chúng ta đã giữ sợi dây kia ở đâu (giả sử chúng ta giữ nó đủ xa để thực sự đạt được trạng thái này). Điều này có nghĩa là có tối đa \(N^2\) trạng thái mà chúng ta cần xem xét, vì mỗi trạng thái được xác định bởi một cặp chỉ số dây leo.

Bây giờ chúng ta có thể giải quyết Test set 1. Chúng ta có một đồ thị với \(N^2\) nút và tối đa \(N\) cạnh từ mỗi nút, và chúng ta muốn kiểm tra xem có đường đi giữa hai nút nào đó hay không. Vì chúng ta có tối đa \(N^3\) cạnh tổng cộng, bất kỳ thuật toán duyệt đồ thị tiêu chuẩn nào (như BFS hoặc DFS) cũng sẽ cho phép chúng ta giải quyết bài toán.

Giới hạn số lượng cạnh

Đối với Test set 2, một giải pháp \(O(N^3)\) sẽ không đạt yêu cầu, và chúng ta cần tinh tế hơn một chút. Có một số mẹo có thể sử dụng để giảm độ phức tạp. Một là tận dụng lại thực tế là trạng thái mục tiêu chỉ phụ thuộc vào sợi dây chúng ta bắt đầu, chứ không phụ thuộc vào vị trí chúng ta giữ nó. Điều này có nghĩa là thực tế chỉ có tối đa \(N\) cạnh từ một sợi dây nhất định - nếu chúng ta bắt được sợi dây \(j\) từ sợi dây \(i\) khi giữ nó ở vị trí \(A\), chúng ta không cần kiểm tra cạnh này khi xem xét các bước di chuyển từ sợi dây \(i\) được giữ ở vị trí \(B\) (vì ngay cả khi chúng ta đến được sợi dây \(j\), chúng ta cũng sẽ đến một trạng thái mà chúng ta đã phân tích rồi). Do đó, chúng ta cần thực hiện tối đa \(N^2\) lần duyệt cạnh để thăm tất cả các nút có thể đến được. Có nhiều kỹ thuật khác nhau để cài đặt điều này (ví dụ, với mỗi sợi dây, chúng ta có thể sắp xếp các sợi dây khác theo khoảng cách từ sợi dây này, và mỗi lần xử lý danh sách này từ sợi dây gần nhất và loại bỏ tất cả các cạnh đã duyệt), chúng tôi khuyến khích bạn khám phá các phương án.

Một phương án thay thế cho bài toán lớn

Một phương án thay thế là nhận thấy một sự thật khác - phần vị trí của trạng thái (nghĩa là khoảng cách từ gốc mà bạn giữ sợi dây) không bao giờ tăng lên. Điều này là do nếu bạn đu từ dây \(i\) sang dây \(j\), điều đó có nghĩa là bạn đã giữ dây \(i\) cách gốc ít nhất \(|d_i - d_j|\), trong khi lượng này đồng thời là giới hạn trên cho vị trí bạn sẽ giữ dây \(j\).

Điều này có nghĩa là chúng ta có thể sử dụng thuật toán Dijkstra để tìm, cho mỗi sợi dây, vị trí tối đa mà chúng ta có thể giữ sợi dây này - chúng ta coi vị trí dây giảm dần như thời gian tăng dần, và trong mỗi bước, chúng ta phân tích những độ dài nào chúng ta có thể đạt được cho mỗi sợi dây bằng cách di chuyển từ sợi dây hiện tại, sau đó chọn sợi dây có độ dài lớn nhất để phân tích. Điều này sẽ cho chúng ta một giải pháp \(O(N^2 \log N)\), đủ nhanh.

Tăng tốc hơn nữa

Một sự thật thú vị là bài toán này có thể được giải nhanh hơn \(O(N^2)\), mặc dù bạn không cần nhận ra điều này để giải các bộ dữ liệu của chúng tôi. Điểm mấu chốt ở đây là nếu bạn có thể băng qua đầm lầy, bạn luôn có thể làm điều đó mà không cần đi ngược lại (nghĩa là bạn luôn bắt một sợi dây ở phía trước, không bao giờ đu ngược lại). Một cách dễ dàng để sử dụng quan sát này là sửa đổi thuật toán Dijkstra đã đề cập ở trên để xử lý các dây leo từ đầu đến cuối, điều này sẽ chuyển \(O(N^2 \log N)\) thành \(O(N^2)\).

Để giảm xuống \(O(N)\), chúng ta cần thêm một mẹo nữa. Lưu ý rằng nếu chúng ta có thể chạm tới một sợi dây, chúng ta sẽ nhận được vị trí lớn nhất (nghĩa là tốt nhất) nếu chúng ta đu tới nó từ một sợi dây càng xa càng tốt. Khi chúng ta chỉ di chuyển về phía trước, điều này có nghĩa là ngay khi chúng ta có thể chạm tới bất kỳ sợi dây cụ thể nào, chúng ta nên ghi lại vị trí đạt được và không bao giờ cần kiểm tra bất kỳ cách nào khác để chạm tới nó. Điều này có nghĩa là chúng ta có thể có một giải pháp \(O(N)\) bằng cách theo dõi sợi dây chúng ta đang xử lý và sợi dây xa nhất chúng ta đã đạt tới cho đến nay, và từ mỗi sợi dây chỉ cố gắng cập nhật các sợi dây mà chúng ta chưa chạm tới. Vì mỗi sợi dây sẽ được cập nhật tối đa một lần và được đọc tối đa một lần, chúng ta sẽ thực hiện \(O(N)\) thao tác.

Chúng tôi khuyến khích bạn hoàn thiện các chi tiết và cố gắng chứng minh bổ đề "không bao giờ đi ngược lại" - nó không hề tầm thường!

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