Thảo luận kỳ thi

Kỳ thi: Chọn HSG tỉnh THPT Gia Lai 2025-2026
Tóm tắt: Đề thi gồm 4 bài toán kiểm tra các kỹ năng trọng tâm của học sinh giỏi, trải dài từ đếm số học bằng bao hàm - loại trừ, quy hoạch động đoạn trên xâu, đến tham lam kết hợp chặt nhị phân và cấu trúc dữ liệu gộp tập hợp.

Trong Bài 1: Đếm dãy (Chọn HSG cấp tỉnh THPT Gia Lai 2025-2026), yêu cầu đếm số dãy số nguyên dương có tổng bằng \(S\) và ước chung lớn nhất bằng \(1\) dễ khiến người làm nghĩ đến việc duyệt phân hoạch. Tuy nhiên khi \(S\) lên tới \(10^9\), quan sát thấy tổng số dãy có tổng \(S\) luôn là \(2^{S-1}\) giúp chuyển bài toán về việc trừ đi các dãy có ước chung lớn hơn \(1\) thông qua phân tích thừa số nguyên tố của \(S\) và áp dụng nguyên lý bao hàm - loại trừ.

Cấu trúc đề tiếp tục thử thách khả năng xử lý truy vấn nhanh qua Bài 2: Xâu đối xứng (Chọn HSG cấp tỉnh THPT Gia Lai 2025-2026). Với độ dài xâu \(N \le 5000\), ta có thể xác định tính đối xứng của mọi đoạn con trước, sau đó xây dựng bảng quy hoạch động hai chiều theo công thức tiền tố \(dp[l][r] = dp[l+1][r] + dp[l][r-1] - dp[l+1][r-1] + pal[l][r]\) để trả lời mỗi truy vấn trong thời gian \(O(1)\).

Nửa sau của đề tập trung vào tư duy tối ưu hóa và tổ chức dữ liệu. Bài 3: Chọn quà (Chọn HSG cấp tỉnh THPT Gia Lai 2025-2026) yêu cầu nhận xét chỉ có tối đa một loại quà được chọn nhiều lần để duyệt từng mốc \(b_i\) kết hợp mảng tiền tố và chặt nhị phân, trong khi Bài 4: Tải ứng dụng (Chọn HSG tỉnh THPT Gia Lai 2025-2026) là ví dụ chuẩn mực cho việc dùng Disjoint Set Union kết hợp kỹ thuật gộp bảng băm từ tập nhỏ sang tập lớn (small-to-large).

Bạn nên bắt đầu giải từ Bài 2: Xâu đối xứng (Chọn HSG cấp tỉnh THPT Gia Lai 2025-2026) để khởi động kỹ năng quy hoạch động mảng hai chiều, trước khi chuyển sang phân tích số học ở Bài 1: Đếm dãy (Chọn HSG cấp tỉnh THPT Gia Lai 2025-2026) và thử sức với hai bài còn lại.

Kỳ thi: IOI 2026 — Day 2
Tóm tắt: Ngày thi thứ hai của IOI 2026 mang đậm màu sắc xây dựng và giao tiếp thông tin, đặt trọng tâm vào việc thiết kế giao thức và mô hình hóa cấu trúc đồ thị thay vì các cấu trúc dữ liệu thuần túy.

Trong IOI 2026 Ngày 2 Bài 1 - Classroom Game, bạn phải giúp các giáo viên ghi lại dãy số tối đa \(63\) phần tử lên tờ giấy của học sinh chưa giơ tay để sau \(M\) lượt hoán đổi vị trí bí mật, hiệu trưởng vẫn xác định chính xác thời điểm từng người đã giơ tay. Cách tiếp cận trực tiếp là cố gắng ghi đè mốc thời gian ngay tại vị trí học sinh, nhưng việc các tờ giấy bị luân chuyển theo hoán vị ẩn đòi hỏi bạn phải thiết kế cách mã hóa và lưu vết thông tin sao cho không bị thất lạc qua từng lượt.

Màu sắc xây dựng tiếp tục thể hiện rõ ở IOI 2026 Ngày 2 Bài 2 - Magic City, nơi bạn cần tạo ra một mạng lưới các điểm tham quan thuộc \(2K\) loại sao cho mọi bộ ba loại thú vị đều xuất hiện dưới dạng đường đi độ dài \(2\), trong khi bậc của mỗi đỉnh không vượt quá \(K\). Với việc tối ưu điểm số dựa trên số đỉnh \(N\), bài toán đặt ra thách thức gom cụm và tái sử dụng các cạnh nối một cách hiệu quả để thỏa mãn mọi bộ ba chuyển tiếp với quy mô đồ thị nhỏ nhất.

Độ thử thách của contest còn nằm ở IOI 2026 Ngày 2 Bài 3 - Partition, khi người thứ nhất được phép bổ sung tối đa \(K - 1\) giá trị vào mảng ban đầu để người thứ hai chỉ cần nhìn mảng sau khi sắp xếp là có thể chia đều thành \(K\) nhóm có tổng bằng nhau. Câu hỏi mấu chốt là làm thế nào để chọn ra ít số nhất nhằm vừa cân bằng tổng các nhóm, vừa để lại tín hiệu nhận diện phân hoạch rõ ràng sau khi mảng đã bị xáo trộn thứ tự bởi thao tác sắp xếp.

Bộ đề ngày 2 rất đáng để rèn luyện kỹ năng phân tích bất biến và thiết kế chiến thuật trong các bài toán giao tiếp. Bạn nên bắt đầu làm quen từ IOI 2026 Ngày 2 Bài 2 - Magic City để rèn luyện tư duy ghép nối đồ thị, sau đó tiến tới thử thách mã hóa trạng thái ở IOI 2026 Ngày 2 Bài 1 - Classroom Game và IOI 2026 Ngày 2 Bài 3 - Partition.

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.

Kỳ thi: NOI Trung Quốc 2026 - Ngày 2
Tóm tắt: Kỳ thi Ngày 2 của CCF NOI 2026 mang đến bộ ba bài toán điển hình về tư duy biến đổi điều kiện: từ kỹ thuật chặt nhị phân kết hợp quy hoạch động kiểm tra tính khả thi, bài toán cấu trúc dữ liệu truy vấn quan hệ kề trên cây qua mã Prüfer, đến bài toán đếm cây nâng cao bằng quy hoạch động trên cây kết hợp bao hàm loại trừ.

Ở NOI Trung Quốc 2026 - Median, bài toán yêu cầu chia dãy thành \(k\) đoạn liên tiếp sao cho trung vị của các trung vị từng đoạn đạt giá trị lớn nhất. Thay vì tối ưu trực tiếp giá trị thực, hướng tiếp cận trực tiếp là chặt nhị phân đáp án \(x\), sau đó gán mỗi phần tử bằng \(+1\) nếu \(a_i \ge x\) và \(-1\) nếu ngược lại. Với \(k \le 5\), bài toán kiểm tra quy về quy hoạch động theo số đoạn đã phân chia cùng tổng giá trị dấu; khi \(k\) lớn, tính khả thi có thể xác định nhanh qua vị trí và khoảng cách giữa các phần tử nhận giá trị \(1\).

Chuyển sang NOI Trung Quốc 2026 - Kapok, mỗi đoạn con \([l, r)\) trong dãy ký ức mô tả một cây thông qua mã Prüfer, và ta cần trả lời \(m\) truy vấn kiểm tra hai đỉnh \(x, y\) có kề nhau hay không. Do mỗi truy vấn gắn với một đoạn độ dài thay đổi và phép giới hạn giá trị \(\min(a_i, k-1)\), việc xử lý độc lập từng truy vấn rất tốn kém. Cách giải quyết hiệu quả là phân nhóm truy vấn theo thuật toán Mo kết hợp mảng lưu vị trí xuất hiện gần nhất và chia khối để duy trì thông tin dựng cạnh kề của cây.

Bài toán đòi hỏi kỹ thuật đại số và tổ hợp cao nhất là NOI Trung Quốc 2026 - Rainbow Tree, yêu cầu đếm cấu hình trên cây có gốc gồm \(n \le 200\) đỉnh lấy dư theo \(998244353\). Hướng xử lý dựa trên quy hoạch động trên cây với các mảng trạng thái \(dp[x][i][j]\) theo kích thước cây con tại đỉnh \(x\). Khi gộp các cây con, ta dùng phép nhân chập kết hợp kỹ thuật bao hàm loại trừ để loại bỏ các trạng thái trùng lặp hoặc không hợp lệ.

Thứ tự tiếp cận hợp lý nhất là bắt đầu từ NOI Trung Quốc 2026 - Median để rèn luyện kỹ năng đưa bài toán tìm kiếm về bài toán kiểm tra tính khả thi, sau đó đọc NOI Trung Quốc 2026 - Kapok trước khi thử sức với bài toán đếm NOI Trung Quốc 2026 - Rainbow Tree.