USACO 2018 - US Open - Hạng Bạch Kim

Để chuẩn bị cho những cơ hội nghề nghiệp lâu dài bên ngoài trang trại, cô bò Bessie đã bắt đầu học các thuật toán từ nhiều trang web lập trình trực tuyến. Hai thuật toán yêu thích của cô là “sắp xếp nổi bọt” và “sắp xếp nhanh”, nhưng thật không may, Bessie rất dễ nhầm lẫn hai thuật toán này và cuối cùng lại cài đặt một thuật toán lai khá kỳ lạ!

Ta gọi vị trí nằm giữa hai phần tử \(i\) và \(i+1\) trong một mảng \(A\) là một “điểm phân hoạch” nếu giá trị lớn nhất trong \(A[...i]\) không lớn hơn giá trị nhỏ nhất trong \(A[i+1 \ldots]\). Bessie nhớ rằng sắp xếp nhanh sắp xếp lại một mảng sao cho mảng có một điểm phân hoạch, rồi đệ quy sắp xếp hai phía \(A[...i]\) và \(A[i+1 \ldots]\). Tuy nhiên, dù đã nhận ra chính xác rằng tất cả các điểm phân hoạch trong một mảng có thể được xác định trong thời gian tuyến tính, cô lại quên mất sắp xếp nhanh phải sắp xếp lại mảng như thế nào để nhanh chóng tạo ra một điểm phân hoạch! Trong một quyết định có thể là sai lầm thuật toán tồi tệ nhất lịch sử các thuật toán sắp xếp, cô không may quyết định dùng sắp xếp nổi bọt cho nhiệm vụ này.

Dưới đây là phác thảo cách cài đặt ban đầu của Bessie để sắp xếp một mảng \(A\). Trước tiên, cô viết một hàm đơn giản thực hiện một lượt sắp xếp nổi bọt:

bubble_sort_pass (A) {
   for i = 0 to length(A)-2
      if A[i] > A[i+1], swap A[i] and A[i+1]
}

Sau đó, mã đệ quy cho hàm sắp xếp nhanh (kiểu gần giống) của cô có cấu trúc như sau:

quickish_sort (A) {
   if length(A) = 1, return
   do { // Main loop
      work_counter = work_counter + length(A)
      bubble_sort_pass(A)
   } while (no partition points exist in A)
   divide A at all partition points; recursively quickish_sort each piece
}

Bessie tò mò không biết mã của mình sẽ chạy nhanh đến đâu. Để đơn giản, cô cho rằng mỗi vòng lặp chính cần thời gian tuyến tính, nên trong vòng lặp, cô tăng một biến toàn cục có tên work_counter thêm một lượng tương ứng để theo dõi tổng khối lượng công việc mà thuật toán thực hiện.

Với một mảng đầu vào, hãy dự đoán giá trị cuối cùng của work_counter sau khi mảng được xử lý bởi quickish_sort.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 100\,000\)). \(N\) dòng tiếp theo mô tả lần lượt \(A[0] \ldots A[N-1]\); mỗi phần tử là một số nguyên thuộc khoảng \(0 \ldots 10^9\). Các phần tử đầu vào không nhất thiết đôi một khác nhau.

Dữ liệu ra

In ra giá trị cuối cùng của work_counter.

Ví dụ

7
20
2
3
4
9
8
7

12

Nguồn

USACO 2018 US Open Contest, Platinum — Out of Sorts

Tác giả bài toán: Brian Dean.

Mỗi buổi sáng, tàu tốc hành chạy ngang qua trang trại để tới thành phố lớn; mỗi buổi chiều, nó chạy ngang qua theo hướng ngược lại để trở về vùng ngoại ô. Hôm nay, Bessie dành thời gian quan sát đoàn tàu cả buổi sáng lẫn buổi chiều.

Bessie biết trước rằng đoàn tàu có \(N\) toa (\(1 \leq N \leq 10^6\)), được đánh số thuận tiện từ \(0 \dots N-1\). Toa \(i\) có ghi số ID \(c_i\) (\(0 \leq c_i \leq 10^9\)). Tất cả các số đều nhìn thấy được cả vào buổi sáng lẫn buổi chiều, nên Bessie có hai cơ hội quan sát số của mỗi toa. Cụ thể, khi đoàn tàu chạy ngang qua vào buổi sáng, Bessie quan sát được \(c_0\), tiếp theo là \(c_1\), và cứ thế cho đến \(c_{N-1}\). Khi đoàn tàu chạy ngang qua vào buổi chiều, cô lại quan sát được \(c_0\), tiếp theo là \(c_1\), và cứ thế cho đến \(c_{N-1}\).

Bessie đã chọn một số nguyên \(K\) (\(1 \leq K \leq N\)), và cô muốn xác định số ID nhỏ nhất trong mỗi đoạn gồm \(K\) toa liên tiếp. Cô có một cuốn sổ để thực hiện tính toán, nhưng nó khá nhỏ, còn chữ viết tay (hay viết móng?) của cô lại khá lớn. Chẳng hạn, sổ thậm chí có thể không đủ chỗ để ghi cả \(N+1-K\) giá trị nhỏ nhất. Vì những lý do khó hiểu, Bessie sẵn lòng kêu các giá trị nhỏ nhất lên trời ngay khi tính được, nên ít nhất điều này không phải là vấn đề.

Đoàn tàu sắp tới! Hãy giúp Bessie tìm \(N+1-K\) giá trị nhỏ nhất khi đoàn tàu chạy ngang qua hai lần, đồng thời bảo đảm cô sử dụng hiệu quả cuốn sổ có dung lượng hạn chế. Cuốn sổ được chia thành \(5500\) ô, được đánh số thuận tiện từ \(0 \dots 5499\), và mỗi ô có thể lưu chính xác một số nguyên trong đoạn từ \(-2^{31}\) đến \(2^{31}-1\), kể cả hai đầu mút. Ban đầu, mỗi ô lưu số nguyên \(0\).

Giao thức tương tác

Đây là một bài tương tác, nhưng bạn sẽ không sử dụng I/O chuẩn hoặc I/O tệp. Cụ thể, bạn phải cài đặt hàm sau để giúp Bessie quản lý hiệu quả không gian hạn chế trong cuốn sổ:

void helpBessie(int ID);

Mỗi khi một toa tàu chạy ngang qua, cả vào buổi sáng lẫn buổi chiều, hàm của bạn sẽ được gọi và đầu vào của hàm là số ID ghi trên toa tàu đó.

Trong phần cài đặt hàm helpBessie, bạn có thể gọi các hàm sau:

• int get(int index): lấy giá trị số nguyên được lưu tại chỉ số đã cho trong sổ của Bessie.
• void set(int index, int value): đặt số nguyên tại chỉ số đã cho thành giá trị đã cho.
• void shoutMinimum(int output): yêu cầu Bessie kêu số đã cho lên trời.
• int getTrainLength(): trả về \(N\), số toa tàu.
• int getWindowLength(): trả về \(K\), độ dài cửa sổ.
• int getCurrentCarIndex(): trả về chỉ số của toa tàu hiện đang chạy ngang qua.
• int getCurrentPassIndex(): trả về \(0\) nếu Bessie đang quan sát lượt tàu buổi sáng và trả về \(1\) nếu cô đang quan sát lượt tàu buổi chiều.

Để giúp bạn bắt đầu viết mã, đề bài cung cấp các mã mẫu ban đầu cho C/C++ và Java. Rất tiếc, bài này không hỗ trợ bài nộp bằng Python hoặc Pascal.

Các giá trị nhỏ nhất của cửa sổ phải được xuất theo đúng thứ tự: giá trị nhỏ nhất trên các toa \(0, 1, \dots, K-1\) phải được xuất trước giá trị nhỏ nhất trên các toa \(1, 2, \dots, K\), và cứ tiếp tục như vậy. Ngoài ràng buộc về thứ tự này, hàm của bạn có thể xuất các giá trị nhỏ nhất trong bất kỳ lần gọi hàm nào và vào bất kỳ thời điểm nào. Chẳng hạn, hàm có thể không tạo ra đầu ra trong một số lần gọi và tạo ra nhiều đầu ra trong những lần gọi khác.

Bessie có trí nhớ ngắn hạn tuyệt vời, vì vậy không có hạn chế nào về bộ nhớ được sử dụng bên trong hàm helpBessie, ngoài giới hạn thông thường là 256 MB. Tuy nhiên, giữa hai toa tàu, Bessie không thể “nhớ” bất cứ điều gì không được lưu trong sổ. Vì vậy, giữa các lần gọi hàm, chương trình không được duy trì trạng thái nào ngoài trạng thái được lưu thông qua các lời gọi get và set.

Điều này có nghĩa là:

Bạn KHÔNG ĐƯỢC PHÉP tạo bất kỳ biến toàn cục hoặc biến tĩnh không phải hằng số nào. Mọi lời giải làm như vậy sẽ bị loại. Các huấn luyện viên SẼ kiểm tra thủ công để xác minh lời giải tuân thủ tinh thần của bài toán. Vì bài này không cần I/O tệp, bạn cũng KHÔNG ĐƯỢC PHÉP thực hiện bất kỳ thao tác I/O tệp nào trong mã.

Tổng số lời gọi set cộng với tổng số lời gọi get mà chương trình thực hiện được giới hạn ở \(25 \cdot 10^6\) cho mỗi bộ dữ liệu kiểm tra.

Dữ liệu vào

Bạn không đọc dữ liệu trực tiếp từ đầu vào chuẩn. Bộ chấm biết trước \(N\), \(K\) và dãy \(c_0, c_1, \dots, c_{N-1}\); trong mỗi lượt tàu chạy qua, bộ chấm lần lượt gọi helpBessie(c_i) với \(i=0,1,\dots,N-1\). Định dạng hiển thị trong ví dụ gồm \(N\), \(K\) trên dòng đầu và \(N\) số ID trên dòng thứ hai.

Dữ liệu ra

Bạn không ghi trực tiếp ra đầu ra chuẩn. Hãy gọi shoutMinimum đúng \(N+1-K\) lần để báo các giá trị nhỏ nhất của các cửa sổ theo thứ tự từ trái sang phải như mô tả ở trên.

Ví dụ

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

5
2
0
0
0
1
3
3

Nguồn

USACO 2018 US Open Contest, Platinum — Train Tracking

Tác giả bài toán: Dhruv Rohatgi.

Bác nông dân John tự hào vì điều hành một trang trại có khả năng kết nối tốt. Trang trại gồm \(N\) đồng cỏ (\(2 \leq N \leq 50\,000\)), được nối với nhau bằng \(N-1\) đường đi hai chiều có độ dài bằng một. Bác nông dân John nhận thấy rằng bằng cách sử dụng một chuỗi thích hợp gồm các đường đi này, ta có thể di chuyển từ bất kỳ đồng cỏ nào tới bất kỳ đồng cỏ nào khác.

Mặc dù trang trại được kết nối, bác nông dân John lo lắng về điều có thể xảy ra nếu một đường đi bị chặn, vì khi đó trang trại sẽ bị chia thành hai tập đồng cỏ rời nhau: đàn bò có thể di chuyển trong từng tập nhưng không thể di chuyển giữa hai tập. Vì vậy, ông xây thêm một tập gồm \(M\) đường đi hai chiều (\(1 \leq M \leq 50\,000\)), mỗi đường có độ dài là một số nguyên dương không vượt quá \(10^9\). Đàn bò vẫn chỉ sử dụng các đường đi ban đầu để di chuyển, trừ khi một trong số chúng bị chặn.

Nếu một trong các đường đi ban đầu bị chặn, trang trại sẽ bị chia thành hai phần rời nhau. Bác nông dân John sẽ chọn đúng một đường thay thế trong số các đường bổ sung để khôi phục kết nối giữa hai phần, nhờ đó đàn bò lại có thể di chuyển từ bất kỳ đồng cỏ nào tới bất kỳ đồng cỏ nào khác.

Với mỗi đường đi ban đầu trong trang trại, hãy giúp bác nông dân John chọn đường thay thế phù hợp ngắn nhất.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\). Mỗi dòng trong \(N-1\) dòng tiếp theo mô tả một đường đi ban đầu bằng hai số nguyên \(p\), \(q\), trong đó \(p \ne q\) là hai đồng cỏ được đường đi nối với nhau và đều thuộc khoảng \(1 \ldots N\). Mỗi dòng trong \(M\) dòng còn lại mô tả một đường đi bổ sung bằng ba số nguyên \(p\), \(q\) và \(r\), trong đó \(r\) là độ dài của đường đi. Giữa mỗi cặp đồng cỏ có nhiều nhất một đường đi.

Dữ liệu ra

Với mỗi đường trong \(N-1\) đường đi ban đầu, theo đúng thứ tự chúng xuất hiện trong dữ liệu vào, in độ dài của đường thay thế phù hợp ngắn nhất có thể kết nối lại trang trại nếu đường ban đầu đó bị chặn. Nếu không tồn tại đường thay thế phù hợp, in -1.

Ví dụ

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

7
7
8
5
5

Nguồn

USACO 2018 US Open Contest, Platinum — Disruption

Tác giả bài toán: Brian Dean.