USACO 2025 - Tháng 1 - Hạng Vàng

Lưu ý: Giới hạn thời gian của bài này là 4 giây, gấp đôi giới hạn mặc định.

Farmer John có một cây nhị phân gồm \(N\) đỉnh được đánh số từ \(1\) đến \(N\) (\(1 \leq N < 2\cdot 10^5\) và \(N\) là số lẻ). Với \(i>1\), cha của đỉnh \(i\) là \(\lfloor i/2\rfloor\). Mỗi đỉnh có một giá trị nguyên ban đầu \(a_i\) và một chi phí \(c_i\) để đổi giá trị ban đầu thành bất kỳ giá trị nguyên nào khác (\(0\le a_i,c_i\le 10^9\)).

Federal Bovine Intermediary (FBI) đã giao cho ông nhiệm vụ tìm một giá trị trung vị xấp xỉ trong cây này, và ông đã nghĩ ra một thuật toán thông minh để làm vậy.

Ông bắt đầu tại đỉnh cuối cùng \(N\) và lần lượt đi ngược lại. Tại mỗi bước của thuật toán, nếu một đỉnh không phải là trung vị của chính nó và hai con của nó, ông hoán đổi giá trị của đỉnh hiện tại với giá trị của đỉnh con mà lẽ ra là trung vị. Khi thuật toán kết thúc, giá trị tại đỉnh \(1\) (gốc) là trung vị xấp xỉ.

FBI cũng đưa cho Farmer John danh sách \(Q\) (\(1 \leq Q \leq 2\cdot 10^5\)) truy vấn độc lập, mỗi truy vấn được xác định bởi một giá trị mục tiêu \(m\) (\(0\le m\le 10^9\)). Với mỗi truy vấn, trước tiên FJ sẽ thay đổi một số giá trị ban đầu của các đỉnh, rồi thực thi thuật toán xấp xỉ trung vị. Với mỗi truy vấn, hãy xác định tổng chi phí nhỏ nhất có thể để FJ khiến đầu ra của thuật toán bằng \(m\).

Dữ liệu vào

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

\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i\) và \(c_i\).

Dòng tiếp theo chứa \(Q\).

\(Q\) dòng tiếp theo, mỗi dòng chứa một giá trị mục tiêu \(m\).

Dữ liệu ra

In \(Q\) dòng, mỗi dòng là tổng chi phí nhỏ nhất có thể ứng với giá trị mục tiêu \(m\) tương ứng.

Ví dụ

5
10 10000
30 1000
20 100
50 10
40 1
11
55
50
45
40
35
30
25
20
15
10
5

111
101
101
100
100
100
100
0
11
11
111

Phân nhóm

• Inputs 2-4: \(N,Q\le 50\).
• Inputs 5-7: \(N,Q\le 1000\).
• Inputs 8-16: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Gold — Median Heap

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1473

Tác giả đề: Suhas Nagar và Benjamin Qi

Xét một đồ thị vô hướng gồm \(N\) đỉnh được đánh số \(1\dots N\) và \(M\) cạnh (\(1\le N\le 2\cdot 10^5, 0\le M\le 4\cdot 10^5\)). Bạn được cho một chuỗi nhị phân \(s_1s_2\dots s_N\). Tại thời điểm \(t\) với mỗi \(t\in [1,N]\):

• Nếu \(s_t=0\), đỉnh \(t\) bị xóa khỏi đồ thị.
• Nếu \(s_t=1\), đỉnh \(t\) bị xóa khỏi đồ thị, đồng thời các cạnh được thêm vào giữa mọi cặp đỉnh kề với đỉnh \(t\) ngay trước khi nó bị xóa.

Lưu ý rằng trong cả hai trường hợp, khi một đỉnh bị xóa khỏi đồ thị, tất cả các cạnh liên thuộc với nó cũng bị xóa.

Hãy đếm số cặp đỉnh có thể đi tới nhau qua một dãy cạnh nào đó ngay trước mỗi thời điểm \(1\ldots N\).

Dữ liệu vào

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

Dòng thứ hai chứa chuỗi bit \(s\) có độ dài \(N\).

\(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên biểu diễn một cạnh của đồ thị.

Dữ liệu ra

In \(N\) dòng, là số cặp trước mỗi thời điểm.

Ví dụ

3 2
111
1 2
1 3

3
1
0

3 2
000
1 2
1 3

3
0
0

7 8
1101101
6 2
1 2
2 3
6 3
1 3
1 7
4 5
2 7

11
7
4
2
1
1
0

Phân nhóm

• Inputs 4-6: \(N\le 100\).
• Inputs 7-8: Mọi \(s_i\) đều bằng không.
• Inputs 9-11: Mọi \(s_i\) đều bằng một.
• Inputs 12-23: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Gold — Reachable Pairs

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1474

Tác giả đề: Benjamin Qi

Trang trại của Farmer John tràn đầy thảm thực vật xanh tốt và mọi con bò đều muốn chụp một bức ảnh về vẻ đẹp tự nhiên của nó. Không may, Bessie vẫn có nơi cần đến, nhưng cô không muốn làm gián đoạn bất kỳ buổi chụp ảnh nào.

Bessie hiện đang đứng tại \((X,0)\) trên mặt phẳng \(XY\) và muốn đi đến \((0,Y)\) (\(1\le X,Y\le 10^6\)). Không may, \(N\) (\(1 \leq N \leq 3 \cdot 10^5\)) con bò khác đã quyết định tạo dáng trên trục \(X\). Cụ thể hơn, bò \(i\) sẽ đứng tại \((x_i,0)\) với một nhiếp ảnh gia ở \((0,y_i)\) sẵn sàng chụp ảnh cho nó, trong đó \((1 \leq x_i,y_i \leq 10^6)\). Chúng sẽ bắt đầu tạo dáng ngay trước thời điểm \(s_i\) (\(1 \leq s_i < T\)) và tiếp tục tạo dáng trong thời gian rất dài (chúng phải chụp được bức ảnh thật hoàn hảo). Ở đây, \(1\le T\le N+1\).

Bessie biết lịch chụp ảnh của mọi con bò, và cô sẽ đi quãng đường Euclid ngắn nhất để đến đích mà không cắt qua đường ngắm từ bất kỳ nhiếp ảnh gia nào đến con bò tương ứng (đường đi của cô gồm một hoặc nhiều đoạn thẳng).

Nếu Bessie khởi hành tại thời điểm \(t\), cô sẽ tránh đường ngắm của tất cả các cặp nhiếp ảnh gia/bò bắt đầu tạo dáng tại thời điểm \(s_i \le t\), và gọi khoảng cách đến đích cuối cùng của cô là \(d_t\). Hãy xác định các giá trị \(\lfloor d_t\rfloor\) với mỗi số nguyên \(t\) từ \(0\) đến \(T-1\), tính cả hai đầu.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(T\), lần lượt biểu diễn số con bò tạo dáng trên trục \(x\) và khoảng thời gian Bessie có thể khởi hành.

Dòng thứ hai chứa \(X\) và \(Y\), lần lượt biểu diễn tọa độ \(X\) ban đầu của Bessie và tọa độ \(Y\) đích của cô.

\(N\) dòng tiếp theo chứa \(s_i\) \(x_i\) và \(y_i\). Đảm bảo mọi \(x_i\) đôi một khác nhau và khác \(X\), mọi \(y_i\) đôi một khác nhau và khác \(Y\). Mọi \(s_i\) được cho theo thứ tự không giảm, với \(s_i \leq s_{i+1}\).

Dữ liệu ra

In \(T\) dòng, trong đó dòng thứ \(t\) (đánh số từ \(0\)) chứa \(\lfloor d_t\rfloor\).

Ví dụ

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

9
9
9
10
12

2 3
10 7
1 2 10
1 9 1

12
16
16

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

12
12
12
12
14
14

Phân nhóm

• Inputs 4-6: \(N\le 100\).
• Inputs 7-9: \(N\le 3000\).
• Inputs 10-12: \(T\le 10\).
• Inputs 13-18: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Gold — Photo Op

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1475

Tác giả đề: Suhas Nagar