Kỳ thi: IOI 2026 — Day 1
Tóm tắt: Ngày thi đầu tiên mang đến ba thử thách đa dạng từ tương tác phục hồi cấu trúc cây, tìm phương án dịch chuyển điểm đạt đối xứng với chi phí tối thiểu, đến thiết lập chiến thuật xếp khối trên lưới trực tuyến.

Trong IOI 2026 Ngày 1 Bài 1 - Ball Machine, bạn chỉ biết số lượng nút lá \(M\) và phải tìm cấu trúc cây ẩn thông qua các thao tác chèn bóng vào lá rồi thu thập lại dãy giá trị theo thứ tự duyệt đệ quy. Khi một quả bóng được chèn vào một lá trống, nó sẽ di chuyển lên trên dọc theo đường đi tới gốc cho đến khi gặp nút bị chiếm dụng hoặc chạm đỉnh. Với ràng buộc tổng số lần thu thập và giá trị bóng lớn nhất \(K + B \le 1000\), điều quan trọng là quan sát thứ tự xuất hiện của các giá trị trong mảng kết quả sau mỗi lần giải phóng máy để xác định quan hệ cha con giữa các nút.

Tiếp theo, IOI 2026 Ngày 1 Bài 2 - Monuments đặt ra bài toán di chuyển \(N\) di tích trên trục tọa độ sao cho số lượng điểm tại mỗi vị trí \(x > 0\) bằng số lượng điểm tại \(-x\), đồng thời tối thiểu hóa tổng khoảng cách dịch chuyển. Khó khăn nằm ở \(M\) vị trí cố định không được phép xê dịch, có thể khiến việc tạo tính đối xứng trở nên bất khả thi. Khi tiếp cận, bạn cần quan sát các vị trí cố định đã cho để ghép cặp hoặc bù các di tích tự do vào vị trí đối diện tương ứng nhằm tối ưu chi phí.

Tại IOI 2026 Ngày 1 Bài 3 - Tiling Game, bạn phải nhận lần lượt từng khối kích thước \(2 \times 2\) có từ \(0\) đến \(3\) ô đen và đặt ngay vào lưới \(2N \times 2M\) tại các ô có hàng và cột chẵn. Mục tiêu là xếp kín lưới mà không để tạo thành bất kỳ hình vuông \(2 \times 2\) toàn ô đen nào tại bất kỳ vị trí nào, kể cả các vị trí lệch chẵn lẻ. Điểm mấu chốt là cần phân tích vị trí các ô trắng của từng khối nhận được để sắp đặt biên tiếp xúc giữa các khối lân cận một cách an toàn.

Bạn nên bắt đầu đọc và giải Monuments trước để rèn luyện tư duy phân nhóm và tối ưu chi phí, sau đó chuyển sang thử sức với Ball Machine và Tiling Game để xử lý các bài toán tương tác.