Bảng Nhân

Nguồn: Codeforces Group Độ khó: Trung bình Tìm kiếm nhị phân Chặt nhị phân đáp án

Đề bài

Cho một ma trận các số nguyên gồm $n$ dòng $m$ cột. Các dòng được đánh số từ $1$ đến $n$ từ trên xuống dưới. Các cột được đánh số từ $1$ đến $m$ từ trái qua phải. Giá trị của số nguyên tại dòng $i$ cột $j$ là phép nhân $i \times j$. Lấy tất cả các số trong ma trận và sắp xếp tăng dần. Hãy tìm số nguyên thứ $k$ trong dãy đã sắp xếp.

Dữ liệu nhập:

• Là ba số nguyên $n$, $m$, $k$ cách nhau một khoảng trắng $(1 \le n, m \le 10^5;\ 1 \le k \le n \times m)$.

Dữ liệu xuất:

• Là số nguyên thứ $k$ sau khi sắp xếp các số trong ma trận.

Subtask:

• 50% số test đầu tiên có $1 \le n, m \le 1000$.
• 50% số test còn lại không có giới hạn gì thêm.

Ví dụ 1 – input

2 3 4

Ví dụ 1 – output

3

Ví dụ 2 – input

3 4 6

Ví dụ 2 – output

4

Giải thích test 1: ma trận là

1	2	3
2	4	6

Các số sau khi sắp xếp: 1 2 2 3 4 6 ⇒ số thứ 4 là 3.

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 😇. Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé, các bạn nào 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:

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ộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Vét cạn + sortÝ tưởngChặt nhị phânMấu chốtĐếm O(1)/dòngCách 2AC O(N log NM)

Cách 1Vét cạn: đưa hết vào mảng rồi sắp xếp – Subtask 1

Cách làm vét cạn của bài này thì chắc em nhìn vào cũng thấy đó là duyệt qua toàn bộ các vị trí trong ma trận, với mỗi vị trí $i, j$ tính tích $i \times j$ sau đó đưa kết quả lưu vào cái mảng 1 chiều a. Cứ thế lưu hết tất cả các tích vị trí $i \times j$ trong ma trận lại rồi thì sắp xếp mảng 1 chiều đó tăng dần và kết quả giá trị tích thứ $k$ sẽ là a[k].

Source code theo cách làm đó sẽ như sau:

#include <bits/stdc++.h>
using namespace std;
long long solve1(long long n, long long m, long long k){
    vector<long long> a;
    a.push_back(0);
    for(long long i = 1; i <= n; ++i){
        for(long long j = 1; j <= m; ++j){
            a.push_back(i * j);
        }
    }
    sort(a.begin(), a.end());
    return a[k];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long n, m, k;
    cin >> n >> m >> k;
    cout << solve1(n, m, k);
    return 0;
}

def solve1(n, m, k):
    a = [0]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            a.append(i * j)
    a.sort()
    return a[k]

n, m, k = map(int, input().split())
print(solve1(n, m, k))

C++▶ Chạy tay từng dòng codeCách 1 (vét cạn): đưa mọi tích i·j vào vector, sort rồi lấy a[k], O(NM log NM).

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

Dữ liệu mẫu:

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

2using namespace std;

3long long solve1(long long n, long long m, long long k){

4 vector<long long> a;

5 a.push_back(0);

6 for(long long i = 1; i <= n; ++i){

7 for(long long j = 1; j <= m; ++j){

8 a.push_back(i * j);

9 }

10 }

11 sort(a.begin(), a.end());

12 return a[k];

13}

14int main(){

15 ios::sync_with_stdio(0);

16 cin.tie(0);

17 long long n, m, k;

18 cin >> n >> m >> k;

19 cout << solve1(n, m, k);

20 return 0;

21}

ChậmVừaNhanhRất nhanh

Do vị trí $i, j$ trong bài tính từ 1 vì thế tích nhỏ nhất sẽ là 1. Và do tính vị trí từ 1 trong khi mảng thì index tính từ 0 nên anh cho luôn a[0] = 0 để sau khi sắp xếp thì nó vẫn giữ nguyên vị trí đó không làm ảnh hưởng đến dữ liệu, và nhờ thế mà các phần tử còn lại nằm từ vị trí 1 trở đi cho thống nhất với đề bài.

Thì nếu làm theo hướng này ta sẽ thấy độ phức tạp thời gian lớn nhất sẽ căn cứ theo hàm sort. Hàm sort có độ phức tạp $O(X \log X)$ với $X$ là tổng số phần tử mà mảng đang chứa. Trong trường hợp này tổng số phần tử mảng đang chứa là $N \times M$ nên độ phức tạp thời gian lúc này sẽ là $O(N M \log(N M))$, và độ phức tạp không gian sẽ là $O(N M)$.

Không gian$O(N M)$

Thời gian$O(N M \log(N M))$

Với $N, M \le 1000$ (subtask 1) thì mảng có $10^6$ phần tử, sắp xếp vẫn ổn. Nhưng trường hợp xấu nhất khi $N, M$ tối đa là $10^5$ thì mảng có tới $10^{10}$ phần tử, vừa tràn bộ nhớ vừa chắc chắn bị TLE khỏi phải bàn cãi. Nên cách làm này chắc chắn không giải quyết được trọn vẹn vấn đề.

Ý tưởngChặt nhị phân đáp án

Hướng giải quyết tối ưu cho bài này là dùng kỹ thuật gọi là tìm kiếm nhị phân trên đáp án, tên tiếng Anh là Binary search the answer, hoặc dân trong ngành còn gọi là chặt nhị phân đáp án.

Giải thích sơ lược cho em hiểu: giả sử em đã biết miền đáp án nằm trong 1 đoạn từ Left đến Right nào đó. Thay vì cứ thử lần lượt từ Left đến Right sẽ rất lâu thì em cứ thử giả định nó nằm ở giữa, sau đó kiểm tra: nếu xác định nó nằm ở nửa bên phải thì tìm tiếp nửa bên phải đó, nếu xác định nó nằm ở nửa bên trái thì tìm tiếp qua nửa bên trái. Rồi lặp lại quy trình ở trên cho đến khi tìm được.

Này nó cũng giống như việc em đọc sách, khi cần tìm 1 trang sách nào đó thì thay vì lật từ trang đầu đến trang cuối, em cũng lật ở giữa, rồi dựa vào số trang (hay mục lục của chương đánh trên từng trang) em sẽ xác định được trang mình cần tìm nằm ở nửa bên phải hay nửa bên trái của trang vừa lật, rồi từ đó lại tìm tiếp, lặp lại quy trình như trên.

Như bài này, đầu tiên ta sẽ hiểu đáp án (giá trị phần tử tại vị trí thứ $K$) chắc chắn nằm trong đoạn từ $1$ đến $n \times m$ đúng không? Tại nhỏ nhất là $1$, lớn nhất sẽ là $n \times m$. Rồi giờ tìm cái ở giữa, tức là ban đầu $L = 1$, $R = n \times m$ thì $mid = (L + R) / 2$, này chắc em hiểu hen?

Tìm kiếm nhị phân như em đã biết sẽ còn lặp nếu $L \le R$. Trong bài này, ta đếm tổng số lượng phần tử $\le mid$ trên mỗi dòng:

• Nếu tổng đó $< K$: $mid$ nhỏ quá, cần tăng lên ⇒ cập nhật $L = mid + 1$.
• Nếu tổng đó $\ge K$: $mid$ có thể là đáp án hoặc lớn quá ⇒ giảm xuống, cập nhật $R = mid - 1$.

Vì sao đúng?

Gọi $cnt(x)$ = số phần tử của bảng $\le x$. Khi $x$ tăng thì $cnt(x)$ chỉ tăng hoặc giữ nguyên. Số thứ $k$ chính là giá trị $x$ nhỏ nhất thoả $cnt(x) \ge k$. Mà "nhỏ nhất thoả điều kiện đơn điệu" thì chặt nhị phân được, và khi vòng lặp dừng ($L > R$) thì $L = R + 1$ chính là giá trị đó.

Ví dụChạy tay với bảng 5 × 5, k = 10

Giờ ví dụ ma trận $5 \times 5$, tức là đáp án sẽ nằm trong khoảng $1$ đến $25$. Ta ghi nó ra, có phải ta sẽ có các giá trị trên từng dòng như thế này không:

	cột 1	cột 2	cột 3	cột 4	cột 5	≤ mid
dòng 1	1	2	3	4	5	5
dòng 2	2	4	6	8	10	5
dòng 3	3	6	9	12	15	4
dòng 4	4	8	12	16	20	3
dòng 5	5	10	15	20	25	2

mid = 13: ô xanh là các số ≤ 13. Tổng = 19 ≥ k = 10 → mid đang lớn quá (hoặc vừa đủ).

Giờ giả sử $k = 10$, cần tìm số ở vị trí thứ 10 xem nó là số bao nhiêu? Ta có $L = 1$, $R = 25$ thì $mid = 26 / 2 = 13$. Giờ với giá trị 13, xét từng dòng trong ma trận ở trên, ở mỗi dòng đếm xem có bao nhiêu phần tử $\le mid$: dòng 1 thấy có 5 phần tử $\le 13$, dòng 2 có 5, dòng 3 có 4, dòng 4 có 3, dòng 5 có 2. Vậy tổng số lượng các phần tử $\le 13$ là $5 + 5 + 4 + 3 + 2 = 19$.

Trong khi đó nếu đang muốn tìm phần tử tại vị trí $K = 10$, mà khi giả sử đáp án là $mid = 13$ thì số lượng phần tử $\le 13$ lại ra đến 19 số, như vậy nghĩa là giá trị $mid$ này lớn quá nên cần giảm xuống ⇒ $R = mid - 1 = 12$. Cứ thế tiếp tục, toàn bộ quá trình như bảng sau:

L	R	mid	Đếm số ≤ mid trên từng dòng	So với k	Cập nhật
1	25	13	5 + 5 + 4 + 3 + 2 = 19	19 ≥ 10	R = mid − 1 = 12
1	12	6	5 + 3 + 2 + 1 + 1 = 12	12 ≥ 10	R = mid − 1 = 5
1	5	3	3 + 1 + 1 + 0 + 0 = 5	5 < 10	L = mid + 1 = 4
4	5	4	4 + 2 + 1 + 1 + 0 = 8	8 < 10	L = mid + 1 = 5
5	5	5	5 + 2 + 1 + 1 + 1 = 10	10 ≥ 10	R = mid − 1 = 4
5	4	L > R → dừng. Đáp án = L = R + 1 = 5

Em chú ý dòng cuối nhé: khi $mid = 5$ thì tổng là 10, đang thoả $\ge K$ và như hồi đầu anh có nói ta sẽ giảm $mid$ xuống, tức là $R = mid - 1 = 4$. Lúc này $L = 5$, $R = 4$ ⇒ dừng lại vì $L$ đã $> R$ (ta chỉ lặp khi $L \le R$, nguyên lý của binary search). Vậy đáp án lúc này em trả ra $L$ hay $R + 1$ đều được, và đáp án là 5. Đó, nguyên lý binary search là vậy.

Em nhập $n, m, k$ rồi bấm Tiếp để xem từng lần đoán $mid$ (ô xanh là các số $\le mid$, cột bên phải là số lượng đếm được trên mỗi dòng):

n = m = k =

Ví dụ nhanh:

Mấu chốtĐếm số ≤ mid trên mỗi dòng trong O(1)

Việc mỗi giá trị $mid$ cần xét xem từng dòng có bao nhiêu thằng $\le mid$ rồi cộng tổng lại thì bước đó chỉ duyệt qua $N$ dòng thôi, mỗi dòng có thể tính ra ngay lập tức trong $O(1)$. Em phải suy nghĩ chỗ này 😉

Gợi ý: trong mỗi dòng, các phần tử đang tăng dần và là bội của $i$: $i, 2i, 3i, \ldots, m \cdot i$. Nên chỉ cần 1 chút toán học là biết ngay trong dòng $i$ có bao nhiêu phần tử $\le mid$:

số phần tử ≤ mid trên dòng i = min(⌊mid / i⌋, m)

Vì $i \cdot j \le mid \iff j$ $\le \lfloor mid / i \rfloor$, mà $j$ lại không vượt quá $m$ cột. Ví dụ dòng 3 của bảng $5 \times 5$ với $mid = 13$: $\lfloor 13 / 3 \rfloor = 4$ (đó là các số 3, 6, 9, 12), $\min(4, 5) = 4$ ✔. Dòng 1: $\lfloor 13/1 \rfloor = 13$ nhưng chỉ có 5 cột nên $\min(13, 5) = 5$ ✔.

Ta lặp lại điều đó xét qua hết $N$ dòng ⇒ chi phí cho bước này là $O(N) \times O(1) = O(N)$. Và tổng cộng ta chặt nhị phân trên đáp án từ $1$ đến $N \times M$ ⇒ số lần lặp là $O(\log(N M))$ (khoảng 34 lần với $N M = 10^{10}$).

Nên tổng quát độ phức tạp là $O(N \log(N M))$. Nó tốt hơn hẳn cách vét cạn đưa tất cả phần tử vào mảng rồi sort là $O(N M \log(N M))$. Và cách tối ưu này độ phức tạp bộ nhớ chỉ cần $O(1)$, trong khi cách vét cạn kia thì cần mảng lưu trữ $O(N M)$ phần tử.

Cách 2Code chặt nhị phân đáp án – AC

Source code giải quyết theo tư tưởng anh đã trình bày ở trên và cũng đã nộp thành công trên web, em xem để được hiểu rõ hơn. 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. Anh sợ clean lại mất công em đọc không hiểu. Em xem hiểu rồi clean lại sau nhé:

#include <bits/stdc++.h>
using namespace std;
long long solve2(long long n, long long m, long long k){
    long long l = 1, r = n * m;
    while(l <= r){
        long long mid = (l + r) / 2;
        long long cnt = 0;
        for(long long i = 1; i <= n; ++i){
            cnt += min(mid / i, m);
        }
        if(cnt >= k){
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    return r + 1;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long n, m, k;
    cin >> n >> m >> k;
    cout << solve2(n, m, k);
    return 0;
}

def solve2(n, m, k):
    l = 1
    r = n * m
    while l <= r:
        mid = (l + r) // 2
        cnt = 0
        for i in range(1, n + 1):
            cnt += min(mid // i, m)
        if cnt >= k:
            r = mid - 1
        else:
            l = mid + 1
    return r + 1

n, m, k = map(int, input().split())
print(solve2(n, m, k))

C++▶ Chạy tay từng dòng codeCách 2: chặt nhị phân đáp án, mỗi lần đếm số phần tử ≤ mid bằng min(mid / i, m), O(N log NM).

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

Dữ liệu mẫu:

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

2using namespace std;

3long long solve2(long long n, long long m, long long k){

4 long long l = 1, r = n * m;

5 while(l <= r){

6 long long mid = (l + r) / 2;

7 long long cnt = 0;

8 for(long long i = 1; i <= n; ++i){

9 cnt += min(mid / i, m);

10 }

11 if(cnt >= k){

12 r = mid - 1;

13 }

14 else{

15 l = mid + 1;

16 }

17 }

18 return r + 1;

19}

20int main(){

21 ios::sync_with_stdio(0);

22 cin.tie(0);

23 long long n, m, k;

24 cin >> n >> m >> k;

25 cout << solve2(n, m, k);

26 return 0;

27}

ChậmVừaNhanhRất nhanh

• l = 1, r = n * m: miền đáp án. Lưu ý $n \times m$ có thể tới $10^{10}$ nên mọi biến đều là long long.
• cnt += min(mid / i, m): đếm số phần tử $\le mid$ trên dòng $i$ đúng như công thức ở trên.
• cnt >= k thì r = mid - 1, ngược lại l = mid + 1. Hết vòng lặp trả về r + 1 (cũng chính là l).

Không gian$O(1)$

Thời gian$O(N \log(N M))$

Kiểm chứngSo sánh 2 cách bằng test ngẫu nhiên

Trong code gốc, anh để thêm 1 đoạn code được comment lại ở dưới cùng hàm main (đặt cả solve1 và solve2 chung 1 file). Đó là cách để anh check xem với cùng 1 bộ test đưa vào thì giữa 2 cách có sự khác biệt đáp án không? Để từ đó kiểm chứng được độ chính xác của cách làm tối ưu (vì cách vét cạn chắc ăn luôn đúng rồi sao mà sai được haha):

srand(time(0));
while(1){
    long long n = 1 + rand() % 10;
    long long m = 1 + rand() % 10;
    long long k = 1 + rand() % (n * m);
    long long res1 = solve1(n, m, k);
    long long res2 = solve2(n, m, k);
    if(res1 == res2){
        cout << "OK\n";
    }
    else{
        cout << "FAIL\n";
        cout << n << " " << m << " " << k << endl;
        cout << "res1 = " << res1 << endl;
        cout << "res2 = " << res2 << endl;
        break;
    }
}

Bản Python cũng làm y hệt: sinh ngẫu nhiên $n, m \in [1, 10]$, $k \in [1, n m]$, so solve1 với solve2, khác nhau thì in ra bộ test để mình dò lỗi.

Ghi chú của mình: code C++ và Python của cả 2 cách là của anh (mình chỉ tách riêng solve1, solve2 thành 2 chương trình). Mình đã kiểm tra với 200 bộ test ngẫu nhiên ($1 \le n, m \le 12$) so với cách liệt kê và sắp xếp trực tiếp: khớp 100%. Với test lớn nhất $n = m = 10^5$, $k = 5 \cdot 10^9$: Cách 2 bản C++ chạy khoảng 0.01 giây, bản Python khoảng 0.35 giây trên máy mình; Cách 1 với $n = m = 1000$ chạy khoảng 0.06 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 😇