Ngẫm về Fixing Array
Fixing Array là bài 4 trong kỳ chọn đội tuyển Olympic sinh viên của ĐH SPKT TPHCM (HCMUTE).
Đề bài
Time limit: 0.5s
Memory limit: 256MB
Cho dãy số nguyên a[1], a[2],... a[n]. Thực hiện sắp xếp lại dãy thành 1 dãy không giảm bằng 1 trong 2 thao tác sau:
-
Lấy 1 số ra khỏi dãy, đặt số đó vào đầu dãy. Giá sử lấy số
a[i]ra, dãy sẽ trở thànha[i], a[1],... a[i-1], a[i+1],... a[n]. -
Lẫy 1 số ra khỏi dãy, đặt số đó vào cuối dãy. Giá sử lấy số
a[i]ra, dãy sẽ trở thànha[1],... a[i-1], a[i+1],... a[n], a[i].
Yêu cầu: Hãy xác định số thao tác ít nhất để biến đổi dãy đã cho thành một dãy không giảm.
Dữ liệu
-
Dòng đầu chứa số nguyên dương
n -
Dòng thứ 2 chứa
nsố nguyên không âma[1], a[2],... a[n](a[i] <= 10^9)
Kêt quả
Một số nguyên duy nhất là số thao tác ít nhất tìm được.
Hạn chế
- Subtask 1: (10% điểm)
n <= 300, các số đôi một khác nhau - Subtask 2: (10% điểm)
n <= 5000, các số đôi một khác nhau - Subtask 3: (10% điểm)
n <= 300000, các số đôi một khác nhau - Subtask 4: (20% điểm)
n <= 300 - Subtask 5: (20% điểm)
n <= 5000 - Subtask 6: (30% điểm)
n <= 300000.
Ví dụ
| stdin | stdout |
|---|---|
| 5 1 2 3 4 5 |
0 |
| 5 5 4 3 2 1 |
4 |
| 5 1 3 2 4 5 |
2 |
Cách giải
Coi dãy a là 1-index. Gọi fix_array(a[1..n]) là số bước tối thiểu để xếp lại dãy a để làm cho dãy tăng dần.
Ta có vài nhận xét quan trọng:
-
Nếu dãy
atăng dần –>fix_array(a[1..n]) = 0. -
Nếu dãy
agiảm dần –>fix_array(a[1..n]) = len(a) - max(freq_a(x) for x in a).Chứng minh: Dãy
agiảm dần, tuy nhiên dãy conx, x,... x(freq_a(x)lầnx,xbất kì thuộca) lại là dãy tăng dần. Nếu chọn 1 giá trịxlàm mốc, ta cần đưa các giá trị< xvề đầu dãy và các giá trị> xvề cuối dãy, tổng cộng tốnlen(a) - freq_a(x)bước. Do vậy số bước tối ưu làlen(a) - max(freq_a(x) for x in a)bước.
Trước hết ta lọc dãy a làm 3 dãy con (các phần tử vẫn giữ nguyên thứ tự ban đầu trong a):
-
left_side: các số< min(a[1], a[n]). -
right_side: các số> max(a[1], a[n]). -
inside: các số nằm trong[a[1], a[n]].
Dễ thấy việc đưa các số trong left_side về bên trái a[1] và đưa các số trong right_side về bên phải là độc lập với việc sắp xếp lại các số trong tập inside. Do vậy trong trường hợp này, ta tiến hành sắp xếp các số trong inside trước.
Ta tạo 1 danh sách các phần tử phân biệt (đã được sắp xếp thứ tự) của inside, tên là unique_inside.
Định nghĩa các phần tử đứng đúng vị trí (về bên trái): dãy con inside' của inside (các phần tử của dãy con giữ nguyên thứ tự so với dãy gốc) gồm các phần tử đứng đúng vị trí nếu trong dãy con đó, inside'[i] xuất hiện liên tiếp đúng freq_a(inside'[i]) lần (inside'[i] < inside'[len(inside') - 1]) và inside'[len(inside') - 1] xuất hiện liên tiếp ít nhất 1 lần.
Định nghĩa các phần tử đứng đúng vị trí (về bên phải) ta làm ngược lại.
Mã Python đánh dấu các phần tử bị sai vị trí:
i = 0
is_position_correct = [False] * len(inside)
for x in unique_inside:
count_x = 0
while i < len(inside) and count_x < freq_a[x]:
if inside[i] == x:
is_position_correct[i] = True
count_x += 1
i += 1
Bước đánh dấu các phần tử bị sai vị trí mất O(n).
Ta áp dụng chiến lược gần giống với trường hợp dãy a giảm dần, đó là chọn 1 phần tử x làm mốc, đưa các giá trị < x về đầu dãy và các giá trị > x về cuối dãy. Mọi phần tử == x đều đứng đúng vị trí.
Gọi m là vị trí x xuất hiện đầu tiên trong inside:
- Bắt đầu từ vị trí
msang phải, ta tìm các phần tử đứng đúng vị trí, gọi vị trí phải nhất đúng vị trí làr. - Bắt đầu từ vị trí
m-1sang trái, ta tìm các phần tử đứng đúng vị trí, gọi vị trí trái nhất đúng vị trí làl.
Ta lần lượt đưa các phần tử sai vị trí về đúng vị trí. Số bước di chuyển là số phần tử bị sai vị trí.
Số bước tối thiểu để xếp lại inside là giá trị nhỏ nhất của số bước thu được với mỗi giá trị x phân biệt trong inside.
Ví dụ: inside = [2, 5, 4, 3, 4, 4, 4, 5, 3, 6] –> freq_a = {2: 1, 3: 2, 4: 5, 5: 2, 6: 1}
Chọn phần tử x = 4 làm mốc –> vị trí x xuất hiện đầu tiên m = 3:
- Bắt đầu từ vị trí
msang phải, có[inside[3], inside[5], inside[6], inside[7], inside[8]] (== [4, 4, 4, 4, 5])đứng đúng vị trí. - Bắt đầu từ vị trí
m-1sang trái, không có phần tử nào đứng đúng vị trí.
–> Ta thu được 2 chốt: l = 3, r = 8.
- Đưa các giá trị
[inside[0], inside[4], inside[9]] (== [2, 3, 3])về đầu danh sách, mất 3 bước. - Đưa các giá trị
[inside[1], inside[10]] (== [5, 6])về cuối danh sách, mất 2 bước.
Tổng số bước xếp lại inside nếu chọn x = 4 làm mốc là 5.
Sau khi tính được số bước nhỏ nhất để xếp lại inside, ta cộng với số bước xếp left_side và right_side về đúng vị trí là được đáp số cuối cùng.
Bước tìm phần tử mốc x sao cho số lượng phần tử bị sai vị trí là ít nhất có thể cũng mất O(n). Do vậy ta cần lựa chọn 1 trong 2 giải pháp tối ưu:
- Chỉ đích danh phần tử mốc
x0, tính số phần tử bị sai vị trí trongO(n). - Vẫn kiểm tra từng phần tử mốc
x, tính số phần tử bị sai vị trí trongO(1)hoặcO(log n).
Ta sẽ thử xử lý giải pháp 2.
Gọi x_1, x_2,... x_m là các phần tử phân biệt của inside (x_1 < x_2 < ... < x_m).
Ta định nghĩa l_i là chỉ số xuất hiện đầu tiên, r_i là chỉ số xuất hiện cuối cùng của x_i trong inside.
Gọi count_correct_positions_left(x) đếm số lượng các phần tử x_j đứng đúng vị trí về bên trái của x (x_j < x),
count_correct_positions_right(x) đếm số lượng các phần tử x_j đứng đúng vị trí về bên phải của x (x <= x_j)
Trước hết, ta có 2 nhận xét sau:
- Số lượng vị trí chính xác về bên trái của
x_1luôn là0. - Số lượng vị trí chính xác về bên phải của
x_mluôn làfreq_a[x_m].
Xét x_i và x_(i+1) và 2 khoảng [l_i, r_i] và [l_(i+1), r_(i+1)]:
Số phần tử chính xác về bên phải của x_i có thể tính từ số phần tử chính xác về bên phải của x_(i+1):
- Nếu
r_i < l_(i+1):
# l_i r_i l_(i+1) r_(i+1)
# |-----| |---------|
count_correct_positions_right(x_i) = freq_a[x_i] + count_correct_positions_right(x_(i+1))
- Nếu
l_(i+1) < r_i < r_(i+1):
# l_(i+1) r_(i+1)
# |---------------|
# l_i r_i
# |--------------|
# l_(i+1) r_(i+1)
# |---------------|
# l_i r_i
# |-------|
count_correct_positions_right(x_i) = freq_a[x_i] + (số lượng chỉ số j của x_(i+1) mà r_i < j)
- Nếu
r_(i+1) < r_i:
# l_(i+1) r_(i+1) l_i r_i
# |---------| |-----|
# l_(i+1) r_(i+1)
# |---------------|
# l_i r_i
# |--------------|
# l_(i+1) r_(i+1)
# |--------|
# l_i r_i
# |---------------|
count_correct_positions_right(x_i) = freq_a[x_i]
Tương tự, số phần tử chính xác về bên trái của x_(i+1) có thể tính từ số phần tử chính xác về bên trái của x_i:
- Nếu
r_i < l_(i+1):
# l_i r_i l_(i+1) r_(i+1)
# |-----| |---------|
count_correct_positions_left(x_(i+1)) = count_correct_positions_left(x_i) + freq_a[x_i]
- Nếu
l_i < l_(i+1) < r_i:
# l_i r_i
# |--------------|
# l_(i+1) r_(i+1)
# |---------------|
# l_(i+1) r_(i+1)
# |--------|
# l_i r_i
# |---------------|
count_correct_positions_left(x_(i+1)) = count_correct_positions_left(x_i) + (số lượng chỉ số j của x_i mà j < l_(i+1))
- Nếu
l_(i+1) < l_i:
# l_(i+1) r_(i+1) l_i r_i
# |---------| |-----|
# l_(i+1) r_(i+1)
# |---------------|
# l_i r_i
# |--------------|
# l_(i+1) r_(i+1)
# |---------------|
# l_i r_i
# |-------|
count_correct_positions_left(x_(i+1)) = 0
Số phần tử chính xác khi lấy x làm gốc là count_correct_positions_left(x) + count_correct_positions_right(x).
Để xây dựng 2 mảng cnt_correct_pos_left[i] (== count_correct_positions_left(x_i)) và cnt_correct_pos_right[i] (== count_correct_positions_right(x_i)), ta khởi tạo cnt_correct_pos_left[1] và cnt_correct_pos_right[n], lặp 2 vòng ngược nhau để hoàn thiện 2 mảng này từ phần tử vừa tính trước đó.
Độ phức tạp
- Độ phức tạp không gian:
O(n) - Độ phức tạp thời gian:
O(n log n)do cần sắp xếp để tìm ra các phần tử phân biệt của mảnginside. Mảnginsidecó độ dài tối đa làn.
Mã nguồn
from collections import defaultdict
import bisect
def fix_array(a):
n = len(a)
freq_a = defaultdict(int)
for x in a:
freq_a[x] += 1
if all(a[i-1] <= a[i] for i in range(1, n)):
return 0
if all(a[i-1] >= a[i] for i in range(1, n)):
return n - max(freq_a.values())
left_side = []
right_side = []
inside = []
min_pivot, max_pivot = sorted([a[0], a[n-1]])
for x in a:
if x < min_pivot:
left_side.append(x)
elif x > max_pivot:
right_side.append(x)
else:
inside.append(x)
idx_list_dict = defaultdict(list)
for i in range(len(inside)):
idx_list_dict[inside[i]].append(i)
unique_inside = sorted(set(inside))
cnt_correct_pos_left = [0 for x in unique_inside]
cnt_correct_pos_right = [freq_a[x] for x in unique_inside]
for i in range(len(unique_inside)-2, -1, -1):
x = unique_inside[i]
next_x = unique_inside[i+1]
l_i, r_i = idx_list_dict[x][0], idx_list_dict[x][-1]
l_i1, r_i1 = idx_list_dict[next_x][0], idx_list_dict[next_x][-1]
if r_i < l_i1:
cnt_correct_pos_right[i] = freq_a[x] + cnt_correct_pos_right[i+1]
elif l_i1 < r_i < r_i1:
# cnt_correct_pos_right[i] = freq_a[x] + sum(1 for j in idx_list_dict[next_x] if r_i < j)
cnt_correct_pos_right[i] = freq_a[x] + len(idx_list_dict[next_x]) - bisect.bisect(idx_list_dict[next_x], r_i)
else:
cnt_correct_pos_right[i] = freq_a[x]
for i in range(len(unique_inside)-1):
x = unique_inside[i]
next_x = unique_inside[i+1]
l_i, r_i = idx_list_dict[x][0], idx_list_dict[x][-1]
l_i1, r_i1 = idx_list_dict[next_x][0], idx_list_dict[next_x][-1]
if r_i < l_i1:
cnt_correct_pos_left[i+1] = cnt_correct_pos_left[i] + freq_a[x]
elif l_i < l_i1 < r_i:
# cnt_correct_pos_left[i+1] = cnt_correct_pos_left[i] + sum(1 for j in idx_list_dict[x] if j < l_i1)
cnt_correct_pos_left[i+1] = cnt_correct_pos_left[i] + bisect.bisect(idx_list_dict[x], l_i1)
else:
cnt_correct_pos_left[i+1] = 0
# print(*zip(unique_inside, cnt_correct_pos_left, cnt_correct_pos_right))
min_cnt_incorrect_pos = min(
len(inside) - cnt_left - cnt_right
for cnt_left, cnt_right in zip(cnt_correct_pos_left, cnt_correct_pos_right)
)
# min_cnt_incorrect_pos = min(count_incorrect_positions(unique_idx) for unique_idx in range(len(unique_inside)))
return len(left_side) + min_cnt_incorrect_pos + len(right_side)
if __name__ == '__main__':
test_cases = [
[1, 3, 2, 4, 5],
[2, 1, 4, 6, 3, 5],
[5, 1, 3, 6, 4, 2],
[1, 5, 2],
[2, 1, 4, 3, 2],
[3, 2, 5, 2, 2, 1],
[2, 5, 4, 3, 4, 4, 4, 4, 3, 6],
[2, 5, 4, 3, 4, 4, 4, 5, 3, 6],
[2, 5, 4, 3, 4, 4, 3, 4, 5, 6],
]
for arr in test_cases:
print(arr, fix_array(arr))