Phân tích: No Cheating

Các cuộc thi lập trình chắc chắn đã thay đổi theo năm tháng. Ngày nay, quy hoạch động là một vấn đề tầm thường đối với nhiều người, và ghép cặp trên đồ thị hai phía không còn là một ý tưởng bí mật nữa. Hơn một nửa số thí sinh đã giải được tập dữ liệu nhỏ của bài toán này, và 77 người đã vượt qua các bài kiểm tra lớn.

Tập dữ liệu nhỏ (Test set 1 - Visible)

Các bài kiểm tra nhỏ có thể được giải bằng quy hoạch động. Ý tưởng chính là thực hiện việc này theo từng hàng.

Cách tiếp cận quy hoạch động ngây thơ có các trạng thái \((R_1, r)\), trong đó \(r\) là số hàng và \(R_1\) là các cấu hình có thể có của hàng hiện tại. Để tính giá trị của \((R_1, r)\) (số lượng học sinh tối đa có thể xếp vào \(r\) hàng đầu tiên, với hàng thứ \(r\) giống hệt \(R_1\)), người ta có thể lặp qua tất cả các giá trị có thể có của \(R_2\) (cấu hình hàng \(r-1\)) và sử dụng giá trị của \((R_2, r-1)\).

Một cách tiếp cận tinh vi hơn cũng đi theo từng hàng, nhưng trong mỗi hàng, chúng ta thực hiện theo từng ô vuông. Các trạng thái là \((S, r, c)\), trong đó \((r, c)\) là vị trí hiện tại và \(S\) là mặt nạ bit cho tối đa \(N\) vị trí trước \((r, c)\). Đây là tất cả các ô vuông bên trái trên cùng một hàng và tất cả các ô vuông từ cột \((c-1)\) đến cột cuối cùng ở hàng trước đó. Bằng cách này, mỗi giá trị của \((S, r, c)\) có thể được tính trong thời gian hằng số.

Người ta có thể ước tính số lượng trạng thái là \(O(M \cdot N \cdot 2^N)\). Nhưng thực tế số lượng trạng thái nhỏ hơn nhiều. Không khó để thấy rằng, với hạn chế không có hai ghế cạnh nhau theo chiều ngang đều bị chiếm, số lượng trạng thái \(S\) là \(O(F_N)\), số Fibonacci thứ \(N\). Điều này có nghĩa là giải pháp quy hoạch động thậm chí có thể xử lý một lớp học có kích thước khoảng 35 x 35.

Tập dữ liệu lớn (Test set 2 - Hidden)

Tuy nhiên, các trường đại học thực sự có những lớp học rất lớn. Tập dữ liệu lớn có các bài kiểm tra với 80 hàng và 80 cột.

Ý tưởng then chốt là nhìn thấu bài toán và nhận thấy rằng đây là một bài toán đồ thị chuẩn. Hãy để mỗi ô vuông là một nút. Những gì bài toán yêu cầu là chọn một tập hợp các nút, sao cho một số cặp nút không thể được chọn cùng nhau. Hãy vẽ một cạnh giữa mỗi cặp nút như vậy. Đây là bài toán tìm tập độc lập cực đại (maximum independent set) nổi tiếng của đồ thị. Mặc dù bài toán tập độc lập tổng quát là NP-khó, chúng ta biết rằng bài toán này có thể giải được trên đồ thị hai phía. A-ha! Đồ thị thực sự là đồ thị hai phía, bởi vì tất cả các cạnh đều nằm giữa một ô vuông ở các cột được đánh số lẻ và các ô vuông ở các cột được đánh số chẵn.

Chúng ta có thể dễ dàng tìm thấy ghép cặp cực đại trên đồ thị hai phía. Hãy xem ghép cặp cực đại có thể giúp chúng ta giải quyết bài toán như thế nào. Giả sử kích thước của bộ ghép là \(X\) và số lượng nút trong đồ thị là \(N\). Lưu ý rằng tập độc lập cực đại không thể chứa nhiều hơn \(N - X\) nút, bởi vì nếu nhiều hơn, bạn sẽ có hai nút cùng thuộc một cạnh của bộ ghép cặp cực đại nằm trong tập này.

Nói chung, chúng ta có các mối quan hệ sau giữa các tham số đồ thị quan trọng. Đối với một đồ thị \(G = (V, E)\), gọi \(\alpha(G)\) là kích thước của tập độc lập cực đại, \(m(G)\) là kích thước của bộ ghép cặp cực đại, \(\mu(G)\) là kích thước của tập phủ đỉnh tối thiểu.

• Phần bù của một tập độc lập là một tập phủ đỉnh, và ngược lại. Vì vậy \(\alpha(G) + \mu(G) = |V|\).
• Để phủ tất cả các cạnh, chúng ta cần một đỉnh từ bất kỳ cạnh nào của một bộ ghép cặp. Vì vậy \(\mu(G) \ge m(G)\).
• Nếu \(G\) là đồ thị hai phía, thì \(\mu(G) = m(G)\). Tương đương, \(\alpha(G) + m(G) = |V|\).

Sự thật cuối cùng có thể được chứng minh trực tiếp, hoặc như một hệ quả của định lý Hall, hoặc như một ứng dụng của định lý luồng cực đại - lát cắt tối thiểu mạnh mẽ. Dưới đây chúng tôi cung cấp một chứng minh mang tính xây dựng phù hợp với bài toán của chúng ta.

Chứng minh

Chúng ta sẽ chứng minh rằng \(N - X\) nhỏ hơn hoặc bằng kích thước của tập độc lập cực đại. Giả sử chúng ta có một bộ ghép cặp cực đại \(M\) và một tập \(S\) chứa tất cả các nút không nằm trong \(M\). Bây giờ hãy thêm vào \(S\) tất cả các nút từ \(M\) nằm ở phía bên trái của đồ thị hai phía. \(S\) có kích thước \(N - X\). Nếu \(S\) không phải là một tập độc lập, thì nó có một nút \(u\) từ \(M\) và một nút khác \(v\) không thuộc \(M\), sao cho \((u, v)\) là một cạnh. Để khắc phục vấn đề này, chúng ta loại bỏ \(u\) khỏi \(S\) và thêm nút \(u'\) vào \(S\) trong đó \((u, u')\) là một cạnh từ bộ ghép cặp. Nếu thao tác này gây ra vấn đề với một nút khác trong bộ ghép cặp, thì chúng ta có thể loại bỏ nút đó và thêm nút ghép của nó, và cứ tiếp tục như vậy. Thủ tục lặp lại này được đảm bảo sẽ kết thúc vì chúng ta chỉ xóa các nút từ phía bên trái của đồ thị và thêm các nút từ phía bên phải. Sẽ không có vấn đề gì gây ra bởi các nút ở phía bên phải của đồ thị và các nút bên ngoài bộ ghép cặp vì điều đó có nghĩa là chúng ta có thể tìm thấy một đường tăng cường, và bộ ghép cặp cực đại không phải là bộ ghép lớn nhất có thể.

Chúng ta đã chứng minh rằng trong bất kỳ đồ thị hai phía nào, kích thước của tập độc lập cực đại bằng kích thước của đồ thị trừ đi kích thước của bộ ghép cặp cực đại.

Mã nguồn

Chúng tôi tin rằng nhiều thí sinh đã chuẩn bị sẵn thuật toán ghép cặp hai phía tiêu chuẩn. Dưới đây là một giải pháp mẫu giữ đồ thị hai phía trong tư duy và thực sự chạy thuật toán ghép cặp trực tiếp trên bảng.

int C, N, M;
string bd[100];

int nbx[100][100], nby[100][100], v[100][100];
int T=0;

bool dfs(int a, int b) {
  if (a<0) return true;
  if(v[a][b]==T) return false;
  v[a][b]=T;
  for (int i=a-1;i<=a+1;i++)
    for (int j=b-1;j<=b+1;j+=2)
      if (i>=0 && i<M && j>=0 && j<N && bd[i][j]=='.') {
        if (dfs(nbx[i][j], nby[i][j])) {
          nbx[i][j]=a; nby[i][j]=b;
          nbx[a][b]=i; nby[a][b]=j;
          return true;
        }
      }
  return false;
}

int play() {
  memset(nbx,-1,sizeof(nbx));
  memset(nby,-1,sizeof(nby));
  memset(v, -1, sizeof(v)); T=-1;
  int rst=0;
  for(int i=0;i<M;i++) for(int j=0;j<N;j++) {
    if (bd[i][j]=='.') {
      rst++;
      if (j%2) {
        T++;
        if (dfs(i,j)) rst--;
      }
    }
  }
  return rst;
}

int main() {
  cin>>C;
  for (int i=1; i<=C; i++) {
    cin>>M>>N;
    for (int r=0;r<M;r++) cin>>bd[r];
    cout<<"Case #"<<i<<": "<<play()<<endl;
  }
  return 0;
}

Thông tin thêm

• Maximum independent set
• Bipartite Matching

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