Phân tích

Tập dữ liệu nhỏ (Small dataset)

Lưu ý rằng trong bài toán này, chúng ta coi các hành khách như một "người chơi" duy nhất trong một trò chơi, và giả định tất cả họ hợp tác để trả tổng số tiền ít nhất có thể cho thành phố. Điều này có nghĩa là không quan trọng ai thực sự trả tiền cho một thẻ vào ga cụ thể. Đặc biệt, khi tàu rời một ga, phí trên mỗi thẻ vào ga trên tàu tăng lên (thêm \(N - i\), trong đó \(i\) là số ga mà thẻ này đã đi qua cho đến nay). Vì tất cả hành khách cuối cùng đều phải rời tàu điện ngầm, tất cả các thẻ vào ga đều sẽ phải được thanh toán — vì vậy chúng ta có thể trừ ngay số tiền này khỏi "tổng" của hành khách và tiếp tục.

Chừng nào chưa có ai rời tàu, không cần phải trao đổi thẻ vào ga. Chỉ khi có ai đó cần rời đi, các hành khách (cùng với những người vừa mới vào) cần tập hợp lại và tìm xem những hành khách vừa rời đi sẽ mang theo thẻ vào ga nào. Họ nên chọn những thẻ vào ga đã ở trên tàu trong thời gian ngắn nhất cho đến nay, vì ở mỗi điểm dừng tiếp theo, giá cho một thẻ vào ga như vậy sẽ lớn hơn giá cho bất kỳ thẻ nào đã ở trên tàu lâu hơn (vì giá là \(N - i\), với \(i\) là số ga thẻ đã đi). Điều này có nghĩa là tại mỗi ga, hành khách nên gộp tất cả các thẻ lại với nhau, và sau đó bất cứ ai muốn rời đi sẽ lấy các thẻ vào ga có khoảng cách nhỏ nhất.

Đối với tập dữ liệu nhỏ, một cách cài đặt ngây thơ của thuật toán này sẽ hoạt động. Chúng ta có thể xử lý từng ga một, giữ một hàng đợi ưu tiên (hoặc thậm chí chỉ là bất kỳ cấu trúc lưu trữ nào) của các thẻ vào ga hiện có. Khi bất kỳ ai muốn rời đi, chúng ta lặp qua danh sách để tìm thẻ đã ở trên tàu trong thời gian ngắn nhất, cộng chi phí của nó vào tổng chi phí của hành khách và xóa nó khỏi danh sách. Chúng ta cũng cần tính toán số tiền mà hành khách đáng lẽ phải trả (theo vé gốc), nhưng may mắn là điều đó rất dễ dàng.

Tập dữ liệu lớn (Large dataset)

Tập dữ liệu lớn cần tinh tế hơn một chút. Với lượng hành khách và số ga khổng lồ, chúng ta cần tránh xử lý các sự kiện không cần thiết. Trước hết, chúng ta chỉ nên xử lý các ga mà tại đó có người muốn vào hoặc ra. Điều này sẽ khiến chúng ta chỉ xử lý \(O(M)\) ga, ít hơn nhiều so với \(N\) ga nếu xử lý tuần tự. Hơn nữa, chúng ta nên tránh xử lý từng hành khách một.

Để đạt được mục tiêu này, hãy nhận thấy rằng thứ tự mà chúng ta muốn đưa thẻ ra cho hành khách thực chất là một ngăn xếp (stack) LIFO — thẻ nào vào sau cùng sẽ ra trước tiên. Vì vậy, chúng ta có thể giữ thông tin về các thẻ vào ga hiện có trên tàu trong một ngăn xếp. Bất cứ khi nào một nhóm hành khách mới vào, chúng ta lấy thẻ vào ga của họ và đưa chúng vào ngăn xếp (dưới dạng một phần tử, lưu trữ số lượng thẻ và ga vào). Bất cứ khi nào bất kỳ nhóm nào muốn rời đi, chúng ta duyệt qua ngăn xếp. Nếu nhóm thẻ trên cùng đủ lớn, chúng ta chỉ cần giảm kích thước của nó, trả tiền cho những gì chúng ta đã lấy và tiếp tục. Nếu không, chúng ta lấy toàn bộ nhóm thẻ, trả tiền cho nó, giảm số lượng thẻ chúng ta cần theo kích thước của nhóm đó và tiếp tục duyệt ngăn xếp.

Thuật toán này sẽ chỉ mất tổng cộng \(O(M)\) thời gian để xử lý tất cả hành khách — chúng ta sẽ đẩy vào ngăn xếp tối đa \(M\) lần, vì vậy chúng ta sẽ lấy toàn bộ một nhóm từ ngăn xếp tối đa \(M\) lần, và mỗi nhóm hành khách rời đi sẽ làm giảm kích thước của một nhóm (không lấy toàn bộ nhóm thẻ) tối đa một lần, vì vậy tổng cộng — tối đa \(M\) thao tác như vậy trong toàn bộ thuật toán. Ngoài ra, chúng ta cần sắp xếp tất cả các sự kiện (một nhóm hành khách vào hoặc ra) trước, vì vậy chúng ta có thể giải quyết toàn bộ bài toán trong \(O(M \log M)\).

Cuối cùng, khi cài đặt, cần phải cẩn thận. Do số lượng ga và hành khách lớn, chúng ta phải sử dụng số học modulo cẩn thận vì — như mọi khi với số học modulo — chúng ta có nguy cơ bị tràn số. Đặc biệt, bất cứ khi nào chúng ta nhân ba số (khi tính toán số tiền phải trả cho một nhóm vé), chúng ta cần lưu ý áp dụng modulo sau khi nhân hai số đầu tiên.

Công thức tính giá tiền cho quãng đường \(d\) ga là:

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