Phân tích: Picking Up Chicks

Lời giải gồm nhiều bước; mỗi bước làm bài toán dễ hơn cho đến khi nó trở nên đơn giản.

Bước 1. Đổi chỗ sớm nhất có thể (hoặc hoàn toàn không đổi)

Giả sử một con bắt kịp con phía trước. Ta có ba lựa chọn:

1. Nhấc ngay con chậm để con nhanh vượt qua.
2. Để chúng chạy cùng nhau một lúc rồi mới nhấc con chậm.
3. Để chúng chạy cùng nhau hết thời gian còn lại và không cho con nhanh vượt.

Lựa chọn 2 không bao giờ cần thiết. Trực giác là chẳng có lý do gì giữ con nhanh lại nếu sau đó vẫn làm đúng thao tác đổi chỗ ấy. Chính thức hơn, giả sử một lời giải đổi hai con \(P,Q\) tại \(T_1\), dù chúng gặp lần đầu tại \(T_0<T_1\). Chuyển thao tác về \(T_0\). Với từng con và từng thời điểm, vị trí của nó hoặc không đổi, hoặc gần chuồng hơn; do đó lời giải mới vẫn hợp lệ.

Bước 2. Không bao giờ đổi hai con đều sẽ đến chuồng đúng hạn

Nếu hai con cuối cùng đều đến kịp, ta có thể bỏ lần đổi giữa chúng mà cả hai vẫn đến kịp. Trong phần đường còn lại, con nhanh cần cùng số lần đổi như trước, hoặc ít hơn vì vài con có thể đã tránh đường. Giữ chúng cùng nhau đến cuối vì thế tiết kiệm ít nhất một lần đổi.

Bước 3. Nếu một con không thể đến kịp, mọi con phía sau nó đều phải đổi với nó

Nếu một con về lý thuyết không thể đến kịp, tức là

thì mọi con xuất phát phía sau nó muốn đến kịp đều phải đổi chỗ với nó; nếu không, những con ấy cũng không đến kịp.

Bước 4. Chia gà thành hai lớp để có cận dưới

Tô đỏ các con về lý thuyết có thể đến kịp, và xanh các con không thể. Với mỗi con đỏ, số lần đổi cần thiết ít nhất bằng số con xanh xuất phát gần chuồng hơn nó. Vì vậy, nếu tính số này cho từng con đỏ, đáp án ít nhất là tổng của \(K\) số nhỏ nhất.

Bước 5. Cận dưới đó chính là đáp án

Các lần đổi trên là bắt buộc, và ta không cần thêm lần nào khác. Chọn \(K\) con đỏ ban đầu gần chuồng nhất, rồi đổi chúng với các con xanh ngay khi gặp. Do đã chọn \(K\) con đỏ gần chuồng nhất, số con xanh cản đường là nhỏ nhất có thể; nhớ rằng không bao giờ cần đổi hai con đỏ.

Bước 6. Viết mã

Sau các quan sát trên, lời giải thực tế rất đơn giản:

  num_red = 0
  num_blue = 0
  answer = 0
  for i = N - 1 .. 0:
    if num_red == K:
      break
    if X[i] + T * V[i] < B:
      num_blue += 1
    else:
      num_red += 1
      answer += num_blue
  if num_red >= K:
    output answer
  else
    output "IMPOSSIBLE"

Nguồn

Bản dịch đầy đủ dựa trên phân tích chính thức của Google Code Jam 2010 - Picking Up Chicks, thuộc kho Google Coding Competitions (Apache-2.0).