Nói Chuyện Riêng (ARGUMENT)

Nguồn: Đề thi HSG Tin học Độ khó: Trung bình Bảng băm (Map) Sắp xếp

Đề bài

Bài 3: Nói chuyện riêng [ARGUMENT] – 2 điểm

Trong giờ tập quân sự, học sinh của tất cả các lớp xếp thành một hàng dài để hành quân dã ngoại. Để phân biệt lớp này với lớp khác, mỗi lớp được mô tả bằng một mã định danh riêng. Lớp có mã định danh càng lớn thì yêu cầu về tính kỷ luật khi hành quân càng cao.

Các bạn học sinh cùng một lớp thường nói chuyện ngay cả khi đang hành quân. Chính xác hơn, nếu có hai bạn cùng lớp có vị trí trong hàng khác nhau không quá $K$ thì họ sẽ nói chuyện với nhau.

Hãy xác định số hiệu lớn nhất của lớp có hai bạn nói chuyện với nhau (để còn kỷ luật mẫu!!!)

Input:

• Dòng đầu tiên ghi hai số nguyên dương $N$, $K$ lần lượt là số bạn học sinh trong hàng và khoảng cách tối đa để có thể nói chuyện với nhau $(1 \le N \le 50000,\ 1 \le K \le N)$.
• $N$ dòng sau, mỗi dòng ghi định danh lớp của một bạn đứng trong hàng hành quân (theo thứ tự từ $1$ đến $N$).

Output: Một số nguyên duy nhất là mã định danh lớn nhất của lớp có hai bạn học sinh nói chuyện với nhau. Nếu không có ai nói chuyện riêng thì ghi $-1$.

input

6 3
7
3
4
2
3
4

output

4

Lời mở đầu

Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình viết lại thành bài giải chi tiết để các bạn tham khảo nhen. Hi 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

Trước tiên các bạn đảm bảo là hiểu rõ đề rồi hen. Ta có nhiều lớp học, mỗi lớp có 1 ID riêng, và có danh sách $N$ học sinh đứng thành hàng, biết từng học sinh thuộc lớp có ID bao nhiêu. Như ví dụ: đầu hàng là số $7$ nghĩa là bạn đứng đầu thuộc lớp ID $= 7$; tiếp đó là số $3$ nghĩa là bạn thứ 2 thuộc lớp ID $= 3$... 2 học sinh nếu cùng lớp và khoảng cách giữa họ (trị tuyệt đối hiệu 2 vị trí, ví dụ bạn thứ 2 với bạn thứ 5 thì khoảng cách là $3$) mà $\le K$ thì sẽ nói chuyện với nhau. Trong các cặp nói chuyện, chọn lớp có ID lớn nhất để in ra; không có cặp nào thì in $-1$.

• Bạn thứ 2 nói chuyện với bạn thứ 5: cùng lớp $3$, khoảng cách $5 - 2 = 3 \le K = 3$.
• Bạn thứ 3 nói chuyện với bạn thứ 6: cùng lớp $4$, khoảng cách $6 - 3 = 3 \le 3$.
• Bạn thứ 1 (lớp $7$) và bạn thứ 4 (lớp $2$) không nói chuyện với ai vì lớp của họ chỉ có mình họ.

Vậy có 2 cặp nói chuyện thuộc lớp $3$ và lớp $4$, ID lớn nhất là 4.

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

Cách 1Bảng băm lưu vị trí gần nhất · O(N)Cách 2Sắp xếp cặp (ID, vị trí) · O(N log N)

Cách 1Bảng băm lưu vị trí xuất hiện gần nhất của mỗi lớp – O(N)

Bắt đầu xét từ bạn học sinh đầu tiên. Dùng 1 cái bảng băm (hash table), trong C++ là unordered_map. Nó giống như 1 cuốn từ điển: truyền vào key thì nó trả ra value. Ở đây key là ID lớp, value là vị trí của bạn học sinh lớp đó. Khai báo: unordered_map<int, int> ump;.

Xét bạn thứ 1: lưu key $= 7$, value $= 1$ (lớp 7 xuất hiện tại vị trí 1). Xét bạn thứ 2: lưu key $= 3$, value $= 2$... Cứ xét đến bạn thứ $i$ có ID lớp là $x$ thì tìm xem $x$ đã có trong bảng băm chưa: auto it = ump.find(x);

• Nếu không tìm thấy (it == ump.end()): thêm mới ump[x] = i.
• Nếu tìm thấy: nghĩa là trước đó (các vị trí $1..i-1$) đã từng có bạn cùng lớp $x$. Tính khoảng cách i - it->second (it->first là key, it->second là value). Nếu $\le K$ thì 2 bạn này nói chuyện ⇒ cập nhật Max = max(Max, x) (ban đầu Max = -1). Sau đó luôn cập nhật it->second = i.

Vì sao phải cập nhật lại vị trí gần nhất?

Ví dụ lớp $3$ xuất hiện tại các vị trí $1, 5, 8$. Ta đang xét vị trí từ nhỏ đến lớn: khi ở $5$ thì so với $1$; sau đó phải cập nhật value $= 5$, để khi lên $8$ thì so với $5$ (khoảng cách $8 - 5 = 3$, gần hơn). Nếu không cập nhật thì value vẫn là $1$, khoảng cách $8 - 1 = 7$ – xa quá, có thể bỏ lỡ cặp nói chuyện. Với mỗi vị trí, bạn cùng lớp gần nhất phía trước là ứng viên tốt nhất, nên chỉ cần nhớ vị trí gần nhất là đủ.

Minh hoạ

Em nhập $K$ và dãy ID lớp rồi bấm Tiếp. Ô vàng là bạn đang xét, ô tím là bạn cùng lớp gần nhất phía trước (lấy từ bảng băm); xanh lá là cặp nói chuyện được, đỏ là xa quá.

K ID lớp

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::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k;
    int Max = -1;
    unordered_map<int, int> ump;
    for(int i = 1; i <= n; ++i){
        int x;
        cin >> x;
        auto it = ump.find(x);
        if(it == ump.end()){
            ump[x] = i;
        }
        else{
            if(i - it->second <= k){
                Max = max(Max, x);
            }
            it->second = i;
        }
    }
    cout << Max;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, k = int(data[0]), int(data[1])
    Max = -1
    ump = {}
    for i in range(1, n + 1):
        x = int(data[1 + i])
        if x not in ump:
            ump[x] = i
        else:
            if i - ump[x] <= k:
                Max = max(Max, x)
            ump[x] = i
    print(Max)

main()

C++▶ Chạy tay từng dòng codeBảng băm ump lưu vị trí gần nhất của mỗi lớp; gặp lại lớp cũ thì kiểm tra khoảng cách ≤ K.

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

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); cout.tie(0);

7 int n, k;

8 cin >> n >> k;

9 int Max = -1;

10 unordered_map<int, int> ump;

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

12 int x;

13 cin >> x;

14 auto it = ump.find(x);

15 if(it == ump.end()){

16 ump[x] = i;

17 }

18 else{

19 if(i - it->second <= k){

20 Max = max(Max, x);

21 }

22 it->second = i;

23 }

24 }

25 cout << Max;

26 return 0;

27}

ChậmVừaNhanhRất nhanh

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

• Không gian: $O(N)$ cho bảng băm (tối đa $N$ lớp khác nhau).
• Thời gian: unordered_map với các thao tác insert, find trung bình $O(1)$ nên tổng quát chỉ $O(N)$. $N$ tối đa $5 \cdot 10^4$, nhỏ hơn rất nhiều so với ngưỡng $10^8$ của 1 giây ⇒ yên tâm.

Không gian$O(N)$

Thời gian$O(N)$

Đừng vội dùng mảng đánh dấu theo ID

Nếu phiên bản C++ trên máy chấm cũ quá (trước C++11) thì không dùng unordered_map được. Lúc này bạn nào đọc không kỹ đề sẽ tưởng các ID lớp nằm trong đoạn $[1, N]$ rồi dùng mảng đánh dấu thay cho unordered_map. Nhưng điều này là sai: đề không hề nói rõ ID lớp nằm trong đoạn nào, nó có thể tới 1 tỷ, và tất nhiên không thể tạo mảng đánh dấu 1 tỷ phần tử được. Giải pháp là cách 2 bên dưới.

Cách 2Sắp xếp các cặp (ID lớp, vị trí) – O(N log N)

Nếu nhìn kỹ vấn đề sẽ thấy bài này hoàn toàn chỉ cần mảng thông thường, với sự hỗ trợ của kỹ thuật sắp xếp. Với ví dụ mẫu, đánh số thứ tự học sinh từ $1$ đến $N$ thì ta có danh sách cặp (ID lớp, STT): $(7, 1), (3, 2), (4, 3), (2, 4), (3, 5), (4, 6)$.

Đi sắp xếp giảm dần theo ID lớp, nếu ID lớp trùng nhau thì sắp tăng dần theo STT:

$(7, 1),\ (4, 3),\ (4, 6),\ (3, 2),\ (3, 5),\ (2, 4)$

Đặc tính của sắp xếp đã giúp gom nhóm các ID lớp bằng nhau về nằm sát cạnh nhau. Giờ chỉ việc duyệt 1 vòng lặp: xét phần tử $i$ với lân cận trước nó $i - 1$, nếu trùng ID lớp thì lấy STT của $i$ trừ STT của $i - 1$ (STT lớn trừ STT nhỏ) xem có $\le K$ không. Nếu thỏa thì dừng luôn, in ra ID lớp đó – vì danh sách đang giảm dần theo ID nên đó chính là ID lớn nhất. Xét hết danh sách mà không thấy thì in $-1$. Ví dụ trên: $(4, 3)$ và $(4, 6)$ cùng lớp, $6 - 3 = 3 \le 3$ ⇒ in $4$ ngay.

Vì sao chỉ cần xét 2 phần tử kề nhau?

Trong cùng một nhóm ID, STT đã tăng dần, nên cặp có khoảng cách nhỏ nhất chắc chắn là 2 phần tử kề nhau trong nhóm – giống y như ý "vị trí gần nhất" ở cách 1.

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;

pair<int, int> a[50005];

bool cmp(const pair<int, int> &a, const pair<int, int> &b){
    if(a.first == b.first){
        return a.second < b.second;
    }
    return a.first > b.first;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; ++i){
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a + 1, a + n + 1, cmp);
    for(int i = 2; i <= n; ++i){
        if(a[i].first == a[i - 1].first && a[i].second - a[i - 1].second <= k){
            cout << a[i].first;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, k = int(data[0]), int(data[1])
    a = [(int(data[1 + i]), i) for i in range(1, n + 1)]
    # giảm dần theo mã lớp, cùng mã lớp thì tăng dần theo vị trí
    a.sort(key=lambda p: (-p[0], p[1]))
    for i in range(1, n):
        if a[i][0] == a[i - 1][0] and a[i][1] - a[i - 1][1] <= k:
            print(a[i][0])
            return
    print(-1)

main()

C++▶ Chạy tay từng dòng codeSắp xếp giảm dần theo ID lớp (cùng ID thì tăng theo vị trí), gặp cặp kề nhau cùng ID cách ≤ K thì in luôn.

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

Dữ liệu mẫu:

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

2using namespace std;

3

4pair<int, int> a[50005];

5

6bool cmp(const pair<int, int> &a, const pair<int, int> &b){

7 if(a.first == b.first){

8 return a.second < b.second;

9 }

10 return a.first > b.first;

11}

12

13int main(){

14 ios::sync_with_stdio(0);

15 cin.tie(0); cout.tie(0);

16 int n, k;

17 cin >> n >> k;

18 for(int i = 1; i <= n; ++i){

19 cin >> a[i].first;

20 a[i].second = i;

21 }

22 sort(a + 1, a + n + 1, cmp);

23 for(int i = 2; i <= n; ++i){

24 if(a[i].first == a[i - 1].first && a[i].second - a[i - 1].second <= k){

25 cout << a[i].first;

26 return 0;

27 }

28 }

29 cout << -1;

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)$ cho mảng cặp.
• Thời gian: input $O(N)$, sắp xếp $O(N \log N)$, xử lý $O(N)$ ⇒ lấy theo thằng lớn nhất: $O(N \log N)$. $N = 50000$ thì $50000 \cdot \log_2 50000$ chưa đến 1 triệu, trong khi ngưỡng 1 giây tối đa là 100 triệu nên không sợ TLE.

Không gian$O(N)$

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

Điều thú vị: O(N log N) mà chạy không thua O(N)

Khi mình cho 2 cách chạy cùng bộ dữ liệu random (tool check so kết quả 2 cách), nhiều lúc thấy cách 2 chạy nhanh ngang, thậm chí nhanh hơn cách 1 một chút xíu, dù về lý thuyết $O(N)$ phải tốt hơn $O(N \log N)$. Lý do: cách 1 dùng unordered_map, còn cách 2 chỉ dùng mảng bình thường. Các cấu trúc dữ liệu có sẵn trong thư viện STL như vector, stack, queue, map, set, unordered_map... thường chạy chậm hơn cỡ 3 đến 5 lần so với cách giải tương tự chỉ dùng mảng thường. Nên một thuật $O(N \log N)$ với $N$ tới $10^6$ mà dùng STL thì vẫn có khả năng TLE vài test lớn. Muốn chắc ăn nhất thì dùng mảng thường; tuy nhiên không phải lúc nào cũng bắt buộc, có những tình huống dùng thư viện có sẵn lại tối ưu hơn, tùy tình huống mà áp dụng nhé.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 400 bộ test ngẫu nhiên ($N \le 60$, ID lớp nhỏ lẫn lớn tới $10^9$), so với code vét cạn xét mọi cặp – khớp hết. Với $N = 50000$: cả 2 cách bản C++ đều chạy dưới 0.05 giây, bản Python dưới 0.2 giây. Trong code cách 2 mình khai báo mảng toàn cục pair<int, int> a[50005] thay cho mảng kích thước biến a[n + 1] trong hàm main (vốn không thuộc chuẩn C++), logic giữ nguyên.

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 😇