Phân tích: Dire Straights

Dire Straights có một trong những dữ liệu nhỏ dễ nhất của Vòng 3. Nhiều lời giải vét cạn hoặc quay lui làm đúng theo luật có thể tìm ra đáp án hợp lệ trong thời gian cho phép. Vì vậy, thay vì xét dữ liệu nhỏ, ta sẽ xét dữ liệu lớn, vốn cần một nhận xét để xây dựng cách tham lam.

Một chiến lược trực quan là sắp xếp toàn bộ lá bài, rồi lần lượt đặt chúng xuống bàn và tạo một dãy liên tiếp mới bất cứ khi nào cần. Mục tiêu là làm độ dài dãy ngắn nhất lớn nhất có thể, nên khi có lựa chọn, ta luôn tăng độ dài của dãy ngắn nhất. Ta chỉ còn phải chứng minh lựa chọn này là tối ưu.

Giả sử có hai dãy liên tiếp, một dãy từ \(a\) đến \(b\), dãy kia từ \(c\) đến \(d\), với \(a<c\le d<b\).

   a-------b
    c-----d

Có thể thay hai dãy này bằng dãy từ \(a\) đến \(d\) và dãy từ \(c\) đến \(b\), như minh họa dưới đây, mà không làm giảm điểm. Thực tế, thay đổi này còn có thể làm điểm tăng.

   a------d
    c------b

Điều đó cho thấy ta luôn có thể bảo đảm một dãy bắt đầu muộn hơn không bao giờ kết thúc trước một dãy bắt đầu sớm hơn. Vì vậy, ghép lá bài tiếp theo vào dãy ngắn nhất trong số các dãy có thể nối là tối ưu.

Cuối cùng, xét kích thước của mọi dãy; độ dài của dãy ngắn nhất chính là số điểm đạt được trong Dire Straights.

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