I. Giới thiệu về Rời rạc hóa

Trong lập trình thi đấu và lĩnh vực Toán học, khái niệm Rời rạc hóa thường được nhắc đến. Rời rạc hóa là quá trình chuyển đổi các hàm, mô hình hoặc biến thành các đối số rời rạc, giúp dữ liệu có thể dễ dàng xử lý trên máy tính. Một cách đơn giản, quá trình này nhằm giảm kích thước vùng dữ liệu lớn xuống vùng dữ liệu nhỏ mà không làm thay đổi kết quả của bài toán.

Trong chuyên đề này, chúng ta sẽ tìm hiểu một kỹ thuật phụ trợ trong Rời rạc hóa, đó là kỹ thuật Nén số hay còn có tên gọi là Đánh lại số thứ tự. Kỹ thuật này cho phép chúng ta chuyển đổi một dãy số từ vùng giá trị lớn xuống vùng giá trị nhỏ, đồng thời vẫn giữ nguyên mối quan hệ về giá trị lớn - nhỏ giữa các phần tử trong dãy. Bài toán được phát biểu như sau:

Cho dãy số AAA gồm n phần tử a1, a2, …, an. Cần phải đưa các giá trị trong mảng về đoạn [1,n] mà vẫn đảm bảo được mối quan hệ lớn - bé giữa các phần tử trong mảng.

Yêu cầu: Biến đổi mảng AAA sao cho thỏa mãn điều kiện trên?

Input:

• Dòng đầu tiên chứa số nguyên dương n.
• Dòng thứ hai chứa n số nguyên a1, a2, …, an phân tách bởi dấu cách.

Ràng buộc:

• 1≤n≤10^5.
• |ai|≤10^9; ∀i: 1≤i≤n.

Output:

• In ra mảng AAA sau khi đã biến đổi.

Ví dụ:

Input:

5
100 100 2000 1500 900000

Output:

1 1 3 2 4

II. Kỹ thuật Rời rạc hóa

Để giải quyết bài toán trên, có hai phương pháp cài đặt chính: Sắp xếp và Sử dụng ánh xạ (Map). Dưới đây là mô tả chi tiết cho cả hai cách:

Phương pháp 1: Sắp xếp

Đầu tiên, tạo một mảng BBB lưu lại các phần tử của dãy AAA cùng với hai thông số:

bi={ai,i}; ∀i:1≤i≤n

Tiếp theo, sắp xếp mảng BBB theo giá trị của ai. Sử dụng C++ với kiểu pair hoặc Python với kiểu tuple để lưu trữ. Sau khi sắp xếp, kiểm tra từng phần tử nếu giá trị khác nhau thì cấp phát giá trị mới cho các phần tử tương ứng và nếu giá trị giống nhau thì giữ nguyên giá trị cũ.

Độ phức tạp thuật toán: O(n log n)

Cài đặt mã nguồn:

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

void discretizing(int n, vector < int > &a, vector < pair < int, int > > &b)
{
    sort(b.begin() + 1, b.end());
    a[b[1].second] = 1;
    int counter = 1;
    for (int i = 2; i <= n; ++i)
        if (b[i].first != b[i - 1].first)
            a[b[i].second] = ++counter;
        else
            a[b[i].second] = counter;
}

int main()
{
    int n;
    cin >> n;
    vector < int > a(n + 1);
    vector < pair < int, int > > b(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        b[i] = {a[i], i};
    }
    discretizing(n, a, b);
    for (int i = 1; i <= n; ++i)
        cout << a[i] << ' ';
}

Phương pháp 2: Sử dụng ánh xạ (Map)

Ở phương pháp này, ta sẽ lưu các phần tử trong mảng AAA cùng với vị trí của chúng vào một map. Sau đó, sử dụng một biến counter để cập nhật giá trị cho các phần tử theo mối quan hệ trong mảng.

Độ phức tạp: O(n log n)

Cài đặt:

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

int main()
{
    int n;
    cin >> n;
    vector < int > a(n + 1);
    map < int, vector < int > > cnt;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        cnt[a[i]].push_back(i);
    }
    int counter = 0;
    for (auto e: cnt)
    {
        ++counter;
        for (int p: e.second)
            a[p] = counter;
    }
    for (int i = 1; i <= n; ++i)
        cout << a[i] << ' ';
}

III. Bài tập ứng dụng

Bài 1: Phát đồng xu

Trong một trò chơi, n người chơi xếp thành một vòng tròn và được đánh số từ 1 tới n. Có m lượt phát đồng xu cho các người chơi với quy tắc phát từ vị trí l đến r.

Input:

• Dòng đầu chứa hai số nguyên n, m.
• m dòng tiếp theo chứa từng cặp l, r.

Output:

• Số đồng xu lớn nhất và số lượng người chơi nhận được số đồng xu lớn nhất.

Bài 2: Dãy số

Cho dãy số A và hai giá trị L, R, hãy đếm số cặp vị trí đặc biệt trong dãy sao cho tổng đoạn giữa các cặp nằm trong khoảng [L,R].

IV. Tài liệu tham khảo

• VNOI.
• Competitive Programming 3 - Steven Halim & Felix Halim.
  source: viblo