Đặt trạm phát xa nhau nhất

Bối cảnh

Một tuyến hạ tầng có n vị trí có thể đặt trạm phát, mỗi vị trí là một tọa độ nguyên trên trục số. Cần chọn đúng k vị trí để khoảng cách nhỏ nhất giữa hai trạm được chọn là lớn nhất có thể. Ví dụ, nếu đặt các trạm quá gần nhau thì vùng phủ giao thoa; mục tiêu là "dàn đều" chúng tốt nhất.

Duyệt mọi tập k vị trí là không khả thi. Sau khi sort tọa độ, hãy chuyển câu hỏi "đáp án là bao nhiêu?" thành câu hỏi quyết định: với một khoảng cách D cho trước, có thể chọn được ít nhất k trạm sao cho mọi cặp liên tiếp đã chọn cách nhau ≥D hay không? Ta kiểm tra tham lam từ trái sang phải: luôn chọn vị trí đầu tiên, sau đó chọn vị trí sớm nhất đủ xa. Nếu D khả thi thì mọi giá trị nhỏ hơn D cũng khả thi; nếu D không khả thi thì mọi giá trị lớn hơn cũng không khả thi. Tính đơn điệu này cho phép binary search trên đáp án.

Đây là bài Advanced kinh điển kiểu "Aggressive Cows", rất gần HSG/Olympic/ICPC.

Điểm cốt lõi của dạng "binary search on answer" là không cần biết ngay cấu hình tối ưu; chỉ cần một hàm kiểm tra đúng/sai cho một giá trị D và chứng minh tính đơn điệu. Khi viết can(D), hãy tách nó khỏi binary search để có thể tự test độc lập: thử D rất nhỏ phải dễ đạt, D rất lớn phải khó đạt. Đây là thói quen quan trọng khi giải các bài tối ưu trong contest.

Yêu cầu

1. Sort tọa độ.
2. Viết hàm can(D) kiểm tra tham lam có chọn được k vị trí cách nhau ít nhất D.
3. Binary search giá trị D lớn nhất còn khả thi.
4. In D tối ưu.

Yêu cầu tổ chức code

Không dùng two pointers hay cấu trúc dữ liệu ngoài phạm vi B16.

Online Judge chấm output. Giảng viên có thể review source code để xác nhận học viên dùng đúng công cụ của buổi và không vượt prerequisite.

Input

Dòng 1 n k; dòng 2 n tọa độ.

Output

Một số nguyên: khoảng cách nhỏ nhất lớn nhất có thể.

Ràng buộc

2≤k≤n≤5000, |position|≤10^9.

Ví dụ 1

Input

5 3
1 2 8 4 9

Output

3

Giải thích

Sort vị trí thành 1 2 4 8 9. Với D=3, có thể chọn 1,4,8 — ba trạm và khoảng cách lần lượt 3,4, nên D=3 khả thi. Với D=4, chọn 1 rồi 8, sau đó không còn vị trí nào cách 8 ít nhất 4; chỉ được hai trạm nên D=4 không khả thi. Vì predicate đổi từ true sang false sau 3, binary search trả đáp án tối đa 3.

Ví dụ 2

Input

2 2
0 100

Output

100

Giải thích

Chỉ có hai vị trí 0 và 100, đồng thời k=2 nên mọi phương án hợp lệ bắt buộc chọn cả hai. Khoảng cách nhỏ nhất duy nhất là 100-0 = 100. Hàm can(100) chọn 0 rồi 100 và đạt đủ hai trạm; với bất kỳ D>100, vị trí thứ hai không còn đủ xa nên predicate sai. Vì vậy boundary true lớn nhất của binary search là 100.

Thông tin học tập

• Module: M05
• Buổi: B16
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: sort, binary search on answer, greedy feasibility, monotonic predicate
• Giới hạn kiến thức: B01-B16
• Time limit: 2 second(s)
• Memory limit: 256 MB
• Point: 100