KOI 2026 - Vòng 2 - THPT

Có \(N\) học sinh và \(N\) loại đồ ăn nhẹ, đều được đánh số từ \(1\) đến \(N\). Học sinh \(i\) thích \(C_i\) loại có chỉ số \(A_{i,1},\ldots,A_{i,C_i}\). Ban đầu mỗi loại đồ ăn có đúng một chiếc.

Đưa các học sinh vào phòng theo một thứ tự. Khi vào, một học sinh lấy tất cả đồ ăn mà mình thích và còn lại trong phòng. Hãy quyết định liệu có thể chọn thứ tự sao cho mọi học sinh lấy đúng một đồ ăn hay không. Nếu có, hãy in một thứ tự như vậy.

Dữ liệu vào

• Dòng đầu chứa \(N\).
• \(N\) dòng tiếp theo: dòng \(i\) chứa \(C_i\) rồi đến \(C_i\) số \(A_{i,j}\).

Dữ liệu ra

In -1 nếu không thể. Ngược lại in một hoán vị \(P_1,\ldots,P_N\) sao cho khi học sinh vào theo thứ tự đó, mỗi người lấy đúng một đồ ăn.

Ràng buộc

• \(1 \le N \le 200000\), \(1 \le C_i \le N\).
• \(1 \le A_{i,j} \le N\).
• \(\sum C_i \le 500000\); các đồ ăn mà cùng một học sinh thích là khác nhau.

Phân nhóm

• Nhóm 1 (6 điểm): \(C_i = 1\) với mọi \(i\).
• Nhóm 2 (11 điểm): nếu tồn tại thứ tự hợp lệ thì thứ tự \(1,2,\ldots,N\) cũng hợp lệ.
• Nhóm 3 (8 điểm): \(N \le 5\).
• Nhóm 4 (12 điểm): \(N \le 18\).
• Nhóm 5 (18 điểm): \(N \le 300\).
• Nhóm 6 (20 điểm): \(N \le 5000\).
• Nhóm 7 (25 điểm): Không có ràng buộc bổ sung.

Ví dụ

3
2 1 2
2 2 3
1 2

3 1 2

Theo thứ tự này, học sinh \(3\) lấy đồ ăn \(2\), học sinh \(1\) lấy đồ ăn \(1\), rồi học sinh \(2\) lấy đồ ăn \(3\); vì vậy mỗi người lấy đúng một món.

2
2 1 2
2 1 2

-1

4
1 3
1 2
3 4 2 3
2 1 2

1 2 3 4

Nguồn

KOI 2026 Round 2, problem Snack Distribution. Tài liệu, dữ liệu chấm và mã nguồn mẫu từ Korean Olympiad in Informatics, phát hành theo CC BY-NC-SA 4.0.

Một nhà máy hoạt động trong \(2T+1\) ca theo thứ tự: đêm ngày \(0\), ban ngày ngày \(1\), đêm ngày \(1\), ban ngày ngày \(2\), đêm ngày \(2\), ..., ban ngày ngày \(T\), đêm ngày \(T\). Ứng viên \(i\) có kỹ năng \(A_i\), mức đóng góp \(B_i\), lương cơ bản \(C_i\) và ngày làm việc \(D_i\). Nếu được thuê, người đó làm đúng ba ca: đêm ngày \(D_i-1\), ban ngày ngày \(D_i\) và đêm ngày \(D_i\).

Trong mỗi ca, xếp tất cả người làm ca đó theo kỹ năng tăng dần rồi ghép người thứ \(1\) với thứ \(2\), thứ \(3\) với thứ \(4\), v.v. Mọi ca phải có số người chẵn; một ca không có ai làm vẫn hợp lệ. Với một cặp gồm người \(x\) có kỹ năng cao hơn người \(y\):

• Trong ca ban ngày, lợi nhuận sản xuất tăng \(B_x-B_y\); giá trị này có thể âm.
• Trong ca ban đêm, nhà máy trả tổng phụ cấp \(A_x-A_y\) cho cặp đó.

Tổng tiền lương bằng tổng lương cơ bản \(C_i\) của những người được thuê cộng toàn bộ phụ cấp ban đêm. Hãy chọn tập ứng viên hợp lệ để tối đa hóa tổng lợi nhuận sản xuất trừ tổng tiền lương, đồng thời in một tập đạt tối ưu.

Dữ liệu vào

• Dòng đầu: \(N\), \(T\).
• \(N\) dòng tiếp theo: \(A_i,B_i,C_i,D_i\).

Dữ liệu ra

In giá trị tối đa trên dòng thứ nhất và số công nhân được thuê \(K\) trên dòng thứ hai. Nếu \(K>0\), dòng thứ ba chứa \(K\) chỉ số đôi một khác nhau theo thứ tự bất kỳ; nếu \(K=0\), dòng này có thể rỗng hoặc được bỏ qua. Nếu có nhiều tập tối ưu, in bất kỳ tập nào.

Ràng buộc

• \(1\le T\le N\le500\).
• \(0\le A_i,B_i,C_i\le1000\), \(1\le D_i\le T\).
• Các \(A_i\) đôi một khác nhau.

Phân nhóm

• Nhóm 1 (13 điểm): \(N\le20\).
• Nhóm 2 (14 điểm): \(T=1\).
• Nhóm 3 (20 điểm): \(T\le10\).
• Nhóm 4 (22 điểm): với mọi \(1\le d\le T\), có không quá \(8\) ứng viên thỏa \(D_i=d\).
• Nhóm 5 (31 điểm): Không có ràng buộc bổ sung.

Ví dụ

6 2
21 0 1 1
13 25 0 2
22 20 3 2
20 5 2 2
4 23 0 2
25 16 8 1

7
4
1 3 4 6

Với tập này, lợi nhuận ban ngày là \(16+15=31\). Tổng phụ cấp ba ca đêm là \(4+4+2=10\), tổng lương cơ bản là \(14\), nên giá trị mục tiêu bằng \(31-(10+14)=7\). Cặp công nhân trong ca ngày và ca đêm có thể khác nhau vì mỗi ca đều ghép lại theo thứ tự kỹ năng.

5 2
40 23 10 1
59 22 2 2
32 7 10 2
52 30 0 1
38 10 3 1

0
0

12 3
6 19 4 2
32 0 1 3
12 0 4 3
25 7 0 2
35 15 5 1
28 25 5 2
19 27 3 3
30 13 3 2
1 24 5 3
20 11 0 2
2 1 5 2
24 28 3 2

20
8
1 3 4 6 7 10 11 12

Nguồn

KOI 2026 Round 2, problem Factory. Tài liệu, dữ liệu chấm và mã nguồn mẫu từ Korean Olympiad in Informatics, phát hành theo CC BY-NC-SA 4.0.

Cho hoán vị \(A=[A_1,\ldots,A_N]\). Một lần biến đổi của dãy \(B=[B_1,\ldots,B_K]\) là xóa đồng thời mọi phần tử \(B_i\) với \(2\le i<K\) và \(B_{i-1}>B_i<B_{i+1}\), rồi ghép các phần tử còn lại theo thứ tự cũ.

Với mỗi truy vấn \((l,r,t)\), hãy tìm số phần tử còn lại của dãy \([A_l,\ldots,A_r]\) sau \(t\) lần biến đổi.

Dữ liệu vào

• Dòng đầu chứa \(N,Q\).
• Dòng thứ hai chứa hoán vị \(A\).
• \(Q\) dòng tiếp theo chứa \(l,r,t\).

Dữ liệu ra

In \(Q\) dòng theo thứ tự dữ liệu vào; dòng thứ \(j\) là câu trả lời cho truy vấn thứ \(j\).

Ràng buộc

• \(1\le N,Q\le200000\).
• \(A\) là hoán vị của \(1,\ldots,N\).
• \(1\le l\le r\le N\), \(1\le t\le N\).

Phân nhóm

• Nhóm 1 (6 điểm): \(N\le5000\) và mọi truy vấn có \(l=1,r=N\).
• Nhóm 2 (11 điểm): mọi truy vấn có \(l=1,r=N\).
• Nhóm 3 (6 điểm): \(t=1\) với mọi truy vấn.
• Nhóm 4 (12 điểm): \(t=N\) với mọi truy vấn.
• Nhóm 5 (7 điểm): tồn tại \(p\) (\(1\le p\le N\)) sao cho \(A_i>A_{i+1}\) với mọi \(1\le i<p\) và \(A_i<A_{i+1}\) với mọi \(p\le i<N\).
• Nhóm 6 (26 điểm): sau 20 lần biến đổi toàn bộ \(A\), dãy không còn thay đổi.
• Nhóm 7 (32 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 5
5 1 3 2 4
1 5 1
1 5 2
1 4 1
2 5 1
1 5 5

3
2
3
3
2

15 7
14 5 2 7 11 13 3 12 9 4 10 8 1 6 15
1 15 1
1 15 2
1 15 3
1 15 4
1 15 5
1 15 6
1 15 7

11
8
6
4
3
2
2

10 10
9 6 4 1 8 2 3 5 7 10
1 10 1
1 10 2
1 10 5
1 9 3
2 10 2
2 10 4
3 8 1
3 8 2
1 5 4
4 8 3

8
6
2
3
5
3
4
3
2
3

Nguồn

KOI 2026 Round 2, problem Local Minimum Removal. Tài liệu, dữ liệu chấm và mã nguồn mẫu từ Korean Olympiad in Informatics, phát hành theo CC BY-NC-SA 4.0.

Trên một dãy \(N\) ô, hai nghệ sĩ Alice và Bob luôn đứng ở hai ô khác nhau, với Alice ở bên trái Bob. Có \(M\) bệ nhảy; bệ \(i\) đưa người từ ô \(x_i\) đến ô \(y_i\).

Mỗi hành động chỉ di chuyển một người: Alice có thể đi sang phải một ô, Bob có thể đi sang trái một ô, hoặc một người dùng bệ nhảy tại ô của mình. Sau mỗi hành động, Alice vẫn phải ở bên trái Bob.

Một ô có thể có nhiều bệ nhảy. Cả Alice và Bob đều có thể dùng bất kỳ bệ nào không giới hạn số lần; bệ \(i\) chỉ dùng được khi người đó đang ở ô \(x_i\) và đưa người đó đến đúng ô \(y_i\). Một kế hoạch có thể dùng \(0\) hoặc nhiều hành động.

Với mỗi kế hoạch \((a,b,c,d)\), hãy xác định có thể bắt đầu với Alice ở \(a\), Bob ở \(b\) và kết thúc ở \(c,d\) hay không.

Dữ liệu vào

• Dòng đầu chứa \(N,M\).
• \(M\) dòng tiếp theo chứa \(x_i,y_i\).
• Dòng tiếp theo chứa \(Q\).
• \(Q\) dòng tiếp theo chứa \(a,b,c,d\).

Dữ liệu ra

In \(Q\) dòng; dòng thứ \(j\) là YES nếu kế hoạch thứ \(j\) khả thi, ngược lại là NO.

Ràng buộc

• \(2\le N\le200000\), \(0\le M\le200000\), \(1\le Q\le500000\).
• \(1\le x_i,y_i\le N\), \(x_i\ne y_i\).
• \(1\le a<b\le N\), \(1\le c<d\le N\).

Phân nhóm

• Nhóm 1 (8 điểm): \(N,M,Q\le100\).
• Nhóm 2 (14 điểm): \(x_i<y_i\) với mọi bệ nhảy.
• Nhóm 3 (13 điểm): \(N\le3000\).
• Nhóm 4 (13 điểm): \(Q\le10\).
• Nhóm 5 (52 điểm): Không có ràng buộc bổ sung.

Ví dụ

6 2
3 5
4 2
4
2 4 3 4
2 3 2 5
2 3 4 5
3 4 1 2

YES
YES
YES
NO

10 3
5 10
6 8
7 4
5
5 6 4 10
5 6 3 9
1 10 2 9
6 8 4 9
9 10 1 10

YES
NO
YES
YES
NO

Nguồn

KOI 2026 Round 2, problem Acrobatics. Tài liệu, dữ liệu chấm và mã nguồn mẫu từ Korean Olympiad in Informatics, phát hành theo CC BY-NC-SA 4.0.