Kỳ thi: Orange Contest #02
Tóm tắt: Kỳ thi gồm 5 bài toán với cấu trúc điểm trải rộng từ các bài toán tính toán cơ bản đến xử lý trường hợp, mô phỏng tham lam và quy hoạch động trên tập ước số.

Orange Contest #02 - Phát Triển Dự Án AI yêu cầu tìm số giờ tối thiểu để viết xong \(n\) dòng mã khi người thứ hai có thể chọn tự viết ngay hoặc mất \(z\) giờ chuẩn bị AI rồi tăng tốc gấp 10 lần. Người đọc chỉ cần tính riêng số giờ trọn vẹn theo từng lựa chọn dựa trên phép chia làm tròn lên và lấy giá trị nhỏ hơn.

Orange Contest #02 - Hàng Hóa Trên Kệ kiểm tra khả năng gom các loại hàng hóa giống nhau về cùng các đoạn liền kề sau tối đa một lần hoán đổi hai vị trí trên kệ. Ta quan sát rằng một lần đổi vị trí chỉ tách hoặc gộp tối đa một số ít đoạn, nên sau khi nén giá trị và đếm số khối, chỉ cần kiểm tra các vị trí đầu mút của những phần tử xuất hiện ở nhiều hơn một khối.

Orange Contest #02 - Lối Thoát Không Gian đặt bài toán tìm đường đi ngắn nhất giữa hai trạm \(a\) và \(b\) trong đồ thị đầy đủ với trọng số cạnh là \(\frac{\max(u, v)}{\gcd(u, v)}\). Vì giới hạn đỉnh lên tới \(10^9\) nhưng chi phí phụ thuộc trực tiếp vào quan hệ chia hết, ta có thể rút gọn với \(\gcd(a, b)\) rồi áp dụng quy hoạch động ghi nhớ trên tập các ước số của \(a\) và \(b\).

Orange Contest #02 - Sắp Xếp Chỗ Ngồi yêu cầu tối đa hóa số người được xếp vào các bàn tiệc theo thứ tự đến, trong đó khách hướng nội chỉ ngồi bàn trống, khách hướng ngoại chỉ ngồi bàn đã có người, còn khách hướng trung có thể chọn một trong hai. Do tính chất linh hoạt của khách hướng trung, ta có thể duyệt qua số lượng khách hướng trung đóng vai trò mở bàn mới rồi mô phỏng lại cách xếp theo từng bước.

Orange Contest #02 - Làm Phẳng Kem yêu cầu tìm chiều cao tối đa để san phẳng lớp kem cho từng tiền tố độ dài \(i\) khi phần kem thừa luôn bị gạt sang vị trí bên phải. Thay vì thử từng độ cao cắt dao, ta nhận xét lượng kem dồn lại trên mỗi tiền tố bị chặn trên bởi trung bình cộng tích lũy và chỉ cần duy trì giá trị nhỏ nhất của các mức trung bình này theo từng bước duyệt mảng.

Bạn nên bắt đầu luyện tập với Phát Triển Dự Án AI và Làm Phẳng Kem để làm quen với thao tác tính toán mảng trước khi thử sức với Sắp Xếp Chỗ Ngồi, Hàng Hóa Trên Kệ và Lối Thoát Không Gian.