Editorial for square1: Thuật toán điểm giữa

Hiểu bài toán

Bài toán yêu cầu tính tổng số điểm được tạo ra sau N vòng lặp của thuật toán điểm giữa. Bắt đầu với 4 đỉnh của một hình vuông (N=0). Trong mỗi vòng lặp, với mỗi hình vuông hiện có, ta thêm:

1. 4 điểm trung điểm của các cạnh (mỗi cạnh được chia đôi).
2. 1 điểm trung tâm của hình vuông. Sau đó, mỗi hình vuông cũ được chia thành 4 hình vuông nhỏ hơn. Nhiệm vụ là tìm công thức tổng quát cho số điểm sau N vòng lặp.

• N=0: 4 điểm.
• N=1: 4 điểm cũ + 12 điểm biên mới (3 điểm/ cạnh * 4 cạnh) + 4 điểm tâm mới (1 điểm/hình * 4 hình) = 20 điểm? Không, đề bài nói N=1 ra 9 điểm. Xem lại mô tả. Mô tả: Bắt đầu 4 đỉnh. Vòng lặp 1:

1. Thêm điểm trung điểm của 4 cạnh. (4 điểm mới).
2. Thêm điểm tâm của hình vuông. (1 điểm mới). Tổng: 4 (cũ) + 4 (cạnh) + 1 (tâm) = 9 điểm. Các điểm này tạo thành 4 hình vuông. Vòng lặp 2: Áp dụng cho 4 hình vuông. Với mỗi hình vuông: thêm 4 điểm biên, 1 điểm tâm. Số lượng điểm mới: 4 * (4 + 1) = 20 điểm. Tổng điểm: 9 + 20 = 29? Đề bài Output 2 là 25.

Phân tích lại: N=1: 9 điểm (4 gốc + 4 biên + 1 tâm). N=2: 25 điểm. Chênh lệch: 25 - 9 = 16 điểm mới. Nếu có 4 hình vuông, mỗi hình thêm 5 điểm (4 biên, 1 tâm) thì thêm 20 điểm. Tại sao lại là 16? Có thể các điểm biên được chia sẻ. Xem xét đồ thị: Đỉnh (Vertices) V, Cạnh (Edges) E. Số điểm = V. N=0: V = 4. N=1: V = 9. N=2: V = 25. Công thức: N=0: (0+1)^2 * 4 = 4? (2^0 * 2)^2 = 4? N=1: 9 = 3^2. N=2: 25 = 5^2. N=3: Ta có thể dự đoán là 9^2 = 81. Quy luật: Số điểm sau N vòng lặp là (2^N + 1)^2. Kiểm tra: N=0: (1+1)^2 = 4. (OK). N=1: (2+1)^2 = 9. (OK). N=2: (4+1)^2 = 25. (OK). Giải thích: Hình vuông ban đầu chia làm 2^N đoạn theo mỗi chiều. Vậy có (2^N + 1) điểm dọc theo mỗi cạnh. Tổng số điểm trên lưới hình vuông là (2^N + 1)^2. Bài toán này thực chất là tìm số đỉnh của lưới hình vuông đều sau N bước chia đôi.

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

Cách Mô phỏng theo quy tắc xuất hiện

#include <stdio.h>
#include <math.h>

int main() {
    int n;
    scanf("%d", &n);
    // Sau N vòng lặp, mỗi cạnh được chia thành 2^n đoạn
    // Do đó có 2^n + 1 điểm trên mỗi cạnh
    // Tổng số điểm là (2^n + 1)^2
    // De quy ve so nguyen lon neu can, nhung N <= 15 nen int du
    int t = pow(2, n); // 2^n
    long long ans = (long long)(t + 1) * (t + 1);
    printf("%lld", ans);
    return 0;
}

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

Dựa trên quan sát số lượng điểm sau N vòng lặp là các số chính phương: 4, 9, 25... Ta thấy quy luật là (2^N + 1)^2. Với N <= 15, 2^15 = 32768, nên số điểm tối đa khoảng 10^9, nằm trong giới hạn của kiểu long long hoặc int (nếu dùng 64-bit hoặc cẩn thận). Công thức này lấy số điểm dọc theo một cạnh là (2^N + 1) và nhân lên cho cả lưới.

Cách Mô phỏng theo biến đổi đồ thị (Dựa trên code accepted)

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    // Solution 2: Tính m là số điểm dọc theo một cạnh
    // Ban đầu m = 2 (tương ứng 1 đoạn, 2 điểm đầu cuối)
    // Mỗi vòng lặp, số đoạn tăng gấp đôi, số điểm tăng thêm số đoạn mới (m-1)
    // m_new = m + (m - 1) = 2*m - 1
    // Vòng lặp 1: m = 2*2 - 1 = 3
    // Vong lap 2: m = 2*3 - 1 = 5
    // Ket qua cuoi cung: m*m
    long long m = 2;
    for(int i = 0; i < n; i++) {
        m = 2 * m - 1;
    }
    printf("%lld", m * m);
    return 0;
}

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

Đây là cách tiếp cận mô phỏng lại quá trình tăng số điểm. Thay vì dùng công thức tổng quát ngay, ta duy trì biến m là số điểm trên một cạnh (hoặc một chiều).

• Ban đầu: 2 điểm (m=2).
• Mỗi bước: Số đoạn tăng gấp đôi. Số điểm mới thêm = số đoạn cũ. M = (m-1)2 + 1 = 2m - 1. Sau N bước, ta có m điểm trên mỗi cạnh, tổng số điểm là mm. Cách này mô phỏng chính xác quy trình.

Cách Giải thích Logic (Tính toán trực tiếp)

#include <stdio.h>
#include <math.h>

int main() {
    int n;
    scanf("%d", &n);
    // Solution 3: Dùng pow
    // hvc = 2^n (so doan moi can)
    // s = (hvc + 1)^2
    int hvc = 1 << n; // 2^n
    printf("%lld", (long long)(hvc + 1) * (hvc + 1));
    return 0;
}

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

Cách này cài đặt trực tiếp công thức (2^N + 1)^2. Sử dụng phép dịch bit 1 << n để tính 2^N nhanh hơn và chính xác hơn hàm pow của thư viện math.h (vì pow trả về double, có thể sai số khi cast sang int).

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

Bài học kinh nghiệm

• Quy luật hình học: Sau mỗi bước, mỗi cạnh của các hình vuông được chia đôi, dẫn đến số điểm dọc theo mỗi chiều tăng theo quy luật: 2 -> 3 -> 5 -> 9... (công thức tổng quát: Pnew = 2*Pold - 1).
• Công thức tổng quát: Số điểm sau N vòng lặp chính là bình phương của số điểm trên một cạnh: (2^N + 1)^2.
• Vì N chỉ nhỏ (≤ 15), ta có thể sử dụng phép tính số học nguyên thông thường mà không cần đến số chính xác lớn (Big Integer).

Lỗi thường gặp

• Sử dụng kiểu dữ liệu quá nhỏ: Với N=15, kết quả là (32768 + 1)^2 ≈ 1.07 * 10^9. Nếu dùng int (32-bit) trên một số hệ thống có thể tràn số nếu không dùng long long.
• Lỗi logic về số lượng điểm mới: Cẩn thận phân biệt giữa số lượng hình vuông mới và số điểm mới. Điểm ở biên được chia sẻ giữa các hình vuông kề nhau.