Phân tích bài toán

• Mỗi bước biến đổi thay đổi 4 phần tử liên tiếp trong dãy: \(a_i, a_{i+1}, a_{i+2}, a_{i+3}\) thành \(|a_i - a_{i+1}|, |a_{i+1} - a_{i+2}|, |a_{i+2} - a_{i+3}|, |a_{i+3} - a_i|\).
• Mục tiêu là đưa tất cả phần tử về 0, tức là trạng thái \([0, 0, ..., 0]\).
• Đây là bài toán tìm kiếm trạng thái, cần tìm số bước tối thiểu để đạt được trạng thái mục tiêu.
• Vì \(n \leq 8\) và \(a_i \leq 10^9\), không gian trạng thái có thể rất lớn, nhưng ta có thể tối ưu hóa bằng cách chuẩn hóa dãy và sử dụng tìm kiếm có giới hạn (Iterative Deepening DFS - IDDFS).

Ý tưởng giải

1. Chuẩn hóa dãy:

   • Quan sát rằng phép biến đổi dựa trên hiệu tuyệt đối \(|a - b|\). Nếu tất cả các phần tử trong dãy chia hết cho một số \(g\) (ƯCLN của các phần tử khác 0), ta có thể chia toàn bộ dãy cho \(g\) mà không ảnh hưởng đến tính chất của bài toán.
   • Điều này giúp giảm giá trị các phần tử, thu hẹp không gian trạng thái.

2. Tìm kiếm trạng thái:

   • Sử dụng thuật toán Iterative Deepening DFS (IDDFS) để tìm số bước tối thiểu.
   • Ở mỗi bước, thử tất cả các lựa chọn 4 phần tử liên tiếp (\(n - 3\) lựa chọn với \(n \leq 8\)).
   • Với mỗi lựa chọn, tạo trạng thái mới sau khi biến đổi và tiếp tục tìm kiếm.

3. Tối ưu hóa:

   • Bộ nhớ: Sử dụng \(unordered_map\) để lưu các trạng thái đã duyệt, tránh lặp lại.
   • Ưu tiên trạng thái: Sắp xếp các trạng thái con theo tổng giá trị các phần tử (\(sum(a_i)\)) để thử các trạng thái "gần" với toàn 0 trước.
   • Giới hạn độ sâu: Thử các độ sâu từ 0 đến một giới hạn (ví dụ: 50) để đảm bảo tìm được đáp án tối thiểu.

4. Kiểm tra trạng thái mục tiêu:

   • Một trạng thái được coi là mục tiêu nếu tất cả phần tử bằng 0.

Cách giải chi tiết

Dựa trên đoạn code bạn cung cấp, dưới đây là các bước giải bài toán:

Bước 1: Đọc input và khởi tạo

• Đọc dãy số vào vector \(v\).
• Tạo cấu trúc \(State\) để biểu diễn trạng thái của dãy, chứa mảng \(a[8]\).
• Gán \(gN = n\) (số phần tử của dãy).
• Khởi tạo trạng thái ban đầu \(start\) với \(start.a[i] = v[i]\).

Bước 2: Chuẩn hóa dãy

• Tính ƯCLN (\(g\)) của các phần tử khác 0 trong dãy.
• Chia tất cả phần tử cho \(g\) để thu gọn giá trị.
• Nếu dãy đã toàn 0 sau khi chuẩn hóa, in ra \(0\) và kết thúc.

Code chuẩn hóa:

int gcd_int(int a, int b) {
    if (b == 0) return a;
    return gcd_int(b, a % b);
}

void chuanHoa(State &s) {
    int g = 0;
    for (int i = 0; i < gN; i++) {
        if (s.a[i]) {
            g = (g == 0 ? s.a[i] : gcd_int(g, s.a[i]));
        }
    }
    if (g > 1)
        for (int i = 0; i < gN; i++)
            s.a[i] /= g;
}

Bước 3: Tìm kiếm với IDDFS

• Sử dụng thuật toán IDDFS với độ sâu tăng dần từ \(0\) đến \(50\).
• Với mỗi độ sâu \(limit\), chạy DFS với giới hạn độ sâu để kiểm tra xem có thể đạt trạng thái toàn 0 không.
• Trong DFS:
  • Nếu trạng thái hiện tại toàn 0, trả về \(true\).
  • Nếu độ sâu đạt \(limit\), trả về \(false\).
  • Nếu trạng thái đã được duyệt với độ sâu nhỏ hơn, bỏ qua.
  • Thử tất cả các lựa chọn 4 phần tử liên tiếp (\(i\) từ \(0\) đến \(gN - 4\)):
    • Tạo trạng thái mới \(nxt\) sau khi biến đổi.
    • Chuẩn hóa trạng thái \(nxt\).
    • Tính tổng các phần tử (\(tinhDiem\)) để ưu tiên trạng thái có tổng nhỏ.
  • Sắp xếp các trạng thái con theo tổng tăng dần.
  • Thử DFS trên từng trạng thái con.

Code DFS:

bool dfs(State s, int depth, int limit) {
    if (khongCo(s)) return true;
    if (depth == limit) return false;
    if (memo.find(s) != memo.end() && memo[s] <= depth) return false;
    memo[s] = depth;

    vector<pair<long long, State>> StateSau;
    for (int i = 0; i <= gN - 4; i++) {
        State nxt = s;
        int a = s.a[i], b = s.a[i+1], c = s.a[i+2], d_val = s.a[i+3];
        nxt.a[i] = abs(a - b);
        nxt.a[i+1] = abs(b - c);
        nxt.a[i+2] = abs(c - d_val);
        nxt.a[i+3] = abs(d_val - a);
        chuanHoa(nxt);
        StateSau.push_back({tinhDiem(nxt), nxt});
    }
    sort(StateSau.begin(), StateSau.end(), [](auto &p1, auto &p2) {
        return p1.first < p2.first;
    });
    for (auto &p : StateSau)
        if (dfs(p.second, depth + 1, limit)) return true;
    return false;
}

Bước 4: In kết quả

• Với mỗi độ sâu \(limit\) từ \(0\) đến \(50\):
  • Xóa bộ nhớ \(memo\) để tránh tràn.
  • Nếu DFS trả về \(true\) với độ sâu \(limit\), in \(limit\) và kết thúc.
• Nếu không tìm được đáp án sau \(50\) bước, in \(-1\).

Code chính:

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<int> v;
    int x;
    while (cin >> x) v.push_back(x);
    gN = v.size();
    State start;
    for (int i = 0; i < gN; i++) start.a[i] = v[i];
    chuanHoa(start);
    if (khongCo(start)) {
        cout << 0 << "\n";
        return 0;
    }
    for (int limit = 0; limit <= 50; limit++) {
        memo.clear();
        if (dfs(start, 0, limit)) {
            cout << limit << "\n";
            return 0;
        }
    }
    cout << -1 << "\n";
    return 0;
}

Ví dụ minh họa

Input: \(0, 1, 3, 5, 9\)

Quá trình biến đổi (theo đề bài):

1. \(0, 1, 3, 5, 9\) → \(0, 2, 2, 4, 8\) (chọn \(i=1\))
2. \(0, 2, 2, 4, 8\) → \(0, 0, 2, 4, 6\) (chọn \(i=1\))
3. \(0, 0, 2, 4, 6\) → \(0, 2, 2, 2, 6\) (chọn \(i=2\))
4. \(0, 2, 2, 2, 6\) → \(0, 0, 0, 4, 4\) (chọn \(i=1\))
5. \(0, 0, 0, 4, 4\) → \(0, 0, 4, 0, 4\) (chọn \(i=2\))
6. \(0, 0, 4, 0, 4\) → \(0, 4, 4, 4, 4\) (chọn \(i=2\))
7. \(0, 4, 4, 4, 4\) → \(0, 0, 0, 0, 0\) (chọn \(i=1\))

Output: \(7\)

Tối ưu hóa

• Chuẩn hóa: Giảm giá trị phần tử bằng cách chia cho ƯCLN.
• Ưu tiên trạng thái: Sắp xếp trạng thái con theo tổng để thử các trạng thái "gần" mục tiêu trước.
• Bộ nhớ: Sử dụng \(unordered_map\) với hàm băm tùy chỉnh (\(StateHash\)) để lưu trạng thái.
• IDDFS: Tăng độ sâu từ từ, đảm bảo tìm đáp án tối thiểu mà không tiêu tốn quá nhiều bộ nhớ.

Độ phức tạp

• Thời gian:
  • Mỗi bước DFS tạo tối đa \(n - 3 \leq 5\) trạng thái con.
  • Với độ sâu tối đa \(50\), số trạng thái có thể rất lớn, nhưng được giới hạn bởi bộ nhớ và chuẩn hóa.
  • Tổng thời gian phụ thuộc vào số trạng thái duyệt được, tối ưu hóa bởi \(memo\) và chuẩn hóa.
• Không gian: \(O(1)\) cho mảng \(State\), cộng với \(unordered_map\) lưu trữ các trạng thái (phụ thuộc vào số trạng thái duy nhất).

Kết luận

Thuật toán sử dụng IDDFS kết hợp với chuẩn hóa dãy và ưu tiên trạng thái là một cách tiếp cận hiệu quả cho bài toán. Nó đảm bảo tìm được số bước tối thiểu hoặc xác định không có lời giải trong thời gian hợp lý, phù hợp với các ràng buộc của đề bài.