| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | maroonrk | 133 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
Hi everyone!
Both onsite editions of OCPC 2026 Summer have now concluded: Hong Kong SAR, China on 8–16 August, and Iași, Romania, on 12–20 September. I'd like to share the results and a few moments from the two sites 😊
This season took the same set of seven ICPC-style contests to City University of Hong Kong and Alexandru Ioan Cuza University of Iași, with remote participation alongside both editions.
Hi everyone!
The OCPC (Osijek Competitive Programming Camp), an award-winning camp for university students preparing for ICPC and other coding competitions, is back this Summer 2026 — this time with two onsite editions:
Both editions are organized by us together with local hosts at each site, and use the same contest set — so you take part in one of them. As a rough guide, the Iași edition is most convenient for teams based in Europe, and Hong Kong for teams in APAC and East Asia — but you are welcome at whichever you prefer. The camp is inspired by the competitive programming camps we attended during our active ICPC years: 7 ICPC-style contests (5 hours, 9–12 problems each), with analysis sessions and days off in between.
Please use this form to register for the camp!
Participation free is completely waived for in-person teams of this site!
Hi everyone!
There are 3 roughly similar problems on Library Checker:
All of them ask us to find $$$c_0, \dots, c_{2^n-1}$$$, where
where $$$\circ$$$ stands for bitwise xor, bitwise and, and "disjoint or" correspondingly.
As of now, my submissions are the fastest one for all 3 problems, and in this blog I'd like to explain how it is achieved.
XOR / AND convolutions are fairly simple, which is why my 30 ms submissions are closely followed by others. However, for subset convolution, my submission uses 94 ms with just 34 MiB, while all other submissions (except the one by Qwerty1232 on the second place, whose approach is similar to mine) use at least 300 ms and 180 MiB each.
If you want to check whether your subset convolution is good, I would suggest trying out 1034E - Little C Loves 3 III. Its constraints are very tight in both time and memory specifically to cut off subset convolution, but an optimal implementation would pass (see e.g. 355217827 by me or 355275135 by Qwerty1232).
Prerequisite: Know how the problems above are solved (e.g. see this blog).
If you are potentially interested in participating in OCPC in person in Summer/Autumn 2026, please fill this form!
Hi everyone!
The 7th OCPC (Winter 2026) has concluded last week, and as usual, I'd like to write a blog with some closing remarks.
Hi everyone!
I was itching to apply SIMD in another problem, and this time my attention picked the following problem:
Library Checker — Enumerate Primes. You are given $$$N$$$, $$$A$$$ and $$$B$$$. Find $$$\pi(N)$$$, and print all $$$p_{kA + B} \leq N$$$.
It is guaranteed that $$$N \leq 5 \cdot 10^8$$$ and that the total number of primes to print is at most $$$10^6$$$.
After some tweaking, I managed (#336744) to reduce my time consumption in this problem to 83 ms and memory consumption to 25 MiB, which makes it a top-1 submission on the Library Checker. For comparison, the top-2 solution (#148169) takes 172 ms and 15 MiB, meaning that what I describe here is a 2x improvement in terms of the running time.
We can also compare it to what appears to be the state of the art of sieving, the primesieve tool. On my laptop, it runs for 27 ms on one thread with $$$n = 5 \cdot10^8$$$, while my program runs for 67 ms, of which 9.5 ms is typically the output. Ignoring the latter part, we can say that it is within 2x from the state of the art at this scale.
Hi everyone!
As you may know, it is often recommended to put these lines in your header:
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
And they're usually great![1] Well, until they aren't. For last 2-3 days I was riddled with the issue that CP-Algorithms Library would perform very well on Library Checker, but whenever I tried to also apply it on Codeforces, it will fail to speed up the code, and sometimes would even make it much slower. As I finally figured out the cause, I'd like to write a blog about it, so that other people don't waste as much time.
Mitigating these issues improved my running time on 1975G - Zimpha Fan Club from 1530 ms in 316602668 to 203 ms in 352602775.
See the "Takeaway" section at the bottom.
Hi everyone!
The OCPC (Osijek Competitive Programming Camp), an award-winning camp for university students to prepare for ICPC and other coding competitions, is back again this winter, on January 24 — February 1, 2026!
The camp is organized by adamant and -is-this-fft- on the premises of the University of Osijek in Osijek, Croatia.
The camp is inspired by various competitive programming camps that we attended during our active years in ICPC, and is aimed to help college students prepare for ICPC regional contests and finals. The camp will consist of 7 ICPC-style contests and 2 days off.
The participation fee for both online and onsite participants is 198€ per team.
Similar to previous camp editions, the fee does not include regular meals, travel or accommodation.
We support and empathize with those affected by the ongoing war in Ukraine, therefore we offer a free participation for affected individuals and teams affiliated with Ukrainian institutions.
Additionally, we would like to offer the following discounts:
We do not require any proof or documentation when using the hardship option, and trust your self-assessment. Nevertheless, we ask you to be mindful when using it, as we still have to rely on participation fees as the baseline for running the camp.
The expected starting time for the contests is 10am CET. For remote participants, it is still a preferred starting time, but we will make accommodations for virtual participation at a later time, when necessary.
Most of our contests are originally developed for the camp. A small number of contests may be based on previous contests that have not been released to the general public. If you have seen some problems of a contest before, you can't participate on that day. We will privately contact participants who might be affected.
After the camp, we will have a silence period during which camp materials will not be released to the public. We ask participants not to discuss the problems in public unless they obtained an explicit permission from contest authors.
If you would like to get a feel of the contests, you can find links to some of the previously published camp contests here.
If you have any questions about the camp, please feel free to send us an email, or join our Discord server!
If you are interested in participating, please fill the form here.
Register before December 14, 2025 to receive an early bird discount!
We ask you to register before January 17, 2026 if you want to participate remotely and before January 10, 2026 if you want to participate in Osijek. If you require a visa, please register as soon as possible, as it might take a few weeks to receive (depending on your location).
If your university or organization has a lively ICPC community that may be interested in attending the camp, and you have some contacts of people in charge (e.g. coaches) we would highly appreciate if you could share some details in a direct message to me. Thanks!
We'd like to thank and praise the authors of the contests in the camp:
You can find more details about contest rules and technical setup on the website.
Finally, we say special thanks to
Hi everyone!
I'd like to announce that ETH Zürich team selection contest has concluded last weekend, and we now uploaded it to the Codeforces gym at Swiss Subregional 2025-2026. The contest was prepared by fedimser, Blackphoenyx, alagorithmet, faden13, boboquack and TecTrixer. It was a 5 hour long contest, intended for individual participation. It was also used by some other Swiss universities, hence the name :)
Thank you very much to Ming_Xu for testing the contest! We hope that the contest will be interesting to Codeforces audience, in particular you may want to try 106170F - Random Maze and 106170H - Möbius Band Coloring that were not solved by anyone during the live contest. Congratulations to the winners:
Hope I correctly matched your names against your Codeforces logins!
Hi everyone!
Just recently, the last mirror of the summer season of OCPC 2025 has concluded. I would like to take this moment to share some of the details and statistics on how it went with the community 😊
Hi everyone!
It was a while since I posted last update about CP-Algorithms. As a general reminder, it is a community project that started off in 2014 by RodionGork as a translation of e-maxx, a Russian go-to resource at the time by e-maxx for learning core competitive programming algorithms. Since then, CP-Algorithms grew quite a lot (which also prompted a rename from original project name e-maxx-eng) and includes a lot of new, original articles, and a lot of translated articles were enhanced and/or extended or even completely rewritten.
In this blog, I would like to share a bunch of updates about the site, to make sure it's still in the collective memory 😅
Since my last post, we have a few new maintainers in the project: kostka spike1236 and mhayter. Welcome on board, everyone!
Also, as a general reminder, we are always on the lookout for new maintainers!
Please reach out to us if you're interested, and let us know of any of your prior experience in technical writing, computer science and competitive programming. We will be happy to expand our team!
Over last year, we had the following new articles:
We also have a few more in the works in the Pull Requests section.
We have launched a Discord server (currently with ~500 members)! You are very welcome to join us here to stay updated about what's going on with the project. Also, please feel free to post any feedback or requests there, and generally have fun!
In particular, you are welcome to use the server for any of the following:
Any constructive suggestions are welcome!
We have launched a donation campaign! CP-Algorithms is ad-free, and run by volunteers. By donating a small amount, you can help us grow and achieve our next goal of establishing monetary bounties for contributors writing new articles. As a thanks, you will be assigned an exclusive patron role in our Discord server, and, depending on the donation amount, a place on our website.
We use Open Source Collective as our fiscal host, so you may be sure that our handling of the donations is as transparent as possible, and they are used strictly to further our (non-profit) goals as a volunteer project.
A mandatory section asking you to help us out as a contributor 😊
Hi everyone!
Every once in a while someone makes a competitive programming Discord server. Today, we're inviting you to join one of them 😊
So, first things first, the big flashy link for those who want to cut to the chase:
Name: GF
Members: 1000+ (and growing!)
Admins: Little_Bunny rewhile defnotmee adamant
Moderators:
| jeroenodb | Dominater069 | tfg | Dragos | BucketPotato | Intellegent |
| meooow | berr | de_sousa | fishy15 | eggag32 | DenjellBoone |
Now that we've taken care of that, let's discuss in more detail!
Our server is called GF (short for Generating Function, or, perhaps, a girlfriend? Who knows!). We identify by these statements:
Some more facts about us:
;gitgud score gets a special shiny role, and Discord nitro subscription for a month as a prize.That said, if you are a Div. 1 user who wants to keep in touch with other coders throughout the world, or simply have a platform for real time contest discussions, you're very welcome to join!
P.S.: We also want to hold a Div. 1 contest on Codeforces, so if you have some nice problem ideas, we'd be happy to chat!
Hi everyone!
OCPC 2025 Summer just concluded for Bucharest and remote participants. I hope everyone involved had lots of fun participating, and ended up learning something new and useful for official competitive programming events.
As it is always extremely tricky to schedule onsite events like this in Summer, I once again ask for your help with determining the best conditions that we can provide to accommodate as much participants as possible.
Historically, OCPC participation, both onsite and remote was smaller in summer than in winter, due to various reasons, including internships, conflicting events, and more. Nevertheless, there is some demand for the event in summer as well, which is why we still want and hope to maintain the current schedule of hosting the event twice a year.
This time around, we had an extra survey about best scheduling for summer, which ended up with majority of pollers indicating that they are only available in a very brief window in June. Such timing, of course, was very tight for us, and as it turned out later, for some of our previous regular participants as well, yet we tried our best to make it work.
Unfortunately, the results were somewhat mixed, which is why we feel the need to once again try to poll opinions for scheduling. We know that there are a lot of factors that can be involved in decision-making process, also beyond just the dates, which is why this time around the poll will be more open-ended and focused on figuring out which factors people care about most when deciding about their attendance.
That being said, we would really appreciate it if you could spare some time to fill the following survey.
The poll is currently primarily intended for those who, under at least some hypothetical circumstances (even if largely different from the way the camp operates now), would consider participating in Europe (this refers to the camp site, not necessarily participant's home location).
Every opinion matters, so please don't hesitate to be direct and bold with us!
Of course, please don't hesitate to, alternatively, reach out to me directly with any input you may have on the matter. I really hope that we can figure something out that will fit as much people as possible together!
Hi everyone!
This blog is not about asymptotic optimization. Refer to this comment for those.
There is a problem on Library Checker that goes as follows:
Many Factorials: You're given $$$n_1,\dots,n_t$$$, where $$$t \leq 10^5$$$. For each $$$i$$$, find $$$n_i! \bmod M$$$, where $$$M = 998\;244\;353$$$.
In this blog, we will learn how to solve this task in 61 ms, without precalc and without FFT. That's right, we will take the dumbest solution we can imagine, and will improve its constant factor until its decent enough. How much decent? Well, let's use the following baseline:
It doesn't do anything fancy, just splits the domain in blocks of length $$$2^{16}$$$, then computes all factorials in naive manner within each block, and uses intermediate computation results to find each particular factorial in $$$O(1)$$$ per input query, for a total runtime of $$$O(M+n)$$$.
The solution above takes 3745 ms, so the final result of 61 ms is a 60x improvement.
Many thanks to Qwerty1232 for useful discussions!
... Probably.
Hi everyone!
As some of you might already know, I don't like NTT. Primary reasons for this are:
But, to my regret, the overwhelming mainstream in modern competitive programming is NTT. Primary reasons are:
There is nothing I can do about the last, but today I'll address the first 3. Optimizing complex FFT was on my mind for quite some time, but I didn't really work on it that much until the blog by Qwerty1232 on optimizing NTT has dropped, which motivated me to actually put some serious effort into this.
In this blog, we will primarily focus on optimizations that are specific to complex arithmetic. Of course, people already mostly know of its challenges, as mentioned above, but it also offers some unique benefits that might alleviate them, and even help get the upper hand in certain cases! My main examples for this:
I would like to express my sincerest thanks to:
Hi everyone!
... And a happy May day!
We are very happy to announce that OCPC (formerly, the Osijek Competitive Programming Camp) is back this Summer, on June 21-29, 2025! While the dates are pretty tight, they appear to be the ones that are most suitable (among all the summer internships, exams, other coding events, etc) for the majority of people who filled the dates questionnaire.
This time, the camp is hosted by the Faculty of Mathematics and Computer Science of the University of Bucharest in Bucharest, Romania and is brought to you by the organizing team of adamant, -is-this-fft- and livlivi.
The camp is inspired by various competitive programming camps that we attended during our active years in ICPC, and is aimed to help college students prepare for ICPC regional contests and finals. The camp will consist of 7 ICPC-style contests and 2 days off.
Before going into further details, we would also like to announce that we expect the following mirror sites this Summer:
India: OCPC with the collaboration of GoForGold and ICPC India will have an onsite mirror for top teams from India, so if you are one of the world finalist or got top rank in this year Asia West Finals and have chances left for world finals then you can join Indian mirror which will be scheduled during the second half of July.
Indonesia: We will also organize a mirror site on the premises of the Bina Nusantara University (BINUS) in Jakarta for people based in the APAC region. This mirror is planned to be held in the late August, shortly before ICPC World Finals.
The mirror sites use the same consest sets, but typically have a different organizing team (for example, this winter, a mirror in Singapore, APAC was organized by errorgorn). As the mirror sites will happen after the European (and online) camp edition, they will be properly announced later on. Mirror sites are primarily intended for onsite participation, so if you are geographically located in the corresponding region (or are willing to go there for the camp), we encourage you to wait for the corresponding announcement.
If you want to participate remotely or in Europe, please register for the Bucharest edition of the camp (the one announced here).
The participation fee for both online and onsite participants is 201€ per team.
Similar to previous camp editions, the fee does not include regular meals, travel or accommodation.
We support and empathize with those affected by the ongoing war in Ukraine, therefore we offer a free participation for affected individuals and teams affiliated with Ukrainian institutions.
The expected starting time for the contests is 10am CEST. For remote participants, it is still a preferred starting time, but we will make accommodations for virtual participation at a later time, when necessary.
Most of our contests are originally developed for the camp. A small number of contests may be based on previous contests that have not been released to the general public. If you have seen some problems of a contest before, you can't participate on that day. We will privately contact participants who might be affected.
After the camp, we will have a silence period during which camp materials will not be released to the public. We ask participants not to discuss the problems in public unless they obtained an explicit permission from contest authors.
If you would like to get a feel of the contests, you can find links to some of the previously published camp contests here.
If you have any questions about the camp, please feel free to send us an email, or join our Discord server!
If you are interested in participating, please fill the form here.
We ask you to register before June 14 if you want to participate remotely and before June 7 if you want to participate in Bucharest. If you require a visa, please register as soon as possible, as it might take a few weeks to receive (depending on your location).
Also, if your university or organization has a lively ICPC community that may be interested in attending the camp, and you have some contacts of people in charge (e.g. coaches) we would highly appreciate if you could share some details in a direct message to me. Thanks!
We'd like to thank and praise the authors of the contests in the camp:
... And others! You can find more details about contest rules and technical setup on the website.
Finally, we say special thanks to
Hi everyone!
We are currently trying to schedule OCPC 2025 Summer (see e.g. wrap for this Winter for details), and as it always happens, it is very difficult due to potential conflicts with other events and camps. As such, we need some help from all potential participants to choose the best dates for the camp.
We would really appreciate it if everyone potentially interested in participating this Summer would fill this form.
Filling the form is not binding, of course, and its main purpose is to collect necessary information before actually scheduling the camp, so please fill it even if you're not certain yet whether you would attend or not.
If you have any further scheduling-related information that you would like us to consider, please write it here in the comments, or reach out to me in DM. Scheduling in summer is always hard, but we hope to make through it with your help.
P.S. We are also looking for problem authors! Please reach out to me in DM, if interested. We pay (see the wrap blog for details).
Hi everyone!
Recently, linear programming (LP) duality was brought up in a Discord server, and it made me think again about how, whenever it is introduced, it's most often very poorly motivated. Some examples that I've seen include:
After some thinking, I would like to share a geometric interpretation to LP duality, that I think should very intuitively and directly explain what's the meaning of our actions, and why does it actually deliver the same result (and not just an upper bound) as the primal problem.
Tl;dr. Both primal and dual LP problems find the supporting hyperplane of the feasible set with the given normal vector. However, the primal problem parameterizes the feasible set and finds the touching point of the hyperplane within the set, while the dual problem parameterizes all hyperplanes with the given normal vector s.t. the feasible set lies below them, and finds the hyperplane with the minimum parameter among them.
Hi everyone!
The 5th Osijek Competitive Programming Camp has just concluded, and we couldn't be happier about the way it is shaping :)
Hi everyone!
We are very happy to announce that Osijek camp is back this Winter, on February 15-23, 2025, right before the 2025 ICPC Europe Championship on February 28 — March 2, 2025. The camp is hosted by the School of Applied Mathematics and Computer Science of the University of Osijek and is brought to you by the organizing team of adamant and -is-this-fft-.
The camp is inspired by various competitive programming camps that we attended during our active years in ICPC, and is aimed to help college students prepare for ICPC regional contests and finals. The camp will consist of 7 ICPC-style contests and 2 days off.
If you're participating in ICPC APAC, or are close to Singapore, please consider the Singapore mirror organized by errorgorn.
After some discussions with participants, and also thanks to the continued support of our sponsors, we decided to reform the structure of participation fees for the camp. While previously, participation fees were 100€ and 150€ per participant for online and onsite participation correspondingly, in this camp the participation fee for both online and onsite participants is 201€ per team.
For a full 3-person team, this marks a 33% reduction in the price of online participation, and a 55% reduction in the price of onsite participation! We hope that it will help us to incentivize onsite participation, and also participation in full teams, to make sure that it is as close as possible to the intended ICPC contest experience for everyone involved.
Note that, similar to previous camp editions, the fee does not include regular meals, travel or accommodation. Some further details about location, travel and food options can be found on the website.
We support and empathize with those affected by the ongoing war in Ukraine, therefore we offer a free participation for affected individuals and teams affiliated with Ukrainian institutions.
The expected starting time for the contests is 10am CET. For online participants, it is still a preferred starting time, but we will make accommodations for virtual participation at a later time, when necessary.
Most of our contests are originally developed for the camp. A small number of contests may be based on previous contests that have not been released to the general public. If you have seen some problems of a contest before, you can't participate on that day. We will privately contact participants who might be affected.
After the camp, we will have a silence period during which camp materials will not be released to the public. We ask participants not to discuss the problems in public unless they obtained an explicit permission from contest authors.
If you would like to get a feel of the contests, you can find links to some of the previously published camp contests here.
If you are interested in participating, please fill the form here.
We ask you to register before February 8 if you want to participate online and before February 1 if you want to participate onsite. If you require a visa, please register as soon as possible, as it might take a few weeks to receive (depending on location).
Also, if your university or organization has a lively ICPC community that may be interested in attending the camp, and you have some contacts of people in charge (e.g. coaches) we would highly appreciate if you could share some details in a direct message to me. Thanks!
We'd like to thank and praise the authors of the contests in the camp:
... And others. We would also like to thank errorgorn and Um_nik for their help with reviewing problem proposals. You can find more details about contest rules and technical setup on the website.
Finally, we say special thanks to
Okay guys, I know it sounds like Top 10 optimizations 2017- (collectors edition) but hear me out
Hi everyone!
Recently, a problem ordered set has been added to Library Checker.
Essentially, the problem asks you to maintain a set $$$\{a_1,\dots,a_n\}$$$ that supports the following operations:
Of course, all these can be done with GNU policy-based data structures (pbds) in $$$O(\log n)$$$ per query, which leads to the shortest code. At the same time, it has a huge constant factor in practice, so a natural question arises. What would be the fastest way to solve this? One of my earliest blogs already addressed this: we can use a Fenwick tree over the bitmask of the set and then do a jumping binary search to get the $$$k$$$-th element. I implemented this in two separate structures: fenwick and fenwick_set.
The first one is the actual implementation of a Fenwick tree, while the second is a wrapper with set-like interface. Then, the fenwick structure is standard and straightforward, including finding lower bound of a prefix sum:
Then, the replies to the queries would look like this:
Here, we use an additional bit vector present to test if the element is actually present in the set. Submitting this solution, we find out that it works 213ms, while the top solution is around 140ms. How come? Isn't Fenwick so fast it's close to $$$O(1)$$$ in practice?
I brought this topic up in the Discord AC server, and chromate00 suggested quite a clever trick to enhance it further: Just integrate the Fenwick tree more with our favorite little mrmriend bitset! What it actually means is, since we represent a set, we can split its bitmask into blocks of 64 bits, each stored in a single uint64_t, and then Fenwick tree will be used to approximately answer queries based on popcounts of these 64-sized blocks, while the last part would be covered by bit magic.
In other words, this allows us to reduce memory consumption of the Fenwick tree itself from $$$n$$$ to $$$\frac{n}{64}$$$ (should be slightly better for cache too), and correspondingly query performance from $$$\log n$$$ to $$$\log \frac{n}{64}$$$. Note that for this, we also need to quickly find the $$$k$$$-th set bit in a 64-bit integer, and also find the number of set bits before the $$$k$$$-th bit. The second one is straightforward with std::popcount:
size_t order_of_bit(uint64_t x, size_t k) {
return k ? std::popcount(x << (64 - k)) : 0;
}
The first one is less so, but it is also doable "quickly" with bmi2 intrinsic:
size_t kth_set_bit(uint64_t x, size_t k) {
return std::countr_zero(_pdep_u64(1ULL << k, x));
}
Here, _pdep_u64 takes a bitmask as the first argument and applies it to only set bits of the second argument. In other words, _pdep_u64(1 << k, x) is 1 << t, where $$$t$$$ is the $$$k$$$-th bit of $$$x$$$. Doing all this, and also adding fast io on top, I've managed to outperform the top-1 solution by 4 ms 😃
Note: You might want to do #pragma GCC target("bmi2,popcount") for this to work properly.
Do you like me hate coordinate compression? Well, you're in the right place! From now on, you can use
auto compress_coords(auto &coords) {
std::vector<int> original;
original.reserve(size(coords));
std::ranges::sort(coords);
int idx = -1, prev = -1;
for(auto &x: coords) {
if(x != prev) {
idx++;
prev = x;
original.push_back(x);
}
x.get() = idx;
}
return original;
}
The code above takes a range of reference_wrapper<int>, then automatically assigns all concerned values to their order index in the sorted array, and returns the sorted vector of all distinct original values. This way, you no longer need to disrupt your main function with stupid things such as a[i] = lower_bound(begin(srt), end(srt), a[i]) - begin(srt), you just collect all your references in the array, and give the array to compress_coords! See how simple it is:
vector<reference_wrapper<int>> coords;
for(auto &it: a) {
cin >> it;
coords.push_back(ref(it));
}
vector queries(q, pair{0, 0});
for(auto &[t, x]: queries) {
cin >> t >> x;
if(t != 2) {
coords.push_back(ref(x));
}
}
auto values = compress_coords(coords);
After that, you can treat a[i] and q[i] as if they are already compressed, and you can always put them as an index in values if you want to recover their original value. Simple and universal, am I right?
P.S. All these are conveniently implemented and structured here in CP-Algorithms library, so you might check it out if you want.
P.P.S. Are there any more efficient yet simple structures for Ordered Set problem?
Hi everyone!
As Codeforces now supports C++23, it seems to be the right time to discuss some of the particularly interesting features.
Some noteworthy ones that were already mentioned elsewhere include:
views::zip that maps two ranges into pairs (A[i], B[i]).views::enumerate that maps range into pairs (i, a[i]).views::adjacent<k> that maps range into tuples (a[i], ..., a[i+k-1]).views::cartesian_product that maps two ranges into pairs (A[i], B[j]) with all possible i and j.ranges::to<Container> that creates a container out of a view, e.g. to<vector>(views::iota(0, n)).ranges::fold_left and ranges::fold_right, range versions of std::accumulate/std::reduce.insert_range/append_range/prepend_range/assign_range for containers (not in GCC yet).print/println for formatted printing (it seems that standard formatters for ranges are not in GCC yet).But there are also two features that weren't covered in as much detail as they deserve, deducing this and generators.
Assume that you want to write a recursive lambda. What are your options? Naturally, you'd try something like this:
auto fact = [&](int x) {
return x ? x * fact(x - 1) : 1;
};
You will not be allowed to do it, because inside the lambda, you use fact before its type is deduced. One way to circumvent it is to write function<int(int)> fact = ... instead. While it is attractive, it makes the calls to fact more expensive, and in certain cases might even lead you to TLE, e.g. if you try to use this for depth-first traversal of a big graph.
Until C++23, the best practice was to do something like this:
auto fact = [&](auto &&self, int x) -> int {
return x ? x * self(self, x - 1) : 1;
};
cout << fact(fact, n) << endl;
While much more efficient on practice, it looks very ugly. And C++23 helps us, allowing to do this instead:
auto fact = [&](this auto fact, int x) -> int {
return x ? x * fact(x - 1) : 1;
};
cout << fact(n) << endl;
Just as if it was a proper recursive function!
Another interesting feature that I haven't seen mentioned in competitive programming discussions at all are coroutines. Assume that you need to factorize a number. If you depend on Pollard's rho algorithm, your flow probably looks as follows:
vector<int> factors;
void factorize(uint64_t m) {
if(is_prime(m)) {
factors.push_back(m);
} else if(m > 1) {
auto g = proper_divisor(m);
factorize(g);
factorize(m / g);
}
}
And it's always annoying that to store the result, you have to either keep a global vector, or take output vector as an argument by reference (and pass it around each time). Ideally you'd want to return a vector, but then you might be afraid of accidentally getting a quadratic runtime, and even besides that you'd need to write extra code to merge the results. Coroutines allow us to rewrite it as follows:
std::generator<uint64_t> factorize(uint64_t m) {
if(is_prime(m)) {
co_yield m;
} else if(m > 1) {
auto g = proper_divisor(m);
co_yield std::ranges::elements_of(factorize(g));
co_yield std::ranges::elements_of(factorize(m / g));
}
}
for(int p: factorize(m)) {
...
}
In this manner, factorize will return a generator, which is basically a view wrapper to the function above which generates consecutive elements on the range "on the fly", while also suspending execution of the function between accesses to the resulting range. This way, we avoid the need to store the results of the recursive function somewhere, as well as the need to incorporate external logic or callbacks into the function if we want to do something as soon as you get the next element.
From performance perspective, of course, coroutines may be slightly inferior to having a global vector to store the results. For example, this submission to finding strongly connected components takes 278ms and 108 MB of memory, while its global vector version only needs 229ms and 65 MB. Still I think coroutines are pretty nice concept to keep in mind and might simplify code or make it better structured in a lot of cases.
Hi everyone!
In this blog, we will learn how to find the asymptotic expansion of $$$H_n = \sum\limits_{k=1}^n \frac{1}{k}$$$.
In the recent Meta Hacker Cup, problem C of the round 3 reduced to finding the sum of $$$\frac{1}{a+bk}$$$ for given $$$a$$$ and $$$b$$$, over all $$$k \in [L, R)$$$.
Now, putting it into Wolfram, you can see that
where $$$\psi(z)$$$ is the digamma function. It is sufficient to solve this problem, as you can use boost or scipy to find it. But I feel like it's long time to satiate my curiosity on how it can be computed without knowing the digamma function in advance, and this blog is focused just on that.
First of all, let's define $$$H(n) = \sum\limits_{k=1}^{n} \frac{1}{k}$$$, the $$$n$$$-th harmonic number. If $$$a = 0$$$, we can say that
Notice how it is similar to the formula with the digamma function? That's not a coincidence! In fact, we can e.g. re-define $$$H(n)$$$ as
and this definition will be quite easy to update to also allow non-integer $$$n$$$, by changing the upper sumation limit to $$$\lfloor n \rfloor - 1$$$.
With this in mind, we can re-express the whole sum as
This is also similar to the formula with $$$\psi$$$, because $$$\psi(n) = H(n-1)-\gamma$$$ for integer $$$n$$$, where $$$\gamma$$$ is the Euler–Mascheroni constant.
As a very rough first estimate, we can approximate
which is a quite known estimation in many applications, e.g. when finding all divisors of all numbers up to $$$n$$$.
Now, the approach that we will use to finding the true asymptotic expansion of $$$H(n)$$$ is assuming that $$$H(n) = \ln n + F(\frac{1}{n})$$$, where $$$F(x)$$$ is an analytic function, meaning that it can be expressed as $$$F(x) = a_0 + a_1 x + a_2 x^2 + \dots$$$, i.e. as a power series.
Note: While $$$F(\frac{1}{n})$$$ is a convenient way to represent the expansion, it actually does not converge in any $$$n$$$. The idea here is rather that each prefix sum $$$F_k(x) = a_0 + \dots + a_k x^k$$$ serves as an increasingly better approximation as you put $$$n \to \infty$$$, but also provides worse approximations on smaller $$$n$$$.
With this assumption, let's find the coefficients of $$$F(x)$$$. For this, consider
In this form, we can rewrite the LHS as a power series in $$$\frac{1}{n}$$$. Indeed,
as follows from the standard expansion $$$\log \frac{1}{1-x} = \sum\limits_{k=1}^\infty \frac{x^k}{k}$$$. At the same time,
can also be represent as a power series in $$$\frac{1}{n}$$$ as
as follows from the standard expansion for $$$\frac{1}{(1-x)^k}$$$. Putting it all back together, we arrive at
For $$$k=1$$$, the coefficients near $$$\frac{1}{n^k}$$$ on both sides are already same, and for all higher $$$k$$$ this requirement turns into
Using the identity above for $$$k=2,3,\dots$$$ allows us to find $$$a_1 = \frac{1}{2}$$$, $$$a_2 = -\frac{1}{12}$$$, $$$a_3=0$$$, $$$a_4=\frac{1}{120}$$$, and so on. Okay but what about $$$a_0$$$? Well, actually, $$$a_0=\gamma$$$! But it is not important for our purposes at all, because it cancels out when we subtract $$$H(L-1)$$$ from $$$H(R-1)$$$.
One can also derive the same result in the form
where $$$\zeta(x)$$$ is the Riemann zeta-function that already occurred e.g. here, but I fail to give any meaningful interpretation to this fact.
One highly "illegal" way to interpret this is as follows. We previously said it makes sense to define
But we can rewrite it as
Now, we already know that $$$\sum\limits_{k=1}^{\infty} k^t = \zeta(-t)$$$, so at $$$n \to \infty$$$ we get
except that what we did was very illegal, and hence it missed the $$$\ln n + \gamma$$$ part completely. But as always with Riemann's zeta function, it quite surprisingly allows us to get estimations for stuff that is actually analytic quite precisely.
Are there any simpler ways to derive it?
Hi everyone!
I'm posting this on behalf of CP-Algorithms, a community project that started off in 2014 by RodionGork as a translation of e-maxx, a Russian go-to resource at the time by e-maxx for learning core competitive programming algorithms. Since then, CP-Algorithms grew quite a lot (which also prompted a rename from original project name e-maxx-eng) and includes a lot of new, original articles, and a lot of translated articles were enhanced and/or extended or even completely rewritten, amounting to a total of 157 articles at the moment.
At the moment, the project is largely maintained by Jakube and adamant (that's me), but as it happens, we don't have as much time to dedicate to it as we used to, so we're looking for some fresh blood to join the effort. This means both potential contributors and maintainers.
As a community project, it is largely driven by volunteering efforts of people who write and translate articles. Moreover, similar to previous years, right about now DigitalOcean is conducting Hacktoberfest, an initiative that will award every participant which will make 4 approved pull requests on Github (in participating projects) during the month of October with a cool, free shirt
UPD: sorry, it's just a digital badge on holopin instead of t-shirts starting last year ☹️
Our project participates in Hacktoberfest, so it could be an easy way for you to contribute into open source and get a t-shirt for it. Not sure what to help us with? Consider the following:
See How to Contribute page for some instructions, or just click on a pencil icon in the upper-right corner of any article to propose changes. You can also use the Article Preview page to see how your changes will look like when they're actually added to the site. If you still have any questions about the process, don't hesitate to reach out to me directly 😊
Besides regular contributors, we're in dire need of having more people joining the maintainer team. You would be granted a right to contribute to the project directly without prior approval, and will need to exercise it appropriately, both when making your own contributions and when reviewing open issues and pull requests that you will be able to merge into the main branch once you think they're good enough.
On top of it, some time ago I started out a competitive programming library with automatic verification via Library Checker as an auxiliary project to CP-Algorithms. Ideally, I would like to let more people join it in the future, and also facilitate its integration into the main website and its articles somehow. Having another motivated maintainer to discuss it and work on it together would be fantastic!
Please reach out to me or Jakob if you're interested, and let us know of any of your prior experience in technical writing, computer science and competitive programming. We will be happy to expand our team!
Hi everyone!
Last Sunday marked the conclusion of the fourth Osijek Competitive Programming Camp (OCPC). In this camp, 54 teams solved at least one problem, of which 10 teams participated onsite. Congratulations to the top-3 teams by overall rating:
For this camp, QuantCo joined us as a platinum sponsor. As a part of the sponsorship, we organized a fun CTF-style event with prizes for the camp. Camp participants were allowed to join in teams of up to 4 people and participate in the CTF challenge virtually in a 3 hour window within 24 hours of the second day-off. Congratulations to the winners:
Thank you, QuantCo, for the event! I think it was very fun, and I hope that we can do something similar in the future :)
 |  |  |
As usual, we had social outings during camp day-offs: Our participants played paintball on Monday, and bowling on Friday.
Also this time I noticed a ping pong table in the courtyard, and got some spare ping pong net, rackets and a ball to play it with some of the camp participants. The experience was somewhat unusual, as the ball movement were less predictable due to wind and stone table material, but nevertheless fun. I jokingly called it playing ping pong on hard mode 😁
Overall, the whether in Osijek in Summer is pretty hot (up to 35℃), which makes it somewhat difficult to run some outdoors activities during the day, but on the other hand Osijek also has a very nice river beach in 15 minutes walking distance from the camp site, and I had some great time swimming there when not being busy with the camp stuff!
Overall, this camp had fewer participants than some previous camps, which we attribute to a combination of factors:
Unfortunately, not all of these factors are within our control. For example, while I was often granted an official leave from my studies or internships to attend training camps, I understand that not all participants are comfortable asking for this (or might not want to spend personal leave days on this), and not all companies/institutions would actually grant them even when asked.
However, we still want to mitigate these issues to the best of our ability! That being said:
And, of course, feedback is very important to us, both from people who participate and from people who would potentially like to participate, but for some reasons can not. If you hesitate about participating, but in principle it is something of interest to you, I'd really appreciate it if you reached out to me, so that we can discuss the issue and try to improve in a way that will resolve your doubts.
Other than that, thank you everyone for your attention, and hopefully see you this winter :)
Hi everyone!
We are thrilled to invite you to The 3rd Universal Cup, Stage 6: Osijek, taking place on August 10th, 2024.
This stage is based on the Potluck contest of OCPC 2024 winter, which featured 52 official teams competing onsite and online during the camp. If you like the contest, please consider participating in our future camps, so that we are able to deliver more high quality contests in the future. Your continuous support is essential for OCPC to keep running and be able to compensate problem authors!
I would like to thank all authors for their efforts on preparing the contest: ToxicPie9, flamestorm, jeroenodb, -is-this-fft- and adamant.
We are looking forward to your participation!
