Editorial for ptit013: Thu hoạch táo

Hiểu bài toán

Bài toán yêu cầu tìm một chu trình (cycle) đi qua tất cả các đỉnh của một lưới hình chữ nhật M x N (kích thước M x N ô vuông, do đó có (M+1) hàng đỉnh và (N+1) cột đỉnh), bắt đầu và kết thúc tại một đỉnh ở góc. Chu trình này phải thỏa mãn:

1. Chỉ đi theo các cạnh của lưới (đi ngang hoặc dọc).
2. Đi qua mỗi đỉnh đúng một lần (trừ đỉnh xuất phát/đích).
3. Số lần rẽ (thay đổi hướng di chuyển) là ít nhất. Đầu vào là M, N. Đầu ra là 'NO' nếu không có chu trình thỏa mãn, hoặc 'YES' kèm số lần rẽ tối thiểu nếu có. Về mặt toán học, đây là bài toán tìm chu trình Hamilton trên đồ thị lưới chữ nhật. Điều kiện tồn tại chu trình Hamilton là đồ thị phải có chu trình Euler, tức là tất cả các đỉnh đều có bậc chẵn. Trong lưới (M+1)x(N+1) đỉnh:

• Nếu cả M+1 và N+1 đều chẵn: Các góc có bậc 2 (chẵn), biên trong có bậc 3 (lẻ). => Không có chu trình.
• Nếu cả M+1 và N+1 đều lẻ: Các góc có bậc 2 (chẵn), biên trong có bậc 4 (chẵn). => Có chu trình.
• Nếu một trong hai chẵn, một lẻ: Các góc có bậc 2 (chẵn), biên trong có bậc 3 (lẻ). => Không có chu trình. Chú ý: M, N là số ô, nên số đỉnh là M+1, N+1. Kết luận điều kiện:
• Nếu (M+1) và (N+1) cùng lẻ => YES.
• Ngược lại => NO. Về số lần rẽ: Chu trình Hamilton trên lưới lưỡng phân (do M+1, N+1 lẻ) có thể được tạo ra bằng cách zig-zag. Số lần rẽ sẽ phụ thuộc vào kích thước.

Các cách tiếp cận

Cách Phân tích trực tiếp theo điều kiện tồn tại chu trình Hamilton

#include <iostream>
using namespace std;

int main() {
    long long m, n;
    cin >> m >> n;
    long long rows = m + 1;
    long long cols = n + 1;

    // Điều kiện tồn tại:
    // Số hàng đỉnh (rows) và số cột đỉnh (cols) phải cùng lẻ.
    // Tức là M và N phải cùng chẵn.
    if (rows % 2 == 1 && cols % 2 == 1) {
        // Xác định số lần rẽ dựa trên việc tạo chu trình zig-zac.
        // Nếu cả rows và cols đều lẻ, ta có thể tạo chu trình.
        // Số lần rẽ sẽ là 2 * min(rows, cols) - 1.
        long long re = 2 * min(rows, cols) - 1;
        cout << "YES " << re;
    } else {
        cout << "NO";
    }
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Giải pháp này dựa trên nhận thức toán học rằng một lưới (M+1)x(N+1) có chu trình Hamilton đi qua mọi đỉnh khi và chỉ khi cả M+1 và N+1 đều là số lẻ. Logic kiểm tra là rows % 2 == 1 && cols % 2 == 1. Nếu điều kiện này thỏa mãn, ta tính số lần rẽ. Công thức 2 * min(rows, cols) - 1 được suy ra từ cấu trúc của chu trình trên lưới hình chữ nhật có một cạnh chẵn và một cạnh lẻ (vì rows và cols cùng lẻ, nên M, N cùng chẵn, một trong M, N có thể lớn hơn hoặc bằng).

Cách Giải pháp tối ưu (Xử lý các trường hợp)

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long m, n;
    if (!(cin >> m >> n)) return 0;
    long long hang = m + 1;
    long long cot = n + 1;

    // Trường hợp biên: Nếu một cạnh bằng 1 (M hoặc N bằng 0 theo đề bài, nhưng giới hạn >=1)
    // Nếu hang == 1 hoặc cot == 1, đồ thị là đường thẳng, không có chu trình.
    if (hang == 1 || cot == 1) {
        cout << "NO";
        return 0;
    }

    // Kiểm tra điều kiện chính: cả hang và cot đều phải lẻ.
    if ((hang % 2 == 1) && (cot % 2 == 1)) {
        long long re;
        bool hangChan = (hang % 2 == 0);
        bool cotChan = (cot % 2 == 0);
        // Logic tính toán số lần rẽ:
        // Nếu cả hai đều lẻ (hangChan = false, cotChan = false), khối này không chạy.
        // Các giải pháp gốc có vẻ xử lý thêm trường hợp chẵn/lẻ léo.
        // Thực tế, với điều kiện题设 (M, N >= 1), công thức chung cho trường hợp TỒN TẠI là:
        // 2 * min(hang, cot) - 1.
        // Code dưới đây là biến thể tổng quát, nhưng với input bài này, ta chỉ vào nhánh else cuối.

        // Tuy nhiên, code gốc kiểm tra như sau:
        if (hangChan && cotChan) {
            re = 2LL * min(hang, cot) - 1;
        } else if (hangChan) {
            re = 2LL * hang - 1;
        } else {
            re = 2LL * cot - 1;
        }
        cout << "YES " << re;
    } else {
        cout << "NO";
    }
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là phiên bản chi tiết hơn của Solution 1. Nó thêm các kiểm tra an toàn cho các trường hợp biên (hàng hoặc cột bằng 1). Logic tính toán số lần rẽ được thực hiện dựa trên giá trị chẵn/lẻ của hàng và cột. Mặc dù code có các nhánh if-else cho các trường hợp chẵn/chẵn, chẵn/lẻ, nhưng với điều kiện đề bài yêu cầu chu trình Hamilton (cùng lẻ), chỉ có nhánh else cuối cùng được thực thi trong các trường hợp hợp lệ. Tuy nhiên, cấu trúc này cho thấy tác giả đã cân nhắc các trường hợp lưới có kích thước chẵn/lẻ.

Cách Phương pháp dựng chu trình Zig-Zag

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    long long m, n;
    cin >> m >> n;
    // Số lượng đỉnh hàng ngang là m+1, cột dọc là n+1
    long long r = m + 1;
    long long c = n + 1;

    // Điều kiện cần và đủ để có chu trình Hamilton trên lưới:
    // Đồ thị phải có chu trình Euler -> tất cả đỉnh có bậc chẵn.
    // Trong lưới (r x c):
    // - Nếu r và c đều lẻ: Các góc có bậc 2, trong có bậc 4 (chẵn) -> OK.
    // - Nếu r hoặc c chẵn: Có đỉnh bậc 3 (lẻ) -> KHÔNG OK.
    if (r % 2 != 1 || c % 2 != 1) {
        cout << "NO";
        return 0;
    }

    // Để tính số lần rẽ, ta dùng kỹ thuật Zig-Zag.
    // Giả sử r <= c (hoặc ngược lại).
    // Chu trình đi theo hình sin (zig-zag).
    // Số lần rẽ = (Số đoạn ngang - 1) * 2 + (Số đoạn dọc).
    // Hoặc tính đơn giản: 2 * min(r, c) - 1.
    long long min_dim = min(r, c);
    long long turns = 2 * min_dim - 1;

    cout << "YES " << turns << endl;
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Phương pháp này là một cách giải thích trực quan của thuật toán 1. Nó chính thức hóa logic bằng cách kiểm tra xem số hàng và số cột của lưới đỉnh có phải là số lẻ hay không. Sau đó, nó tính toán số lần rẽ bằng cách coi việc di chuyển 'zig-zag' là cách hiệu quả nhất để bao phủ lưới. Khi đi zig-zag, bạn rẽ 2 lần cho mỗi 'bước' lặp lại (một lần xuống, một lần trở lại), cộng với các rẽ ở đầu mút. Số lần rẽ tối thiểu được chứng minh là 2 * min(r, c) - 1.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể được chuyển hóa thành bài toán tìm chu trình Hamilton trên đồ thị lưới (M+1)x(N+1).
• Điều kiện tồn tại chu trình Hamilton trên lưới hình chữ nhật là số hàng và số cột của đỉnh đều phải là số lẻ (tương đương M và N đều là số chẵn).
• Số lần rẽ tối thiểu trong chu trình Hamilton trên lưới có thể được tính bằng công thức: 2 * min(M+1, N+1) - 1.

Lỗi thường gặp

• Nhầm lẫn giữa kích thước ô đất (M, N) và kích thước lưới đỉnh (M+1, N+1). Điều kiện chẵn/lẻ phải áp dụng lên M+1 và N+1.
• Quên kiểm tra các trường hợp biên (ví dụ M=1, N=1) dẫn đến kết quả sai lệch.
• Suy nghĩ sai lệch về điều kiện 'ưu tiên đi thẳng'. Trong bài toán tối ưu hóa số rẽ trên lưới Hamilton, 'đi thẳng' không có nghĩa là không rẽ, mà là rẽ ở mức tối thiểu để bao phủ hết lưới. Cấu trúc zig-zag là tối ưu.