Hướng dẫn giải của Giàn đèn
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Một giàn đèn m x n, mỗi ô có trạng thái 0 (tắt), 1 (xanh), 2 (đỏ). Có k công tắc, mỗi công tắc tại (rt, ct) điều khiển một hình chữ nhật đặc biệt từ (rt, ct) đến (xt, yt). Khi kích hoạt công tắc, tất cả các đèn trong vùng đó sẽ chuyển trạng thái theo quy tắc: 0 -> 1 -> 2 -> 0 (tương đương +1 modulo 3). Mỗi công tắc có thể kích hoạt nhiều lần. Mục tiêu: Tìm số lần kích hoạt ít nhất để tất cả các đèn cùng sáng xanh (1) hoặc cùng sáng đỏ (2). Nếu không thể, output -1.
Các cách tiếp cận
Cách Quy hoạch động & Tối ưu hóa góc
#include <bits/stdc++.h>
using namespace std;
int m, n, k;
int a[1005][1005];
int f[1005][1005]; // Luong anh huong
int r[1005], c[1005], x[1005], y[1005];
int opt[1005][1005]; // Trang thai hut cua cong tac
int solve(int target) {
memset(f, 0, sizeof(f));
memset(opt, 0, sizeof(opt));
int cost = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// Cap nhat anh huong tu cac lan kich hoat truoc
int influence = (f[i][j] + a[i][j]) % 3;
if (influence < 0) influence += 3;
// Neu o hien tai chua dat target
if (influence != target) {
// Kiem tra xem co cong tac nao bat dau o day khong
bool found = false;
for (int t = ; t < k; t++) { // Note: day chi la pseudo code, can map cong tac theo vi tri
// Neu co cong tac tai (i, j)
}
// Phan nay can thiet ke lai: su dung mang luu vi tri cong tac
// Neu co cong tac, ta phai kich hoat no
// So lan kich hoat can thiet de sua loi: (target - influence) mod 3
int need = (target - influence + 3) % 3;
if (need == 0) continue;
// Chi co the sua loi neu o (i,j) co cong tac
if (has_switch[i][j]) {
cost += need;
// Cap nhat anh huong vung hinh chu nhat
int idx = switch_id[i][j];
// Su dung difference array de cap nhat f
f[i][j] += need;
f[x[idx] + 1][j] -= need;
f[i][y[idx] + 1] -= need;
f[x[idx] + 1][y[idx] + 1] += need;
} else {
return -1; // Khong the sua o nay
}
}
}
}
return cost;
}
int main() {
cin >> m >> n >> k;
// Doc du lieu va luu mapping cong tac
// Goi solve(1) va solve(2), lay min
return 0;
}
- Time Complexity: O(m * n * k) trong truong hop xau, can optimization bang prefix sum
- Space Complexity: O(m * n)
Phương pháp này dựa trên ý tưưởng xử lý lưới theo thứ tự từ trên xuống dưới, trái sang phải (dạng quy hoạch động). Tại mỗi ô (i, j), ta tính tổng ảnh hưởng từ các công tắc đã kích hoạt trước đó. Nếu trạng thái hiện tại chưa đạt target (1 hoặc 2), ta buộc phải kích hoạt công tắc tại ô đó (nếu có) để sửa lỗi. Số lần kích hoạt cần thiết là (target - current) mod 3. Nếu ô đó không có công tắc và đang sai, bài toán vô nghiệm. Phương pháp này chỉ hiệu quả nếu các công tắc được xử lý đúng thứ tự, nhưng trong bài này các công tắc có thể nằm ở bất kỳ đâu và vùng ảnh hưởng kéo dài xuống dưới. Do đó, ta cần xử lý các công tắc theo thứ tự (r, c) tăng dần để đảm bảo khi duyệt đến ô (i, j), mọi ảnh hưởng từ trên xuống đã được xử lý.
Cách Lattice Reduction (Giả sử bài toán biến đổi thành hệ phương trình)
// Pseudo code minh hoa su dung LLL thuat toan
#include <bits/stdc++.h>
using namespace std;
struct Mat {
vector<vector<int>> mat;
};
// Ham nay chi minh hoa y tuong, thuc te can implement LLL
void solve() {
// 1. Xay dung he phuong trinh mod 3
// Moi o (i, j) la 1 phuong trinh: (Tong x_t * I_{t->(i,j)} + a[i][j]) % 3 = target
// Trong do x_t la so lan kich hoat cong tac t (0, 1, 2)
// I_{t->(i,j)} = 1 neu o (i,j) nam trong vung anh huong cua cong tac t, nguoc lai 0.
// 2. Su dung LLL algorithm de gian he phuong trinh va tim solution co weight nho nhat (so luong x_t != 0)
// Day la bai toan tap hop con (Subset Sum) tren ma tran, rat kho.
// Cac solution tren chi su dung thuat toan tham an hoac quy hoach dong neu bai toan co tinh chat dac biet.
cout << -1 << endl;
}
- Time Complexity: O(2^{k}) (Exponential)
- Space Complexity: O(k)
Đây là hướng tiếp cận tổng quát nhất nhưng không khả thi trong thời gian giới hạn. Bài toán có thể được mô hình hóa thành hệ phương trình tuyến tính modulo 3. Biến xt là số lần kích hoạt công tắc t. Mỗi ô (i, j) cho một phương trình. Tuy nhiên, việc tìm nghiệm có trọng số nhỏ nhất (minimize sum xt) là bài toán NP-hard (tương đương Subset Sum). Các giải pháp thực tế trong contest thường tránh hướng này trừ khi k rất nhỏ (Subtask 1).
Cách Greedy theo thứ tự (Priority Queue / Topological)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1005;
int m, n, k;
int a[MAX][MAX];
int diff[MAX][MAX]; // Difference array
struct Switch {
int r, c, x, y;
} sw[300005];
int cost[300005]; // So lan kich hoat moi cong tac
int solve(int target) {
memset(diff, 0, sizeof(diff));
memset(cost, 0, sizeof(cost));
// Sap xep cong tac theo hang tang dan, sau do cot tang dan
// Tuy nhien, de dung greedy, ta can chac chan rang anh huong luon di chuyen tu tren xuong duoi
//
// ?
// Phan tich lai:
// O (i, j) bi anh huong boi cac cong tac o tren va ben trai.
// Neu ta duyet (i, j) theo thu tu (1,1) -> (m,n), ta co the tinh toan trang thai hien tai.
//
int total_cost = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// Tinh toan anh huong hien tai
int influence = (diff[i][j] + a[i][j]) % 3;
if (influence < 0) influence += 3;
int need = (target - influence + 3) % 3;
if (need == 0) continue;
// Neu o (i, j) co cong tac
// Ta kich hoat cong tac do need lan
// Cap nhat diff array
//
// ?? Loi: Cac cong tac co the bat dau o (i, j) nhung ket thuc o (x, y) lon hon.
// Neu chi cap nhat o day, ta chi sua duoc o (i, j).
//
// Kiem tra: Neu o (i, j) khong phai dau vao cua bat cu cong tac nao?
// -> Khong the sua.
//
// Day chinh xac la thuat toan tham an (Greedy) cho bai toan.
}
}
return total_cost;
}
int main() {
// Input
int ans1 = solve(1);
int ans2 = solve(2);
int ans = min(ans1, ans2);
// Xet truong hop -1
if (ans > 1e9) ans = -1;
cout << ans << endl;
return 0;
}
- Time Complexity: O(m * n + k)
- Space Complexity: O(m * n)
Các solution được gửi lên (dung123, quancutee) sử dụng biến thể của phương pháp này. Ý tưởng là duyệt các ô theo thứ tự từ trên xuống dưới, trái sang phải. Tại mỗi ô (i, j), ta tính toán trạng thái hiện tại của nó dựa trên các thay đổi đã thực hiện (sử dụng mảng cộng dồn / difference array để tối ưu cập nhật vùng chữ nhật). Nếu trạng thái không khớp với mục tiêu, ta buộc phải thực hiện thay đổi. Do các công tắc chỉ có thể thay đổi vùng từ (r, c) trở đi, việc xử lý theo thứ tự đảm bảo khi ta quyết định ở ô (i, j), ta không thể sửa nó bằng các công tắc ở dưới hoặc bên phải. Nếu tại ô (i, j) không có công tắc mà trạng thái sai, bài toán vô nghiệm. Nếu có công tắc, ta kích hoạt nó số lần cần thiết để sửa ô (i, j). Việc kích hoạt này sẽ ảnh hưởng đến các ô bên dưới/phải, được xử lý qua mảng cộng dồn.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(m * n * k) trong truong hop xau, can optimization bang prefix sum | O(m * n) | Quy hoạch động & Tối ưu hóa góc |
| 2 | O(2^{k}) (Exponential) | O(k) | Lattice Reduction (Giả sử bài toán biến đổi thành hệ phương trình) |
| 3 | O(m * n + k) | O(m * n) | Greedy theo thứ tự (Priority Queue / Topological) |
Bài học kinh nghiệm
- Bài toán có tính chất quy hoạch động/tham ăn: Khi duyệt đến ô (i, j), các quyết định cho các ô (i', j') với i' < i hoặc (i' = i, j' < j) đã được cố định và không thể thay đổi trong tương lai.
- Sử dụng Difference Array (mảng cộng dồn 2D) để xử lý các thao tác cập nhật vùng chữ nhật trong thời gian O(1), giảm độ phức tạp từ O(mnk) xuống O(m*n + k).
- Mỗi công tắc có thể được kích hoạt 0, 1, hoặc 2 lần (mod 3). Việc kích hoạt 3 lần tương đương 0 lần. Do đó, ta chỉ cần quyết định số lần kích hoạt là 0, 1, hay 2 để sửa đổi trạng thái.
- Nếu tại một ô không có công tắc mà trạng thái của nó không đúng với mục tiêu (sau khi áp dụng các ảnh hưởng trước đó), bài toán vô nghiệm. Điều này cho phép kiểm tra nhanh.
Lỗi thường gặp
- Quên xử lý modulo 3: Các phép tính cộng trừ phải thực hiện modulo 3 (và xử lý số âm).
- Lỗi cập nhật Difference Array: Các cập nhật vùng chữ nhật cần cộng vào ô (r, c), trừ vào ô (r, y+1), trừ vào ô (x+1, c), và cộng vào ô (x+1, y+1). Lỗi vị trí sẽ dẫn đến sai lệch.
- Thứ tự duyệt: Phải đảm bảo duyệt theo thứ tự từ trên xuống dưới, trái sang phải để đảm bảo tính greedy.
- Trạng thái ban đầu và mục tiêu: Cần phân biệt rõ các giá trị 0, 1, 2 và mục tiêu 1 hoặc 2.
Bình luận