Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	165
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

tweety's blog

O(1) runtime prime checking

By tweety, history, 4 years ago, In English

Hello fellow people of Codeforces

I hope everyone doing well in these uncertain and unprecedented times. I wanted to share this cool C++20 trick that I learned recently.

Check out this cool implementation of is_prime(n) to test if n integer is prime in O(1) runtime (without any runtime precomputation!)

bool is_prime(int n);

#include <iostream>
#include <cstdlib>
#include <ctime>

const int MAXN = 100000;

template<int N>
struct Sieve {
    bool is_prime[N];
    constexpr Sieve() : is_prime() {
        for (int i = 2; i < N; i++) {
            is_prime[i] = true;
        }
        for (int i = 2; i < N; i++) if (is_prime[i]) {
            for (int j = 2 * i; j < N; j += i) {
                is_prime[j] = false;
            }
        }
    }
};

template<Sieve<MAXN> s>
struct SieveWrapper {
    static bool get(int n) {
        return s.is_prime[n];
    }
};

bool is_prime(int n) {
    return SieveWrapper<Sieve<MAXN>{}>::get(n);
}

/*
bool slow_is_prime(int n) {
    return (Sieve<MAXN>{}).is_prime_[n];
}
*/
    
int main() {
    auto t1 = time(NULL);
    
    // compute answer for 1000 random integers
    int ans = 0;
    for (int i = 0; i < 1000; i++) {
        ans += is_prime(rand() % MAXN);
    }

    auto t = time(NULL) - t1;

    std::cout << "Answer: " << t << ". Elapsed time: " << t << "s" << std::endl;
}

This code computes primes up to MAXN during compilation and stores them in a table right in the compiled binary. On a runtime is_prime(n) call, it queries the compiled table to find the result. Check this compiled assembly to find the sieve mask baked in the binary: https://godbolt.org/z/G6o84x.

This trick is achieved by passing the constructed Sieve as a template argument, which is always evaluated on compile-time. If you compile this code using older C++ standard, you will get the error:

error: a non-type template parameter cannot have type 'Sieve<MAXN>'

However, since C++20, non-type template parameter can have any LiteralType (note). In short, it is possible to compile-time compute an instance of any class with a constexpr constructor.

Here is a time test of compile-time vs run-time sieve computation:

main.cpp

#include <iostream>
#include <vector>
#include <chrono>
#include <cstdlib>

using namespace std;

const int MAXN = 100000;

template<int N>
struct Sieve {
    bool is_prime[N];
    constexpr Sieve() : is_prime() {
        for (int i = 2; i < N; i++) {
            is_prime[i] = true;
        }
        for (int i = 2; i < N; i++) if (is_prime[i]) {
            for (int j = 2 * i; j < N; j += i) {
                is_prime[j] = false;
            }
        }
    }
};

template<Sieve<MAXN> s>
struct SieveWrapper {
    static bool get(int n) {
        return s.is_prime[n];
    }
};

bool fast_is_prime(int n) {
    return SieveWrapper<Sieve<MAXN>{}>::get(n);
}


bool slow_is_prime(int n) {
    return (Sieve<MAXN>{}).is_prime[n];
}


const int reps = 1000;
int main() {
    vector<int> numbers(reps);
    for (int i = 0; i < reps; i++) {
        numbers[i] = rand() % MAXN;
    }

    int ans = 0;
    auto t1 = chrono::high_resolution_clock::now();
    for (auto &n : numbers) {
        ans += slow_is_prime(n);
    }
    auto t2 = chrono::high_resolution_clock::now();
    cout << "Runtime ans: " << ans << ". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t2 - t1).count() << endl;

    ans = 0;
    t1 = chrono::high_resolution_clock::now();
    for (auto &n : numbers) {
        ans += fast_is_prime(n);
    }
    t2 = chrono::high_resolution_clock::now();
    cout << "Compiletime ans: " << ans << ". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t2 - t1).count() << endl;
}

Compiled with GCC 9.3.0 using the command g++ -std=c++2a main.cpp. This is the execution output on my laptop:

Runtime ans: 90. Elapsed (ms): 1008
Compiletime ans: 90. Elapsed (ms): 0

Of course no one re-computes sieve 1000 times, this is done here for the sole purpose of showing that the algorithm is not computing sieve in run time 1000 times.

While such tricks won't help you cheat pass Codeforces problems, they might will help your submission stand out for fastest runtimes. Hope you found this interesting!

Name	CF Handle	Country	Previous IOIs
Román Castellarin	ponysalvaje	Argentina	2013 — 2014 — 2015
Maximiliano Redigonda	mredigonda	Argentina	2015
Gianni Weinand	Weheineman	Argentina	2014 — 2015
Gastón Fontenla	gfonn	Argentina	First Participation
Mushegh Shahinyan	MyLeg	Armenia	2014 — 2015
Levon Muradyan	_LeMur_	Armenia	First Participation
Ashot Matevosyan	ashmat98	Armenia	First Participation
Karen Mkrtumyan	KARM	Armenia	First Participation
Jerry Mao	jerry	Australia	2015
Declan McDonnell	DXsmiley	Australia	2015
Belinda Shi	BeeShi	Australia	First Participation
Richard Gong	gongy	Australia	First Participation
Florian Leimgruber	fleimgruber	Austria	2014 — 2015
Miklós Horváth	—	Austria	First Participation
Simon Lehner-Dittenberger	—	Austria	2015
Stefan Kurzbauer	—	Austria	First Participation
Jubayer Rahman Nirjhor	Alpha_Q	Bangladesh	First Participation
Syed Rubab Redwan	rubabredwan	Bangladesh	First Participation
Ruhan Habib	ruhan.habib39	Bangladesh	First Participation
Tasmeem Reza	Bruteforceman	Bangladesh	First Participation
Ilya Medyanikov	Ferathorn	Belarus	2015
Fedar Karabeinikau	Mediocrity	Belarus	2014
Mikhail Natalevich	minthe	Belarus	First Participation
Artur Petukhouski	Arthur	Belarus	First Participation
Damien Galant	damien_g	Belgium	2014 — 2015
Corentin Simon	azercoco	Belgium	First Participation
Bruno Ploumhans	BrunoPloumhans	Belgium	First Participation
Ruben Van Dijck	—	Belgium	First Participation
Rogério Junior	rogerioagjr	Brazil	First Participation
Pedro Henrique	Pedrohso	Brazil	First Participation
Victor Agnez	victoragnez	Brazil	First Participation
Lucca Siaudzionis	luccasiau	Brazil	2015
Alexander Crustev	perchema	Bulgaria	First Participation
Encho Mishinev	Enchom	Bulgaria	2013 — 2014 — 2015
Hristo Venev	mustrumr	Bulgaria	2012 — 2013 — 2014 — 2015
Daniel Atanasov	—	Bulgaria	2015
Yikuan Li	FatalEagle	Canada	2014 — 2015
Farbod Yadegarian	NoWoDeYo	Canada	2015
Kevin Sun	ksun48	Canada	First Participation
Jeffrey Xiao	jeffrey.xiao	Canada	First Participation

tweety's blog

Application 1: Counting the number of ways for reaching a vertex

Solution

Application 2: Shortest path with a specified number of steps

Solution

Application 3: Nth Fibonacci number in O(log n)

Solution