KOI TST 2026 - Vòng 1

Đề bài

Một dãy được gọi là cân bằng nếu thỏa mãn định nghĩa đệ quy sau:

• Mọi dãy có độ dài \(1\) đều cân bằng.
• Dãy có độ dài \(2k+1\), \(S=[S_0,\ldots,S_{2k}]\), là cân bằng nếu:
• \([S_0,\ldots,S_{k-1}]\) cân bằng;
• \([S_{k+1},\ldots,S_{2k}]\) cân bằng;
• \(S_k\) là giá trị lớn nhất duy nhất trong toàn bộ \(S\).

Cho dãy \(A\) gồm \(N\) số nguyên. Ký hiệu \(A[i\ldots j]\) là dãy con liên tiếp từ phần tử \(i\) đến phần tử \(j\).

Có \(Q\) thao tác, mỗi thao tác thay đổi một phần tử của \(A\) và các thay đổi được giữ lại. Ở trạng thái ban đầu và sau mỗi thao tác, hãy tính số cặp \((i,j)\) thỏa mãn

và \(A[i\ldots j]\) là một dãy cân bằng.

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

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

long long initialize(int N, vector<int> A);
long long update_sequence(int p, int v);

• initialize được gọi đúng một lần. Hàm phải trả về số dãy con cân bằng của dãy ban đầu.
• Mỗi lời gọi update_sequence(p, v) gán \(A[p]=v\) và phải trả về số dãy con cân bằng sau thay đổi. Hàm này được gọi tổng cộng \(Q\) lần sau initialize.
• Chương trình nộp không được thực hiện thao tác vào/ra.

Ràng buộc

• \(1\le N\le 10^5\).
• \(0\le Q\le 10^5\).
• \(1\le A[i]\le 10^9\).
• Với mỗi lần cập nhật: \(0\le p\le N-1\) và \(1\le v\le 10^9\).

Phân nhóm

Grader mẫu

Grader mẫu đọc \(N,Q\), dãy \(A\), rồi \(Q\) dòng p v. Grader in kết quả của initialize, sau đó in kết quả của từng lần cập nhật, mỗi kết quả trên một dòng.

4 0
1 1 1 1

4

12 0
8 9 7 9 2 3 2 8 4 6 2 6

18

7 2
1 3 4 4 2 1 6
3 1
3 2

7
9
8

Nguồn: Kỳ thi tuyển chọn đội tuyển IOI Hàn Quốc 2026 - Vòng 1, giấy phép CC BY-NC-SA 4.0.

Đề bài

Một mạng truyền thông gồm \(N\) máy tính, đánh số từ \(0\) đến \(N-1\), và các đường truyền hai chiều. Ban đầu mạng không có đường truyền nào.

Với mỗi \(u=0,1,\ldots,T-1\), một tập \(E_u\) gồm các đường truyền phân biệt được cho trước. Tại thời điểm \(u+0.5\), trạng thái của từng đường truyền trong \(E_u\) bị đảo: đường chưa có sẽ được thêm, còn đường đang có sẽ bị xóa.

Hai máy \(a,b\) được gọi là kết nối tại giây \(t\) nếu có một đường đi giữa chúng chỉ dùng các đường truyền tồn tại tại giây \(t\). Một máy luôn kết nối với chính nó. Hai máy được gọi là kết nối trong toàn bộ khoảng \([l,r]\) nếu chúng kết nối tại mọi thời điểm nguyên \(t=l,l+1,\ldots,r\).

Có \(Q\) truy vấn. Mỗi truy vấn cho máy \(x\) và khoảng thời gian \([l,r]\); hãy trả về số máy \(y\) kết nối với \(x\) trong toàn bộ khoảng đó.

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

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

vector<int> count_computers(
    int N,
    int T,
    int Q,
    vector<vector<array<int, 2>>> E,
    vector<array<int, 3>> F
);

• E có độ dài \(T\). Mỗi E[i] là tập các đường truyền bị đảo tại thời điểm \(i+0.5\); mỗi đường truyền được biểu diễn bởi [a, b].
• F có độ dài \(Q\). F[j] = [x, l, r] mô tả truy vấn thứ \(j\).
• Hàm phải trả về mảng \(R\) có độ dài \(Q\), trong đó \(R[j]\) là đáp án truy vấn thứ \(j\).
• Hàm được gọi đúng một lần và chương trình nộp không được thực hiện thao tác vào/ra.

Ràng buộc

• \(2\le N\le 100\,000\).
• \(1\le T\le 100\,000\).
• \(1\le Q\le 250\,000\).
• Mỗi \(E_i\) chứa các đường truyền phân biệt.
• Gọi \(S=\sum_{i=0}^{T-1}|E_i|\), ta có \(S\le 100\,000\).
• Mọi đường truyền thỏa mãn \(0\le a<b\le N-1\).
• Mọi truy vấn thỏa mãn \(0\le x\le N-1\) và \(0\le l\le r\le T\).

Phân nhóm

Grader mẫu

Grader mẫu đọc \(N,T,Q\). Với mỗi \(i\), grader đọc \(|E_i|\) rồi các cặp đầu mút của \(E_i\). Cuối cùng, grader đọc \(Q\) bộ x l r và in từng đáp án trên một dòng.

4 5 7
2
0 1
1 2
2
2 3
1 3
2
0 1
0 3
4
0 1
1 2
0 3
2 3
1
1 3
1 1 1
2 2 2
3 3 3
0 0 5
2 1 3
1 1 4
3 2 3

3
4
4
1
3
2
4

4 5 7
2
0 1
1 2
1
2 3
1
0 1
3
0 1
1 2
2 3
1
1 2
1 1 1
2 2 2
3 3 3
0 0 5
2 1 3
1 1 4
3 2 3

3
4
3
1
2
1
3

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

3
1
3
3
1

10 27 10
1
3 8
1
8 9
1
3 6
1
1 6
1
0 8
1
1 4
1
3 7
1
0 5
1
1 2
1
0 5
1
1 9
1
3 9
1
5 8
1
1 4
1
1 2
1
1 7
1
3 7
1
3 6
1
0 8
1
2 4
1
6 9
1
0 8
1
8 9
1
3 8
1
1 6
1
0 9
1
3 4
5 0 17
8 23 26
5 7 24
4 5 6
0 3 12
8 15 18
2 4 12
6 0 2
5 9 15
1 6 17

1
3
1
1
1
8
1
1
1
6

Nguồn: Kỳ thi tuyển chọn đội tuyển IOI Hàn Quốc 2026 - Vòng 1, giấy phép CC BY-NC-SA 4.0.

Đề bài

Cho một cây có gốc gồm \(N\) đỉnh, đánh số từ \(0\) đến \(N-1\), với gốc là đỉnh \(0\). Mỗi đỉnh có đúng \(0\) hoặc \(2\) con; nếu có hai con thì thứ tự con trái và con phải được xác định. Mỗi cạnh \(e\) có độ dài nguyên dương \(c_e\).

Ta cần vẽ cây trên mặt phẳng tọa độ. Mỗi đỉnh \(v\) được đặt tại một điểm lưới nguyên phân biệt \(m_v=(x_v,y_v)\), trong đó \(m_0=(0,0)\).

Cạnh \(e=(p,v)\) được vẽ thành một đường đi từ \(m_p\) đến \(m_v\) thỏa mãn:

• Khi đi từ \(m_p\) đến \(m_v\), mỗi đoạn luôn đi theo hướng tăng \(x\) hoặc tăng \(y\), không đi chéo. Chỉ được đổi hướng tại điểm lưới nguyên; một đường đi dài \(k\) chỉ có thể đổi hướng tại \(k-1\) điểm trung gian.
• Nếu \(v\) là con trái của \(p\), đoạn đầu tiên đi theo hướng tăng \(x\).
• Nếu \(v\) là con phải của \(p\), đoạn đầu tiên đi theo hướng tăng \(y\).
• Độ dài đường đi không nhỏ hơn \(c_e\).
• Các đường đi không được cắt nhau: không điểm trong nào của một đường đi được thuộc một đường đi khác. Điểm đầu và cuối không được tính là điểm trong.

Độ sâu của đỉnh \(v\) trong hình vẽ được định nghĩa là

Tất cả các lá phải có cùng độ sâu; giá trị chung này gọi là độ sâu lưới. Hãy tìm độ sâu lưới nhỏ nhất trong mọi hình vẽ hợp lệ.

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

long long compute_min_depth(
    int N,
    vector<int> P,
    vector<int> C,
    vector<int> D
);

Với mỗi \(1\le i\le N-1\):

• cha của đỉnh \(i\) là P[i-1];
• cạnh nối chúng có độ dài C[i-1];
• D[i-1]=0 nếu \(i\) là con trái, và D[i-1]=1 nếu \(i\) là con phải.

Luôn tồn tại ít nhất một hình vẽ hợp lệ. Hàm phải trả về độ sâu lưới nhỏ nhất, được gọi đúng một lần, và chương trình nộp không được thực hiện thao tác vào/ra.

Ràng buộc

• Các cạnh tạo thành một cây gốc tại đỉnh \(0\).
• Mỗi đỉnh có \(0\) hoặc \(2\) con.
• \(3\le N\le 200\,000\).
• \(0\le P[i]\le N-1\).
• \(1\le C[i]\le 10^9\).
• \(D[i]\in\{0,1\}\).

Khoảng cách giữa hai đỉnh của cây là tổng độ dài các cạnh trên đường đi duy nhất nối chúng.

Phân nhóm

Trong nhóm 3, nếu không tồn tại hình vẽ có độ sâu lưới đúng bằng \(K\), hàm được phép trả về \(-1\) thay cho độ sâu lưới nhỏ nhất. Cụ thể:

• Nếu tồn tại hình vẽ có độ sâu \(K\), chỉ giá trị \(K\) được chấp nhận.
• Nếu không tồn tại hình vẽ có độ sâu \(K\), cả giá trị nhỏ nhất thực sự và \(-1\) đều được chấp nhận.

Grader mẫu

Grader mẫu đọc \(N\), sau đó đọc \(N-1\) dòng P[i] C[i] D[i], và in giá trị trả về.

5
4 1 0
0 2 1
4 1 1
0 1 0

2

9
0 2 0
0 1 1
1 1 0
1 1 1
2 1 0
2 1 1
5 1 0
5 1 1

4

Nguồn: Kỳ thi tuyển chọn đội tuyển IOI Hàn Quốc 2026 - Vòng 1, giấy phép CC BY-NC-SA 4.0.

Đề bài

Youngwoo có hai mảng số nguyên \(A,B\) cùng độ dài \(N\), trong đó \(A[i]\le B[i]\) với mọi \(i\).

Một đoạn \([l,r]\) được gọi là tuyệt vời nếu có thể biến mảng

thành

bằng cách lặp lại thao tác sau. Với mảng hiện tại \(X=[X[0],\ldots,X[r-l]]\), chọn hai chỉ số phân biệt \(i,j\) sao cho \(X[i]=X[j]\), rồi tăng \(X[i]\) thêm \(1\).

Có \(Q\) truy vấn. Truy vấn thứ \(j\) hỏi đoạn \([L[j],R[j]]\) có tuyệt vời hay không.

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

vector<int> array_operation(
    vector<int> A,
    vector<int> B,
    vector<int> L,
    vector<int> R
);

Hàm phải trả về mảng \(S\) độ dài \(Q\). S[j] bằng \(1\) nếu đoạn được hỏi là tuyệt vời, ngược lại bằng \(0\). Hàm được gọi đúng một lần và chương trình nộp không được thực hiện thao tác vào/ra.

Ràng buộc

• \(1\le N,Q\le 250\,000\).
• \(1\le A[i]\le B[i]\le 10^9\).
• \(0\le L[j]\le R[j]\le N-1\).

Phân nhóm

Grader mẫu

Grader mẫu đọc \(N,Q\), tiếp theo là \(N\) dòng A[i] B[i], rồi \(Q\) dòng L[j] R[j]. Grader in mảng kết quả trên một dòng.

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

1 1 0

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

1 1 0 1 0

Nguồn: Kỳ thi tuyển chọn đội tuyển IOI Hàn Quốc 2026 - Vòng 1, giấy phép CC BY-NC-SA 4.0.