Blog entries - Codeforces

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
KeFan Dong	KFDong	China	First Participation
Zhizhou Ren	Stilwell	China	First Participation
Wu Zuofan	brandnewnode	China	First Participation
Ce Jin	jcvb	China	First Participation
Marin Kisic	mkisic	Croatia	First Participation
Adrian Beker	abeker	Croatia	First Participation
Vilim Lendvaj	vilim_l	Croatia	First Participation
Domagoj Bradac	DBradac	Croatia	2015
Ernesto David Peña Herrera	Ernestico	Cuba	First Participation
Filip Bialas	f.bialas	Czech Republic	2015
Richard Hladík	RiHL	Czech Republic	First Participation
Ronald Luc	—	Czech Republic	First Participation
Václav Volhejn	-Wave-	Czech Republic	First Participation
Michael José Gonzáles Bardales	Mjgonzales	Dominican Republic	2015
Kelvin Xavier García Tiburcio	xavier	Dominican Republic	First Participation
Ahmed ElBatanony	ElBatanony	Egypt	First Participation
Ayman AbdALLAH	—	Egypt	First Participation
Mahmoud Badawy	mahmoudbadawy	Egypt	First Participation
Sherif Nafee	Sh1co	Egypt	First Participation
Andres Unt	.I.	Estonia	2014 — 2015
Oliver Nisumaa	SLLN	Estonia	2015
Toomas Tennisberg	toomas	Estonia	2015
Kristjan Kongas	kkongas	Estonia	First Participation
Juha Harviainen	Kuha	Finland	First Participation
Hannes Ihalainen	Hansuzu	Finland	First Participation
Pietari Kaskela	eXeP	Finland	First Participation
Kalle Luopajärvi	kllp	Finland	2013 — 2014 — 2015
Félix Breton	—	France	First Participation
Théophane Vallaeys	—	France	2015
Thomas Sepulchre	—	France	2015
Arthur Léonard	Arturgo	France	2014 — 2015
Malvika Raj Joshi	a0666	India	2014 — 2015
Rajat De	rajat1603	India	First participation
Sampriti Panda	sampriti	India	First participation
Srijon Mukherjee	—	India	First participation
Stacia Edina Johanna	—	Indonesia	2015
Sergio Vieri	—	Indonesia	First participation
Kwee Lung Sin	Klungs	Indonesia	First participation
Muhammad Yusuf Sholeh	yusufsholeh	Indonesia	First participation
Ali Bahjati	LiTi	Iran	2015
AmirMohammad Dehghan	PrinceOfPersia	Iran	First participation
Arash Mahmoudian	Reyna	Iran	First participation
SeyedParsa Mirtaheri	SeyedParsa	Iran	First participation
Liran Markin	markin2000	Israel	2015
Noam Tashma	—	Israel	First participation
Ron Solan	—	Israel	First participation
Tomer Adar	Tomer.Adar	Israel	First participation
Takuya Inoue	yokozuna57	Japan	2015
Riku Kawasaki	maroonrk	Japan	First Participation
Yuta Takaya	yutaka1999	Japan	2014 — 2015
Takahiro Masuda	namonakiaccount	Japan	2015
Amangeldi Zhusubaliev	bktl4ever	Kyrgyzstan	First participation
Arsen Kasymov	AcPlusOne	Kyrgyzstan	First participation
Azret Kenzhaliev	Azret	Kyrgyzstan	2015
Bolot Bekbolotov	bolot.bekbolotov	Kyrgyzstan	First participation
Aleksejs Popovs	popoffka	Latvia	2011 — 2012 — 2013 — 2014 — 2015
Aleksandrs Zajakins	Sanja	Latvia	First Participation
Ingus Jānis Pretkalniņš	Ingus	Latvia	2014 — 2015
Daniels Keziks	DKezik	Latvia	First Participation
Dimitar Bajraktarov	whitewind664	Macedonia	2015
Dushan Terzic	dusante1	Macedonia	First Participation
Nikola Stojkoski	nikolastojkoski	Macedonia	First Participation
Vladimir Maksimovski	ReaLNero	Macedonia	First Participation
Zi Song Yeoh	zscoder	Malaysia	First Participation
Jen Khai Yew	jenkhai	Malaysia	2015
Jia Jen Ng	tempeh	Malaysia	2014 — 2015
Uday Patel	dtb_oods	Malaysia	First Participation
Marcel Bezdrighin	please_delete_account	Moldova	2014 — 2015
Mihail Tarigradschi	ThatMathGuy	Moldova	2015
Gabriel Cojocaru	I_Love_Tina	Moldova	First Participation
Daniel Grosu	explodingking	Moldova	First Participation
Christopher Brown	—	New Zealand	2014 — 2015
Jonathan Khoo	Sosunser	New Zealand	2015
Chris Jung	xenoframium	New Zealand	First Participation
Chuanye Chen	andrewchen	New Zealand	First Participation
Chibuoyim Faith Wilson Ogbonna	ogbonnachibuoyim12	Nigeria	2015
Lesi Bright	—	Nigeria	First Participation
Tanitoluwa Adebayor	—	Nigeria	First Participation
Peter Achimugo	—	Nigeria	First Participation
Robin Yu	robinyu	Philippines	2015
Farrell Wu	wfe2017	Philippines	First Participation
Maded Batara	—	Philippines	First Participation
Ian Palabasan	pocavreportgroup	Philippines	2015
Mateusz Radecki	Radewoosh	Poland	First Participation
Paweł Burzynski	pawelek1	Poland	First Participation
Juliusz Pham	a.piasta	Poland	First Participation
Jarek Kwiecień	yarek	Poland	2014 — 2015
Hyunsoo Kim	khsoo01	Republic of Korea	First Participation
Gyuho Suh	WilliamGyuhoSuh	Republic of Korea	First Participation
Seungwon Shin	Namnamseo	Republic of Korea	First Participation
Jaehyun Koo	ko_osaga	Republic of Korea	2015
Andrei Costin Constantinescu	Andrei1998	Romania	First Participation
Costin Andrei Oncescu	geniucos	Romania	First Participation
Andrei Popa	AndreiNet	Romania	2015
Radu Muntean	heracle	Romania	First Participation
Vladislav Makeev	V--o_o--V	Russia	2015
Mikhail Putilin	SpyCheese	Russia	2015
Stanislav Naumov	josdas	Russia	First Participation
Grigory Reznikow	vintage_Vlad_Makeev	Russia	First Participation
Denis Solonkov	solonkovda	Russia	First Participation — Unofficial (Host Team)
Alexandra Drozdova	demon1999	Russia	First Participation — Unofficial (Host Team)
Mikhail Anoprenko	manoprenko	Russia	First Participation — Unofficial (Host Team)
Askhat Sakhabiev	super_azbuka	Russia	First Participation — Unofficial (Host Team)
Nenad Bauk	fifiman	Serbia	First Participation
Dušan Živanović	zDule98	Serbia	2015
Luka Vukelić	—	Serbia	First Participation
Nikola Spasić	NNSpasic	Serbia	First Participation
Zhang Guangxuan	zhangguangxuan99	Singapore	First Participation
Pang Wen Yuen	pwypeanut	Singapore	2015
Clarence Chew	—	Singapore	First Participation
Jacob Por Loong Teo	jacobtpl	Singapore	2015
Peter Ralbovský	peto159	Slovakia	2013 — 2014 — 2015
Samuel Sládek	samo98	Slovakia	2015
Michal Sládeček	misoxxx	Slovakia	2015
Paulína Smolárová	paulinia	Slovakia	First Participation
Jan Olivetti Auladell	OneStone	Spain	First Participation
Jordi Calstellví Foguet	jcastellvi	Spain	2015
Jordi Rodríguez Manso	JordiR	Spain	First Participation
Miquel Ortega Sánchez-Colomer	metatron	Spain	2015
Joakim Blikstad	Xylofo	Sweden	2014 — 2015
Fredrik Hernqvist	Freda	Sweden	2015
Karl Lundstig	lundstig	Sweden	2015
David Wärn	_h_	Sweden	2015
Mahmoud Hassan	tweety	Syria	First Participation
Besher Massri	besher	Syria	2015
Muhammed Dwik	Bug	Syria	2015
Samir Aldroubi	Sgauwjwjj	Syria	First Participation
Ta Jui Ho	darry140	Taiwan	First Participation
Bo Shi Yu	fsps60312	Taiwan	First Participation
Jui Nan Yen	gkevinyen5418	Taiwan	First Participation
Hao Cheng Yang	howard41436	Taiwan	First Participation
Farhod Farmon	Farhod	Tajikistan	First Participation
Nodir Daminov	Nodir.Daminov	Tajikistan	2015
Nozim Safarov	deleteeeeeeeeed	Tajikistan	First Participation
Farrukh Karimov	Barsic	Tajikistan	First Participation
Adem Khachnaoui	ademkhachnaoui	Tunisia	2015
Mohamed Fadhel Omar	baal-hammon	Tunisia	2015
Ahmed Rekik	rekikahmed	Tunisia	First Participation
Ahmed Selmi	ahmedselmi	Tunisia	First Participation
Mustafa Erdem Kirez	kalimm	Turkey	First Participation
Murat Ekici	muratt	Turkey	First Participation
Osman Orhan Uysal	osmanorhan	Turkey	First Participation
Yasin Kaya	ykaya	Turkey	First Participation
Bayram Guvanjov	bayram98	Turkmenistan	2014
Bekmyrat Atayev	Bekmyrat.A	Turkmenistan	First Participation
Kerim Kochekov	Kerim.K	Turkmenistan	First Participation
Perman Atayev	PermanAtayev	Turkmenistan	First Participation
Aslandukov Matvey	BigBag	Ukraine	2015
Tsypko Anton	arsijo	Ukraine	First Participation
Machula Maksym	mHuman	Ukraine	First Participation
Minakov Stanislav	stas99	Ukraine	First Participation
Daniel Chiu	waterfalls	United States of America	2015
Calvin Lee	negativebplusorminus	United States of America	First Participation
Lawrence Li	lawrenceli	United States of America	First Participation
Dhruv Rohatgi	pacu	United States of America	First Participation
Phan Duc Nhat Minh	minh141198	Vietnam	2015
Pham Cao Nguyen	natsukagami	Vietnam	First Participation
Le Quang Tuan	goodthingstaketime_._	Vietnam	First Participation
Tran Tan Phat	tanphatls987	Vietnam	First Participation

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	SecondThread	150
8	-is-this-fft-	149
9	pajenegod	145
10	BledDest	144

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