Phân tích: Crop Triangles

Tập dữ liệu nhỏ (Small case) có thể dễ dàng giải quyết bằng cách duyệt trâu (brute force). Đối với mỗi tổ hợp ba điểm, bạn cần kiểm tra xem trọng tâm có tọa độ nguyên hay không. Một phần khó khăn là việc tạo ra dãy các điểm, vì sử dụng số nguyên 32-bit có thể dẫn đến tràn số khi thực hiện các phép nhân. Một cách để giải quyết vấn đề đó là sử dụng số nguyên 64-bit.

Quan sát giúp giải quyết tập dữ liệu lớn (Large case) là chúng ta không cần quan tâm đến phạm vi tọa độ của các điểm trong đầu vào. Chúng ta chỉ quan tâm đến tọa độ modulo 3.

Để trọng tâm \(((x_1 + x_2 + x_3) / 3, (y_1 + y_2 + y_3) / 3)\) có tọa độ nguyên, ta cần:

• \((x_1 + x_2 + x_3) \equiv 0 \pmod 3\)
• \((y_1 + y_2 + y_3) \equiv 0 \pmod 3\)

Chúng ta có 9 loại điểm khác nhau dựa trên số dư khi chia cho 3. Trong bucket[i], chúng ta sẽ đếm số lượng điểm mà \(x \pmod 3 = i / 3\) và \(y \pmod 3 = i \pmod 3\). Có ba kiểu chọn 3 điểm từ 9 lớp này: cả ba điểm cùng lớp; đúng hai điểm cùng lớp; hoặc ba điểm thuộc ba lớp khác nhau. Trong đó, các bộ hợp lệ gồm:

1. Cả ba điểm thuộc cùng một lớp.
2. Ba điểm thuộc ba lớp khác nhau \((x_1, y_1), (x_2, y_2), (x_3, y_3)\) sao cho \((x_1+x_2+x_3) \equiv 0 \pmod 3\) và \((y_1+y_2+y_3) \equiv 0 \pmod 3\).

Dễ dàng nhận thấy rằng không thể có tam giác nào có đúng hai điểm cùng loại và điểm còn lại thuộc loại khác mà vẫn thỏa mãn điều kiện trọng tâm là điểm lưới.

Dưới đây là đoạn mã thực hiện ý tưởng này:

    for (int i = 0; i < n; i++) {
      bucket[((int)X0 % 3) * 3 + (int)Y0 % 3]++;
      X0 = (A * X0 + B) % M;
      Y0 = (C * Y0 + D) % M;
    }

    // The first case.
    for (int i = 0; i < 9; i++)
      // We use the formula for n choose 3 so that,
      // we don't use the same point twice or count
      // the same triangle more than once.
      ret += bucket[i] * (bucket[i]-1) * (bucket[i]-2) / 6;

    // The third case.
    for (int i = 0; i < 9; i++)
      for (int j = i + 1; j < 9; j++)
        for (int k = j + 1; k < 9; k++)
          if (((i / 3) + (j / 3) + (k / 3)) % 3 == 0) &&
              ((i % 3) + (j % 3) + (k % 3)) % 3 == 0)
            ret += bucket[i] * bucket[j] * bucket[k];
    cout << "Case #" << prob++ << ": " << ret << endl;

Độ phức tạp

• Việc tạo các điểm mất \(O(n)\).
• Việc đếm các điểm vào 9 thùng (buckets) mất \(O(n)\).
• Việc tính toán số lượng tam giác từ 9 thùng mất \(O(9^3)\) hoặc \(O(9)\) tùy cách cài đặt, đây là hằng số.
• Tổng độ phức tạp: \(O(n)\) cho mỗi bộ test.

Dựa trên phân tích chính thức của Google Code Jam.