USACO 2026 - Kỳ thi 2 - Hạng Vàng

John Nông Dân có \(N\) (\(1\le N\le 5\cdot 10^4\)) nhà kho nằm dọc theo một con đường. Nhà kho thứ \(i\) chứa \(a_i\) kiện cỏ khô và \(b_i\) bao thức ăn \((0\le a_i,b_i\le 10^9)\).

Bessie phàn nàn về sự bất bình đẳng giữa các nhà kho. Cô định nghĩa "độ mất cân bằng" của trang trại là hiệu giữa lượng cỏ khô lớn nhất trong một nhà kho bất kỳ và lượng thức ăn nhỏ nhất trong một nhà kho bất kỳ. Nói một cách chính thức, độ mất cân bằng là \(\max(a) - \min(b)\).

Để giải quyết mối lo của Bessie, John Nông Dân có thể thực hiện đúng \(K\) (\(1\le K\le 10^{18}\)) lần chuyển đổi. Trong mỗi lần chuyển đổi, ông chọn một nhà kho \(i\), bán một kiện cỏ khô của nhà kho đó và mua một bao thức ăn mới cho chính nhà kho ấy. Lưu ý rằng các lượng trong trang trại có thể âm (ông không ngại mắc nợ). Nói một cách chính thức, lặp lại \(K\) lần: chọn một chỉ số \(i\in [1,N]\), giảm \(a_i\) đi một và tăng \(b_i\) lên một.

Hãy giúp John Nông Dân xác định độ mất cân bằng nhỏ nhất có thể sau khi thực hiện đúng \(K\) lần chuyển đổi.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1 \leq T \leq 10^3\)), số lượng bộ test độc lập.

Dòng đầu tiên của mỗi bộ test chứa \(N\) và \(K\).

Dòng tiếp theo chứa \(a_1\dots a_N\).

Dòng tiếp theo chứa \(b_1\dots b_N\).

Tổng \(N\) trên tất cả các bộ test không vượt quá \(5 \cdot 10^4\).

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên duy nhất là giá trị nhỏ nhất có thể của \(\max(a) - \min(b)\) sau khi thực hiện \(K\) lần chuyển đổi.

Ví dụ

4
1 10
5
3
2 6
100 96
0 4
3 3
1 1 2
0 0 1
3 3
1 2 2
0 1 1

-18
90
0
0

Phân nhóm

• Các test 2–4: \(K\le 500\), tổng \(N\) trên tất cả các bộ test không vượt quá \(500\).
• Các test 5–8: Tổng \(N\) trên tất cả các bộ test không vượt quá \(500\).
• Các test 9–13: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 2, Gold Division — Balancing the Barns. Tác giả: Rohin Garg.
https://usaco.org/index.php?page=viewproblem2&cpid=1569

Bessie được cho một đồ thị vô hướng gồm \(N\) (\(1\le N\le 2 \cdot 10^5\)) đỉnh được đánh số \(1\dots N\) và \(M\) cạnh (\(N - 1\le M\le 2 \cdot 10^5\)). Mỗi cạnh được mô tả bởi hai số nguyên \(u, v\) (\(1\le u, v \le N\)), biểu thị một cạnh vô hướng giữa hai đỉnh \(u\) và \(v\), cùng một chữ cái Latin viết thường \(c\) trong khoảng từ a đến z, là giá trị trên cạnh. Đồ thị đã cho được đảm bảo liên thông. Đồ thị có thể có cạnh song song hoặc khuyên.

Định nghĩa \(f(a, b)\) là phép nối các giá trị cạnh nhỏ nhất theo thứ tự từ điển trong số tất cả các đường đi bắt đầu tại đỉnh \(a\) và kết thúc tại đỉnh \(b\). Một đường đi có thể chứa cùng một cạnh nhiều lần (tức là được phép có chu trình).

Với mỗi \(i\) (\(1\le i \le N\)), hãy giúp Bessie xác định độ dài của \(f(1, i)\). In ra độ dài này nếu nó hữu hạn; nếu không, in ra \(-1\).

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\le T\le 10\)), số lượng bộ test độc lập. Mỗi bộ test có định dạng như sau:

Dòng đầu tiên chứa \(N\) và \(M\).

\(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên, sau đó là một chữ cái Latin viết thường.

Đảm bảo rằng cả tổng \(N\) lẫn tổng \(M\) trên tất cả các bộ test đều không vượt quá \(4\cdot 10^5\).

Dữ liệu ra

Với mỗi bộ test, in ra \(N\) số nguyên cách nhau bởi dấu cách trên một dòng mới.

Ví dụ

2
1 0
2 2
1 1 a
2 1 b

0
0 -1

2
7 7
1 2 a
1 3 a
2 4 b
3 5 a
5 6 a
6 7 a
7 4 a
4 3
1 2 z
2 3 x
3 4 y

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

Phân nhóm

• Các test 3–4: Mọi ký tự đều là a.
• Các test 5–8: Mọi ký tự đều là a hoặc b.
• Các test 9–14: \(N,M\le 5000\).
• Các test 15–22: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 2, Gold Division — Lexicographically Smallest Path. Tác giả: Daniel Zhu và Yash Belani.
https://usaco.org/index.php?page=viewproblem2&cpid=1570

Bessie đang cố trốn khỏi những người nông dân. Những người nông dân sở hữu \(N\) (\(2 \le N \le 5 \cdot 10^5\)) trang trại, với một con đường một chiều nối trang trại thứ \(i\) đến trang trại thứ \(a_i\) (\(1 \le i \le N\), \(a_i \neq i\)). Có \(F\) (\(1 \le F \le N\)) người nông dân và người nông dân thứ \(i\) ban đầu đứng tại trang trại \(s_i\) (\(1 \le s_i \le N\), mọi \(s_i\) đôi một khác nhau). Tại mỗi bước thời gian, mỗi người nông dân đi theo con đường ở trang trại hiện tại của mình để đến trang trại tiếp theo. Bessie bị bắt nếu có bất kỳ lúc nào cô ở cùng một trang trại với một người nông dân.

Giả sử Bessie bắt đầu tại một trang trại \(b\). Tại mỗi bước thời gian, cô có hai lựa chọn: nghỉ lại (ở nguyên tại trang trại hiện tại) hoặc đi theo con đường để đến trang trại tiếp theo. Nếu chọn di chuyển, cô di chuyển đồng thời với những người nông dân. Bessie phải lựa chọn các bước di chuyển sao cho cô không bị bất kỳ người nông dân nào bắt tại bất kỳ thời điểm hữu hạn nào.

Với mỗi trang trại xuất phát \(b\) (\(1 \le b \le N\)), hãy tìm số lần lớn nhất Bessie có thể chọn nghỉ lại nếu cô bắt đầu tại trang trại \(b\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(F\), lần lượt là số trang trại và số người nông dân.

Dòng thứ hai chứa \(a_1 \ldots a_N\), mô tả con đường một chiều đi ra từ mỗi trang trại.

Dòng thứ ba chứa \(s_1 \ldots s_F\), vị trí xuất phát của mỗi người nông dân.

Dữ liệu ra

In ra \(N\) dòng; dòng thứ \(b\) gồm một số nguyên duy nhất biểu thị số lần lớn nhất Bessie có thể chọn nghỉ lại nếu cô bắt đầu tại trang trại \(b\). Nếu Bessie không có cách nào để tránh bị bắt tại mọi thời điểm hữu hạn, in ra \(-1\). Nếu Bessie có thể nghỉ lại vô hạn lần, in ra \(-2\).

Ví dụ

4 1
2 1 4 3
1

-1
0
-2
-2

Phân nhóm

• Test 2: \(N \le 50\).
• Các test 3–10: \(N \le 2000\).
• Các test 11–20: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 2, Gold Division — The Chase. Tác giả: Alex Liang.
https://usaco.org/index.php?page=viewproblem2&cpid=1571