Question

[Hồ Quang Dũng lyk76tin tink76]

J. Mảng tốt time limit per test1 second memory limit per test512 megabytes

Cho dãy a1,a2,a3,...,ana1,a2,a3,...,an thoả mãn ai≠ai+1ai≠ai+1. Hãy thực hiện các thao tác gán ai=vai=v sao cho v≠ai−1v≠ai−1 và v≠ai+1v≠ai+1, để mảng cuối cùng chỉ có hai giá trị khác nhau xuất hiện trên mảng.

Input

Dòng đầu tiên của dữ liệu vào chứa số nguyên tt (1≤t≤1051≤t≤105), là số lượng test. Mô tả của các test như sau:

• Dòng đầu tiên của mỗi test chứa một số nguyên dương nn (2≤n≤2⋅1052≤n≤2⋅105) là độ dài của mảng.
• Dòng thứ hai của mỗi test chứa nn số nguyên aiai (1≤ai≤n1≤ai≤n). Dữ liệu đảm bảo rằng ai≠ai+1ai≠ai+1 với 1≤i≤n−11≤i≤n−1.

Dữ liệu đảm bảo rằng tổng của nn trong tất cả các test không vượt quá 2⋅1052⋅105. Output

Với mỗi test, in ra một số nguyên duy nhất là số lượng phép biến đổi nhỏ nhất cần thực hiện.

Example Input Copy

2
5
3 4 1 3 4
2
2 1

Output Copy

3
0

Note

1. 25%25% số điểm có tổng nn trong tất cả các test không vượt quá 100100
2. 25%25% số điểm có tổng nn trong tất cả các test không vượt quá 500500
3. 25%25% số điểm có tổng nn trong tất cả các test không vượt quá 40004000
4. 25%25% số điểm không có ràng buộc gì thêm

Answer 1

[Gia Bao]

Đây là một bài toán khá thú vị liên quan đến việc biến đổi mảng sao cho sau cùng mảng chỉ còn đúng 2 giá trị khác nhau xuất hiện, đồng thời đảm bảo tính chất a[i] != a[i+1] luôn được giữ trong suốt quá trình biến đổi.

---

Đề bài tóm tắt

• Cho mảng a có n phần tử, thỏa mãn a[i] != a[i+1] với mọi i.
• Ta được phép thực hiện các thao tác: gán a[i] = v với điều kiện v != a[i-1] và v != a[i+1].
• Mục tiêu: biến đổi mảng sao cho mảng cuối cùng chỉ còn 2 giá trị khác nhau xuất hiện.
• Hỏi số thao tác gán nhỏ nhất cần thực hiện.

---

Phân tích

• Mảng ban đầu đã thỏa mãn a[i] != a[i+1], tức là các phần tử liên tiếp khác nhau.
• Mục tiêu là chỉ còn 2 giá trị khác nhau trong toàn mảng.
• Do a[i] != a[i+1] nên mảng có thể xem như xen kẽ các giá trị, ví dụ: x y x y x y ...
• Việc giữ a[i] != a[i+1] đồng nghĩa các giá trị ở vị trí chẵn và lẻ phải khác nhau.
• Tức là sau biến đổi, mảng có dạng: vị trí chẵn toàn giá trị A, vị trí lẻ toàn giá trị B (với A != B).

Ý tưởng:

• Ta muốn biến đổi sao cho vị trí chẵn chứa một giá trị (cố định), vị trí lẻ chứa một giá trị khác (cố định).
• Việc này tương đương với:
• • Chọn một giá trị val_even cho các vị trí chẵn,
  • Chọn một giá trị val_odd cho các vị trí lẻ,
  • Trong đó val_even != val_odd.
• Vì các vị trí chẵn và lẻ hiện tại chứa các giá trị khác nhau, ta sẽ chọn các giá trị tối ưu sao cho số lần biến đổi là nhỏ nhất.

---

Cách làm cụ thể

1. Đếm tần suất các giá trị xuất hiện ở vị trí chẵn (freq_even) và vị trí lẻ (freq_odd).
2. Lấy 2 giá trị có tần suất lớn nhất ở vị trí chẵn, và 2 giá trị có tần suất lớn nhất ở vị trí lẻ (để có phương án dự phòng).
3. Ta thử tất cả các tổ hợp (val_even, val_odd) trong 4 giá trị tìm được sao cho val_even != val_odd.
4. Với mỗi tổ hợp, tính số lần biến đổi cần thực hiện = (số vị trí chẵn - freq_even[val_even]) + (số vị trí lẻ - freq_odd[val_odd]).
5. Kết quả là giá trị nhỏ nhất trong các phương án trên.

---

Độ phức tạp

• Với tổng số phần tử trên tất cả test là 2*10^5, việc đếm tần suất và thử 4x4 tổ hợp rất nhanh.

---

Code tham khảo (Python)

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))

    freq_even = {}
    freq_odd = {}

    for i in range(n):
        if i % 2 == 0:
            freq_even[a[i]] = freq_even.get(a[i], 0) + 1
        else:
            freq_odd[a[i]] = freq_odd.get(a[i], 0) + 1

    # Lấy 2 giá trị tần suất cao nhất ở vị trí chẵn
    even_sorted = sorted(freq_even.items(), key=lambda x: x[1], reverse=True)
    even_sorted += [(None,0), (None,0)]  # đảm bảo có đủ phần tử
    even_top2 = even_sorted[:2]

    # Lấy 2 giá trị tần suất cao nhất ở vị trí lẻ
    odd_sorted = sorted(freq_odd.items(), key=lambda x: x[1], reverse=True)
    odd_sorted += [(None,0), (None,0)]
    odd_top2 = odd_sorted[:2]

    res = n  # max biến đổi = n

    for even_val, even_count in even_top2:
        for odd_val, odd_count in odd_top2:
            if even_val != odd_val:
                changes = ( (n+1)//2 - even_count ) + ( n//2 - odd_count )
                if changes < res:
                    res = changes

    print(res)

---

Giải thích ví dụ trong đề bài:

Input:

2
5
3 4 1 3 4
2
2 1

• Test 1:
• • Vị trí chẵn (0,2,4): 3,1,4
  • Vị trí lẻ (1,3): 4,3
  • freq_even: {3:1, 1:1, 4:1}
  • freq_odd: {4:1, 3:1}
  • Các tổ hợp thử: ví dụ (3,4), (3,3), (1,4), (1,3), (4,4), (4,3)...
  • Chọn (3,4): biến đổi = số vị trí chẵn - freq_even[3] + số vị trí lẻ - freq_odd[4] = 3 -1 + 2 -1 = 3
• Test 2:
• • Vị trí chẵn: 2 (1 vị trí)
  • Vị trí lẻ: 1 (1 vị trí)
  • Hai giá trị khác nhau nên mảng đã thỏa mãn, không cần biến đổi, output 0.

---

Bạn muốn mình giải thích chi tiết hơn hay giúp triển khai code trên theo ngôn ngữ khác không?