Test Set 1

Có nhiều cách giải Test Set 1, chẳng hạn quy về bài toán luồng. Cũng có thể tìm chiến lược tham lam hoặc công thức: số chuyến cần thiết là cực đại của số vé khách 1, số vé khách 2 và số vé ghế 1; số lần thăng hạng là

Tuy nhiên, chứng minh trực tiếp các cách này không dễ; phân tích tổng quát dưới đây giải thích vì sao chúng đúng.

Test Set 2: các cận dưới

Số vé của bất kỳ một khách nào là cận dưới cho số chuyến, vì hai vé của cùng khách không thể thực hiện trong một chuyến. Số vé ghế 1 cũng là cận dưới vì ghế 1 không thể thăng hạng và một chuyến chỉ có một ghế 1.

Mở rộng nhận xét thứ hai: trong tập mọi vé cho các ghế \(1,2,\ldots,k\), mỗi chuyến thực hiện được nhiều nhất \(k\) vé, kể cả sau khi thăng hạng. Gọi \(S_k\) là số vé có vị trí không vượt quá \(k\); khi đó \(\lceil S_k/k\rceil\) là một cận dưới. Vì vậy đặt

Đạt được cận khi mỗi khách có một vé

Trước hết giả sử mỗi khách chỉ có một vé. Chừng nào còn vị trí \(p\) có hơn \(R\) vé, thăng hạng một vé tại \(p\) sang một vị trí trước đó đang có ít hơn \(R\) vé. Một vị trí như vậy chắc chắn tồn tại vì \(R\ge\lceil S_p/p\rceil\). Sau quá trình này, không vị trí nào có quá \(R\) vé.

Vì không có khách lặp, ta có thể lặp \(R\) lần: ở mỗi chuyến lấy một vé còn lại của mỗi vị trí đang có vé. Ta thu được đúng \(R\) chuyến, trong khi cận dưới chứng minh không thể dùng ít hơn.

Trường hợp một khách có nhiều vé

Khi khách có nhiều vé, bước tham lam xếp chuyến ở trên có thể thất bại nếu thực hiện ngây thơ. Ta dùng mô hình ma trận để chứng minh vẫn luôn tồn tại lịch hợp lệ.

Xét một kế hoạch gồm các chuyến cố định. Đặt \(S=\max(N,C)\) và tạo ma trận kế hoạch chuyến đi vuông cấp \(S\). \(C\) hàng đầu biểu diễn khách, \(N\) cột đầu biểu diễn ghế; các hàng hoặc cột còn lại là khách hoặc ghế giả.

Với mỗi chuyến, xây dựng một song ánh giữa khách và ghế. Khách tham gia được ghép với ghế của họ; khách không tham gia được ghép với ghế trống hoặc ghế giả. Nếu ghế nhiều hơn khách, mỗi ghế trống được ghép với một khách giả. Giá trị ô \((b,p)\) là số lần khách biểu diễn bởi hàng \(b\) được ghép với vị trí biểu diễn bởi cột \(p\). Giá trị này là cận trên, không nhất thiết là số lần chính xác khách thật sự ngồi ghế đó, vì có các ghép giả.

Với kế hoạch gồm \(R\) chuyến, tổng mọi hàng và mọi cột của ma trận đều bằng \(R\): mỗi chuyến cộng 1 vào đúng một ô trên mỗi hàng và mỗi cột. Điều quan trọng là chiều ngược lại cũng đúng: mọi ma trận nguyên không âm có mọi tổng hàng và tổng cột bằng \(R\) đều là ma trận kế hoạch của một lịch gồm \(R\) chuyến. Đây là một biến thể đơn giản của định lý Birkhoff–von Neumann: ma trận như vậy phân rã thành tổng của \(R\) ma trận hoán vị, và mỗi ma trận hoán vị tương ứng một chuyến.

Tập vé cũng được biểu diễn bằng ma trận vuông cấp \(S\), trong đó ô \((b,p)\) là số vé ghế \(p\) mà khách \(b\) giữ. Ta nói \(M\le M'\) nếu mọi ô của \(M\) không vượt ô tương ứng của \(M'\). Sau khi thăng hạng, ma trận vé cần không vượt ma trận kế hoạch chuyến đi.

Thuật toán thăng hạng tham lam ở trên thật ra tạo một ma trận vé mà không tổng hàng hay tổng cột nào vượt \(R\), ngay cả khi một khách có nhiều vé. Tổng hàng không đổi khi thăng hạng và đã không vượt \(R\) theo định nghĩa; cận tiền tố bảo đảm có chỗ chuyển để mọi tổng cột không vượt \(R\). Có thể thêm các ghép giả để nâng mọi tổng hàng/cột lên đúng \(R\), rồi dùng phân rã Birkhoff–von Neumann để nhận một lịch \(R\) chuyến. Đây là mảnh ghép còn thiếu để biến lời giải tưởng như ngây thơ thành lời giải đầy đủ.

Số lần thăng hạng

Vì chỉ cần báo số lần thăng hạng chứ không cần chỉ rõ các vé, với mỗi vị trí \(p\) có \(cnt_p>R\), ta buộc phải chuyển ít nhất \(cnt_p-R\) vé đi; thuật toán trên chuyển đúng từng ấy. Do đó

Đếm vé theo khách, theo ghế và quét các tổng tiền tố cho thời gian \(O(N+C+M)\) và bộ nhớ \(O(N+C)\).

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2017, Round 2, bài Roller Coaster Scheduling; kho Google Coding Competitions (Apache-2.0).