Khoảng Cách Bằng X

Nguồn: Bài tập học viên gửi Độ khó: Trung bình Mảng đánh dấu Vét cạn Tìm kiếm

Đề bài

KHOẢNG CÁCH BẰNG X

Cho mảng $A[\,]$ gồm $N$ phần tử và số $X$. Nhiệm vụ của bạn là tìm cặp phần tử $A[i] - A[j] = X$. Nếu tồn tại $A[i] - A[j] = X$ đưa ra $1$, ngược lại đưa ra $-1$.

Input:

• Dòng đầu tiên đưa vào số lượng bộ test $T$.
• Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test gồm hai dòng: dòng thứ nhất là cặp số $N$, $X$; dòng tiếp theo là $N$ số $A[i]$ là các phần tử của mảng $A[\,]$.
• $T, N, X, A[i]$ thỏa mãn ràng buộc: $1 \le T \le 100$; $1 \le N, X \le 10^5$; $1 \le A[i] \le 10^5$.

Output: Đưa ra kết quả mỗi test theo từng dòng.

Giới hạn thời gian: 1 giây.

Ví dụ – input

2
6 78
5 20 3 2 5 80
5 45
90 70 20 80 50

Ví dụ – output

1
-1

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é:

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

Giải thích ví dụ cho bạn nào chưa hiểu đề:

• Bộ test 1: $X = 78$, mảng $\{5, 20, 3, 2, 5, 80\}$. Có cặp $80 - 2 = 78$ ⇒ in 1.
• Bộ test 2: $X = 45$, mảng $\{90, 70, 20, 80, 50\}$. Hiệu của mọi cặp là $20, 70, 10, 40, 50, 10, 20, 60, 30, 30$ – không có hiệu nào bằng $45$ ⇒ in -1.

Nhắc lại ngưỡng TLE

Với giới hạn 1 giây, tổng số lần lặp của cả bài chỉ nên ở mức $(3 \div 5) \cdot 10^7$ là an toàn với phần lớn hệ thống chấm, cao lắm là $10^8$ (hên xui). Đó là với C/C++, còn Python, Java, C# chạy chậm hơn thì ngưỡng phải thấp hơn. Lưu ý bài này có tới $T$ bộ test, nên phải nhân thêm $T$ vào số lần lặp nha.

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 mọi cặp · O(T·N²)Cách 2Mảng đánh dấu · O(T·(N + 10^5))

Cách 1Vét cạn xét tất cả các cặp – O(T·N²)

Cách đơn giản nhất là vét cạn xét tất cả các cặp số: khi nào tìm được cặp thoả mãn thì dừng lại in ra $1$, còn xét đến tận cùng vẫn không có cặp nào thì in ra $-1$. Cứ thế xét hết tất cả các bộ test, đơn giản vậy thôi.

Giải thích thêm một số chỗ trong code bên dưới:

1. Dùng abs để viết gọn. Mọi phần tử và $X$ đều dương. Hiệu $a[i] - a[j]$ có thể âm (khi $a[i] \lt a[j]$) hoặc dương, trong khi $X$ luôn dương. Hai vòng lặp lồng nhau với $j \gt i$ chỉ xét mỗi cặp một lần, lẽ ra phải kiểm tra cả $a[i] - a[j]$ lẫn $a[j] - a[i]$; dùng hàm trị tuyệt đối abs thì hiệu âm hay dương đều thành dương, chỉ việc so với $X$, gọn hơn hẳn.
2. Cờ hiệu check và mẹo thoát 2 vòng lặp. Ban đầu check = -1 (chưa tìm thấy), tìm thấy thì gán check = 1; cuối cùng in luôn check cũng chính là đáp án. Khi tìm thấy rồi muốn thoát cả 2 vòng lặp, nhưng break chỉ thoát vòng gần nhất (vòng for j), vòng for i vẫn chạy tiếp. Mẹo: trước khi break ta gán i = n; vòng for i tăng i++ thành $n + 1$, không còn thoả i < n nữa nên cũng kết thúc luôn.

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 main(){
    int t;
    cin >> t;
    while(t--){
        int n, x;
        cin >> n >> x;
        int a[n];
        for(int i = 0; i < n; ++i){
            cin >> a[i];
        }
        int check = -1;
        for(int i = 0; i < n; ++i){
            for(int j = i + 1; j < n; ++j){
                if(abs(a[i] - a[j]) == x){
                    check = 1;
                    i = n;
                    break;
                }
            }
        }
        cout << check << endl;
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.read().split()
    p = 0
    t = int(data[p]); p += 1
    out = []
    for _ in range(t):
        n, x = int(data[p]), int(data[p + 1]); p += 2
        a = [int(v) for v in data[p:p + n]]; p += n
        check = -1
        for i in range(n):
            for j in range(i + 1, n):
                if abs(a[i] - a[j]) == x:
                    check = 1
                    break
            if check == 1:  # đã tìm thấy thì thoát luôn vòng ngoài
                break
        out.append(str(check))
    print('\n'.join(out))

main()

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

• Không gian: mảng $a$ của mỗi bộ test ⇒ $O(N)$.
• Thời gian: $O(N)$ đọc mảng + $O(N^2)$ tìm cặp, nhân với $T$ bộ test ⇒ $O(T \cdot N^2)$. Trường hợp xấu nhất là không bộ test nào có cặp thoả mãn (luôn phải xét tới cùng) với $T = 100$, $N = 10^5$: $100 \cdot (10^5 + 10^{10}) \approx 10^{12}$, tức khoảng 1000 tỷ lần lặp ⇒ chắc chắn TLE.

Không gian$O(N)$

Thời gian$O(T \cdot N^2)$

Vẫn nên cài đặt

Dù bị TLE, các bạn vẫn nên cài đặt cách vét cạn này để sau này lấy nó làm công cụ kiểm tra tính chính xác cho cách làm tối ưu (sinh test nhỏ ngẫu nhiên rồi so kết quả 2 code).

Cách 2Kỹ thuật mảng đánh dấu – O(T·(N + 10^5))

Dấu hiệu dễ nhìn ra bài này giải được tối ưu bằng kỹ thuật mảng đánh dấu: giá trị $X$ cũng như các $a[i]$ chỉ nằm trong đoạn từ $1$ đến $10^5$.

Muốn có cặp $a_i - a_j = X$ thì chuyển vế đổi dấu: $a_i = a_j + X$ hoặc $a_j = a_i - X$. $X$ đề đã cho sẵn, $a_i, a_j$ đại diện cho các giá trị trong mảng. Nhìn ví dụ 1: $X = 78$, mảng $\{5, 20, 3, 2, 5, 80\}$. Khi xét $a[0] = 5$, nếu trong mảng có một số $y = 5 + 78 = 83$ hoặc $y = 5 - 78 = -73$ thì ta tìm được cặp thoả mãn (vì $83 - 5 = 78$, hay $5 - (-73) = 78$). Mà các giá trị trong mảng chỉ nằm trong $[1, 10^5]$, nên $y$ nào nằm ngoài đoạn này thì bỏ qua, không cần xét; ở đây chỉ cần tìm xem có số $83$ trong mảng không.

Ý tưởng

Duyệt từng $a[i]$, tính $y = a[i] + X$ và $y = a[i] - X$; chỉ xét các $y$ hợp lệ trong $[1, 10^5]$ và kiểm tra $y$ có nằm trong mảng không. Có thì kết luận ngay $1$, không thì xét tiếp $a[i]$ sau.

Nếu kiểm tra "$y$ có trong mảng không" bằng cách duyệt lại cả mảng thì vẫn là $O(N^2)$. Đây là lúc mảng đánh dấu ra tay:

• Tạo mảng check có $10^5 + 1$ phần tử (chỉ số $0..10^5$, bỏ qua chỉ số 0), khởi tạo toàn false.
• Khi đọc mỗi $a[i]$, gán check[a[i]] = true. Thao tác này chỉ tốn $O(1)$ vì mảng truy cập được vào chỉ số bất kỳ ngay lập tức.
• Đọc xong, muốn biết $y$ có xuất hiện trong mảng không thì chỉ cần nhìn check[y]: true là có, false là không ⇒ $O(1)$.

Vậy chỉ tốn thêm bộ nhớ cho mảng check, nhưng bù lại bước tìm cặp rút từ $O(N^2)$ xuống còn $O(N)$.

Minh hoạ

Em nhập $X$ và mảng $a$ (giá trị nhỏ để dễ nhìn) rồi bấm Tiếp: đầu tiên các ô check[v] được tô xanh dương cho mọi $v$ có trong mảng, sau đó với từng $a[i]$ ta "nhảy" tới ô $a[i] + X$ và $a[i] - X$ để kiểm tra:

X Mảng a

Ví dụ nhanh:

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 main(){
    ios_base::sync_with_stdio(false); // đọc nhanh vì dữ liệu vào có thể tới 10^7 số
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        int n, x;
        cin >> n >> x;
        int a[n];
        bool check[100001] = {false};
        for(int i = 0; i < n; ++i){
            cin >> a[i];
            check[a[i]] = true;
        }
        int res = -1;
        for(int i = 0; i < n; ++i){
            int y = a[i] + x;
            if(y >= 1 && y <= 100000){
                if(check[y] == true){
                    res = 1;
                    break;
                }
            }
            y = a[i] - x;
            if(y >= 1 && y <= 100000){
                if(check[y] == true){
                    res = 1;
                    break;
                }
            }
        }
        cout << res << endl;
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.read().split()
    p = 0
    t = int(data[p]); p += 1
    out = []
    for _ in range(t):
        n, x = int(data[p]), int(data[p + 1]); p += 2
        a = [int(v) for v in data[p:p + n]]; p += n
        check = [False] * 100001  # mảng đánh dấu: check[v] = True nếu v có trong mảng
        for v in a:
            check[v] = True
        res = -1
        for v in a:
            y = v + x
            if 1 <= y <= 100000 and check[y]:
                res = 1
                break
            y = v - x
            if 1 <= y <= 100000 and check[y]:
                res = 1
                break
        out.append(str(res))
    print('\n'.join(out))

main()

Về 2 dòng đọc nhanh

Mình thêm ios_base::sync_with_stdio(false); cin.tie(NULL); vào code gốc. Lý do: dữ liệu vào xấu nhất có tới $T \cdot N = 10^7$ số (gần 60 MB). Mình đo thử, riêng việc đọc bằng cin thường đã mất gần 3 giây, thêm 2 dòng này thì cả chương trình chỉ còn khoảng 0.7 giây. Thuật toán không đổi gì cả.

C++▶ Chạy tay từng dòng codeĐánh dấu check[a[i]] = true, rồi với mỗi a[i] tra check[a[i] + x] và check[a[i] - x].

Dữ liệu vào (stdin) – sửa thoải mái2 6 78 5 20 3 2 5 80 5 45 90 70 20 80 50

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 ios_base::sync_with_stdio(false); // đọc nhanh vì dữ liệu vào có thể tới 10^7 số

6 cin.tie(NULL);

7 int t;

8 cin >> t;

9 while(t--){

10 int n, x;

11 cin >> n >> x;

12 int a[n];

13 bool check[100001] = {false};

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

15 cin >> a[i];

16 check[a[i]] = true;

17 }

18 int res = -1;

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

20 int y = a[i] + x;

21 if(y >= 1 && y <= 100000){

22 if(check[y] == true){

23 res = 1;

24 break;

25 }

26 }

27 y = a[i] - x;

28 if(y >= 1 && y <= 100000){

29 if(check[y] == true){

30 res = 1;

31 break;

32 }

33 }

34 }

35 cout << res << endl;

36 }

37 return 0;

38}

ChậmVừaNhanhRất nhanh

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

• Không gian: mảng $a$ $O(N)$ + mảng đánh dấu $O(10^5 + 1)$.
• Thời gian: mỗi bộ test tốn $O(10^5)$ khởi tạo mảng check + $O(N)$ đọc dữ liệu + $O(N)$ tìm cặp; nhân với $T$ bộ test ⇒ $O(T \cdot \max(N, 10^5))$. Trường hợp xấu nhất: $10^2 \cdot 10^5 \cdot 3 = 3 \cdot 10^7$ lần lặp, vừa đủ ở ngưỡng an toàn nên không sợ TLE.

Không gian$O(N + 10^5)$

Thời gian$O(T \cdot (N + 10^5))$

Đến đây các bạn đã thấy cái hay của giải thuật rồi chứ? Cách làm trước trong trường hợp xấu nhất phải lặp khoảng 1000 tỷ lần, cách này rút xuống chỉ còn 30 triệu lần lặp 😍.

Thật ra chỉ cần kiểm tra a[i] + X

Nếu có cặp $a_i - a_j = X$ thì khi duyệt tới $a_j$, ta sẽ thấy $a_j + X = a_i$ có trong mảng. Vậy chỉ kiểm tra $y = a[i] + X$ là đủ, phần kiểm tra $a[i] - X$ chỉ giúp tìm ra sớm hơn (như nút "Tìm thấy bằng a[i] − X" ở khung chạy tay). Giữ cả 2 cho dễ hiểu cũng không sao.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 400 bộ input ngẫu nhiên (mỗi bộ có tới 5 test), so với code vét cạn xét mọi cặp $i \ne j$ – khớp hết. Với $T = 100$, $N = X = 10^5$ (khoảng 59 MB dữ liệu vào): cách 2 bản C++ chạy khoảng 0.7 giây (khoảng 2.7 giây nếu không có 2 dòng đọc nhanh), bản Python khoảng 3 giây, chủ yếu là thời gian đọc dữ liệu. Cách 1 chỉ với một bộ test $N = 10^5$ đã mất hơn 6 giây ⇒ TLE đúng như phân tích.

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 😇