Factory Machines (CSES 1620)

Nguồn: CSES Problem Set – 1620 Độ khó: Trung bình Tìm kiếm nhị phân Chặt nhị phân đáp án Nhận xét

Đề bài

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

CSES 1620 – Factory Machines (Các máy trong nhà máy)

Một nhà máy có $n$ cái máy có thể dùng để làm ra sản phẩm. Mục tiêu của bạn là làm ra tổng cộng $t$ sản phẩm.

Với mỗi máy, bạn biết số giây mà máy đó cần để làm ra một sản phẩm. Các máy có thể hoạt động đồng thời, và bạn được tự do sắp xếp lịch làm việc của chúng.

Hỏi thời gian ngắn nhất cần để làm ra $t$ sản phẩm là bao nhiêu?

Dữ liệu vào:

• Dòng đầu tiên gồm hai số nguyên $n$ và $t$: số lượng máy và số lượng sản phẩm.
• Dòng tiếp theo gồm $n$ số nguyên $k_1, k_2, \ldots, k_n$: thời gian để làm ra một sản phẩm của từng máy.

Kết quả: In ra một số nguyên: thời gian ít nhất cần để làm ra $t$ sản phẩm.

Ràng buộc:

• $1 \le n \le 2 \cdot 10^5$
• $1 \le t \le 10^9$
• $1 \le k_i \le 10^9$

Giới hạn: thời gian 1 giây, bộ nhớ 512 MB.

Giải thích ví dụ: máy 1 làm 2 sản phẩm, máy 2 làm 4 sản phẩm và máy 3 làm 1 sản phẩm.

CSES 1620 – Factory Machines

Time limit: 1.00 s. Memory limit: 512 MB.

A factory has $n$ machines which can be used to make products. Your goal is to make a total of $t$ products.

For each machine, you know the number of seconds it needs to make a single product. The machines can work simultaneously, and you can freely decide their schedule.

What is the shortest time needed to make $t$ products?

Input

The first input line has two integers $n$ and $t$: the number of machines and products.

The next line has $n$ integers $k_1, k_2, \ldots, k_n$: the time needed to make a product using each machine.

Output

Print one integer: the minimum time needed to make $t$ products.

Constraints

• $1 \le n \le 2 \cdot 10^5$
• $1 \le t \le 10^9$
• $1 \le k_i \le 10^9$

Explanation: Machine 1 makes two products, machine 2 makes four products and machine 3 makes one product.

Ví dụ – input

3 7
3 2 5

Ví dụ – output

8

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

Nhắc lại ngưỡng TLE

Với các hệ thống chấm giới hạn 1 giây, tối đa toàn bài chỉ nên lặp khoảng $(3 \div 5) \cdot 10^7$ lần là an toàn, tệ nhất là $10^8$ (lúc này thì hên xui nhé). Ngưỡng này là cho C/C++; Python, C#, Java chạy chậm hơn nên ngưỡng phải thấp hơn. Đề cho 2 giây thì nhân 2 ngưỡng, 100 ms thì chia 10, cứ thế thôi. Bài này giới hạn 1 giây.

Đề gốc là tiếng Anh nhưng ngắn gọn, ở trên mình đã dịch sang tiếng Việt. Mình giải thích lại cho bạn nào chưa hiểu: nhà máy có $N$ cái máy, mỗi máy cần một số giây cố định để làm ra 1 sản phẩm, các máy hoạt động độc lập với nhau. Cần làm ra $T$ sản phẩm thì hãy phân bổ công việc cho từng máy sao cho thời gian hoàn thành đủ $T$ sản phẩm là ít nhất. Ta không cần in ra cách phân bổ, chỉ cần in con số thời gian ít nhất đó.

Ví dụ của đề: $N = 3$ máy với thời gian $\{3, 2, 5\}$, cần $T = 7$ sản phẩm, đáp án 8 giây. Cụ thể:

• Máy 1 làm 2 sản phẩm ⇒ xong trong $3 \cdot 2 = 6$ giây.
• Máy 2 làm 4 sản phẩm ⇒ xong trong $2 \cdot 4 = 8$ giây.
• Máy 3 làm 1 sản phẩm ⇒ xong trong $5 \cdot 1 = 5$ giây.

Tổng cộng $2 + 4 + 1 = 7$ sản phẩm. Cho 3 máy chạy cùng lúc thì máy 3 xong đầu tiên ở giây 5, máy 1 xong ở giây 6, cuối cùng máy 2 xong ở giây 8. Căn cứ theo máy xong sau cùng thì 8 giây là thời gian nhanh nhất để làm ra 7 sản phẩm.

Các bạn chú ý giới hạn: $N \le 2 \cdot 10^5$, $T \le 10^9$, $k_i \le 10^9$. Với $N = 2 \cdot 10^5$ thì muốn chạy trong 1 giây toàn bài phải cỡ $O(N \log N)$ trở xuống; còn $O(N^2) = 4 \cdot 10^{10}$ là chắc chắn TLE. Nhìn giới hạn mà ước tính độ phức tạp cần có, từ đó định hình ra cách giải, đó là thói quen tốt các bạn nên tập.

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

Cách 1Liệt kê mọi thời điểm rồi sắp xếp · chỉ chạy được test nhỏCách 2Tìm kiếm nhị phân theo thời gian · O(N·log(T·Min))

Cách 1Liệt kê thời điểm làm xong từng sản phẩm rồi sắp xếp

Cách đơn giản nhất mà mình nghĩ nhiều bạn sẽ nhìn ra: tính ra thời điểm làm xong từng sản phẩm của mỗi máy, trộn tất cả vào một mảng a rồi sắp xếp tăng dần. Muốn biết thời điểm sớm nhất có đủ $T$ sản phẩm thì đó chính là a[T - 1]. Với ví dụ của đề:

• Máy 1 (3 giây/sản phẩm): các thời điểm $3, 6, 9, 12, 15, 18, 21, \ldots$
• Máy 2 (2 giây/sản phẩm): các thời điểm $2, 4, 6, 8, 10, 12, 14, \ldots$
• Máy 3 (5 giây/sản phẩm): các thời điểm $5, 10, 15, 20, 25, 30, 35, \ldots$

Trộn lại và sắp tăng dần (mỗi máy lấy $T = 7$ thời điểm), sản phẩm thứ 7 được tô xanh:

2345668910101212141515182021253035

Tính index từ 0 thì từ a[0] đến a[T - 1] là đủ $T$ giá trị (mỗi giá trị ứng với 1 sản phẩm), nên a[T - 1] chính là thời điểm có đủ $T$ sản phẩm. Với $T = 7$: a[6] = 8 là đáp án.

Vì sao mỗi máy phải lấy đủ T thời điểm?

Ta không biết trước mỗi máy sẽ góp bao nhiêu sản phẩm vào $T$ sản phẩm sớm nhất; lỡ lấy thiếu thì khi trộn lại sẽ sai. Chắc ăn nhất là mỗi máy lấy đủ $T$ thời điểm (một máy cùng lắm cũng chỉ làm hết $T$ sản phẩm thôi).

Cách này rất dễ nhìn ra tư tưởng và cũng dễ cài đặt. Nhưng với giới hạn của đề thì không ổn: mảng phải chứa $T \cdot N$ phần tử. Trường hợp xấu nhất $T = 10^9$, $N = 2 \cdot 10^5$ thì $T \cdot N = 2 \cdot 10^{14}$ phần tử; mỗi phần tử chỉ 4 byte thôi cũng đã cần khoảng 745 GB bộ nhớ, trong khi đề cho có 512 MB. Còn giả sử bằng một cách thần thánh nào đó tạo được mảng như vậy, thì riêng bước sắp xếp $O(M \log M)$ với $M = 2 \cdot 10^{14}$ đã cần cỡ $90 \cdot 10^{14}$ phép tính; máy xử lý $10^8$ phép tính mỗi giây thì phải chạy… gần 3 năm 😅.

Tuy vậy, nếu chưa nghĩ ra cách tối ưu thì mình khuyên các bạn cứ cài theo hướng đơn giản này trước: tuy chạy lâu nhưng rất dễ cài và luôn cho kết quả chính xác, nhờ đó ta dùng nó làm code vét cạn để kiểm tra cách tối ưu về sau. Mình code nhanh cho các bạn tham khảo:

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, t;
    cin >> n >> t;
    vector<long long> a;
    while(n--){
        int x;
        cin >> x;
        for(int i = 1; i <= t; ++i){
            a.push_back(1LL * i * x);
        }
    }
    sort(a.begin(), a.end());
    cout << a[t - 1];
    return 0;
}

n, t = map(int, input().split())
k = list(map(int, input().split()))
a = []
for x in k:
    for i in range(1, t + 1):
        a.append(i * x)
a.sort()
print(a[t - 1])

Giải thích một số chỗ trong code ở trên:

1. 3 dòng đầu hàm main (ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);) giúp đẩy nhanh tốc độ nhập xuất với C++. Bài này input có thể lên tới $2 \cdot 10^5$ số nên thêm 3 dòng này vào cho chương trình chạy nhanh hơn.
2. Mình dùng vector là mảng động rất tiện: không cần biết trước kích thước, cần phần tử nào thì push_back vào.
3. Chỗ 1LL * i * x: $i$ và $x$ đều là int, tích của chúng có thể vượt $2^{31}$ (ví dụ $x = 10^9$, $i = 3$) nên mình nhân với 1LL trước để phép nhân thực hiện trên long long, tránh tràn số.

Không gian$O(N \cdot T)$

Thời gian$O(NT \log(NT))$

Chỉ dùng để kiểm tra

Cách này chỉ chạy được với $N \cdot T$ nhỏ (vài triệu trở xuống). Nộp lên CSES sẽ bị tràn bộ nhớ / TLE ngay ở những test lớn đầu tiên.

Cách 2Tìm kiếm nhị phân theo thời gian – O(N·log(T·Min))

Cách làm tốt hơn thực ra vẫn dựa trên tư tưởng của cách 1 nhưng cách tiếp cận vấn đề sẽ khác. Mình chỉ hỏi một câu thôi, bạn nào muốn tự làm thì đọc câu này xong rồi nếu đã lóe lên tư tưởng thì đừng đọc tiếp nữa mà tự làm tiếp hen:

Câu hỏi mấu chốt

Tới giây thứ $X$ thì tất cả các máy làm ra được tối đa bao nhiêu sản phẩm?

Câu trả lời là tính được dễ dàng: máy có thời gian $k_i$ thì tới giây $X$ làm được $\left\lfloor X / k_i \right\rfloor$ sản phẩm (chỉ lấy phần nguyên). Với ví dụ $\{3, 2, 5\}$:

• $X = 5$: $5/3 + 5/2 + 5/5 = 1 + 2 + 1 = 4$ sản phẩm.
• $X = 10$: $10/3 + 10/2 + 10/5 = 3 + 5 + 2 = 10$ sản phẩm.

Đây là mấu chốt để giải bài này: $X$ càng lớn thì tổng số sản phẩm $S(X) = \sum \left\lfloor X / k_i \right\rfloor$ càng lớn (hoặc giữ nguyên), $X$ nhỏ thì $S(X)$ nhỏ. Nó tăng dần theo $X$. Và đáp án chính là giây $X$ nhỏ nhất mà $S(X) \ge T$. Hàm tăng dần + tìm giá trị nhỏ nhất thỏa điều kiện ⇒ áp dụng tìm kiếm nhị phân (Binary Search) được ngay! Bạn nào chưa biết tìm kiếm nhị phân thì phải tìm hiểu trước rồi mới xem tiếp phần này mới hiểu được nhé.

Đoạn tìm kiếm [Left, Right]

• Tối thiểu cũng phải là 1 giây ⇒ Left = 1.
• Tối đa: giao hết $T$ sản phẩm cho máy nhanh nhất là chắc chắn xong ⇒ Right = Min · T, với Min là thời gian nhỏ nhất trong các máy. Ví dụ đề: Min = 2 nên Right = $2 \cdot 7 = 14$.

Chạy tay với ví dụ của đề ($T = 7$):

L	R	Mid	S(Mid) = Mid/3 + Mid/2 + Mid/5	So với T = 7	Cập nhật
1	14	7	2 + 3 + 1 = 6	6 < 7, thiếu	L = Mid + 1 = 8
8	14	11	3 + 5 + 2 = 10	10 ≥ 7, đủ	R = Mid − 1 = 10
8	10	9	3 + 4 + 1 = 8	8 ≥ 7, đủ	R = Mid − 1 = 8
8	8	8	2 + 4 + 1 = 7	7 ≥ 7, đủ	R = Mid − 1 = 7
8	7	L > R ⇒ dừng, đáp án L = 8

Đến đây các bạn đã nhìn ra bản chất của bài rồi chứ? Nó chỉ là tìm kiếm nhị phân thôi hehe, nhưng quan trọng là phải nhìn ra được mấu chốt vấn đề.

Lấy kết quả theo L chứ không theo R

Thử với input 3 5 / 3 2 5 (cần $T = 5$). Danh sách thời điểm ở cách 1 là $2, 3, 4, 5, 6, 6, \ldots$ nên đáp án là 6 (sản phẩm thứ 5 và thứ 6 cùng xong ở giây 6). Chạy tay:

• L = 1, R = 10 ⇒ Mid = 5: $1 + 2 + 1 = 4 \lt 5$ ⇒ L = 6.
• L = 6, R = 10 ⇒ Mid = 8: $2 + 4 + 1 = 7 \ge 5$ ⇒ R = 7.
• L = 6, R = 7 ⇒ Mid = 6: $2 + 3 + 1 = 6 \ge 5$ ⇒ R = 5.
• L = 6 > R = 5 ⇒ dừng.

Điều kiện lặp là L <= R (đoạn $[L, R]$ chỉ hợp lệ khi $L \le R$). Vì khi số sản phẩm $\ge T$ ta cập nhật R = Mid - 1, nên lúc dừng lại kết quả phải lấy theo L; lấy theo R sẽ sai vì R đã bị trừ đi 1 ở lần cuối cùng (ở trên R = 5 trong khi đáp án là 6). Chỗ này các bạn chạy tay thêm vài ví dụ là hiểu rõ ý mình liền.

Minh hoạ tìm kiếm nhị phân trên trục thời gian

Mỗi hàng là một máy, mỗi chấm là thời điểm máy đó làm xong 1 sản phẩm. Vạch cam là Mid; các chấm nằm bên trái vạch (tô đậm) là số sản phẩm làm được tới giây Mid. Vùng xanh nhạt là đoạn $[L, R]$ còn đang tìm. Em nhập dữ liệu rồi bấm Tiếp:

T (số sản phẩm) Thời gian các máy

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo toàn bộ những gì mình phân tích ở trên:

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, t;
    cin >> n >> t;
    long long a[n], Min = 1000000005;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        Min = min(Min, a[i]);
    }
    long long l = 1, r = t * Min, m;
    while(l <= r){
        m = (l + r) / 2;
        long long s = 0;
        for(int i = 0; i < n; ++i){
            s += m / a[i];
        }
        if(s >= t){
            r = m - 1;
        }
        else{
            l = m + 1;
        }
    }
    cout << l;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, t = int(data[0]), int(data[1])
    a = list(map(int, data[2:2 + n]))
    Min = min(a)
    l, r = 1, t * Min
    while l <= r:
        m = (l + r) // 2
        s = sum(map(m.__floordiv__, a))  # tổng số sản phẩm làm được tới giây m
        if s >= t:
            r = m - 1
        else:
            l = m + 1
    print(l)

main()

Giải thích một số chỗ trong code ở trên:

1. Khởi tạo Min = 1000000005 (1 tỷ lẻ 5) để chắc chắn nó lớn hơn mọi thời gian trong đề (tối đa $10^9$), nhờ vậy lần so sánh đầu tiên chắc chắn cập nhật được Min.
2. Biến s lưu tổng số sản phẩm tối đa làm được tới giây m; để tốt nhất dùng long long tránh tràn số. Toàn bài để chắc ăn mình dùng hết long long luôn vì cũng không tốn thêm bao nhiêu bộ nhớ: $R = T \cdot Min$ có thể lên tới $10^{18}$.
3. Bản Python: sum(map(m.__floordiv__, a)) chính là $\sum m // a_i$, viết kiểu này chạy nhanh hơn vòng for thường khá nhiều.

Yên tâm s không bị tràn

Vì $m \le R = T \cdot Min$ nên mỗi số hạng $m / a_i \le T \cdot Min / a_i \le T \le 10^9$; cộng $N \le 2 \cdot 10^5$ số hạng thì $s \le 2 \cdot 10^{14}$, nằm gọn trong long long.

C++▶ Chạy tay từng dòng codeTìm kiếm nhị phân giây m nhỏ nhất mà tổng m / a[i] ≥ t, in ra l.

Dữ liệu vào (stdin) – sửa thoải mái3 7 3 2 5

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 cout.tie(0);

8 long long n, t;

9 cin >> n >> t;

10 long long a[n], Min = 1000000005;

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

12 cin >> a[i];

13 Min = min(Min, a[i]);

14 }

15 long long l = 1, r = t * Min, m;

16 while(l <= r){

17 m = (l + r) / 2;

18 long long s = 0;

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

20 s += m / a[i];

21 }

22 if(s >= t){

23 r = m - 1;

24 }

25 else{

26 l = m + 1;

27 }

28 }

29 cout << l;

30 return 0;

31}

ChậmVừaNhanhRất nhanh

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

• Không gian: $O(N)$ để lưu mảng a thời gian của các máy.
• Thời gian: $O(N)$ đọc dữ liệu + tìm kiếm nhị phân trên đoạn $[1, T \cdot Min]$ mất $O(\log(T \cdot Min))$ lần (tối đa khoảng 60 lần vì $T \cdot Min \le 10^{18}$), mỗi lần duyệt $O(N)$ để tính tổng sản phẩm. Theo quy tắc cộng BigO lấy thành phần lớn nhất ⇒ $O(N \cdot \log(T \cdot Min))$, cỡ $2 \cdot 10^5 \cdot 60 = 1{,}2 \cdot 10^7$ phép tính, yên tâm không bị TLE.

Không gian$O(N)$

Thời gian$O(N \log(T \cdot Min))$

Các bạn đã thấy giải thuật hay chưa? Cùng giải quyết một vấn đề nhưng một cách thì chạy mất gần 3 năm, còn một cách chỉ chạy mất chưa tới 0,1 giây, chớp mắt cái là ra kết quả luôn. Thế mới thấy hay đúng không các bạn 😁

Lưu ý khi nộp Python

Bản Python dù đã viết gọn vẫn phải làm khoảng $1{,}2 \cdot 10^7$ phép chia, trên máy mình mất khoảng 1,3–1,6 giây với test lớn nhất, nên có thể bị TLE trên CSES (giới hạn 1 giây). Bạn nào nộp thì nên ưu tiên C++ nhé.

Ghi chú của mình: code C++ và Python của cả 2 cách đều cho đúng output ví dụ của đề, và đã được so với một chương trình vét cạn (tăng dần từng giây $X$ cho tới khi $\sum X / k_i \ge T$) trên 500 bộ test ngẫu nhiên nhỏ – khớp hết. Với test lớn nhất ($N = 2 \cdot 10^5$, $T = 10^9$, $k_i$ tới $10^9$) trên máy mình: C++ cách 2 chạy khoảng 0,08–0,18 giây; Python cách 2 khoảng 1,3–1,6 giây.

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 😇