Hướng dẫn cho Google Code Jam 2022 - Controlled Inflation

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Nhận xét then chốt

Với mỗi khách hàng, sắp các áp suất mục tiêu theo thứ tự tăng dần hoặc giảm dần sẽ tạo ra một lời giải tối ưu; không hoán vị nào khác của các sản phẩm có thể cho số lần nhấn nút nhỏ hơn một cách nghiêm ngặt. Ta chứng minh điều này.

Trước hết, mệnh đề đúng khi chỉ xét riêng từng khách \(i\). Trong quá trình xử lý, có lúc máy bơm ở áp suất nhỏ nhất

\[ \operatorname{Min}_i=\min_{j=1..\mathbf{P}}\mathbf{X}_{i,j}, \]

và có lúc ở áp suất lớn nhất

\[ \operatorname{Max}_i=\max_{j=1..\mathbf{P}}\mathbf{X}_{i,j}. \]

Ta bắt buộc phải chạm đến cả hai giá trị, nên bất kể thứ tự sản phẩm, luôn cần ít nhất \(\operatorname{Max}_i-\operatorname{Min}_i\) lần nhấn. Có thể đạt đúng mức này bằng cách sắp áp suất mục tiêu tăng dần hoặc giảm dần.

Áp suất còn phải được điều chỉnh giữa các khách hàng. Ta xét xem một thứ tự sản phẩm khác có thể tiết kiệm bao nhiêu lần nhấn ở chỗ chuyển tiếp. Trong khi xử lý khách thứ \(i\), máy có lúc ở \(\operatorname{Min}_i\), có lúc ở \(\operatorname{Max}_i\), rồi cuối cùng dừng tại áp suất của sản phẩm cuối \(\mathbf{X}_{i,\mathrm{last}}\). Nếu máy chạm giá trị nhỏ nhất trước giá trị lớn nhất, quá trình này cần ít nhất

\[ (\operatorname{Max}_i-\operatorname{Min}_i)+(\operatorname{Max}_i-\mathbf{X}_{i,\mathrm{last}}) \]

lần nhấn, trong khi phần có thể tiết kiệm ở bước chuyển sang khách sau nhiều nhất là \(\operatorname{Max}_i-\mathbf{X}_{i,\mathrm{last}}\), đúng bằng phần nhấn thêm tối thiểu vừa bỏ ra. Nếu máy chạm giá trị lớn nhất trước giá trị nhỏ nhất, ta có quan hệ đối xứng tương tự. Vì vậy thứ tự khác không thể cải thiện đáp án.

Vét cạn cho Test Set 1

Vì chỉ cần xét thứ tự tăng và giảm, ta chỉ cần giữ \(\operatorname{Min}_i\) và \(\operatorname{Max}_i\) cho từng khách. Với Test Set có phán quyết hiển thị, có thể thử toàn bộ \(2^{\mathbf{N}}\le1024\) cách chọn tăng hoặc giảm cho mỗi khách rồi mô phỏng.

Quy hoạch động

Để làm hiệu quả hơn, dùng quy hoạch động. Gọi \(dp_{i,0}\) là số lần nhấn ít nhất sau khi xử lý \(i\) khách, trong đó sản phẩm của khách cuối được sắp tăng dần. Tương tự, \(dp_{i,1}\) là đáp án sau \(i\) khách khi sản phẩm của khách cuối được sắp giảm dần. Ta cũng lưu áp suất cuối của máy tương ứng là \(l_0\) và \(l_1\).

Ban đầu,

\[ dp_{0,0}=dp_{0,1}=0,\qquad l_0=l_1=0. \]

Giả sử đã tính đến khách \(i\). Với khách \(i+1\), các chuyển trạng thái là

\[ dp_{i+1,0}=\min\begin{pmatrix} dp_{i,0}+|l_0-\operatorname{Min}_{i+1}|+(\operatorname{Max}_{i+1}-\operatorname{Min}_{i+1}),\\ dp_{i,1}+|l_1-\operatorname{Min}_{i+1}|+(\operatorname{Max}_{i+1}-\operatorname{Min}_{i+1}) \end{pmatrix}, \]

và

\[ dp_{i+1,1}=\min\begin{pmatrix} dp_{i,0}+|l_0-\operatorname{Max}_{i+1}|+(\operatorname{Max}_{i+1}-\operatorname{Min}_{i+1}),\\ dp_{i,1}+|l_1-\operatorname{Max}_{i+1}|+(\operatorname{Max}_{i+1}-\operatorname{Min}_{i+1}) \end{pmatrix}. \]

Sau đó cập nhật áp suất cuối:

\[ l_0=\operatorname{Max}_{i+1},\qquad l_1=\operatorname{Min}_{i+1}. \]

Mỗi khách chỉ tạo ra số lượng chuyển trạng thái hằng số sau khi đã tìm cực tiểu và cực đại, nên phần quy hoạch động chạy trong \(O(\mathbf{N})\) thời gian; việc đọc và rút gọn toàn bộ đầu vào cần \(O(\mathbf{N}\mathbf{P})\) thời gian.

Google Code Jam khuyến nghị luyện gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Lời giải này được dịch đầy đủ từ bản phân tích chính thức của Google Code Jam 2022, Vòng 1B.

Bình luận

Tải bình luận...

Không có bình luận nào.