Skip to content

🎲 Случайни числа и Рандомизация (Randomization)

🎯 Въведение

Генерирането на качествени случайни числа е критично важно за много алгоритми: рандомизирани структури от данни (Treaps), хеширане, Monte Carlo симулации и стрес-тестове. В състезателното програмиране рандомизацията може да превърне детерминистичен алгоритъм с най-лош случай \(O(N^2)\) в алгоритъм с очаквано време \(O(N \log N)\).

Случайността не е само за статистика - тя е мощен инструмент за: - Избягване на специално конструирани тестове (anti-hash) - Балансиране на структури от данни (Treap, Skip List) - Рандомизирани алгоритми (QuickSort, Karger's Min Cut) - Вероятностни структури (Bloom Filter, HyperLogLog) - Стрес-тестване на решения

1. Защо rand() е лош избор?

Традиционната C функция rand() (от <cstdlib>) има няколко сериозни проблема: 1. Малък обхват: RAND_MAX често е само 32767 (SHRT_MAX = \(2^{15}-1\)). Ако ви трябва число до \(10^9\), формулата rand() % N е безполезна и дава силно изкривено разпределение. 2. Лошо разпределение: Остатъкът от деление (%) внася "bias" (изкривяване), ако RAND_MAX не се дели точно на \(N\). Например, ако RAND_MAX = 32767 и искаме число от 0 до 10000, някои числа ще излизат по-често от други. 3. Предвидимост: Линейният конгруентен генератор (LCG), който стои зад rand(), е статистически слаб. Последователността може да бъде предвидена след няколко наблюдения. 4. Липса на thread-safety: В многонишкови програми rand() не е thread-safe.

Пример за проблема с bias:

// ЛОШО: Неравномерно разпределение
int bad_random(int n) {
    return rand() % n;  // Bias ако RAND_MAX % n != n-1
}

// Защо е bias?
// Ако RAND_MAX = 32767 и n = 10000:
// Числата 0-767 ще излизат по 4 пъти, а 768-9999 само по 3 пъти

2. Модерният подход: C++11 <random>

Библиотеката <random> въвежда генератора Mersenne Twister, който е индустриален стандарт за ненаучни приложения.

2.1. Генератор (mt19937)

Генерира 32-битови числа с огромен период (\(2^{19937}-1\)). За 64-битови числа използвайте mt19937_64.

2.2. Seed (Начална стойност)

Ако не зададете seed, генераторът ще дава една и съща редица всеки път (полезно за дебъгване, вредно за submit). Най-добрият начин за seed в състезания е комбинация от време и адрес в паметта (за да се избегнат хакове при Codeforces).

#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <algorithm>

using namespace std;

// Инициализация на висококачествен генератор
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// За 64-битови числа:
// mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());

// Помощна функция за диапазон [L, R]
int get_rand(int l, int r) {
    uniform_int_distribution<int> dist(l, r);
    return dist(rng);
}

int main() {
    // 1. Генериране на число
    cout << "Random [1, 100]: " << get_rand(1, 100) << endl;

    // 2. Разбъркване на масив (Shuffle)
    vector<int> v = {1, 2, 3, 4, 5};
    // random_shuffle е deprecated! Ползвайте shuffle с вашия rng.
    shuffle(v.begin(), v.end(), rng);

    cout << "Shuffled: ";
    for (int x : v) cout << x << " ";
    cout << endl;

    return 0;
}

3. Приложения на рандомизацията

3.1. Предпазване от "Anti-Hash" тестове

При хеширане на низове (Rolling Hash), ако използвате фиксирана база (напр. 31) и модул, някой може да генерира колизии специално за тях. Решение: Генерирайте случайна база в началото на програмата.

int BASE = get_rand(256, 1000);

3.2. Randomized QuickSort

За да избегнете \(O(N^2)\) при сортиран масив, избирайте пивота на случаен принцип. std::sort обикновено се грижи за това, но ако пишете свой QuickSelect (за k-тия елемент), е задължително.

3.3. Treap (Cartesian Tree)

Декартовото дърво използва случайни приоритети за всеки възел, за да поддържа дървото балансирано с висока вероятност (\(O(\log N)\)).

3.4. Стрес-тестове (Generator)

Когато решението ви дава "Wrong Answer" и не виждате защо: 1. Напишете "бавно", но сигурно решение (Brute force). 2. Напишете генератор на случайни тестове (използвайки mt19937). 3. Пуснете цикъл, който генерира тест, пуска двете решения и сравнява резултатите.

4. Разпределения (Distributions)

Освен uniform_int_distribution (равномерно), <random> поддържа: * uniform_real_distribution<double>(0.0, 1.0): За вероятности. * normal_distribution: Гаусово разпределение (по-рядко в състезания). * bernoulli_distribution: Ези/тура с вероятност \(p\).

Примери за различни разпределения:

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// Реални числа от 0.0 до 1.0
uniform_real_distribution<double> prob_dist(0.0, 1.0);
double probability = prob_dist(rng);

// Нормално разпределение (Гаусово)
normal_distribution<double> norm_dist(0.0, 1.0);  // mean=0, stddev=1
double gaussian_val = norm_dist(rng);

// Bernoulli (монета)
bernoulli_distribution coin(0.5);  // p=0.5
bool heads = coin(rng);

// Експоненциално разпределение
exponential_distribution<double> exp_dist(1.0);
double exp_val = exp_dist(rng);

5. Рандомизирани алгоритми

5.1. QuickSelect с рандомизация

Намиране на k-тия най-малък елемент с очаквана сложност \(O(N)\).

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int partition(vector<int>& arr, int left, int right) {
    // Избираме случаен pivot
    uniform_int_distribution<int> dist(left, right);
    int pivotIndex = dist(rng);
    swap(arr[pivotIndex], arr[right]);

    int pivot = arr[right];
    int i = left - 1;

    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[right]);
    return i + 1;
}

int quickSelect(vector<int>& arr, int left, int right, int k) {
    if (left == right) return arr[left];

    int pivotIndex = partition(arr, left, right);

    if (k == pivotIndex) {
        return arr[k];
    } else if (k < pivotIndex) {
        return quickSelect(arr, left, pivotIndex - 1, k);
    } else {
        return quickSelect(arr, pivotIndex + 1, right, k);
    }
}

5.2. Reservoir Sampling

Избиране на случаен елемент от поток с неизвестна дължина.

// Избираме k елемента от поток
vector<int> reservoirSample(vector<int>& stream, int k) {
    vector<int> reservoir(k);

    // Запълваме първите k елемента
    for (int i = 0; i < k; i++) {
        reservoir[i] = stream[i];
    }

    // Обработваме останалите елементи
    for (int i = k; i < stream.size(); i++) {
        uniform_int_distribution<int> dist(0, i);
        int j = dist(rng);

        if (j < k) {
            reservoir[j] = stream[i];
        }
    }

    return reservoir;
}

5.3. Monte Carlo метод

Приблизително изчисление чрез случайни симулации.

// Приблизително изчисление на PI
double estimatePi(int samples) {
    int inside_circle = 0;
    uniform_real_distribution<double> dist(0.0, 1.0);

    for (int i = 0; i < samples; i++) {
        double x = dist(rng);
        double y = dist(rng);

        if (x*x + y*y <= 1.0) {
            inside_circle++;
        }
    }

    return 4.0 * inside_circle / samples;
}

6. Стрес-тестване (Stress Testing)

Един от най-мощните инструменти за откриване на грешки.

6.1. Структура на стрес-тест

#include <iostream>
#include <cassert>
#include <random>
#include <chrono>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// Вашето решение (може да има бъгове)
int fastSolution(vector<int>& arr) {
    // ...
}

// Бавно, но сигурно решение (brute force)
int slowSolution(vector<int>& arr) {
    // ...
}

// Генератор на случайни тестове
vector<int> generateTest(int n, int maxVal) {
    vector<int> arr(n);
    uniform_int_distribution<int> dist(1, maxVal);

    for (int i = 0; i < n; i++) {
        arr[i] = dist(rng);
    }

    return arr;
}

int main() {
    int testCount = 1000;

    for (int test = 1; test <= testCount; test++) {
        // Генерираме случаен тест
        int n = rng() % 100 + 1;  // n от 1 до 100
        vector<int> arr = generateTest(n, 1000);

        // Пускаме двете решения
        int fast = fastSolution(arr);
        int slow = slowSolution(arr);

        // Сравняваме
        if (fast != slow) {
            cout << "WA на тест " << test << endl;
            cout << "n = " << n << endl;
            cout << "arr = ";
            for (int x : arr) cout << x << " ";
            cout << endl;
            cout << "Fast: " << fast << ", Slow: " << slow << endl;
            return 1;
        }

        if (test % 100 == 0) {
            cout << "Passed " << test << " tests" << endl;
        }
    }

    cout << "All tests passed!" << endl;
    return 0;
}

6.2. Генератор на различни случаи

// Генератор за низове
string randomString(int length, string alphabet = "abcdefghijklmnopqrstuvwxyz") {
    string result;
    uniform_int_distribution<int> dist(0, alphabet.size() - 1);

    for (int i = 0; i < length; i++) {
        result += alphabet[dist(rng)];
    }

    return result;
}

// Генератор за дървета
vector<pair<int, int>> randomTree(int n) {
    vector<pair<int, int>> edges;

    for (int i = 2; i <= n; i++) {
        uniform_int_distribution<int> dist(1, i - 1);
        int parent = dist(rng);
        edges.push_back({parent, i});
    }

    return edges;
}

// Генератор за графи
vector<pair<int, int>> randomGraph(int n, int m) {
    set<pair<int, int>> edges_set;
    uniform_int_distribution<int> dist(1, n);

    while (edges_set.size() < m) {
        int u = dist(rng);
        int v = dist(rng);
        if (u != v) {
            edges_set.insert({min(u, v), max(u, v)});
        }
    }

    return vector<pair<int, int>>(edges_set.begin(), edges_set.end());
}

🏁 Заключение

Забравете за rand() и srand(time(0)). Използвайте mt19937 за бързина, качество и надеждност.

Резюме на ключовите точки:

  1. Винаги използвайте mt19937: По-добър период, по-добро разпределение, по-трудно предвидим
  2. Seed правилно: Време + адрес или random_device за криптографски случаен seed
  3. Използвайте distributions: uniform_int_distribution вместо % за правилно разпределение
  4. Shuffle с std::shuffle: Винаги подавайте вашия rng като трети параметър
  5. Стрес-тествайте: Най-добрият начин да намерите бъгове преди judge-а
  6. Рандомизирайте критични параметри: Хеш бази, pivot-и в QuickSort, приоритети в Treap

Често срещани грешки:

// ГРЕШНО: Използване на rand()
int x = rand() % n;

// ПРАВИЛНО: Използване на mt19937
uniform_int_distribution<int> dist(0, n-1);
int x = dist(rng);

// ГРЕШНО: Лош seed
mt19937 rng(1);  // Константен seed

// ПРАВИЛНО: Добър seed
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// ГРЕШНО: Deprecated shuffle
random_shuffle(v.begin(), v.end());

// ПРАВИЛНО: Модерен shuffle
shuffle(v.begin(), v.end(), rng);

Приложения в състезанията:

  1. Anti-hash защита: Рандомизирайте константи в хеш функции
  2. Treap: Рандомизирани приоритети за балансиране
  3. QuickSelect/QuickSort: Рандомизиран pivot
  4. Геометрия: Малки случайни пертурбации за избягване на edge cases
  5. Stress testing: Автоматично генериране на тестове

Допълнителни ресурси:

  • C++ Reference: <random> библиотека
  • "The Art of Computer Programming" Vol. 2 (Knuth) - Семиналната книга за random numbers
  • Codeforces блогове за anti-hash техники
  • Примери за стрес-тестване в GitHub repos

Помнете: Рандомизацията не е замяна за правилен алгоритъм, но може да превърне добър алгоритъм във великолепен или да ви спаси от злонамерени тестове!