Phân tích: Cheating a Boolean Tree

Đây là một bài tập cơ bản về quy hoạch động.

Gọi \(F(v, x)\) là số lượng cổng tối thiểu cần lật để làm cho giá trị đầu ra của nút \(v\) là \(x\) (\(x \in \{0, 1\}\)). Giá trị \(F(v, x)\) có thể được tính bằng quy hoạch động như sau:

• Nếu \(v\) là một nút lá với giá trị đầu vào là 0, thì \(F(v, 0) = 0\) (không cần thay đổi gì); và \(F(v, 1)\) có thể được gán bằng một giá trị rất lớn (vô cùng) để chỉ ra rằng "không thể thực hiện được". Tương tự nếu lá có giá trị 1.
• Nếu \(v\) có hai con là \(u\) và \(w\), và cổng tại \(v\) hiện tại là OR:
  • Để \(F(v, 0)\):
    1. Giữ nguyên cổng OR: Cần cả \(u\) và \(w\) có giá trị 0. Chi phí: \(F(u, 0) + F(w, 0)\).
    2. Nếu cổng có thể thay đổi (\(C=1\)), đổi sang cổng AND: Chỉ cần ít nhất một trong hai con \(u\) hoặc \(w\) có giá trị 0. Chi phí: \(1 + \min(F(u, 0) + F(w, 0), F(u, 0) + F(w, 1), F(u, 1) + F(w, 0))\). Thực tế chỉ cần \(1 + \min(F(u, 0), F(w, 0))\) vì nếu cả hai bằng 0 thì phương án 1 đã bao phủ và tốt hơn.
    3. Vậy \(F(v, 0) = \min(\text{phương án 1}, \text{phương án 2})\).
  • Để \(F(v, 1)\):
    1. Giữ nguyên cổng OR: Chỉ cần ít nhất một trong hai con \(u\) hoặc \(w\) có giá trị 1. Chi phí: \(\min(F(u, 1) + F(w, 1), F(u, 1) + F(w, 0), F(u, 0) + F(w, 1))\).
    2. Nếu cổng có thể thay đổi, đổi sang cổng AND: Cần cả \(u\) và \(w\) có giá trị 1. Chi phí: \(1 + F(u, 1) + F(w, 1)\).
    3. Vậy \(F(v, 1) = \min(\text{phương án 1}, \text{phương án 2})\).

Các trường hợp khi cổng tại \(v\) là AND được tính toán tương tự.

Công thức tổng quát cho nút nội bộ \(v\) với con \(u, w\):

Giả sử \(cost\_AND\) là chi phí tối thiểu để nút \(v\) có giá trị \(x\) nếu dùng cổng AND, và \(cost\_OR\) là chi phí tương ứng nếu dùng cổng OR.

• Nếu muốn \(v=1\):
  • \(cost\_AND(v, 1) = F(u, 1) + F(w, 1)\)
  • \(cost\_OR(v, 1) = \min(F(u, 1) + F(w, 0), F(u, 0) + F(w, 1), F(u, 1) + F(w, 1))\)
• Nếu muốn \(v=0\):
  • \(cost\_AND(v, 0) = \min(F(u, 0) + F(w, 1), F(u, 1) + F(w, 0), F(u, 0) + F(w, 0))\)
  • \(cost\_OR(v, 0) = F(u, 0) + F(w, 0)\)

Dựa vào loại cổng \(G\) và khả năng thay đổi \(C\):

• Nếu \(G=AND\) (cổng AND):
  • \(F(v, x) = cost\_AND(v, x)\)
  • Nếu \(C=1\), \(F(v, x) = \min(F(v, x), 1 + cost\_OR(v, x))\)
• Nếu \(G=OR\) (cổng OR):
  • \(F(v, x) = cost\_OR(v, x)\)
  • Nếu \(C=1\), \(F(v, x) = \min(F(v, x), 1 + cost\_AND(v, x))\)

Chúng ta có thể tính toán các giá trị \(F\) theo thứ tự từ dưới lên (bottom-up) từ các lá lên đến gốc, hoặc sử dụng đệ quy có nhớ (top-down).

Độ phức tạp

• Thời gian: \(O(M)\) cho mỗi bộ test, vì mỗi nút chỉ được thăm một lần và các phép tính tại mỗi nút là hằng số.
• Không gian: \(O(M)\) để lưu trữ cấu trúc cây và bảng phương án DP.

Quan sát thêm

Trong bài toán này, vì không có cổng phủ định (NOT), mạch điện thực hiện một hàm đơn điệu. Điều này có nghĩa là nếu chúng ta muốn đầu ra là 1, chúng ta không bao giờ cần quan tâm đến việc thay đổi một giá trị trung gian từ 1 thành 0. Tuy nhiên, việc cài đặt DP đầy đủ cho cả hai trạng thái 0 và 1 tại mỗi nút là đơn giản và an toàn nhất.

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