Pre-computation and hashing are powerful techniques in competitive programming that help optimize solutions and reduce time complexity. Here's an overview of these concepts:

Pre-Computation Techniques

Pre-computation involves computing certain values or data structures before the main part of the algorithm begins. This can help reduce the complexity of operations performed multiple times within the main algorithm.

Prefix Sums

Factorial Pre-computation

Pre-compute factorials to quickly compute combinations or permutations.

#include <iostream>
#include <vector>
#define MOD 1000000007

std::vector<int> computeFactorials(int n) {
    std::vector<int> factorials(n + 1, 1);
    for (int i = 2; i <= n; ++i) {
        factorials[i] = (1LL * factorials[i - 1] * i) % MOD;
    }
    return factorials;
}

int main() {
    int n = 10;
    std::vector<int> factorials = computeFactorials(n);

    std::cout << "Factorial of 5: " << factorials[5] << std::endl; // Output: 120
    return 0;
}

Hashing

Hashing is a technique to map data of arbitrary size to fixed-size values (hash values). Hash tables and hash maps are data structures that use hashing for fast data retrieval.

Hash Map for Frequency Count

#include <iostream>
#include <unordered_map>
#include <vector>

std::unordered_map<int, int> frequencyCount(const std::vector<int>& arr) {
    std::unordered_map<int, int> freqMap;
    for (int num : arr) {
        freqMap[num]++;
    }
    return freqMap;
}

int main() {
    std::vector<int> arr = {1, 2, 2, 3, 3, 3, 4};
    std::unordered_map<int, int> freqMap = frequencyCount(arr);

    for (const auto& entry : freqMap) {
        std::cout << "Element " << entry.first << " occurs " << entry.second << " times." << std::endl;
    }
    return 0;
}

Rolling Hash for String Matching

The rolling hash technique is useful for string matching problems, like finding a substring in a string.

#include <iostream>
#include <string>
#include <vector>

const int BASE = 31;
const int MOD = 1000000007;

std::vector<int> computeHashes(const std::string& s) {
    std::vector<int> hashValues(s.size() + 1, 0);
    int hashValue = 0;
    int basePower = 1;

    for (size_t i = 0; i < s.size(); ++i) {
        hashValue = (1LL * hashValue * BASE + (s[i] - 'a' + 1)) % MOD;
        hashValues[i + 1] = hashValue;
        basePower = (1LL * basePower * BASE) % MOD;
    }

    return hashValues;
}

int getSubstringHash(const std::vector<int>& hashValues, int left, int right) {
    int hashValue = hashValues[right + 1] - (1LL * hashValues[left] * pow(BASE, right - left + 1) % MOD);
    if (hashValue < 0) {
        hashValue += MOD;
    }
    return hashValue;
}

int main() {
    std::string s = "abracadabra";
    std::vector<int> hashValues = computeHashes(s);

    int hash1 = getSubstringHash(hashValues, 0, 2); // Hash of "abr"
    int hash2 = getSubstringHash(hashValues, 7, 9); // Hash of "abr"

    std::cout << "Hash of first 'abr': " << hash1 << std::endl;
    std::cout << "Hash of second 'abr': " << hash2 << std::endl;
    std::cout << (hash1 == hash2 ? "Hashes match" : "Hashes do not match") << std::endl;

    return 0;
}

Summary

Pre-Computation

Hashing