Frequently Asked Questions about Algorithmic Competitions

`memset` Gets TLE#

const int N = 1e8 + 10;
int a[N];

int main()
{
    int t; cin >> t;
    while (t--) {
        memset(a, 0, sizeof a);
        ...
    }
}

The memset function fills the entire array, but when dealing with multiple sets of data, filling a every time will obviously result in a TLE.

There are two possible solutions:

Abandon global variables

The biggest difficulty in abandoning global variables is the problem of variable passing between functions. Generally, a function can add a parameter, but it is inconvenient for dfs. Consider using lambda to implement dfs.
Abandon memset and use fill() or assign()

As long as unnecessary operations are eliminated and the number of operations is within a reasonable range to meet the needs.

I personally prefer the approach of abandoning global variables. To implement this operation for general functions, we use pass-by-reference. Below is an analysis of the recursive lambda approach:

Recursive `lambda`#

Using `self` -- Fastest#

auto dfs1 = [&](auto &self, int u, int p) -> int {
        int ret = 1;
        for(auto v : adj[u]) {
            if(v != p)
                ret += self(self, v, u);
        }
        return ret;
    };

Using self to refer to the expression itself, specifying the direction of deduction for auto, and using a reference to avoid copying.

Using `std::function<>` -- Most convenient#

This template class is used to wrap any callable object, including function pointers, function objects, member function pointers, lambda expressions, etc.

#include <functional>
#include <iostream>

void foo(int x) {
    std::cout << "foo(" << x << ")" << std::endl;
}

int main() {
    std::function<void(int)> f1 = foo;
    f1(42);
    
    std::function<void()> f2 = []() { std::cout << "lambda" << std::endl; };
    f2();
    
    struct Bar {
        void operator()(int x) const {
            std::cout << "Bar::operator()(" << x << ")" << std::endl;
        }
    };
    std::function<void(int)> f3 = Bar();
    f3(123);
    
    return 0;
}

The principle is to pass the function to the class internally. However, there is a large overhead in creating a large number of std::function<> for recursion.

Approach:

function<int(int, int)> dfs2 = [&](int u, int p) {
        int ret = 1;
        for(auto v : adj[u]) {
            if(v != p) {
                ret += dfs2(v, u);
            }
        }
        return ret;
    };

Benchmark#

int main() {
    int n; cin >> n;
    vector<vector<int>> adj(n);
    for(int i = 0; i < n - 1; i++) adj[i].push_back(i + 1);

    auto dfs1 = [&](auto &self, int u, int p) -> int {
        int ret = 1;
        for(auto v : adj[u]) {
            if(v != p)
                ret += self(self, v, u);
        }
        return ret;
    };

    function<int(int, int)> dfs2 = [&](int u, int p) {
        int ret = 1;
        for(auto v : adj[u]) {
            if(v != p) {
                ret += dfs2(v, u);
            }
        }
        return ret;
    };

    cout << fixed << setprecision(10);

    auto start = clock();
    int res1 = dfs1(dfs1, 0, -1);
    cout << res1 << '\n';
    cout << "Passing self: " << (double) (clock() - start) / CLOCKS_PER_SEC << '\n';

    start = clock();
    int res2 = dfs2(0, -1);
    cout << res2 << '\n';
    cout << "std::function: " << (double) (clock() - start) / CLOCKS_PER_SEC << '\n';

    assert(res1 == res2);
    return 0;
}

/* ---- results ---- */

n = 1e5
Passing self: 0.0000000000
std::function: 0.0180000000

n = 1e6
Passing self: 0.0310000000
std::function: 0.0780000000

n = 2e6
Passing self: 0.0620000000
std::function: 0.1750000000

YangWithU