Tam Giác Pháo Hoa

Cho dãy độ dài các que pháo, ta cần chọn 3 que để tạo thành tam giác và phân loại.

Điều kiện tạo tam giác với ~(a \le b \le c): a + b > c~

Điều kiện phân loại tam giác

• Tam giác nhọn: ~(a^2 + b^2 > c^2)~
• Tam giác vuông: ~(a^2 + b^2 = c^2)~
• Tam giác tù: ~(a^2 + b^2 < c^2)~

Như vậy, với các nhận xét trên ta chỉ cần sắp xếp mảng tăng dần. Tạo mảng ~b_i = a_i^2~, sau đấy ta sẽ for duyệt các cặp cạnh ~(i, j)~ với ~i < j~ và sẽ đi tìm cạnh ~k~ ~(j < k)~ còn lại:

• Với tam giác nhọn: tìm vị trí đầu tiên ~idx~ sao cho ~b[idx] \ge b[i] + b[j]~ các ~k \in (j+1, idx-1) ~ là tam giác nhọn
• Với tam giác vuông: ta chỉ cần xét có tồn tại ~k~ mà ~b[k] = b[i] + b[j]~
• Với tam giác tù: tìm vị trí đầu tiên ~idx1~ sao cho ~b[k] > b[i] + b[j]~ và vị trí đầu tiên ~idx2~ sao cho ~(a[k] \ge a[i] + a[j])~ các ~k \in (idx1, idx2 - 1)~ là tam giác tù

Để tìm ~k~ được nhanh chóng ta có thể dùng kỹ thuật tìm kiếm nhị phân.

Độ phức tạp của lời giải trên: ~O(NlogN)~

Code mẫu tham khảo: Link

---

Di Chuyển Quân Tượng

Quân Tượng chỉ di chuyển trên các đường chéo của bàn cờ.

Điều kiện để quân Tượng có thể đi từ ~(R_1, C_1)~ đến ~(R_2, C_2)~: ~2~ ô phải cùng màu, tức là: ~(R_1 + C_1) \% 2 = (R_2 + C_2) \% 2~

• Nếu không thỏa mãn → không thể đi → in ~-1~
• Nếu hai vị trí trùng nhau: ~(R_1 = R_2)~ và ~(C_1 = C_2)~ → không cần di chuyển → in ~0~
• Nếu hai ô nằm trên cùng một đường chéo: ~|R_1 - R_2| = |C_1 - C_2|~ → đi được trong ~1~ bước
• Nếu cùng màu nhưng không cùng đường chéo → luôn đi được trong ~2~ bước

Độ phức tạp của lời giải trên: ~O(1)~

Code mẫu tham khảo: Link

---

Tham Quan Khu Nhà Của BQ

Ta cần tìm đường đi ngắn nhất để đi qua tất cả các căn nhà (nhóm các ô 'X').

Bài toán gồm 3 bước chính:

1. Gom các ô 'X' thành từng căn nhà
2. Tính khoảng cách giữa các căn nhà
3. Giải bài toán đi qua tất cả các căn nhà (bài toán TSP)

Bước 1: Gom nhóm các căn nhà

• Dùng DFS/BFS để gom các ô 'X' liên thông thành một nhóm
• Mỗi nhóm tương ứng với một căn nhà
• Gán id từ ~0 → N-1~

Bước 2: Tính khoảng cách giữa các căn nhà

Với mỗi căn nhà ~i~:

• Chạy BFS từ một ô bất kỳ của căn nhà ~i~
• Gọi ~dist[i][j]~ là khoảng cách ngắn nhất giữa căn nhà i và j

Bước 3: Quy hoạch động bitmask (TSP)

Gọi ~f[i][mask]~ là chi phí nhỏ nhất để:

• đã thăm các căn nhà trong ~mask~
• và hiện tại đang đứng ở căn nhà thứ ~i~

Trạng thái khởi tạo: ~f[i][1 << i] = 0~

Công thức chuyển trạng thái:

• Từ ~(i, mask)~ sang ~(j, mask | (1 << j))~: ~f[j][mask | (1 << j)] = \min(f[j][mask | (1 << j)],\ f[i][mask] + dist[i][j])~

Đáp án là: ~\min(f[i][(1 << N) - 1])~. Nếu không tồn tại đường đi nào → in ~-1~

Độ phức tạp

• Gom nhóm: ~O(R \cdot C)~
• BFS mỗi căn: ~O(N \cdot R \cdot C)~
• DP bitmask: ~O(N^2 \cdot 2^N)~

Code mẫu tham khảo: Link

---

Rút Bài Đầu Xuân

• Khoảng cách tối đa giữa ~2~ số nguyên tốt nhỏ hơn ~2 \cdot 10^9~ là không quá ~500~.
• XOR hoạt động theo từng bit độc lập
• Như vậy, giả sử bit thứ ~i~ của ~N~ đang bật ta chỉ việc tìm số nguyên tố ~p~ nhỏ nhất cũng có bit thứ ~i~ đang bật, khi XOR với số ~p~ thì ta chắc chắn sẽ bật được bit thứ ~i~ của ~N~. Thực hiện việc này từ bit thứ ~i~ lớn nhất XOR dần về các bit nhỏ nhất ta sẽ xây dựng lại được ~N~.
• Lưu ý, sẽ có trường hợp đặc biệt khi ~N = 1~, ta sẽ XOR cho ~2~ số nguyên tố là ~2~ và ~3~.

Độ phức tạp của lời giải trên:

• Tiền xử lý tìm các số nguyên tố ~p~ cho mỗi bit ~i~: ~O(30 * 500 * sqrt(N))~
• Với mỗi testcase: ~O(30)~

Code mẫu tham khảo: Link

---

Trang Trí Đèn Năm Mới

Gọi ~b[i][j]~ là tổng số ô bật trong hình vuông ~2 \times 2~ có góc trái trên tại ~(i, j)~. Tính chất quan trọng

• Khi đảo một hàng hoặc một cột:
  • Trạng thái từng ô thay đổi
  • Nhưng tính chẵn lẻ của ~b[i][j]~ không đổi

Với truy vấn ~(x1, y1, x2, y2)~: Nếu tồn tại ô ~b[i][j]~ lẻ với: ~x1 \le i < x2,\ y1 \le j < y2~ → Không thể biến toàn bộ thành bật → in ~NO~

Ngược lại, nếu tất cả ~b[i][j]~ đều chẵn, luôn có thể biến đổi được với ý tưởng:

• Dùng phép đảo hàng để chuẩn hóa cột đầu
• Sau đó các cột còn lại sẽ đồng nhất
• Dùng phép đảo cột để hoàn tất

Độ phức tạp của lời giải trên:

• Tiền xử lý: ~O(N \cdot M)~
• Mỗi truy vấn: ~O(1)~

Code mẫu tham khảo: Link