Ít người thuê: \(N\le\lceil R C/2\rceil\)

Khi \(N\le\lceil R C/2\rceil\), ta có thể đặt người thuê theo mẫu bàn cờ trong khu căn hộ \(R\times C\) và đạt mức bất hạnh nhỏ nhất bằng 0:

 .X.X     .X.X.     X.X.X
 X.X.     X.X.X     .X.X.
 .X.X     .X.X.     X.X.X
 X.X.     X.X.X     .X.X.
                    X.X.X

4 x 4     4 x 5     5 x 5

Hình trái là khu \(4\times4\), nơi có thể đặt tối đa 8 người vào các căn đánh dấu X mà mức bất hạnh vẫn bằng 0 (căn trống đánh dấu .). Không có hai căn có người nào chung tường. Tương tự, hình giữa đặt được tối đa 10 người với mức bất hạnh bằng 0.

Nếu \(R\) hoặc \(C\) chẵn (hình trái và giữa), có thể cho thuê đúng một nửa số căn. Nếu cả \(R\) và \(C\) lẻ, có hai mẫu bàn cờ; ta chọn mẫu có nhiều ô hơn. Vì vậy, ở hình phải ta chọn màu có 13 dấu X, thay vì màu kia chỉ có 12.

Nhiều người thuê: \(N>\lceil R C/2\rceil\)

Khi \(N>\lceil R C/2\rceil\), chắc chắn có bất hạnh vì ít nhất một cặp người phải ở cạnh nhau. Thay vì bắt đầu với tòa nhà trống rồi thêm người, dễ hơn là bắt đầu từ tòa nhà kín người và loại \(K=R C-N\) người. Ta cần chọn \(K\) người sao cho mức bất hạnh giảm nhiều nhất.

Trước hết xét \(R=1\) hoặc \(C=1\). Trong trường hợp này, luôn có thể loại tối đa \(K\) người sao cho mỗi lần loại giảm 2 điểm — mức giảm lớn nhất có thể — nên đó là tối ưu. Hai ví dụ khi \(C\) chẵn và lẻ:

  .X.X..     .X.X.X.
even C=6     odd C=7

Với \(C\) chẵn, \(K\) không vượt quá \(C/2-1\) vì \(N>\lceil R C/2\rceil\). Do đó luôn có thể loại người theo các vị trí X của hình trái và mỗi lần đều giảm 2 điểm.

Với \(C\) lẻ, \(K\) không vượt quá \((C-1)/2\). Ta luôn có thể loại người theo các vị trí X của hình phải và mỗi lần cũng giảm 2 điểm.

Trường hợp tổng quát \(R,C\ge2\)

Xét bốn tòa nhà sau với mẫu bàn cờ. Các ô mang số là những căn có thể loại người; con số là đóng góp bất hạnh của người đó, tương đương mức giảm khi loại họ:

 .3.2     .3.3.     2.3.2     .3.3.
 3.4.     3.4.3     .4.4.     3.4.3
 .4.3     .4.4.     3.4.3     .4.4.
 2.3.     2.3.2     .4.4.     3.4.3
                    2.3.2     .3.3.

4 x 4     4 x 5     5 x 5     5 x 5

Chiến lược loại tối ưu \(K\) người như sau:

• Nếu \(K\le (R-2)(C-2)/2\), luôn có thể loại \(K\) người ở phần trong (các vị trí 4). Mỗi lần giảm 4, là mức tối đa có thể, nên tối ưu.
• Nếu \(K>(R-2)(C-2)/2\), sau khi loại hết các vị trí 4, tiếp tục loại ở cạnh tại các vị trí 3, mỗi lần giảm 3. Nếu đã loại hết các vị trí cạnh mà vẫn chưa đủ \(K\), loại tiếp ở góc tại các vị trí 2, mỗi lần giảm 2. Tới đây chắc chắn đủ vì \(K\) không vượt quá \(R C/2\).

Khi \(R\) và \(C\) đều lẻ, phải xét cả hai mẫu bàn cờ và chọn mẫu cho mức bất hạnh nhỏ hơn.

Vì sao chiến lược đúng?

Mỗi lần loại chỉ có thể giảm nhiều nhất 4. Trong tòa nhà \(5\times5\) sau, số ở mỗi căn là mức giảm nếu loại người tại đó:

23332
34443
34443
34443
23332

Ta đặt được nhiều nhất \(\lceil(R-2)(C-2)/2\rceil\) vị trí loại có giá trị 4, nên không thể tốt hơn việc dùng ngần ấy số 4 rồi dùng số 3 cho phần còn lại. Vì thế, gọi \(U\) là mức giảm bất hạnh tối đa, ta có:

• \(U\le4K\) nếu \(K\le\lceil(R-2)(C-2)/2\rceil\);
• \(U\le3K+\lceil(R-2)(C-2)/2\rceil\) trong trường hợp còn lại.

Xét chiến lược loại theo mẫu bàn cờ sau, gọi là pattern1:

2.3.2
.4.4.
3.4.3
.4.4.
2.3.2

Mẫu này đạt đúng \(U\) khi \(K\le\lfloor R C/2\rfloor-3\) nếu \(R,C\) đều lẻ, và khi \(K\le\lfloor R C/2\rfloor-2\) nếu một trong \(R,C\) chẵn. Do đó chiến lược tối ưu trong các trường hợp ấy.

Ở những trường hợp còn lại, chiến lược đạt \(U-1\) hoặc \(U-2\) vì buộc phải dùng một số vị trí 2. Nó đã dùng tối đa vị trí 4, và trong điều kiện đó cũng dùng tối đa vị trí 3; cách duy nhất có thể cải thiện là bớt một vị trí 4 để đổi lấy nhiều vị trí 3 hơn.

Điều này thật sự cải thiện trường hợp \(K=\lfloor R C/2\rfloor-1\): mức bất hạnh cuối giảm từ 4 xuống 3 khi dùng mẫu bàn cờ còn lại, gọi là pattern2:

.3.3.
3.4.3
.4.4.
3.4.3
.3.3.

Cụ thể, với pattern1, loại \(K=11\) người làm giảm \(5\cdot4+4\cdot3+2\cdot2=36\). Với pattern2, mức giảm là \(4\cdot4+7\cdot3=37\): dùng ít hơn một số 4 nhưng nhiều số 3 hơn.

Ngược lại, chẳng hạn khi \(K=5\), pattern1 là tối ưu. Nó có năm vị trí 4, trong khi pattern2 chỉ có bốn và phải loại thêm một vị trí 3.

Mã tham khảo C++

#include <cassert>
#include <cstdio>
#include <algorithm>

using namespace std;

int T, R, C, N;

int remove_tenants(int &K, int max_remove, int remove_cost) {
  int removed = min(K, max_remove);
  K -= removed;
  return removed * remove_cost;
}

int get_score(int all, int corners, int inners) {
  int sides = all - corners - inners;
  int K = R * C - N;
  int unhappiness = R * C * 2 - R - C;
  unhappiness -= remove_tenants(K,  inners, 4);
  unhappiness -= remove_tenants(K,   sides, 3);
  unhappiness -= remove_tenants(K, corners, 2);
  assert(K == 0);
  return unhappiness;
}

int min_unhappines() {
  // Guaranteed zero unhappiness.
  if (N <= (R * C + 1) / 2) return 0;

  if (R == 1) {
    int K = R * C - N;
    int unhappiness = C - 1;
    int remove_cost = 2;
    return unhappiness - K * remove_cost;
  }

  if (R % 2 == 1 && C % 2 == 1) {
    // 2.3.2
    // .4.4.
    // 3.4.3
    // .4.4.
    // 2.3.2
    int pattern1 = get_score(
      (R * C + 1) / 2,  // Max #tenants that can be removed.
      4,  // #tenants at the corners of the building.
      ((R-2) * (C-2) + 1) / 2  // #tenants at inner building.
    );

    // .3.3.
    // 3.4.3
    // .4.4.
    // 3.4.3
    // .3.3.
    int pattern2 = get_score(
      (R * C) / 2,  // Max #tenants that can be removed.
      0,  // #tenants at the corners of the building.
      ((R-2) * (C-2)) / 2  // #tenants at inner building.
    );

    return min(pattern1, pattern2);
  }

  // .3.2      2.3.      2.3.2
  // 3.4.  or  .4.3  or  .4.4.
  // .4.3      3.4.      3.4.3
  // 2.3.      .3.2      .3.3.
  return get_score(
    (R * C + 1) / 2,  // Max #tenants that can be removed.
    2,  // #tenants at the corners of the building.
    ((R-2) * (C-2) + 1) / 2  // #tenants at inner building.
  );
}

int main() {
  scanf("%d", &T);
  for (int TC = 1; TC <= T; TC++) {
    scanf("%d %d %d", &R, &C, &N);
    if (R > C) swap(R, C);
    printf("Case #%d: %d\n", TC, min_unhappines());
  }
}

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