Editorial for ptit024: Đố chữ

Hiểu bài toán

Bài toán yêu cầu mã hóa một xâu ký tự bằng cách thay thế các ký tự tại những vị trí có chỉ số là số nguyên tố bằng dấu sao (). Xâu đầu vào có độ dài tối đa 1000 ký tự. Ví dụ, với xâu "LapTrinhPTITLapTrinhTuTraiTim", chỉ số 2 là số nguyên tố nên ký tự 'p' được thay bằng '', chỉ số 3 là số nguyên tố nên 'T' thành '*', và cứ thế cho đến hết xâu.

Các cách tiếp cận

Cách Kiểm tra số nguyên tố cho mỗi chỉ số

#include <stdio.h>
#include <string.h>
#include <math.h>

int nt(int a){
    if(a < 2) return 0;
    if(a == 2) return 1;
    for(int i = 2; i <= sqrt(a); i++){
        if(a % i == 0) return 0;
    }
    return 1;
}

int main(){
    char a[1002];
    gets(a);
    for(int i = 0; i < strlen(a); i++)
        if(nt(i)) a[i] = '*';
    printf("%s", a);
}

• Time Complexity: O(n * sqrt(n))
• Space Complexity: O(1)

Approach này duyệt qua mỗi ký tự của xâu (vòng lặp O(n)). Với mỗi chỉ số i, nó gọi hàm nt(i) để kiểm tra xem i có phải là số nguyên tố không. Hàm nt(i) chạy trong thời gian O(sqrt(i)). Vì vậy, độ phức tạp tổng thể là O(n * sqrt(n)). Với n <= 1000, thời gian này hoàn toàn chấp nhận được.

Cách Sieve of Eratosthenes (Sàng Eratosthenes)

#include <stdio.h>
#include <string.h>

#define MAX 1005

int prime[MAX];

void sieve() {
    for (int i = 0; i < MAX; i++) prime[i] = 1;
    prime[0] = prime[1] = 0;
    for (int i = 2; i * i < MAX; i++) {
        if (prime[i]) {
            for (int j = i * i; j < MAX; j += i)
                prime[j] = 0;
        }
    }
}

int main() {
    sieve();
    char s[MAX];
    scanf("%s", s);
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        if (prime[i])
            s[i] = '*';
    }
    printf("%s", s);
    return 0;
}

• Time Complexity: O(n log log n)
• Space Complexity: O(n)

Đây là cách tiếp cận tối ưu hơn. Thay vì kiểm tra tính nguyên tố cho mỗi số, ta precompute (tính trước) tất cả các số nguyên tố nhỏ hơn hoặc bằng độ dài xâu tối đa (1000) bằng thuật toán Sàng Eratosthenes. Hàm sieve chạy trong O(n log log n). Sau đó, ta chỉ cần duyệt mảng và thay thế các ký tự tại vị trí prime[i] == 1. Độ phức tạp tổng thể là O(n log log n) cho việc xử lý.

Cách Tối ưu hóa Sàng (C++ style)

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

const int MAX = 1005;
bool isPrime[MAX];

void sieve() {
    fill(isPrime, isPrime + MAX, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i < MAX; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < MAX; j += i)
                isPrime[j] = false;
        }
    }
}

int main() {
    sieve();
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        if (isPrime[i]) {
            s[i] = '*';
        }
    }
    cout << s;
    return 0;
}

• Time Complexity: O(N log log N)
• Space Complexity: O(N)

Sử dụng C++ với vector hoặc mảng boolean và hàm fill để làm cho code sạch hơn. Logic sàng vẫn giữ nguyên. Đây là cách làm chuẩn trong lập trình thi đấu khi xử lý bài toán liên quan đến các số nguyên tố trong khoảng giới hạn nhỏ.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán chia làm 2 phần chính: kiểm tra/chỉ định các số nguyên tố và thao tác trên xâu.
• Với giới hạn độ dài xâu nhỏ (1000), thuật toán sàng (Sieve) là cách hiệu quả nhất về tổng thể vì nó tránh việc lặp lại kiểm tra các số giống nhau.
• Chỉ số trong bài toán là 0-based (bắt đầu từ 0).

Lỗi thường gặp

• Quên kiểm tra các trường hợp đặc biệt của số nguyên tố (số 0, 1, số âm) trong hàm kiểm tra riêng lẻ.
• Sử dụng gets() có thể gây tràn bộ đệm nếu không kiểm soát độ dài, scanf() hoặc cin an toàn hơn.
• Độ phức tạp O(n*sqrt(n)) có thể chậm nếu n lớn hơn 1000 (ví dụ lên tới 10^5), nhưng với n=1000 thì vẫn chạy tốt.