Hiểu bài toán

Bài toán yêu cầu tìm số tại vị trí dòng x, cột y trong một ma trận vô hạn được điền theo hình zig-zag. Ma trận bắt đầu bằng số 1 tại (1,1). Các đường chéo song song với đường chéo chính của ma trận được điền lần lượt. Cụ thể, các số trên một đường chéo có hiệu dòng - cột bằng nhau. Ta cần tính toán nhanh giá trị tại (x, y) mà không cần xây dựng ma trận.

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

Cách Phân tích theo đường chéo (Quy luật)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        long long x, y;
        cin >> x >> y;
        long long n = max(x, y);
        long long ans;

        if (n % 2 == 0) {
            // Hang chan: n*n nam o (n, 1)
            if (x == n) {
                ans = n * n - (y - 1);
            } else { // y == n
                ans = (n - 1) * (n - 1) + x;
            }
        } else {
            // Hang le: n*n nam o (1, n)
            if (y == n) {
                ans = n * n - (x - 1);
            } else { // x == n
                ans = (n - 1) * (n - 1) + y;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

• Time Complexity: O(1) cho mỗi query
• Space Complexity: O(1)

Cách tiếp cận này dựa trên việc quan sát quy luật của ma trận zig-zag. Xác định 'độ lớn' của vị trí (x, y) bằng n = max(x, y). Đây là đường chéo thứ n (tính từ ngoài vào).

• Nếu n là số chẵn:
  • Số cuối cùng của đường chéo (số lớn nhất trong các số có max(x,y) = n) là nn, nằm tại (n, 1).
  • Nếu vị trí nằm ở hàng cuối cùng (x = n), ta đi ngược lại từ nn giảm dần theo cột.
  • Nếu vị trí nằm ở cột cuối cùng (y = n), ta đi顺著 từ (n-1)*(n-1) tăng dần theo hàng.
• Nếu n là số lẻ:
  • Số cuối cùng của đường chéo là nn, nằm tại (1, n).
  • Nếu vị trí nằm ở cột cuối cùng (y = n), ta đi ngược lại từ nn giảm dần theo hàng.
  • Nếu vị trí nằm ở hàng cuối cùng (x = n), ta đi顺著 từ (n-1)*(n-1) tăng dần theo cột. Công thức được suy ra trực tiếp từ các quan sát này.

Cách Phân loại theo dòng và cột

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        long long x, y;
        cin >> x >> y;
        if (max(x, y) == y) {
            if (y % 2 == 0) cout << (y - 1) * (y - 1) + x << endl;
            else cout << y * y - (x - 1) << endl;
        } else {
            if (x % 2 == 0) cout << x * x - (y - 1) << endl;
            else cout << (x - 1) * (x - 1) + y << endl;
        }
    }
    return 0;
}

• Time Complexity: O(1) cho mỗi query
• Space Complexity: O(1)

Cách tiếp cận này chia vấn đề dựa trên việc so sánh x và y để xác định dòng hay cột nào chứa số cuối cùng của đường chéo.

1. Nếu y >= x (vị trí nằm ở nửa trên hoặc biên phải của đường chéo):
   • Nếu y chẵn: Số đầu tiên của đường chéo (số nhỏ nhất) nằm ở (1, y) với giá trị (y-1)^2 + 1. Giá trị tại (x, y) tăng dần theo x, nên là (y-1)^2 + x.
   • Nếu y lẻ: Số đầu tiên của đường chéo nằm ở (y, 1) với giá trị (y-1)^2 + 1. Giá trị tại (x, y) tăng dần theo y - hàng, tức là giảm khi đi lên. Giá trị tại (x, y) là y^2 - (x - 1).
2. Nếu x > y (vị trí nằm ở nửa dưới hoặc biên trái của đường chéo):
   • Nếu x chẵn: Số đầu tiên của đường chéo nằm ở (x, 1) với giá trị (x-1)^2 + 1. Giá trị tăng dần theo y - cột, nên là (x-1)^2 + y.
   • Nếu x lẻ: Số đầu tiên của đường chéo nằm ở (1, x) với giá trị (x-1)^2 + 1. Giá trị tăng dần theo x - hàng, tức là giảm khi đi lên. Giá trị tại (x, y) là x^2 - (y - 1). Logic này tương đương với cách tiếp cận 1 nhưng được trình bày dưới dạng các nhánh rẽ dựa trên quan hệ giữa x và y.

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

Bài học kinh nghiệm

• Ma trận được điền theo các đường chéo. Giá trị tại vị trí (x, y) phụ thuộc vào đường chéo chứa nó.
• Đường chéo thứ k (k = max(x, y)) chứa các số từ (k-1)^2 + 1 đến k^2.
• Kiểm tra tính chẵn/lẻ của max(x, y) để xác định hướng điền (tăng/giảm) của các số trên đường chéo.

Lỗi thường gặp

• Sử dụng biến kiểu int dẫn đến tràn số (overflow) khi x, y lên tới 10^7 (kết quả có thể lên tới 10^14). Cần dùng long long.
• Nhầm lẫn giữa các trường hợp chẵn/lẻ của dòng và cột khi xây dựng công thức toán học.