Phân tích: A Digging Problem

Cách thiết lập của bài toán này, nơi bạn có thể đi sang trái, sang phải và đi xuống nhưng không bao giờ đi lên, gợi ý rằng một giải pháp quy hoạch động (DP) là hướng đi đúng đắn, nhưng các chi tiết có phần phức tạp.

Khi chúng ta ở trên một hàng, chúng ta cần biết những ô đá nào đã được đào trước đó để biết chúng ta có thể di chuyển sang trái hoặc sang phải bao xa. Điều này có nghĩa là một trạng thái trong thuật toán của chúng ta có thể là (i, j, air_holes), trong đó i là hàng hiện tại, j là cột hiện tại và air_holes là tập hợp các ô trên hàng i đã được đào trước đó hoặc vốn đã trống. Việc điền giá trị cho các trạng thái này trong toàn bộ ma trận sẽ mất thời gian lũy thừa vì air_holes có thể nhận tới \(2^C\) giá trị. Điều này đủ để giải quyết Small dataset, nhưng đối với Large dataset, chúng ta cần cải thiện thuật toán.

Đầu tiên, hãy quan sát rằng việc đào các ô chỉ có ý nghĩa khi chúng tạo thành một vùng trống liên thông. Sau khi rơi xuống một hàng, chúng ta sẽ chỉ có thể sử dụng vùng các ô trống hiện tại. Bây giờ trạng thái của chúng ta là (i, j, start, end), trong đó start là chỉ số cột bắt đầu của vùng trống hiện tại và end là chỉ số cột kết thúc của vùng đó. Ý tưởng này mang lại một giải pháp đa thức, vì chúng ta có \(O(R \times C^3)\) trạng thái khả thi và có tối đa \(C^2\) trạng thái khác nhau mà chúng ta có thể tạo ra trên hàng tiếp theo.

Nhưng chúng ta có thể cải thiện giải pháp này hơn nữa. Việc đổi hướng sau khi đã bắt đầu đào là không hợp lý; nếu chúng ta đang di chuyển sang phải, việc có bao nhiêu ô trống ở bên trái không quan trọng. Điều này thay đổi trạng thái thành (i, j, dir, count), trong đó dir là hướng hiện tại (trái hoặc phải) và count là số lượng ô trống theo hướng đó. Điều này làm giảm không gian trạng thái xuống còn \(O(R \times C^2)\).

Các chi tiết cài đặt có phần lắt léo, và bạn phải đảm bảo rằng mình không rơi quá \(F\) bước — một chi tiết mà chúng tôi đã lướt qua ở đây. Có nhiều cách khả thi để cài đặt bài toán này, một số cách dẫn đến mã nguồn đơn giản hơn nhiều so với các cách khác. Chúng tôi khuyến khích bạn tải xuống và nghiên cứu các bản cài đặt chính xác khác nhau từ bảng xếp hạng.

Trước khi cuộc thi bắt đầu, chúng tôi đánh giá bài toán này là bài dễ thứ hai trong cuộc thi; nhưng nhiều chi tiết cần thiết để giải quyết nó đã khiến bài toán này có số lượng lời giải thành công ít thứ hai.

Thông tin liên quan

Nếu bạn nằm trong số những thí sinh lâu năm, bài toán này có thể gợi lại những kỷ niệm ngọt ngào về trò chơi cổ điển Lode Runner, và có lẽ là kỷ niệm về nhiều ngày hạnh phúc gắn liền với nó.

Nguồn

Bản dịch dựa trên phân tích chính thức của Google Code Jam 2009 - Round 2 - A Digging Problem, thuộc kho Google Coding Competitions (Apache-2.0).