SEATST 2026 - Ngày 1

Có \(N\) học sinh trong một lớp. Mỗi học sinh được đánh số từ \(0\) đến \(N-1\) theo thứ hạng hiện tại trong lớp: học sinh \(i\) đang có hạng \(i\). Hạng \(0\) là tốt nhất và hạng \(N-1\) là thấp nhất.

Lớp vừa tổ chức hai kỳ thi Tiếng Anh và Toán. Học sinh \(i\) đạt hạng \(A[i]\) trong kỳ thi Tiếng Anh và hạng \(B[i]\) trong kỳ thi Toán. Cả \(A\) và \(B\) đều là các hoán vị độ dài \(N\).

Trong bài này, một hoán vị \(P\) độ dài \(N\) là một mảng thỏa mãn \(0\le P[i]\le N-1\) với mọi \(0\le i<N\), và \(P[i]\ne P[j]\) với mọi \(0\le i<j<N\). Chẳng hạn, \([2,1,0]\) là một hoán vị độ dài \(3\), còn \([1,2,3]\) và \([2,0,2]\) thì không.

Giáo viên muốn xếp hạng lại các học sinh. Thứ hạng mới được biểu diễn bởi một hoán vị \(P\). Với mỗi học sinh \(i\), thứ hạng mới phải thỏa mãn ít nhất một trong hai điều kiện sau:

• Với mọi \(j\) sao cho \(P[j]<P[i]\), học sinh \(j\) có hạng Tiếng Anh tốt hơn học sinh \(i\), tức là \(A[j]<A[i]\); hoặc
• Với mọi \(j\) sao cho \(P[j]<P[i]\), học sinh \(j\) có hạng Toán tốt hơn học sinh \(i\), tức là \(B[j]<B[i]\).

Lưu ý rằng điều kiện chỉ áp dụng cho các học sinh \(j\) có \(P[j]<P[i]\); không có ràng buộc nào đối với các học sinh có \(P[j]\ge P[i]\). Khi kiểm tra điều kiện cho một học sinh \(i\), phải chọn một môn duy nhất rồi so sánh với tất cả các học sinh \(j\) tương ứng; không được đổi môn giữa các học sinh \(j\) khác nhau.

Mức độ bất mãn của thứ hạng mới là mức tụt hạng lớn nhất trong số tất cả học sinh, tức là

Các giá trị \(i-P[i]\) không ảnh hưởng đến mức độ bất mãn.

Hãy tìm mức độ bất mãn nhỏ nhất có thể của thứ hạng mới.

Yêu cầu cài đặt

Bạn cần cài đặt hàm sau:

int minimum_dissatisfaction(int N, std::vector<int> A,
                            std::vector<int> B);

• \(N\) là số học sinh.
• \(A\) là mảng độ dài \(N\) mô tả thứ hạng trong kỳ thi Tiếng Anh.
• \(B\) là mảng độ dài \(N\) mô tả thứ hạng trong kỳ thi Toán.
• Hàm phải trả về mức độ bất mãn nhỏ nhất có thể.
• Trình chấm gọi hàm này đúng một lần.

Bài nộp không được cài đặt hàm main và phải khai báo #include "exam.h".

Giới hạn

• \(1\le N\le 5\,000\,000\).
• \(0\le A[i],B[i]\le N-1\) với mọi \(0\le i<N\).
• \(A[i]\ne A[j]\) và \(B[i]\ne B[j]\) với mọi \(0\le i<j<N\).

Chấm điểm

Trong phần 8, riêng trình chấm được đảm bảo sử dụng \(1500\) ms trong giới hạn thời gian \(3000\) ms.

Ví dụ

Xét lời gọi:

minimum_dissatisfaction(5, [3, 0, 4, 1, 2], [0, 3, 2, 4, 1])

Một cách xếp hạng mới là \(P=[0,2,3,4,1]\).

• Với học sinh \(1\), \(P[1]=2\). Mọi học sinh \(j\) có \(P[j]<P[1]\) đều có hạng Toán tốt hơn học sinh \(1\).
• Với học sinh \(2\), \(P[2]=3\). Mọi học sinh \(j\) có \(P[j]<P[2]\) đều có hạng Tiếng Anh tốt hơn học sinh \(2\).
• Có thể kiểm tra rằng các học sinh còn lại cũng thỏa mãn điều kiện.

Mức độ bất mãn của thứ hạng này là \(1\), và không tồn tại thứ hạng hợp lệ nào có mức độ bất mãn nhỏ hơn. Vì vậy hàm phải trả về 1.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng:

N
A[0] A[1] ... A[N - 1]
B[0] B[1] ... B[N - 1]

và in một số nguyên là giá trị trả về của minimum_dissatisfaction.

Nguồn: Southeast Asia Team Selection Test 2026, Ngày 1, bài Two Exams.

Có \(N\) học sinh tham dự SEATST. Mỗi học sinh đại diện cho đúng một quốc gia. Sau kỳ thi, tất cả học sinh đều có số điểm khác nhau.

Prabowo chuẩn bị đăng bảng xếp hạng lên trang web chính thức. Với mỗi học sinh, bảng xếp hạng ghi quốc gia, điểm số, thứ hạng toàn cuộc và thứ hạng trong quốc gia.

• Thứ hạng toàn cuộc của một học sinh là số học sinh có điểm cao hơn học sinh đó.
• Thứ hạng trong quốc gia của một học sinh là số học sinh cùng quốc gia có điểm cao hơn học sinh đó.

Ví dụ:

Cả hai loại thứ hạng đều bắt đầu từ \(0\) và không bỏ qua giá trị nào, dù xét toàn cuộc hay trong từng quốc gia.

Khi tải bảng xếp hạng lên mạng, Prabowo quên đăng quốc gia và điểm số. Với mỗi học sinh, ta chỉ biết thứ hạng toàn cuộc và thứ hạng trong quốc gia.

Bạn cần tính hai đại lượng:

1. Số cặp học sinh phân biệt bắt buộc thuộc cùng một quốc gia.
2. Số cặp học sinh phân biệt bắt buộc thuộc hai quốc gia khác nhau.

Nếu có hai cách gán học sinh vào các quốc gia đều phù hợp với dữ liệu, trong đó một cặp học sinh cùng quốc gia ở cách thứ nhất nhưng khác quốc gia ở cách thứ hai, thì cặp đó không được tính vào đại lượng nào.

Yêu cầu cài đặt

Bạn cần cài đặt hai hàm sau:

long long count_same_country(int N, std::vector<int> country_rank);
long long count_diff_country(int N, std::vector<int> country_rank);

• \(N\) là số học sinh.
• country_rank là mảng độ dài \(N\); country_rank[i] là thứ hạng trong quốc gia của học sinh có thứ hạng toàn cuộc \(i\).
• Hàm thứ nhất trả về số cặp không có thứ tự gồm hai học sinh phân biệt mà trong mọi cách gán phù hợp, hai học sinh thuộc cùng một quốc gia.
• Hàm thứ hai trả về số cặp không có thứ tự gồm hai học sinh phân biệt mà trong mọi cách gán phù hợp, hai học sinh thuộc hai quốc gia khác nhau.
• Mỗi hàm được gọi không quá một lần trong một test.

Bài nộp không được cài đặt hàm main và phải khai báo #include "country.h".

Giới hạn

• \(1\le N\le 1\,000\,000\).
• Luôn tồn tại ít nhất một cách gán học sinh vào các quốc gia phù hợp với country_rank.

Chấm điểm

Trong 6 phần đầu, trình chấm chỉ gọi count_same_country.

Trong 6 phần cuối, trình chấm chỉ gọi count_diff_country.

Ví dụ

Xét các lời gọi:

count_same_country(9, [0, 0, 1, 0, 2, 1, 3, 2, 1])
count_diff_country(9, [0, 0, 1, 0, 2, 1, 3, 2, 1])

Giả sử các học sinh có hạng toàn cuộc \(0\), \(1\), \(3\) lần lượt đại diện cho Singapore, Malaysia và Indonesia. Khi đó có bốn cách gán phù hợp:

Có đúng bốn cặp bắt buộc cùng quốc gia:

Do đó lời gọi thứ nhất trả về 4.

Có đúng 17 cặp bắt buộc khác quốc gia:

Do đó lời gọi thứ hai trả về 17.

Với dữ liệu khác:

count_same_country(5, [0, 1, 0, 1, 2]) // trả về 2
count_diff_country(5, [0, 1, 0, 1, 2]) // trả về 4

Hai cặp bắt buộc cùng quốc gia là \((0,1)\) và \((2,3)\). Bốn cặp bắt buộc khác quốc gia là \((0,2)\), \((0,3)\), \((1,2)\) và \((1,3)\).

Trình chấm mẫu

Trình chấm mẫu nhận \(N\), lựa chọn same hoặc diff, rồi mảng country_rank, sau đó gọi hàm tương ứng và in một số nguyên là giá trị trả về.

Nguồn: Southeast Asia Team Selection Test 2026, Ngày 1, bài Country Ranks.

Cho một cây có trọng số gồm \(N\) đỉnh, đánh số từ \(0\) đến \(N-1\). Với mỗi \(1\le i<N\), đỉnh \(i\) nối với cha \(P[i]\) bằng một cạnh có trọng số \(W[i]\), trong đó \(P[i]<i\) và \(W[i]\ge 0\). Đỉnh \(0\) không có cha; để thuận tiện, đặt \(P[0]=W[0]=-1\).

Sasaki chỉ có thể di chuyển giữa các đỉnh bằng cách dịch chuyển tức thời. Với mức năng lượng \(e\), Sasaki có thể dịch chuyển từ đỉnh \(u\) đến đỉnh \(v\) khi và chỉ khi đồng thời thỏa mãn:

• \(u\) là tổ tiên của \(v\), hoặc \(v\) là tổ tiên của \(u\);
• XOR theo bit của trọng số tất cả các cạnh trên đường đi giữa \(u\) và \(v\) không vượt quá \(e\).

Một đỉnh được coi là tổ tiên của chính nó. Phép dịch chuyển không tiêu hao năng lượng: sau mỗi lần dịch chuyển, Sasaki vẫn có mức năng lượng \(e\).

Cụ thể, \(u\) là tổ tiên của \(v\) nếu \(u=v\), hoặc \(u=P[v]\), hoặc \(u=P[P[v]]\), và tương tự sau một số lần đi từ một đỉnh lên cha của nó.

XOR theo bit của hai số nguyên không âm \(a,b\), ký hiệu \(a\oplus b\), có bit thứ \(k\) bằng \(1\) khi đúng một trong hai bit thứ \(k\) của \(a,b\) bằng \(1\), và bằng \(0\) trong trường hợp còn lại. Chẳng hạn:

XOR của nhiều số được thực hiện liên tiếp. Vì phép XOR có tính giao hoán và kết hợp, thứ tự các số và thứ tự thực hiện phép toán không ảnh hưởng đến kết quả cuối cùng.

Miyano cần trả lời \(Q\) truy vấn. Mỗi truy vấn cho hai đỉnh \(U,V\). Hãy tìm mức năng lượng nhỏ nhất để Sasaki có thể đi từ \(U\) đến \(V\) bằng không hoặc nhiều lần dịch chuyển.

Yêu cầu cài đặt

Bạn cần cài đặt hai hàm sau:

void init(int N, std::vector<int> P, std::vector<int> W);
int minimum_energy(int U, int V);

• init nhận số đỉnh, mảng cha và mảng trọng số. Hàm được gọi đúng một lần trước mọi lời gọi minimum_energy.
• minimum_energy nhận hai đỉnh của một truy vấn và phải trả về đáp án của truy vấn đó. Hàm được gọi đúng \(Q\) lần.

Bài nộp không được cài đặt hàm main và phải khai báo #include "teleport.h".

Giới hạn

• \(2\le N\le 50\,000\).
• \(1\le Q\le 100\,000\).
• \(P[0]=-1\) và \(0\le P[i]<i\) với mọi \(1\le i<N\).
• \(W[0]=-1\) và \(0\le W[i]<2^{20}\) với mọi \(1\le i<N\).
• \(0\le U,V<N\) trong mỗi truy vấn.

Chấm điểm

Ví dụ

Xét lời gọi khởi tạo:

init(6, [-1, 0, 1, 0, 1, 2], [-1, 3, 2, 0, 2, 1])

Sau đó:

• minimum_energy(2, 4) trả về 1. Có thể dịch chuyển \(2\to0\) rồi \(0\to4\); XOR trên mỗi đường đi đều bằng \(1\).
• minimum_energy(3, 0) trả về 0, vì XOR trên đường \(3\to0\) bằng \(0\).
• minimum_energy(1, 1) trả về 0, vì điểm đầu và điểm cuối trùng nhau.
• minimum_energy(0, 5) trả về 0, vì XOR trên đường \(0\to5\) là \(3\oplus2\oplus1=0\).

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng:

N
P[1] P[2] ... P[N - 1]
W[1] W[2] ... W[N - 1]
Q
U[0] V[0]
U[1] V[1]
...
U[Q - 1] V[Q - 1]

Với mỗi truy vấn, trình chấm in giá trị do minimum_energy trả về trên một dòng.

Nguồn: Southeast Asia Team Selection Test 2026, Ngày 1, bài XOR Teleport.