Phân tích: World Cup 2010

Phát biểu lại bài toán

Trong phần phân tích này, chúng ta sẽ lật ngược hình ảnh sơ đồ thi đấu lại. Điều này phù hợp với quy ước thông thường là gốc của cây nhị phân được vẽ ở trên cùng. Việc này thực tế rất dễ thực hiện về mặt cài đặt. Chúng ta chỉ cần đọc các số đầu vào theo thứ tự ngược lại; phần tử ở vị trí 0 là gốc (tức là trận chung kết), và đối với bất kỳ nút \(i\) nào, hai nút con của nó được đánh chỉ số là \(2i+1\) và \(2i+2\). Trong giải pháp cụ thể này, chúng ta bao gồm các nút cho cả các đội cũng như các trận đấu, vì vậy đồ thị của chúng ta là một cây nhị phân đầy đủ có gốc, trong đó tất cả các nút nội bộ là các trận đấu, và tất cả các lá là các đội.

Có lẽ rõ ràng rằng giải pháp sẽ là quy hoạch động trên cây. Có nhiều cách để thực hiện, nhưng một số cách có thể phức tạp hơn nhiều so với những cách khác. Hãy giới thiệu một giải pháp rất đơn giản dựa trên việc phát biểu lại bài toán như sau.

Hãy tô màu một nút là màu vàng nếu chúng ta định mua vé cho trận đấu tương ứng. Đối với mỗi lá (một đội), đường đi từ gốc đến nó có \(P\) nút nội bộ. Chúng ta gọi một kế hoạch là tốt nếu bất kể kết quả các trận đấu như thế nào, chúng ta sẽ không bao giờ bỏ lỡ quá \(M[i]\) trận đấu cho đội \(i\). Ta có:

(*) Một kế hoạch là tốt khi và chỉ khi, với mọi đội \(i\), đường đi từ gốc đến lá tương ứng với đội \(i\) có ít nhất \(P-M[i]\) nút màu vàng.

Đây thực sự là một bước nhảy vọt về mặt ý tưởng trong việc giải quyết bài toán. Bởi vì ở dạng mới, chúng ta không còn cần phải lo lắng về kết quả của bất kỳ trận đấu cụ thể nào. Một khi đã được phát biểu, nó rất dễ để chứng minh. Chúng tôi để phần chứng minh cho bạn đọc.

Các giải pháp đơn giản cho cả dữ liệu nhỏ và dữ liệu lớn đều dễ dàng suy ra từ cách phát biểu lại này.

Dữ liệu nhỏ

Đối với tập dữ liệu nhỏ, kế hoạch tốt nhất phải có tính chất đóng ngược lên trên (upwards closed), tức là nếu một nút là màu vàng, tất cả các nút trên đường đi từ gốc đến nó cũng phải là màu vàng. Người ta có thể chứng minh điều này bằng cách sử dụng (*) và lưu ý rằng tất cả các mức giá đều giống nhau, và bạn luôn có thể có một kế hoạch rẻ hơn nếu bạn đẩy một số nút vàng lên phía trên.

Vì vậy, một giải pháp cho tập dữ liệu nhỏ sẽ như sau: Đối với mỗi đội \(i\), chúng ta tìm đường đi từ gốc đến nó, và tô màu vàng cho \(P-M[i]\) nút trên cùng. Việc này có thể được thực hiện trong thời gian tuyến tính bằng một sửa đổi đơn giản của thuật toán tìm kiếm theo chiều sâu (DFS).

Dữ liệu lớn

Chúng ta sử dụng quy hoạch động trên cây. Hãy định nghĩa các bài toán con một cách rõ ràng. Đối với bất kỳ nút \(a\) nào và bất kỳ số \(b\) nào từ \(0\) đến \(P\), gọi \(P(a, b)\) là bài toán:

Nếu có \(b\) nút màu vàng trên đường đi từ gốc đến \(a\) (không tính chính \(a\)), cách rẻ nhất để tô màu các nút trong cây con gốc \(a\) sao cho mọi lá trong cây con này đều thỏa điều kiện (*) là gì?

Và chúng ta có thể sử dụng một giá trị lớn không tưởng để biểu thị rằng điều kiện không thể được thỏa mãn.

Khi DP đã được thiết lập, mã nguồn sẽ dễ dàng được viết ra. Đối với mỗi nút nội bộ, chỉ có hai lựa chọn: tô màu vàng hoặc không. Dưới đây là một đoạn trích từ một trong các giải pháp của giám khảo:

i64 A[1<<11][11];  // answers for the dynamic programming.
i64 inp[1<<11];    // input, in reversed order.
int P;

// rooted at a, already buy b tickets from above.
i64 dp(int a, int b) {
  i64& r=A[a][b];
  if(r>=0) return r;
  if(a>=((1<<P)-1)) {r=(b>=(P-inp[a]))?0:1LL<<40; return r;}
  r=std::min(
      inp[a]+dp(2*a+1,b+1)+dp(2*a+2,b+1), 
      dp(2*a+1,b)+dp(2*a+2,b));
  return r;
}

int main() {
  int T;
  cin>>T;
  for (int cs=1; cs<=T; ++cs) {
    cin>>P; int M=(2<<P)-1;
    for (int i=0; i<M; i++) cin>>inp[M-1-i];
    memset(A, -1, sizeof(A));
    cout << "Case #" << cs << ": " << dp(0, 0) <<endl;
  }
  return 0;
}

Độ phức tạp

Số lượng trạng thái DP là số lượng nút trong cây nhân với số lượng mức độ bao phủ có thể (\(P+1\)). Với \(P \le 10\), số lượng nút khoảng \(2^{11}\), vì vậy tổng số trạng thái là khoảng \(2^{11} \times 11\), hoàn toàn nằm trong giới hạn thời gian cho phép.

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