Minimum Incompatibility (LeetCode 1681)

Nguồn: LeetCode 1681 Độ khó: Khó (Hard) Quy hoạch động Bitmask Duyệt submask

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (đề gốc)

1681. Minimum Incompatibility – Độ chênh lệch nhỏ nhất (LeetCode, độ khó Hard)

Cho một mảng số nguyên nums và một số nguyên $k$. Bạn cần chia mảng này thành $k$ tập con có kích thước bằng nhau sao cho không có hai phần tử bằng nhau nào nằm trong cùng một tập con.

Độ chênh lệch (incompatibility) của một tập con là hiệu giữa phần tử lớn nhất và phần tử nhỏ nhất của tập đó.

Hãy trả về tổng độ chênh lệch nhỏ nhất có thể của $k$ tập con sau khi chia mảng một cách tối ưu, hoặc trả về -1 nếu không thể chia được.

Một tập con là một nhóm các số nguyên lấy từ mảng, không quan tâm thứ tự.

Ràng buộc:

• $1 \le k \le$ nums.length $\le 16$
• nums.length chia hết cho $k$
• $1 \le$ nums[i] $\le$ nums.length

Định dạng vào/ra để chạy thử trên máy: trên LeetCode các bạn chỉ cần viết hàm minimumIncompatibility trong class Solution. Để chạy như một chương trình bình thường (và dùng khung chạy tay bên dưới), mình đặt thêm định dạng:

• Dữ liệu vào: dòng đầu gồm 2 số nguyên $n$ (số phần tử) và $k$, dòng thứ hai gồm $n$ số nguyên nums[0], nums[1], ..., nums[n-1].
• Kết quả: một số nguyên là đáp án của bài.

Ví dụ 1

Input: nums = [1,2,1,4],
       k = 2
Output: 4
---stdin---
4 2
1 2 1 4

Cách chia tối ưu là [1,2] và [1,4]. Tổng độ chênh lệch là (2 − 1) + (4 − 1) = 4. Lưu ý chia [1,1] và [2,4] sẽ cho tổng nhỏ hơn, nhưng tập thứ nhất có 2 phần tử bằng nhau.

Ví dụ 2

Input: nums = [6,3,8,1,3,1,2,2],
       k = 4
Output: 6
---stdin---
8 4
6 3 8 1 3 1 2 2

Cách chia tối ưu là [1,2], [2,3], [6,8] và [1,3]. Tổng độ chênh lệch là (2 − 1) + (3 − 2) + (8 − 6) + (3 − 1) = 6.

Ví dụ 3

Input: nums = [5,3,3,6,3,3],
       k = 3
Output: -1
---stdin---
6 3
5 3 3 6 3 3

Không thể chia nums thành 3 tập con mà không có hai phần tử bằng nhau trong cùng một tập.

1681. Minimum Incompatibility (LeetCode, Hard)

You are given an integer array nums and an integer k. You are asked to distribute this array into k subsets of equal size such that there are no two equal elements in the same subset.

A subset's incompatibility is the difference between the maximum and minimum elements in that array.

Return the minimum possible sum of incompatibilities of the k subsets after distributing the array optimally, or return -1 if it is not possible.

A subset is a group integers that appear in the array with no particular order.

Example 1:

Input: nums = [1,2,1,4], k = 2
Output: 4
Explanation: The optimal distribution of subsets is [1,2] and [1,4].
The incompatibility is (2-1) + (4-1) = 4.
Note that [1,1] and [2,4] would result in a smaller sum, but the first subset contains 2 equal elements.

Example 2:

Input: nums = [6,3,8,1,3,1,2,2], k = 4
Output: 6
Explanation: The optimal distribution of subsets is [1,2], [2,3], [6,8], and [1,3].
The incompatibility is (2-1) + (3-2) + (8-6) + (3-1) = 6.

Example 3:

Input: nums = [5,3,3,6,3,3], k = 3
Output: -1
Explanation: It is impossible to distribute nums into 3 subsets where no two elements are equal in the same subset.

Constraints:

• 1 <= k <= nums.length <= 16
• nums.length is divisible by k
• 1 <= nums[i] <= nums.length

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lưu ý nhỏ: khi nộp trên CLUE OJ các bạn dán toàn bộ code, gồm cả hàm main, vì đề trên CLUE OJ đọc dữ liệu vào và in kết quả đúng theo định dạng ở phần đề bài, giống như khi các bạn chạy thử trên máy hoặc ở trang Chạy code online của blog.

Giải thích ví dụ 1 cho bạn nào chưa hiểu đề: nums = [1, 2, 1, 4], $k = 2$ ⇒ mỗi nhóm có $4 / 2 = 2$ phần tử. Có 3 cách chia thành 2 nhóm:

Cách chia	Hợp lệ?	Tổng độ chênh lệch
[1, 2] và [1, 4]	Có	1 + 3 = 4
[1, 1] và [2, 4]	Không (nhóm đầu có hai số 1)	–
[1, 4] và [2, 1]	Có	3 + 1 = 4

Nhỏ nhất là 4. Còn ví dụ 3 có tới bốn số 3 mà chỉ có 3 nhóm, kiểu gì cũng có một nhóm chứa hai số 3 ⇒ $-1$.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Quay lui chia từng phần tử vào nhóm · Python chậm khi n = 16Cách 2QHĐ bitmask + duyệt submask · O(3^n)

Cách 1Quay lui chia từng phần tử vào nhóm

Cách tự nhiên nhất: lần lượt đưa phần tử thứ $0, 1, \ldots, n - 1$ vào một trong $k$ nhóm, miễn là nhóm đó còn chỗ (chưa đủ $n / k$ phần tử) và chưa có số nào bằng nó. Chia xong hết thì tính tổng độ chênh lệch và cập nhật kết quả nhỏ nhất. Một mẹo nhỏ: các nhóm đang rỗng đều như nhau, nên chỉ cần thử đưa vào một nhóm rỗng là đủ (lệnh break trong code), tránh đếm lặp các cách chỉ khác nhau thứ tự nhóm.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int n, k, sz, best;
vector<int> a;
vector<vector<int>> group;

// đưa lần lượt từng phần tử vào một nhóm còn chỗ và chưa có số bằng nó
void backtrack(int i) {
    if (i == n) {
        int sum = 0;
        for (auto &g : group) sum += *max_element(g.begin(), g.end()) - *min_element(g.begin(), g.end());
        best = min(best, sum);
        return;
    }
    for (int j = 0; j < k; j++) {
        if ((int) group[j].size() == sz) continue;
        if (find(group[j].begin(), group[j].end(), a[i]) != group[j].end()) continue;
        group[j].push_back(a[i]);
        backtrack(i + 1);
        group[j].pop_back();
        if (group[j].empty()) break; // các nhóm rỗng như nhau, thử 1 nhóm là đủ
    }
}

int main() {
    cin >> n >> k;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sz = n / k;
    group.assign(k, vector<int>());
    best = INT_MAX;
    backtrack(0);
    cout << (best == INT_MAX ? -1 : best);
    return 0;
}

import sys


def main():
    data = sys.stdin.read().split()
    n, k = int(data[0]), int(data[1])
    a = list(map(int, data[2:2 + n]))
    sz = n // k
    group = [[] for _ in range(k)]
    best = float('inf')

    # đưa lần lượt từng phần tử vào một nhóm còn chỗ và chưa có số bằng nó
    def backtrack(i):
        nonlocal best
        if i == n:
            best = min(best, sum(max(g) - min(g) for g in group))
            return
        for j in range(k):
            if len(group[j]) == sz or a[i] in group[j]:
                continue
            group[j].append(a[i])
            backtrack(i + 1)
            group[j].pop()
            if not group[j]:
                break  # các nhóm rỗng như nhau, thử 1 nhóm là đủ

    backtrack(0)
    print(-1 if best == float('inf') else best)


if __name__ == "__main__":
    main()

Số trạng thái tăng rất nhanh

Nhờ mẹo "chỉ thử một nhóm rỗng", số cách chia mà quay lui phải đi qua đúng bằng số cách chia thật sự: với $n = 16$, $k = 2$ có $\frac{1}{2}\binom{16}{8} = 6435$ cách, $k = 4$ có $\frac{16!}{(4!)^4 \cdot 4!} \approx 2.6$ triệu cách, $k = 8$ khoảng $2$ triệu cách. Mình đo thử: C++ chỉ mất khoảng 0.13 giây (vì $n \le 16$ nên vẫn chạy được), nhưng Python mất khoảng 6 giây với $n = 16, k = 4$. Hơn nữa nếu không có mẹo chặn nhóm rỗng thì số trạng thái còn nhân thêm $k!$ lần. Vì vậy mình vẫn trình bày cách QHĐ bitmask ở dưới – đây mới là lời giải chuẩn, chạy ổn định cho mọi ngôn ngữ.

Cách 2Quy hoạch động bitmask + duyệt submask – O(3^n)

Phương pháp giải: Quy hoạch động + bitmask.

Để ý ta thấy $n \le 16$ – rất nhỏ, đây là dấu hiệu của bitmask. Đề yêu cầu chia thành $k$ tập hợp có số lượng bằng nhau, vậy mỗi tập hợp có số lượng phần tử là $sz = n / k$.

Ta biểu diễn một tập các phần tử bằng một dãy bit mask: bit $b$ bằng 1 nghĩa là phần tử thứ $b$ được chọn, bit $b$ bằng 0 trong trường hợp ngược lại.

Bước 1 – tính cost[mask]

Duyệt toàn bộ các mask. Nếu số lượng phần tử trong mask đúng bằng $sz$, ta kiểm tra các phần tử được chọn có đôi một khác nhau hay không. Nếu có, gán cost[mask] = giá trị phần tử lớn nhất − giá trị phần tử nhỏ nhất. Các mask còn lại có cost = vô cực (không được làm một nhóm).

Bước 2 – quy hoạch động

Gọi f[mask] là tổng chênh lệch nhỏ nhất khi các phần tử đã được chia nhóm chính là tập mask.

• Bài toán cơ sở: f[0] = 0, các f[mask] còn lại bằng dương vô cực.
• Công thức: duyệt mọi submask (tập con) của mask; nếu quyết định đưa các phần tử trong submask vào cùng một nhóm thì:
  f[mask] = min(f[mask], f[mask − submask] + cost[submask])
• Đáp án: f[(1 << n) − 1] (nếu vẫn là vô cực thì in $-1$).

Vì sao mask − submask lại đúng là "phần còn lại"? Vì submask là tập con của mask nên các bit 1 của nó đều nằm trong mask, phép trừ chính là xóa các bit đó đi (giống mask ^ submask). Và mask − submask < mask nên khi duyệt mask tăng dần, f[mask − submask] luôn đã được tính xong.

Duyệt mọi submask của mask

Vòng lặp for (submask = mask; submask > 0; submask = (submask - 1) & mask) đi qua đúng tất cả các tập con khác rỗng của mask, theo thứ tự giảm dần. Phép - 1 tắt bit 1 thấp nhất và bật hết các bit thấp hơn, còn & mask giữ lại đúng những bit thuộc mask. Ví dụ mask = 1011: 1011 → 1010 → 1001 → 1000 → 0011 → 0010 → 0001.

Các bạn nhập dãy và $k$ rồi bấm Tiếp để xem từng f[mask] được tính (ô xanh lá là nhóm submask tốt nhất, ô xanh dương là phần mask − submask đã tính trước đó):

nums k

Ví dụ nhanh:

Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên, anh em có thể tham khảo nhé:

#include <bits/stdc++.h>
using namespace std;

const int inf = 10000005;
int dp[(1 << 16) + 5];
int cost[(1 << 16) + 5];
class Solution {
public:
    int minimumIncompatibility(vector<int>& a, int k) {
        int n = (int) a.size();
        for (int mask = 0; mask < (1 << n); mask++) {
            dp[mask] = inf;
            cost[mask] = inf;
        }
        int sz = n / k;
        for (int mask = 1; mask < (1 << n); mask++) {
            if ((int) __builtin_popcount(mask) == sz) {
                int maxi = -1;
                int mini = inf;
                vector<int> tmp;
                for (int i = 0; i < n; i++) {
                    if ((mask & (1 << i)) > 0) {
                        tmp.push_back(a[i]);
                        maxi = max(maxi, a[i]);
                        mini = min(mini, a[i]);
                    }
                }
                sort(tmp.begin(), tmp.end());
                bool check = true;
                for (int i = 0; i < (int) tmp.size() - 1; i++) {
                    if (tmp[i] == tmp[i + 1]) {
                        check = false;
                        break;
                    }
                }
                if (check == false) {
                    continue;
                }
                cost[mask] = maxi - mini;
            }
        }
        dp[0] = 0;
        for (int mask = 1; mask < (1 << n); mask++) {
            for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
                dp[mask] = min(dp[mask], dp[mask - submask] + cost[submask]);
            }
        }
        return (dp[(1 << n) - 1] == inf ? -1 : dp[(1 << n) - 1]);
    }
};

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    Solution sol;
    cout << sol.minimumIncompatibility(a, k);
    return 0;
}

import sys
from typing import List

INF = 10000005


class Solution:
    def minimumIncompatibility(self, a: List[int], k: int) -> int:
        n = len(a)
        full = (1 << n) - 1
        sz = n // k
        # cost[mask] cho các tập đúng sz phần tử, đôi một khác nhau
        cost = {}
        for mask in range(1, full + 1):
            if bin(mask).count("1") != sz:
                continue
            vals = [a[i] for i in range(n) if mask >> i & 1]
            if len(set(vals)) == sz:
                cost[mask] = max(vals) - min(vals)
        # nhóm theo bit thấp nhất để chỉ thử các nhóm chứa phần tử
        # chưa được chọn có chỉ số nhỏ nhất (tránh đếm lặp thứ tự các nhóm)
        by_low = [[] for _ in range(n)]
        for mask, c in cost.items():
            low = (mask & -mask).bit_length() - 1
            by_low[low].append((mask, c))
        dp = [INF] * (full + 1)
        dp[0] = 0
        for mask in range(full + 1):
            cur = dp[mask]
            if cur == INF or mask == full:
                continue
            free = full ^ mask
            low = (free & -free).bit_length() - 1
            for sub, c in by_low[low]:
                if sub & mask == 0 and cur + c < dp[mask | sub]:
                    dp[mask | sub] = cur + c
        return -1 if dp[full] == INF else dp[full]


def main():
    data = sys.stdin.read().split()
    n, k = int(data[0]), int(data[1])
    a = list(map(int, data[2:2 + n]))
    print(Solution().minimumIncompatibility(a, k))


if __name__ == "__main__":
    main()

Giải thích một số chỗ trong code:

1. __builtin_popcount(mask) đếm số bit 1 của mask, tức số phần tử trong tập.
2. Để kiểm tra các phần tử đôi một khác nhau, mình gom chúng vào tmp, sắp xếp rồi so từng cặp kề nhau.
3. inf = 10000005: dp[mask - submask] + cost[submask] lớn nhất là $2 \cdot 10^7$, vẫn nằm trong int.
4. Bản Python: $3^{16} \approx 4.3 \cdot 10^7$ bước là quá chậm với Python, nên mình cắt tỉa: chỉ đi "tiến" từ những f[mask] đã có giá trị, và nhóm tiếp theo bắt buộc phải chứa phần tử chưa chia có chỉ số nhỏ nhất (thứ tự các nhóm không quan trọng nên ép như vậy không mất nghiệm). Mỗi nhóm hợp lệ được tính sẵn cost và xếp theo bit thấp nhất. Kết quả vẫn y hệt bản C++.

Khung chạy tay (để dễ theo dõi, giới hạn $n \le 6$; ví dụ 2 có $n = 8$ cần quá nhiều bước nên không đưa vào):

C++▶ Chạy tay từng dòng codeCách 2: tính cost[mask] cho các nhóm hợp lệ, rồi dp[mask] = min(dp[mask - submask] + cost[submask]) với mọi submask.

Dữ liệu vào (stdin) – sửa thoải mái4 2 1 2 1 4

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4const int inf = 10000005;

5int dp[(1 << 16) + 5];

6int cost[(1 << 16) + 5];

7class Solution {

8public:

9 int minimumIncompatibility(vector<int>& a, int k) {

10 int n = (int) a.size();

11 for (int mask = 0; mask < (1 << n); mask++) {

12 dp[mask] = inf;

13 cost[mask] = inf;

14 }

15 int sz = n / k;

16 for (int mask = 1; mask < (1 << n); mask++) {

17 if ((int) __builtin_popcount(mask) == sz) {

18 int maxi = -1;

19 int mini = inf;

20 vector<int> tmp;

21 for (int i = 0; i < n; i++) {

22 if ((mask & (1 << i)) > 0) {

23 tmp.push_back(a[i]);

24 maxi = max(maxi, a[i]);

25 mini = min(mini, a[i]);

26 }

27 }

28 sort(tmp.begin(), tmp.end());

29 bool check = true;

30 for (int i = 0; i < (int) tmp.size() - 1; i++) {

31 if (tmp[i] == tmp[i + 1]) {

32 check = false;

33 break;

34 }

35 }

36 if (check == false) {

37 continue;

38 }

39 cost[mask] = maxi - mini;

40 }

41 }

42 dp[0] = 0;

43 for (int mask = 1; mask < (1 << n); mask++) {

44 for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {

45 dp[mask] = min(dp[mask], dp[mask - submask] + cost[submask]);

46 }

47 }

48 return (dp[(1 << n) - 1] == inf ? -1 : dp[(1 << n) - 1]);

49 }

50};

51

52int main() {

53 int n, k;

54 cin >> n >> k;

55 vector<int> a(n);

56 for (int i = 0; i < n; i++) cin >> a[i];

57 Solution sol;

58 cout << sol.minimumIncompatibility(a, k);

59 return 0;

60}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: hai mảng dp và cost có $2^n$ phần tử – $O(2^n)$.
• Thời gian: bước tính cost tốn $O(2^n \cdot n)$. Bước QHĐ: mỗi phần tử, đối với cặp (mask, submask), có 3 trạng thái: không thuộc mask, thuộc mask nhưng không thuộc submask, thuộc submask ⇒ tổng số cặp là $3^n$. Với $n = 16$ là khoảng $4.3 \cdot 10^7$ – chạy tốt trong C++.

Không gian$O(2^n)$

Thời gian$O(3^n)$

Ghi chú của mình: Code C++ và Python của cả 2 cách đã được kiểm tra với 3 ví dụ của đề (đều đúng) và 400 bộ test ngẫu nhiên ($n \le 10$, mọi $k$ là ước của $n$, có cả các test đáp án $-1$), so với code quay lui Cách 1 – khớp hết. Với $n = 16$, Cách 1 C++ khoảng 0.13 giây, Python khoảng 6 giây (k = 4); Cách 2 C++ chạy khoảng 0.06 giây với mọi $k$; bản Python cắt tỉa chạy dưới 0.1 giây với hầu hết các test, chậm nhất khoảng 0.85 giây khi $k = 2$ và 16 số đôi một khác nhau.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇