EJOI 2026 - Ngày 1

Boris và Ihor nhận một dãy \(a_0,a_1,\ldots,a_{N-1}\) gồm các số nguyên dương. Bạn biết toàn bộ dãy, sau đó xét các phần tử từ trái sang phải và phải giao mỗi phần tử cho đúng một trong hai người.

Theo thứ tự nhận, dãy của mỗi người phải tăng nghiêm ngặt. Phần tử đầu tiên của một người có thể có giá trị bất kỳ và một người có thể không nhận phần tử nào.

Với mỗi \(K\) từ \(0\) đến \(N\), hãy xác định độc lập xem có thể chia dãy sao cho Boris nhận đúng \(K\) phần tử hay không.

Giao diện thư viện

Submission C++ phải include increasing.h và cài đặt:

std::vector<bool> increasing_split(std::vector<int> a);

Hàm được gọi đúng một lần. Nó phải trả về vector có đúng \(N+1\) phần tử; phần tử thứ \(K\) là true khi cách chia tương ứng tồn tại.

Dữ liệu vào

Submission không đọc standard input. Sample grader đọc \(N\) rồi dãy \(a\).

Dữ liệu ra

Submission không ghi standard output. Kết quả được trả qua increasing_split.

Ràng buộc

• \(2\le N\le4\cdot10^5\).
• \(1\le a_i\le10^9\).

Phân nhóm

1. \(10\) điểm: \(N\le18\).
2. \(5\) điểm: \(a_i\le a_{i+1}\) với mọi \(0\le i<N-1\).
3. \(5\) điểm: \(a_0\ge\max(a_1,\ldots,a_{N-1})\).
4. \(16\) điểm: \(a\) là hoán vị của \(1,\ldots,N\); với mọi \(i\) thỏa \(a_i<a_{i+1}\), tiền tố \(a_0,\ldots,a_i\) là hoán vị của \(1,\ldots,i+1\).
5. \(21\) điểm: \(N\le5000\); \(a\) là hoán vị của \(1,\ldots,N\); với mọi \(i\) thỏa \(\max(a_0,\ldots,a_i)<a_{i+1}\), tiền tố \(a_0,\ldots,a_i\) là hoán vị của \(1,\ldots,i+1\).
6. \(17\) điểm: \(N\le4\cdot10^5\); \(a\) là hoán vị của \(1,\ldots,N\); với mọi \(i\) thỏa \(\max(a_0,\ldots,a_i)<a_{i+1}\), tiền tố \(a_0,\ldots,a_i\) là hoán vị của \(1,\ldots,i+1\).
7. \(16\) điểm: \(N\le5000\).
8. \(10\) điểm: không có ràng buộc thêm.

Ví dụ

5
3 1 4 5 5

001100

4
1 2 3 4

11111

Nguồn

EJOI 2026 - Ngày 1, Increasing Split.

Đề bài EJOI 2026 được phát hành theo giấy phép Creative Commons Attribution (CC BY).

Có \(N\) địa điểm và một cây giao thông bí mật gồm \(N-1\) cạnh. Với mỗi đỉnh bắt đầu \(i\), ban giám khảo cố định một thứ tự duyệt DFS của toàn bộ cây, bắt đầu tại \(i\). Thứ tự xét các đỉnh kề có thể khác giữa các lần DFS.

Hình 1: Một lượt DFS bắt đầu ở đỉnh \(4\); các mũi tên được đánh số theo thứ tự di chuyển.

Bạn được hỏi phần tử thứ \(j\) trong thứ tự DFS bắt đầu tại \(i\). Hãy khôi phục chính xác cây bí mật. Cây và mọi thứ tự DFS được cố định trước khi chương trình chạy.

Giao diện thư viện

Submission C++ phải include reconstruct.h và cài đặt:

std::vector<std::pair<int, int>> find_tree(int N);

Grader cung cấp:

int guess(int i, int j);

guess(i,j) trả về địa điểm thứ \(j\) trong thứ tự DFS bắt đầu tại \(i\); đặc biệt guess(i,0)=i. Mọi chỉ số phải thuộc \([0,N-1]\). find_tree phải trả đúng \(N-1\) cạnh, với hai đầu mút được đánh số từ \(0\) đến \(N-1\); thứ tự cạnh và thứ tự hai đầu mút không quan trọng. Hàm có thể được gọi \(T\) lần trong một test.

Đây là bài giao tiếp. Submission chạy trong một tiến trình riêng và chỉ được trao đổi với manager qua các hàm trên.

Dữ liệu vào

Submission không đọc standard input. Manager đọc các cây và thứ tự DFS ẩn từ bộ test.

Dữ liệu ra

Submission không ghi standard output. Kết quả được trả từ find_tree.

Ràng buộc

• \(2\le N\le2^{16}+1\).
• Nếu \(N_{\max}\le9\) thì \(1\le T\le100\).
• Nếu \(N_{\max}\le2^{10}+1\) thì \(1\le T\le10\).
• Nếu \(N_{\max}\le2^{16}+1\) thì \(1\le T\le3\).
• guess chạy trong \(O(1)\) ở các phân nhóm 1--6 và \(O(\log N)\) ở phân nhóm 7.
• System grader có thể dùng tối đa \(280\) MiB, được tính trong giới hạn bộ nhớ.

Phân nhóm

1. \(11\) điểm: \(N\le9\).
2. \(6\) điểm: \(N\le100\) và bậc mỗi đỉnh không quá \(2\).
3. \(13\) điểm: \(N\le100\); mỗi DFS luôn ưu tiên đi xa đỉnh \(0\), và nếu có nhiều lựa chọn thì chọn tùy ý.
4. \(11\) điểm: \(N\le100\) và mọi đỉnh khác \(0\) có bậc không quá \(2\).
5. \(10\) điểm: \(N\le100\).
6. \(31\) điểm: \(N\le2^{10}+1\).
7. \(18\) điểm: \(N\le2^{16}+1\).

Ở phân nhóm 6 và 7, gọi \(Q_{\max}\) là số truy vấn lớn nhất trong một lần gọi. Điểm theo tỉ lệ \(S\): \(S=1\) nếu \(Q_{\max}\le L_1\); \(S=0.4+0.6(L_2-Q_{\max})/(L_2-L_1)\) nếu \(L_1<Q_{\max}\le L_2\); \(S=0.2+0.2(3L_2-Q_{\max})/(2L_2)\) nếu \(L_2<Q_{\max}\le3L_2\); và \(S=0.2\) nếu \(Q_{\max}>3L_2\). Phân nhóm 6 dùng \((L_1,L_2)=(3075,9225)\); phân nhóm 7 dùng \((196611,983055)\). Điểm của phân nhóm là tỉ lệ nhỏ nhất trên mọi test.

Hình 2: Điểm của phân nhóm 6 theo số truy vấn lớn nhất.

Hình 3: Điểm của phân nhóm 7 theo số truy vấn lớn nhất.

Ví dụ

Hình 4: Cây giao thông bí mật của ví dụ.

Với một cây có \(6\) đỉnh và thứ tự DFS từ đỉnh \(0\) là [0, 1, 2, 4, 3, 5], các lời gọi guess(0,j) lần lượt trả các phần tử trên. Một kết quả hợp lệ có thể gồm các cạnh (0,1), (0,2), (4,0), (5,4), (3,4).

Nguồn

EJOI 2026 - Ngày 1, Reconstruct.

Đề bài EJOI 2026 được phát hành theo giấy phép Creative Commons Attribution (CC BY).

Một hoán vị ẩn \(p_0,p_1,\ldots,p_{N-1}\) của \(0,\ldots,N-1\) được cố định trước khi chương trình chạy. Bạn có thể hỏi \(p_i\mathbin{\mathrm{XOR}}p_j\) cho hai chỉ số tùy ý.

Hai hoán vị \(a,p\) được gọi là không thể phân biệt nếu \(a_i\mathbin{\mathrm{XOR}}a_j=p_i\mathbin{\mathrm{XOR}}p_j\) với mọi cặp chỉ số. Hãy tìm hoán vị nhỏ nhất theo thứ tự từ điển trong lớp không thể phân biệt với \(p\). Hoán vị \(x\) nhỏ hơn hoán vị \(y\) theo thứ tự từ điển nếu tại vị trí đầu tiên mà chúng khác nhau, phần tử của \(x\) nhỏ hơn phần tử của \(y\).

Giao diện thư viện

Submission C++ phải include xorting.h và cài đặt:

std::vector<int> solve(int N);

Grader cung cấp:

int get_xor(int i, int j);

solve được gọi đúng \(T\) lần. Mỗi lần phải trả hoán vị nhỏ nhất theo thứ tự từ điển. get_xor(i,j) trả \(p_i\mathbin{\mathrm{XOR}}p_j\) trong \(O(1)\); cả hai chỉ số phải thuộc \([0,N-1]\). Giới hạn truy vấn \(Q_i\) của mỗi lần gọi không được truyền cho submission.

Dữ liệu vào

Submission không đọc standard input. Sample grader đọc \(T\), loại giới hạn truy vấn, rồi từng hoán vị ẩn.

Dữ liệu ra

Submission không ghi standard output. Kết quả được trả từ solve.

Ràng buộc

• \(1\le N_i\le2^{20}\).
• \(1\le T\le2^{10}\).
• \(T\cdot\max_i N_i\le2^{25}\).
• Mỗi lần gọi được dùng \(Q_i=N_i\) hoặc \(Q_i=N_i^2\) tùy phân nhóm.

Phân nhóm

1. \(7\) điểm: \(N_i\le2^3\), \(T\le2^{10}\), \(Q_i=N_i^2\).
2. \(18\) điểm: \(N_i\le2^7\), \(T\le2^5\), \(Q_i=N_i^2\).
3. \(5\) điểm: \(N_i\le2^{11}\), \(T\le2^5\), \(Q_i=N_i^2\).
4. \(5\) điểm: \(N_i\le2^{11}\), \(T\le2^5\), \(Q_i=N_i\).
5. \(5\) điểm: \(N_i\le2^{18}\), \(T\le2^5\), \(Q_i=N_i\) và \(N_i\) là lũy thừa của \(2\).
6. \(5\) điểm: \(N_i\le2^{18}\), \(T\le2^5\), \(Q_i=N_i\) và \(N_i\) lẻ.
7. \(30\) điểm: \(N_i\le2^{18}\), \(T\le2^5\), \(Q_i=N_i\).
8. \(25\) điểm: \(N_i\le2^{20}\), \(T\le2^5\), \(Q_i=N_i\).

Ví dụ

Nếu hoán vị ẩn là [2,0,1,3], sáu truy vấn giữa các cặp chỉ số cho phép trả về [0,2,3,1], là hoán vị nhỏ nhất không thể phân biệt. Với \(N=1\), kết quả duy nhất là [0].

Nguồn

EJOI 2026 - Ngày 1, XORting.

Đề bài EJOI 2026 được phát hành theo giấy phép Creative Commons Attribution (CC BY).