Khóa Số 3
Đề bài
Đề thi học sinh giỏi tin học của trường mầm non SuperKids được đặt trong một két sắt và khoá lại bằng một khoá số. Khoá số này có cấu tạo rất đặc biệt: khoá gồm $n$ đĩa tròn đánh số từ 1 tới $n$. Mỗi đĩa chia thành $m$ hình quạt bằng nhau đánh số từ 1 tới $m$, trong đó có đúng một hình quạt bị đục rỗng gọi là khe của đĩa đó.
Ban đầu, các đĩa tròn này được xếp chồng lên nhau sao cho các hình quạt được đánh số giống nhau nằm chồng khít lên nhau. Muốn mở được khoá này cần xoay các đĩa sao cho khe của các đĩa phải chồng khít lên nhau.
Giáo sư X được giao nhiệm vụ phát đề và ông cần mở khoá để lấy đề phát cho các thí sinh. Biết rằng trong một giây, giáo sư X chỉ có thể quay một trong các đĩa theo một trong hai chiều: theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ dịch đi một hình quạt.
Yêu cầu: hãy tính xem giáo sư X phải mất tối thiểu bao nhiêu giây mới mở được khoá của chiếc két sắt.
Dữ liệu:
- Dòng 1 chứa hai số nguyên dương $n, m$ $(n \le 10^5$; $2 \le m \le 10^9)$.
- Dòng 2 chứa $n$ số nguyên dương, số thứ $i$ là số hiệu khe của chiếc đĩa thứ $i$.
Kết quả: ghi ra thời gian tối thiểu tính bằng giây cần để mở được khoá của chiếc két sắt.
Subtask: 50% số test đầu tiên có $n \le 10^4$; 50% số test còn lại không có giới hạn gì thêm.
3 8
8 3 13
Ba đĩa trong ví dụ, ô trắng là khe: 8, 3, 1. Xoay đĩa khe 8 thêm 1 nấc và đĩa khe 3 lùi 2 nấc để cùng về vị trí 1: tổng 3 giây.
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm, kèm toàn bộ tin nhắn của mình với em ấy để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 😇. Chúc các bạn học tốt và gặt hái nhiều thành công.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
50%Cách vét cạn O(N²)
Có phải $O(N^2)$ của em là: em chọn 1 số $a_i$ làm vị trí đích, sau đó xét các $a_j$ còn lại tính số bước xoay đến $a_i$. Từ $x$ mà xoay đến $y$ thì số bước xoay là $|x - y|$ hoặc $m - |x - y|$ (xoay chiều ngược lại), lấy cái nhỏ hơn, cộng hết lại rồi lấy min của tất cả các $a_i$?
Với $n$ tới $10^5$ thì $O(N^2) = 10^{10}$, chắc chắn TLE ở 50% test sau. Bài này thì anh mới xem qua và có ý tưởng như thế này, anh cứ trình bày ra hết rồi em xem xét thật kỹ rồi thử làm nhé.
Ý tưởngSắp xếp + chia đôi vòng tròn
Đầu tiên sort dãy $a$ lại. Với số $a_i$ (vị trí đích), nếu thằng $a_j$ xoay đến $a_i$ mà số nấc xoay lớn hơn $m/2$ thì em biết số nấc phải là $m - |a_i - a_j|$. Hiển nhiên: ổ khoá có 10 nấc mà em xoay theo chiều thuận thấy hết 7 nấc rồi thì nên xoay chiều ngược thôi 😄. Như vậy xoay theo chiều thuận tối đa chỉ $m/2$ nấc.
• Các thằng từ $l$ đến $i$: xoay thẳng, chi phí $a_i - a_j$.
• Các thằng nhỏ hơn $l$ (gọi là $a_x$, $x$ từ 1 đến $l-1$): xoay vòng ngược, chi phí $m - (a_i - a_x) = m - a_i + a_x$.
Nhìn lại công thức: từ $l$ đến $i$ có tổng cộng $i - l + 1$ lần $a_i$ mang dấu dương (vì cộng $a_i - a_j$). Còn đám $a_x$ với $x$ từ 1 đến $l-1$ thì cộng $m - a_i + a_x$: có $l - 1$ lần $m$ xuất hiện và $l - 1$ lần $a_i$ mang dấu âm.
Đến đây em phải đảm bảo là hiểu những gì anh đã nói từ đầu đến giờ rồi thì mới xem tiếp nha 😄. Bây giờ chỉ còn vụ tổng các $a_j$ với $j$ từ $l$ đến $i$ và tổng các $a_x$ với $x$ từ 1 đến $l-1$: dùng mảng cộng dồn (prefix sum) là xong, mỗi tổng tính trong $O(1)$:
Σx=1..l−1 (m − ai + ax) = (l − 1)·(m − ai) + suml−1
Phần bên phải em làm tương tự: tìm $r$ xa nhất bên phải mà $a_r - a_i \le m/2$ (xoay thẳng $a_j - a_i$), những thằng sau $r$ thì xoay vòng $m + a_i - a_j$. Em nháp ra công thức thôi, anh để sẵn trong phần chú thích đầu code.
Vì sao chỉ cần thử đích là một trong các $a_i$? Tổng khoảng cách trên vòng tròn là hàm tuyến tính từng khúc giữa hai khe liên tiếp, nên giá trị nhỏ nhất luôn đạt tại một khe nào đó (giống bài "trung vị" quen thuộc trên đường thẳng). Mình cũng đã kiểm tra bằng máy: thử mọi vị trí đích từ 1 đến $m$ cho ra đúng cùng đáp án.
Minh hoạThử từng vị trí đích
Em nhập $m$ (tối đa 24) và khe của các đĩa (tối đa 10 đĩa), bấm Tiếp để thử lần lượt từng khe làm đích. Chấm xanh dương là đĩa xoay thẳng (nằm trong đoạn $[l, r]$), chấm cam là đĩa nên xoay vòng qua mốc $m \to 1$:
CodeSource code
Anh cũng vừa code và nộp thành công trên web, làm theo đúng tư tưởng ở trên không khác gì hết. Anh nói trước là code này anh code vội ra theo đúng tư tưởng đã chia sẻ với em chứ chưa có clean đâu nha:
#include <bits/stdc++.h>
using namespace std;
/*
Tong (a[i] - a[j]) voi j: minLeft -> i = (i - minLeft + 1) * a[i] - sum[i] + sum[minLeft - 1]
Tong (m - a[i] + a[j]) voi j: 1 -> minLeft - 1 = (minLeft - 1) * (m - a[i]) + sum[minLeft - 1]
Tong (a[j] - a[i]) voi j: i -> maxRight = sum[maxRight] - sum[i - 1] - (maxRight - i + 1) * a[i]
Tong (m + a[i] - a[j]) voi moi j: maxRight + 1 -> n = (n - maxRight) * (m + a[i]) - sum[n] + sum[maxRight]
*/
long long a[100005];
long long sum[100005];
int n;
long long m;
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + a[i];
}
long long ans = 10000000000000000LL;
for (int i = 1; i <= n; i++) {
int l = 1;
int r = i;
long long totalCost = 0LL;
int minLeft = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (a[i] - a[mid] <= m / 2) {
minLeft = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
totalCost += 1LL * (minLeft - 1) * (m - a[i]) - sum[i] + 1LL * (i - minLeft + 1) * a[i] + 2LL * sum[minLeft - 1];
int maxRight = -1;
l = i;
r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] - a[i] <= m / 2) {
maxRight = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
totalCost += 1LL * (n - maxRight) * (m + a[i]) - sum[n] + 2LL * sum[maxRight] - sum[i - 1] - 1LL * (maxRight - i + 1) * a[i];
ans = min(ans, totalCost);
}
cout << ans;
return 0;
}import sys
from bisect import bisect_left, bisect_right
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = [0] + sorted(map(int, data[2:2 + n])) # đánh chỉ số từ 1 giống bản C++
s = [0] * (n + 1)
for i in range(1, n + 1):
s[i] = s[i - 1] + a[i]
half = m // 2
ans = None
for i in range(1, n + 1):
# minLeft: vị trí nhỏ nhất bên trái mà a[i] - a[minLeft] <= m/2 (xoay thuận)
minLeft = bisect_left(a, a[i] - half, 1, i + 1)
# maxRight: vị trí lớn nhất bên phải mà a[maxRight] - a[i] <= m/2
maxRight = bisect_right(a, a[i] + half, i, n + 1) - 1
cost = (minLeft - 1) * (m - a[i]) - s[i] + (i - minLeft + 1) * a[i] + 2 * s[minLeft - 1]
cost += (n - maxRight) * (m + a[i]) - s[n] + 2 * s[maxRight] - s[i - 1] - (maxRight - i + 1) * a[i]
if ans is None or cost < ans:
ans = cost
print(ans)
main()Hai đoạn tìm kiếm nhị phân lần lượt tìm minLeft (vị trí $l$) và maxRight (vị trí $r$). Riêng $j = i$ được tính ở cả hai phần nhưng chi phí bằng 0 nên không ảnh hưởng. Biến ans khởi tạo bằng $10^{16}$, đủ lớn vì chi phí tối đa khoảng $10^5 \times 5 \cdot 10^8 = 5 \cdot 10^{13}$, nhớ dùng long long.
bisect thay cho 2 vòng tìm kiếm nhị phân tự viết. Cả 2 bản đã được kiểm tra với 600 bộ test ngẫu nhiên so với cách thử mọi vị trí đích từ 1 đến $m$; với $n = 10^5$, bản C++ chạy khoảng 0.02 giây, bản Python khoảng 0.16 giây.
Nhận xét
Đăng nhận xét