You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:

  • 305 — search for 305, most probably it will find blogs about the Round 305
  • andrew stankevich contests — search for words "andrew", "stankevich" and "contests" at the same time
  • user:mikemirzayanov title:testlib — search containing "testlib" in title by MikeMirzayanov
  • "vk cup" — use quotes to find phrase as is
  • title:educational — search in title

Results

1.
By lotusblume, 15 months ago, In English
Worst-Case Graphs for Maximum Flow Algorithms Maximum flow algorithms are known to perform significantly better in practice than their worst-case time complexities would suggest. So in this blog, I will present graphs on which the following maximum flow algorithms actually achieve their worst-case running time: | Algorithm | Time Complexity | | ----------------------- | ------------------------------ | | Ford-Fulkerson with DFS | $\mathcal{O}\big(m^2 \cdot U)$ | | Edmonds-Karp | $\mathcal{O}\big(n \cdot m^2\big)$ | | Dinic | $\mathcal{O}\big(n^2 \cdot m\big)$ | | DFS with Scaling | $\mathcal{O}\big(m^2 \cdot \log(U)\big)$ | | Dinic with Scaling | $\mathcal{O}\big(n \cdot m \cdot \log(U)\big)$ | | Most Improving Augmenting Paths | $\mathcal{O}\big(m \cdot \log(U) \cdot (m + n \cdot \log(n))\big)$ | | FIFO Preflow Push | $\mathcal{O}\big(n^3\big)$ | | Highest-Label Preflow Push | $\mathcal{O}\big(n^2 \cdot \sqrt{m}\big)$ | Here and in the rest of this blog: - $n =$ number of vertices, ...
### 1 Benchmark Graphs, The following two graphs will only serve as benchmark graphs when testing the running times on the

Full text and comments »

  • Vote: I like it
  • +927
  • Vote: I do not like it

2.
By gepardo, history, 8 years ago, In English
An alternative sorting order for Mo's algorithm Hello, Codeforces! I think many of you know about Mo's algorithm. For those, who don't know, please read this [blog](https://codeforces.me/blog/entry/7383). Here, I consider an alternative (and faster) approach of sorting queries in Mo's algorithm. # Table of contents * [Canonical version of the algorithm](#s1) * [Achieving a better time complexity](#s2) * [Relation to TSP](#s2-1) * [Hilbert curve](#s2-2) * [Benchmarks](#s3) * [Applicability](#s4) <div style="font-size: 1pt"> &nbsp; [cut] &nbsp; </div> <a name="s1"></a> # Canonical version of the algorithm The canonical version of this algorithm has $O((n + q)\cdot\sqrt{n})$ time complexity if insertions and deletions work in $O(1)$. Usually, the two comparators for query sorting are used. The slowest one: ~~~~~ struct Query { int l, r, idx; inline pair<int, int> toPair() const { return make_pair(l / block, r); } }; inline bool operator<(const Query &a, const Query &b) { re...

Full text and comments »

  • Vote: I like it
  • +431
  • Vote: I do not like it

3.
By bicsi, history, 13 days ago, In English
Optimal Incremental MST in 20 lines of code Hello Codeforces! Some of you might know `BottleneckTree.h` from [my KACTL fork](https://github.com/bicsi/kactl/blob/master/content/graph/BottleneckTree.h) (although it's a little obscure for an ICPC notebook; oh well). [user:freak93,2026-11-05] and I wrote it in 2021. The header says the complexity is "probably $O(\log n)$ amortized". It all started from a 2020 solution by [user:RestingRajarshi,2026-11-05] (more on that at the end). After about 6 years of on-and-off thinking about it, and with the help of Claude, we finally have an answer: it's not :). There are inputs where it takes $\Omega(\sqrt n)$ per operation. The good news is that a small change in the main loop fixes it, and this time we have a proof. We wrote a paper about it: [Incremental Minimum Spanning Trees on a Napkin](https://arxiv.org/abs/2611.05713). I think the structure is super elegant and short enough to be useful in contests, so I'm writing a blog about it. Prerequisites: none, really. It helps to know ...

Full text and comments »

  • Vote: I like it
  • +351
  • Vote: I do not like it

4.
By SecondThread, 2 years ago, In English
Meta Hacker Cup 2024 Schedule — Introducing the Meta Hacker Cup AI Track Meta Hacker Cup 2024 ================== Meta Hacker Cup is back! We’re excited to announce our schedule for our 2024 season, kicking off on September 20th! - Practice Round: [Fri. September 20th, 10am Pacific (72 hours)](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Meta+Hacker+Cup+Practice+Round&iso=20240920T10&p1=234)* - Round 1: [Sat. October 5th, 10am Pacific](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Meta+Hacker+Cup+Round+1&iso=20241005T10&p1=234&ah=3) (3 hours) - Round 2: [Sat. October 19th, 10am Pacific](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Meta+Hacker+Cup+Round+2&iso=20241019T10&p1=234&ah=3) (3 hours) - Round 3: [Sat. November 2nd, 10am Pacific](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Meta+Hacker+Cup+Round+3&iso=20241102T10&p1=234&ah=3) (3 hours) - Finals: [Sat. December 7th, 6am Pacific](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Meta+Hacker+Cup+Finals&iso=20241207T10&p1=234&ah=4) (4 hou...
track or the AI track, but not both. We hope this will create an interesting benchmark for how, We hope this will create an interesting benchmark for how well state-of-the-art machines are able

Full text and comments »

  • Vote: I like it
  • +528
  • Vote: I do not like it

5.
By Monogon, history, 5 years ago, In English
[Tutorial] Blossom Algorithm for General Matching in O(n^3) I have decided to write a tutorial on a topic not even [user:Um_nik,2021-06-29] knows! ([source](https://codeforces.me/blog/entry/92248)) In this tutorial, I will talk about the blossom algorithm, which solves the problem of **general matching**. In this problem, you are given an undirected graph and you need to select a subset of edges (called matched edges) so that no two edges share a vertex, and the number of matched edges is maximized. More common in competitive programming is bipartite matching, which is the same problem but when the graph is guaranteed to be bipartite. In competitive programming, general matching seems to get a lot of hate for being very challenging to implement. However, the blossom algorithm is quite beautiful, and important in the history of algorithm research. It will help if you are already familiar with bipartite matching. I will discuss the high level ideas of the algorithm, but my main focus will be on the tricky implementation details. So you may...

Full text and comments »

  • Vote: I like it
  • +384
  • Vote: I do not like it

6.
By Maksim1744, 5 years ago, In English
Counting primes in $\tilde{{\cal O}}(n^{2/3}\,\,)$ _Some time ago I read [this](https://projecteuler.net/thread=10;page=5#111677) post about calculating prime-counting function in $O(n^{3/4})$ (you have to solve problem 10 to access the post). And in the end author mentioned that there is $O(n^{2/3})$ solution. To my surprise I was not able to find any more or less relevant information on the internet about that. Maybe there is a beautiful blog describing all of this on 10-th page of google, but I decided to collect information I found in this post._ ###Prerequisites - From [distribution of prime numbers](https://en.wikipedia.org/wiki/Prime_number_theorem) $n$-th prime is approximately $n \ln n$, I will use it while proving complexities. ###$\tilde O(n^{3/4})$ Let's start with $O(n^{3/4})$ approach from Project Euler. We will need some definitions: - $\pi(n)$ &mdash; prime counting function, i.e. number of primes which are not greater than $n$. - $S(n, a)$ &mdash; suppose we take all numbers from $1$ to $n$ and sieve them w...

Full text and comments »

  • Vote: I like it
  • +346
  • Vote: I do not like it

7.
By purplesyringa, history, 6 years ago, In English
crazySegmentTree: Segment Tree implementation with 5x faster queries than bottom-up tree Hello, Codeforces! A few days ago [user:MohammadParsaElahimanesh,2021-04-06] posted a blog titled [Can we find each Required node in segment tree in O(1)?](https://codeforces.me/blog/entry/89377) Apparently what they meant was to find each node in $\mathcal{O}(ans)$, according to [ecnerwala's explanation](https://codeforces.me/blog/entry/89377?#comment-777885). But I was too dumb to realize that and accidentally invented a parallel node resolution method instead, which speeds up segment tree a lot. A benchmark for you first, with 30 million RMQ on a 32-bit integer array of 17 million elements. It was run in custom test on Codeforces on Apr 6, 2021. - **Classic implementation from cp-algorithms:** 7.765 seconds, or 260 ns per query - **Optimized classic implementation:** (which I was taught) 4.452 seconds, or 150 ns per query (75% faster than classic) - **Bottom-up implementation:** 1.914 seconds, or 64 ns per query (133% faster than optimized) - **Novel parallel implement...
```cpp #include #include #include , tree a lot. A benchmark for you first, with 30 million RMQ on a 32-bit integer array of 17 million, A benchmark for you first, with 30 million RMQ on a 32-bit integer array of 17 million elements. It, This is the benchmark, along with the four segment tree implementations I checked and a prefix sum

Full text and comments »

  • Vote: I like it
  • +402
  • Vote: I do not like it

8.
By errorgorn, 4 years ago, In English
[Tutorial] Theoretically Faster HLD and Centroid Decomposition This blog was going to be translation of $[1]$ (which is in Chinese) but I think I ended up deviating too much from the source material that it would not be appropriate to call this a translation. Anyways, I am honestly amazed by how ahead of its time this paper is. In its abstract, it starts by saying that the state of art for tree path queries is $O(n \log n + q \sqrt n \log n)$, which I honestly can't fathom how one would arrive, then proceeds to claim that it has found an $O((n+q) \log n)$ algorithm. All the more, in 2007. While I was in the process of writing this blog, [user:smax,2022-07-18] sniped me and posted $[9]$. However, we will focus on static trees **only**. Thanks to [user:oolimry,2022-07-18], [user:everule,2022-07-18] and [user:timreizin,2022-07-18] for proofreading. Note to reader: I am expecting the reader to be familiar with what a splay tree and HLD is. You do not really need to know why splay trees are $O(\log n)$ amortised but you should know what the z...

Full text and comments »

  • Vote: I like it
  • +245
  • Vote: I do not like it

9.
By AlexSkidanov, history, 8 years ago, In English
Are we close to machines solving ICPC problems? Hi, all, I with few other folks at [NEAR](http://near.ai/blog) work on teaching machines to program. A particularly exciting sub-project of that is teaching machines to solve competitive programming problems. In this post I would like to give a quick overview of where the state of the art is today, what the major challenges are, why this is not a popular area of research, and how the CodeForces community can help to address some of the issues the program synthesis community is facing today. We also have a certain budged allocated for this project, and we are paying to the CodeForces members who help us with some data annotation challenges. We have paid more than $10k in our first two annotation projects, and are launching three more projects today. Scroll to the end if you are interested. Competitive programming as a benchmark ====================================== With the emergence of deep learning, neural networks started performing almost at a human level in many ta...
interested. Competitive programming as a benchmark ====================================== With, But what would it even mean to solve programming? What would be a good benchmark and milestones to, Competitive programming as a benchmark ======================================

Full text and comments »

  • Vote: I like it
  • +336
  • Vote: I do not like it

10.
By pajenegod, history, 2 years ago, In English
Tutorial: The fastest tree algorithm, the XOR Linked Tree Hi Codeforces! This is a blog about a really cool folklore technique that seems to have been forgotten over time. I currently only know of one place where it is mentioned on the internet, https://www.algonotes.com/en/minimal-memory-dp/, which is a tutorial by [user:monsoon,2024-10-20] for his problem "Matchings" https://dmoj.ca/problem/ontak2010sko from a POI training camp in 2010 ([see this for more information](https://codeforces.me/blog/entry/92090?#comment-807964)). But I've heard that this technique is even older than that. I originally learnt of this technique a couple of years back when I was digging through the fastest submissions on [problem:321-C] and I saw it being used in a submission [submission:9076307] by [user:Marcin_smu,2024-10-18] from 2014. I don't know if there is a name for this technique, so I've decided to call it the _XOR Linked Tree_ because of its close connection to XOR linked lists https://en.wikipedia.org/wiki/XOR_linked_list. The XOR Linked Tree is...
## Benchmark, -18]. Credit to [user:qmk,2024-10-18] for helping me put together the C++ benchmark. Also, thanks, | C++ Benchmark | Time | Memory | Submission link, | Python Benchmark | Time | Memory | Submission link

Full text and comments »

  • Vote: I like it
  • +284
  • Vote: I do not like it

11.
By brunovsky, 5 years ago, In English
[Tutorial] Network simplex Hello! If you've learned the simplex algorithm and a minimum cost flow algorithm, perhaps you've also heard about this fancy thing called [network simplex](https://en.wikipedia.org/wiki/Network_simplex_algorithm) which is supposed to be a specialization/optimization of the simplex algorithm for computing a [minimum cost circulation](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem). If your google search didn't turn up any interesting results or your interest faded, you might have moved on to other subjects. Well I didn't! So this is a tutorial on network simplex (NS) for the **minimum cost circulation** problem. I'll describe and formulate the problem, show how it relates to the usual minimum cost flow problem, explain the theory behind the algorithm in-depth, and then derive the implementation details. ## Introduction The algorithm commonly used in competitive programming for this sort of task is a minimum cost flow algorithm based on finding augmenting paths in a *f...

Full text and comments »

  • Vote: I like it
  • +493
  • Vote: I do not like it

12.
By Monogon, 4 years ago, In English
[Tutorial] Supporting Priority-Queue-like Undoing on DS _Good morning!_ In this blog, I will present an online algorithm that can perform priority-queue-like undoing on a data structure, given a few assumptions. I will also present and solve a generalization of that problem. For context, I highly recommend reading this blog that shows how to solve the easier problem of queue-like undoing. That blog gave me the inspiration for the trick I will describe here, but I will still try to write this blog so that it can be understood without it. Thank you [user:Noam527,2023-01-08] for introducing such a great trick to the competitive programming community. [[Tutorial] Supporting Queue-like Undoing on DS](https://codeforces.me/blog/entry/83467) Acknowledgment ----------------- Huge thanks go to [user:peltorator,2023-02-20] for hosting a [blog contest](https://codeforces.me/blog/entry/110840). His generous prize of $300 got many people to write blogs on new, interesting ideas, and it was one of the main reasons I wrote this blog. I'm...
compare on a benchmark implementation., values for a few dimensions. It would be interesting to see how they compare on abenchmark

Full text and comments »

  • Vote: I like it
  • +409
  • Vote: I do not like it

13.
By Qwerty1232, 19 months ago, In English
Making NTT convolution 10x faster with avx2 > Text is also available on [github pages](https://piskareviv.github.io/blog_aux_ntt_1/) (formatting may look a bit cleaner there) > Thanks [user:alexxela12345,2025-05-05] for reviewing this blog Hello everyone! I want to share some of my thoughts and experiments on vectorizing NTT. I prefer NTT to real-valued FFT because of the imprecision of the latter. I use `avx2` because it is the most advanced vector extension supported by the majority of modern online judges (including Codeforces), as of 2024. And I have no idea how many bugs (already found two) and how much UB my code contains, at least it passes some kind of tests. ### Benchmark info All the benchmarks are performed on my `Ubuntu 22` `Intel i5-1135g7` laptop. I execute `cpupower frequency-set -d 3.0ghz -u 3.0ghz` before benchmarks to (attempt to) fix CPU frequency for better accuracy. Code is available at [github](https://github.com/piskareviv/blog_aux_ntt_1). You can try running all the benchmarks o...

Full text and comments »

  • Vote: I like it
  • +366
  • Vote: I do not like it

14.
By pajenegod, 3 years ago, In English
Shallowest Decomposition Tree Hi Codeforces! Today I want to tell you about a really cool and relatively unknown technique that is reminiscent of Centroid decomposition, but at the same time is also completely different. The most common and well known decomposition tree algorithm out there is the centroid decomposition algorithm (running in $O(n \log n)$). It is a standard algorithm that is commonly used to solve tons of different kind of divide and conquer problems on trees. However, it turns out that there exists another closely related decomposition tree algorithm, that is in a sense optimal, and can be implemented to run in $O(n)$ time in around $30$ lines of code. I have chosen to call it the _Shallowest Decomposition Tree_. This blog will be all about the shallowest decomposition tree. Something I want to remark on before we start is that I did not invent this. However, very few people know about it. So I decided to make this blog in order to teach people about this super cool and relatively unknown tec...
this problem as a benchmark is to compare the time used to construct the shallowest decomposition

Full text and comments »

  • Vote: I like it
  • +403
  • Vote: I do not like it

15.
By Chilli, history, 8 years ago, In English
C++ STL: Order of magnitude faster hash tables with Policy Based Data Structures TL;DR ----- The Policy Hash Table has 3-6x faster insertion/deletion and 4-10x increase for writes/reads. As far as I can tell, there are no downsides. The policy hash table (specifically the open-addressing version), beats out unordered_map in all my benchmarks. PS: Make sure you read the section a better hash function and use it &mdash; I'd recommend this one: https://github.com/kth-competitive-programming/kactl/blob/master/content/data-structures/HashMap.h Background ------ I've often been irritated by how slow unordered_map is in C++. Too often, I have something that runs fast enough in terms of complexity, but the constant factor from unordered_map slows down the solution too much. Yesterday though, after using the useful order statistics tree from https://codeforces.me/blog/entry/11080, I was curious if there were any other useful data structures hiding in the Policy STL. And lo and behold, I found a hash table. Benchmarks ------------------ Well, enough backsto...

Full text and comments »

  • Vote: I like it
  • +328
  • Vote: I do not like it

16.
By purplesyringa, history, 3 years ago, In English
This one weird trick will speed up your I/O 5x Just do this!! ```cpp #include <iostream> int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); // Your code here int n; std::cin >> n; long long sum = 0; for (int i = 0; i < n; i++) { int x; std::cin >> x; sum += x; } std::cout << sum << std::endl; } ``` This will speed up your code so much you won't have to care about spending time in I/O anymore!! Give likez plz :3 [cut] <!-- --> --- Yeah, no. That's not how it works. We're still using `<iostream>`, and that means we have to rely on virtual inheritance and all the deoptimizations that follow from that. Even if you use a random "here's-my-fast-io-library" snippet from Codeforces, you still depend on block-buffered output. (Also, none of those libraries mesh well with floats.) In many cases, more CPU time is spent encoding/decoding numbers than interacting with the file system. Can we do better? ...Yeah, stupid que...
![Aggregated benchmark results](https://svgshare.com/i/13_o.svg), , будь это не так. Смотрите, к чему за полмесяца привело мое СДВГ: ![Aggregated benchmark results

Full text and comments »

  • Vote: I like it
  • +288
  • Vote: I do not like it

17.
By Chilli, history, 8 years ago, In English
Benchmarking Complexity of Dinic's With Scaling In various places([1](https://codeforces.me/blog/entry/52714)[2](https://codeforces.me/blog/entry/52077?#comment-360923)), people have talked about "Dinic's With Scaling" having $O(VElog(U))$ complexity, where U is the max edge capacity. However, in just as many places, people have cast doubt about this complexity or worried that this algorithm ends up being slower in practice([1](https://codeforces.me/blog/entry/52714?#comment-397827)[2](https://codeforces.me/blog/entry/52077?#comment-360949)). I had the same doubts. In fact, a couple months ago I benchmarked Dinic's with scaling on some hard [test cases](https://codeforces.me/blog/entry/52714?#comment-397861) and thought that Dinic's with/without scaling performed similarly. As it turns out, I benchmarked it again yesterday and found that Dinic's with scaling definitely has significantly better asymptotic complexity (by a factor of V). ## Synthetic Benchmarking I used the hard test case generator at 2 posted by [user:...

Full text and comments »

  • Vote: I like it
  • +149
  • Vote: I do not like it

18.
By Chilli, history, 7 years ago, In English
How to get actual 64 bit bitsets on Codeforces [Not Recommended] [Don't do this at your job] This blog post brought to you by [user:pajenegod,2020-05-16], [user:Narut,2020-05-16], and the rest of #constant-factor on the AC discord server. If you're interested in discussions like this, feel free to join! For the longest time, CF has constrained us to the tyranny of 32 bit C++. Not only has that slowed down our `long long` operations, it has also constrained us to a measly 32 bit constant factor reduction with bitsets! Let's take 2 pieces of equivalent code. For Loop: ~~~~ int a[MAXN], b[MAXN] for (int it = 0; it < iters; it++) for (int i = 0; i < MAXN; i++) if (a[i] & b[i]) cnt++; ~~~~ Bitset: ~~~~ bitset<MAXN> a, b; int cnt = 0; for (int it = 0; it < iters; it++) cnt += (a | b).count(); ~~~~ On Custom Invocation C++17 (32 bit) for MAXN=1e4 and iters=1e5, this boring for loop code runs in 3594 ms, while the equivalent bitset version runs in 104ms. 3594/104 is approximately 32. Ok, disappointing but makes sense. However, Mike...
32x! However, what happens if we try our previous benchmark?, , what happens if we try our previous benchmark? ~~~~ For Loop (C++17 64 bit): 3736 ms Bitset

Full text and comments »

  • Vote: I like it
  • +361
  • Vote: I do not like it

19.
By MikeMirzayanov, 13 years ago, translation, In English
Support of JavaScript V8 and Some Benchmarks I've found some time to support JavaScript, which is so popular now. I chose V8 as the most developed implementation of JavaScript. With the help of a tambourine and a liter of cola [I successfully compiled it on Windows](http://assets.codeforces.com/files/v8-3.32.0.7z). Funny, I was ready to implement workaround to support reading from stdin in JavaScript, but `d8` already supports it! Just use `readline()` to read line from the input. Here is an example of A+B: ~~~~~ var line = readline().split(' ') print(parseInt(line[0]) + parseInt(line[1])) ~~~~~ Interesting fact, that if there is no line-break (\r\n) at the end of line, then `readline()` returns `undefined`. So it is one more reason for good rule: each line should end with eoln. As a tiny research I've implemented HeapSort on C++, Java and JavaScript. I have an opinion that all dynamic typed languages are very slow. But... I've implemented HeapSort on $10^7$ elements from 0 to 9999999. I think it is good benc...
* [С++](https://github.com/MikeMirzayanov/binary-heap-benchmark /blob/master/cpp/heap.cpp) * [Java, /MikeMirzayanov/binary-heap-benchmark), чтобы не потерялось. Предлагаю подключиться и переписать, Actually, I posted the codes in [github](https://github.com/MikeMirzayanov/binary-heap-benchmark, I've implemented HeapSort on $10^7$ elements from 0 to 9999999. I think it is goodbenchmark to, UPD 4. I've updated some compilers and the benchmark results., benchmark to show how fast can be your code if you write like in Pascal or pure C. The result have, Вот я даже запилил микропроект на [github](https://github.com/MikeMirzayanov/binary-heap-benchmark

Full text and comments »

  • Vote: I like it
  • +139
  • Vote: I do not like it

20.
By Al.Cash, 10 years ago, In English
Fast and furious C++ I/O For a long time I've been upset with C++ standard input/output. First of all, I heard that `fread`/`fwrite` are much faster than everything else, and it's impossible to get good times on problems with huge input or output without using those. Secondly, it's really annoying to write formatting string and ampersands in `scanf`, especially with many variables to read. Thirdly, the only way to expand I/O to custom types is by overloading `<<` and `>>` operators on streams, but they are the slowest. I tried to tackle all these issues in my implementation. Remember, that it's targeted for the common use case in programming contests, so it's not as flexible as one might wish. [The code is here](http://ideone.com/X1tP8Q) **Doesn't compile with MSVS.** I apologize in advance to everyone, who will be scrolling through this 500 lines trying to read my solutions. Also it's not advised for people without broad experience with C++ to try to understand the entirety of it (dangerous for your men...
~~~~~ int, printf 1.34 1.43 1.33 int, cout, /miloyip/itoa-benchmark https://github.com/miloyip/dtoa-benchmark I didn't want to go too deep, I spent a lot of time optimizing the code. To prove it, I included my methods in [thisbenchmark, https://github.com/miloyip/itoa-benchmark https://github.com/miloyip/dtoa-benchmark

Full text and comments »

  • Vote: I like it
  • +239
  • Vote: I do not like it

21.
By pavook, history, 4 years ago, In English
Benchmarks of different segment tree implementations Sometimes I wonder, what implementation of a segment tree to use. Usually, I handwave that some will suit, and that works in most of the cases. But today I decided to back up the choice with some data and I ran benchmarks against 4 implementations: <ul> <li> Simple recursive divide-and-conquer implementation <spoiler summary="Code"> ~~~ struct SimpleRecursiveSegmentTree { unsigned size; private: std::vector<long long> t; void _build(const std::vector<int> &v, unsigned p, unsigned l, unsigned r) { if (r == l + 1) { t[p] = v[l]; return; } unsigned m = (l + r) / 2; _build(v, 2 * p + 1, l, m); _build(v, 2 * p + 2, m, r); t[p] = t[2 * p + 1] + t[2 * p + 2]; } long long _get(unsigned p, unsigned l, unsigned r, unsigned a, unsigned b) const { if (b <= l || r <= a) { return 0LL; } if (a <= l && r <= b) { ...
disrupt the benchmark (basically, the more you close — the better) and pin the benchmark, , close any applications that might disrupt the benchmark (basically, the more you close — the, I compiled the benchmark with `#pragma GCC optimize("O3")` on GNU GCC 11.3.0, and ran it with the

Full text and comments »

  • Vote: I like it
  • +126
  • Vote: I do not like it

22.
By brunomont, 6 years ago, In English
[Tutorial] Range minimum query in O(1) with linear time construction <spoiler summary="TL; DR"> Build a sparse table over blocks of size $b = 30 \geq \log{n}$. Now we only need to answer queries of size smaller than $b$. For that, simulate a minqueue of size $b$ over the array, and store a mask of the elements that are currently active in the minqueue. Let $\text{mask[r]}$ be the minqueue mask when the simulation is at position $\text{r}$. Now we can see that, if $r-l+1 \leq b$, then `query(l, r) = r - most_significant_set_bit(mask[r] & ((1<<(r-l+1))-1))`. ~~~~~ template<typename T> struct rmq { vector<T> v; int n; static const int b = 30; vector<int> mask, t; int op(int x, int y) { return v[x] < v[y] ? x : y; } int msb(int x) { return __builtin_clz(1)-__builtin_clz(x); } int small(int r, int sz = b) { return r-msb(mask[r]&((1<<sz)-1)); } rmq(const vector<T>& v_) : v(v_), n(v.size()), mask(n), t(n) { for (int i = 0, at = 0; i < n; mask[i++] = at |= 1) { at = (at<<1)&((1<<b)-1); while (at and op(i, i-msb(at&-at)) == i) at ...
implement. With the benchmark made, we can see that its construction is much faster than Sparse, /1trgA7bKSj4sCGaFmlrV0BmS6da6KdJ3_/view?usp=sharing) to the benchmark files). I compared the following, ://drive.google.com/file/d/1trgA7bKSj4sCGaFmlrV0BmS6da6KdJ3_/view?usp=sharing) to thebenchmark files).

Full text and comments »

  • Vote: I like it
  • +258
  • Vote: I do not like it

23.
By catalystgma, history, 2 years ago, In English
Exponential Length Substrings in Pattern Matching Hi all, I would like to share with you a part of my undergraduate thesis on a Multi-String Pattern Matcher data structure. In my opinion, it's easy to understand and hard to implement correctly and efficiently. It's (relatively) competitive against other MSPM data structures (Aho-Corasick, suffix array/automaton/tree to name a few) when the dictionary size is specifically (uncommonly) large. I would also like to sign up this entry to [user:bashkort,2024-10-04]'s [Month of Blog Posts](https://codeforces.me/blog/entry/133806):-) Many thanks to him and peltorator for supporting this initiative. #### Abstract This work describes a hash-based mass-searching algorithm, finding (count, location of first match) entries from a dictionary against a string $s$ of length $n$. The presented implementation makes use of all substrings of $s$ whose lengths are powers of $2$ to construct an offline algorithm that can, in some cases, reach a complexity of $O(n \log^2n)$ even if there are $O...
trying the LLM dataset intersection, and found the most favourable benchmark., #### Benchmark reproduction, ) instructions. * Finally, the book citation benchmark can be reproduced by following [these](https

Full text and comments »

  • Vote: I like it
  • +268
  • Vote: I do not like it

24.
By Geothermal, history, 3 years ago, In English
A Highly Experimental Training Plan for Beginners Very loosely inspired by some comments on [Thoughts on Reaching Cyan?](https://codeforces.me/blog/entry/101561) and [my recent AMA](https://codeforces.me/blog/entry/118845). Until now, I've avoided telling beginners to practice math before working on competitive programing problems because I haven't figured out a helpful way of doing so. This post is my attempt at telling grays to train math first in a way that might lead to improvement without an absurd time commitment. ## Introduction This section is largely motivation for why I'm proposing this training plan. If you just want to see the instructions for the training plan I'm proposing, you can skip this part. The first subsection in particular is not especially relevant to the rest of the post, but I wanted to have some documentation explaining why I still think the traditional "just solve problems" advice is good. ### The Conventional Advice on Improvement I'm frequently asked for advice on how to improve at co...

Full text and comments »

  • Vote: I like it
  • +248
  • Vote: I do not like it

25.
By halyavin, 10 years ago, In English
The case of slow printf and scanf I know what is the problem ================== _Where we are going we need all the courage we can get_ When I first read the comment that our shiny new gcc 6.2 C++14 compiler has slow printf and scanf I immediately knew what I would do the next weekend. The new MinGW switched to custom implementation and I didn't need anything else to tell what the problem is. _Of course_, their format string parsing is too slow, they copy data around countless times, no file buffering is used and they have enough levels of indirection to make finding the real code feeling like a treasure hunt. What else could be the problem after all? Keeping this thoughts in mind I patiently waited for a weekend. When I finally opened MinGW source and searched for printf function, I was pleasantly surprised. The real implementation was only a couple hops away and soon enough I was looking at the heart of printf code. MinGW did try to conceal it a bit though by naming it mingw_pformat.c. But a ~100Kb source fi...
and get to work. A few hours later I had a working build of mingwex library and thebenchmark, performance on the integer benchmark is 1.3-1.35x slower than the native version., to work. A few hours later I had a working build of mingwex library and the benchmark program that, . Integer benchmark behaves similar to my machine while floating point times are quite different, Floating point benchmark. 5M doubles, printf("%.1lf")/scanf("%lf") printf scanf mingw, ~~~~~ Integer benchmark. 10M integers, printf("%d")/scanf("%d") printf scanf mingw

Full text and comments »

  • Vote: I like it
  • +280
  • Vote: I do not like it

26.
By WLZ, history, 3 years ago, In English
A Slight Generalization of Push-Free Segment Trees Hi everyone! I'd like to share a simple way to use the [push-free segment tree](https://codeforces.me/blog/entry/112890) in some cases where the updates aren't commutative (spoiler: they need to be invertible). The uses cases of this trick are rather limited, though. The problem ------------------ We want to solve the following problem: Given an array $a_0, a_1, \dots, a_{N-1}$, whose elements satisfy certain properties (see [here](https://atcoder.github.io/ac-library/production/document_en/segtree.html)), answer $Q$ queries of the following types: - (Range queries): Given $0 \leq l < r \leq N$, find $a_l \cdot a_{l+1} \cdots a_{r-1}$ (endpoints are left inclusive and right exclusive). - (Range updates): Given $0 \leq l < r \leq N$ and a mapping $f$, update $a_i$ to $f(a_i)$ for all $i \in [l, r)$. $f$ has to satisfy the properties described [here](https://atcoder.github.io/ac-library/production/document_en/lazysegtree.html). Push-free segment trees ------------------ ...
not completely useless after all. You can see that I didn't do the benchmark very carefully, so, You can see that I didn't do the benchmark very carefully, so there may be special cases where the

Full text and comments »

  • Vote: I like it
  • +167
  • Vote: I do not like it

27.
By Chilli, history, 8 years ago, In English
Easy and (Semi)Efficient Dynamic Segment Trees (with Policy Hash Tables) One of my favorite implementations of segment trees has always been ["Easy and Efficient Segment Trees](http://codeforces.me/blog/entry/18051), by [user:Al.Cash,2018-07-27]. I used to dread segtree problems, but after reading that blog post and adapting a super simple implementation I've gotten a lot better with them. However, there are some types of segtree that you can't implement in that fashion, namely dynamic segtrees and persistent segtrees. See here for [criticism](http://codeforces.me/blog/entry/18051?#comment-287332). With the advent of policy hash tables, however, one can now implement dynamic segtrees in [user:Al.Cash,2018-07-27]'s style with somewhat comparable performance to a custom dynamic segtree. ### Standard segtree This is how a standard segtree looks like. You can set a single element, and query for ranges. It's nice and simple, and I think it's a great implementation. ~~~~~ int N; int seg[2 * MAXN]; void modify(int p, int val) { for (seg[p += N] ...

Full text and comments »

  • Vote: I like it
  • +93
  • Vote: I do not like it

28.
By mukel, 13 years ago, In English
C++11 for programming contests... Updated: 30 December 2013 3:27 CEST (Added a brief introduction to Lambda Functions). The [new C++ standard](http://en.wikipedia.org/wiki/C++11), also known as C++11 and also as C++0x is here, with some sugars for programming contest. I'll update this thread soon with new contents (and better structure). You can use C++11 on Topcoder, Codeforces, HackerRank ... This thread is based on my own experience, so you don't need to dig on the whole C++11 specification to find some useful feature you can use in programming contests. ### The "auto" keyword: Type inference is included in many modern programming languages, and C++ is not behind, the "auto" keyword works like "var" in C#, it only tells the compiler to infer the type for us: So, ~~~~~ map< string, pair< int, int > > somyLongTypeName = map< string, pair< int, int > >(); ~~~~~ Can be shortened to, with no impact on speed, since the type is inferred at compile time: ~~~~~ auto longTypeNamesAreHistory = map< strin...

Full text and comments »

  • Vote: I like it
  • +244
  • Vote: I do not like it

29.
By taha06, history, 3 years ago, In English
SD Segment Tree Variation, A Shorter And More Efficient Segment Tree Segment Tree is a powerful data structure in programming, that is why it can still be optimized way more. In this blog I will explain one optimization that can make a basic segment tree slightly faster and easier to write. (idea and the code by me) This does not work on range update range query segment trees. Introduction: ================== Let's consider a point update range query segment tree, while querying we visit many of useless Nodes along the way in order to answer the query moving from the root downwards. ![ ](/predownloaded/ef/4d/ef4d1dcb34f2560f3ddad1fa2f1dd9947e13ebce.png) As you can see, there are nodes (marked in red) that are not needed during the recursion, and we only need to visit the important nodes (marked in green). This is only true when querying in a point update segment tree or updating in a point query segment tree. Main Idea: ================== We can solve a query range $[l, r]$ by noticing we can make it a smaller range $[l + X , r]$, ...
<< K); } } ~~~~~ Benchmark: ================== , #### UPD: Added Benchmark, ] += val; l += (1 << K); } } ~~~~~ Benchmark: ==================

Full text and comments »

  • Vote: I like it
  • +123
  • Vote: I do not like it

30.
By cold_chair, history, 18 months ago, In English
An Open-Source Retrieval Model and Service for Competitive Programming Problems Over the past few years, the number of *duplicate* or *nearly-duplicate* problems in competitive programming has grown noticeably. You can find several discussions about this on Codeforces, for example: * [https://codeforces.me/blog/entry/113064](https://codeforces.me/blog/entry/113064) * [https://codeforces.me/blog/entry/113251](https://codeforces.me/blog/entry/113251) * [https://codeforces.me/blog/entry/118883](https://codeforces.me/blog/entry/118883) To address the issue, we collected a variety of data — problem–solution pairs, duplicate-problem pairs, and pairs of full vs. simplified problem statements. With these data we built a dedicated **benchmark for problem retrieval** and trained a **special-purpose retrieval model** that currently achieves the best performance among open-source models in this domain. You can try the model-powered search service live at **[https://cpret.online/](https://cpret.online/)**. About two years ago, the project [yuantiji.ac](http...
**benchmark for problem retrieval** and trained a **special-purpose retrieval model** that currently, . simplified problem statements. With these data we built a dedicated ** benchmark for problem retrieval

Full text and comments »

  • Vote: I like it
  • +268
  • Vote: I do not like it

31.
By ICPCNews, 4 years ago, In English
45th ICPC World Finals Challenge powered by Huawei <img src="/predownloaded/af/22/af228fee1abb015217d8c524de74898aeff36419.png" align="right" style="height: 300px;" alt="text"/> Hello, Codeforces! **UPD:** Challenge is over. You can find result [by this link](https://codeforces.me/blog/entry/109841) We are happy to invite you to the great event the **45th ICPC World Finals Challenge powered by Huawei**,which will start on [November 17, 2022, 00:00 UTC (UTC+0)](https://www.timeanddate.com/worldclock/fixedtime.html?msg=ICPC+World+Finals+Challenge+powered+by+Huawei&iso=20221117T00&p1=1440). In this Challenge, You will have a unique chance: - to compete during **14 days online challenge**; - to solve **1 or 2 problems** prepared by different business domains of HUAWEI; - to win amazing prizes from HUAWEI! As a special prize, HUAWEI together with ICPC Foundation will provide the travel trip to the 46th Annual ICPC World Finals in a guest role to the 2 winners (1 winner for each problem)! Everybody is welcome to part...
that as emerging applications evolve, benchmark characteristics drift with time and an optimal design, , benchmark characteristics drift with time and an optimal design using benchmarks of today may not be optimal

Full text and comments »

  • Vote: I like it
  • +223
  • Vote: I do not like it

32.
By DNR, 3 weeks ago, In English
Introducing ContributionBench AI labs once treated codeforces problems as a benchmark to hill-climb. They have clearly succeeded at this goal, and achieved superhuman performance for pennies. However, we all know that there's one thing much more important than rating on CF. Conspicuously, it just so happens to be the case that AI is much worse than humans at this one thing. What is this "one thing", you ask? Farming contribution, of course. Recent events (or should I say "Recent actions"?) unfortunately suggest that AI might be developing moderate competence in this once human-dominated field too. [This blog](https://codeforces.me/blog/entry/158241) has received 172 upvotes, something unheard of for AI-authored content. As a [foremost expert](https://codeforces.me/blog/entry/154846) in this field, I'm introducing **ContributionBench**, a benchmark that aims to measure AI progress in contribution-farming. The methodology is simple and robust: 1. A blog is eligible for the benchmark if and only if [pang...
**ContributionBench**, a benchmark that aims to measure AI progress in contribution-farming., 1. A blog is eligible for the benchmark if and only if [pangram](https://www.pangram.com/) detects, AI labs once treated codeforces problems as a benchmark to hill-climb. They have clearly succeeded

Full text and comments »

  • Vote: I like it
  • +52
  • Vote: I do not like it

33.
By MohammadParsaElahimanesh, 3 years ago, In English
Be 8 times faster with radix sort! ## Introduction Radix sort is a sorting algorithm that sorts elements by grouping them based on their digits. It is a non-comparative sorting algorithm that is faster than many other sorting algorithms, including the default `std::sort` function in C++. In this blog post, we will explore how radix sort works and how to implement it in C++. ## How Radix Sort Works In radix sort, we sort elements based on their digits, starting from the least significant digit to the most significant digit. We group the elements based on each digit and sort them accordingly. This process is repeated for each digit until all digits have been considered. The result is a sorted list of elements. ## Implementing Radix Sort in C++ <spoiler summary="Here's an implementation of radix sort in C++:"> ```c++ /// In the name of God the most beneficent the most merciful #include <bits/stdc++.h> using namespace std; template<const bool negative = true, const int BITS = 9, typename _RandomAccessIte...
, we ran a benchmark test on several arrays of integers. Here are the results:, benchmark test on several arrays of integers. Here are the results: | **Array Size** | **Data Type

Full text and comments »

34.
By dedsec_29, history, 4 years ago, In English
[Tutorial] Space-Filling Curves for Mo's Algorithm Ever since I read this [blog](https://codeforces.me/blog/entry/61203), I have been curious to see how space-filling curves other than Hilbert can be used to reduce the run time. In this blog, we will see how Peano curves can help bring down the run time of Mo's algorithm-based solutions. Peano curve generalizes very easily to higher dimensions, so it's worth using for problems based on Mo's algorithm with updates. Prerequisites: [Mo's algorithm](https://cp-algorithms.com/data_structures/sqrt_decomposition.html#mos-algorithm), [Mo's algorithm using Hilbert Curve order](https://codeforces.me/blog/entry/61203), [Mo's algorithm with updates](https://codeforces.me/blog/entry/83630) <br><br> # Relation with TSP In Mo's algorithm, we try to come up with a comparator that can help us sort the queries in such a way that minimizes the total movement of L and R pointers. In other words, if we have $Q$ queries, each of the form $l_i$, $r_i$, then we wish to find such an arrangement of t...

Full text and comments »

  • Vote: I like it
  • +220
  • Vote: I do not like it

35.
By ssvb, 5 years ago, In English
$O(N^2)$ solution to Facebook Hacker Cup 2021 Round 1 problem A2 (part one) Right after the end of Facebook Hacker Cup 2021 Round 1, [user:wjomlex,2021-09-25] posted the following [comment](https://codeforces.me/blog/entry/94726?#comment-839269) in the discussion section under the announcement blog: > A common issue was people writing O(N^2) solutions to problem A when O(N) solutions are necessary. You won't be able to run an O(N^2) solution in 6 minutes when N = 800,000. But is this really true? Challenge accepted! ##### Problem A1 <div> <spoiler summary="Spoiler"> First of all, here is an $O(N)$ solution for [problem A1](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-1/problems/A1): <spoiler summary="Spoiler"> ~~~~~ #include <iostream> #include <vector> #include <stdint.h> using namespace std; /* * This is a solution for problem A1. Time complexity: O(N) * Characters in the input buffer are remapped: 'F' => 0, 'X' => 1, 'O' => 2 */ static int32_t solve_a1(const int8_t *arr, int n) { int32_t ans = 0, h...

Full text and comments »

  • Vote: I like it
  • +203
  • Vote: I do not like it

36.
By DBND, 7 weeks ago, In English
Beating Treaps & Splay with a Simple Idea: A Fast, Amortized Dynamic Segment Tree with Insertion ## The Origin & The Benchmarks: A Hardware-Aware Approach A few months ago, I independently conceptualized an idea for an amortized dynamic data structure. However, it wasn't until recently that I finally found the time to sit down and write a truly optimized, production-ready implementation for it. Curious to see if anyone else had thought of this, I dug deep into the Codeforces archives and stumbled upon a heavily forgotten [blog post from 12 years ago](http://codeforces.me/blog/entry/12285). The author successfully implemented the core base-logic: traversing down to a leaf and splitting it into two new children. **However, there was a major bottleneck in that ancient version:** It relied on **AVL Tree Rotations** (`left_rotate`, `right_rotate`) to keep the height balanced. In modern competitive programming, heavy pointer-chasing and branch-heavy rotation conditions destroy Cache Locality and inflate the constant factor massively. I realized that instead of doing local...
, achieving simple fast solution. Once I finished my implementation, I decided tobenchmark it against, Once I finished my implementation, I decided to benchmark it against highly optimized, memory-leak

Full text and comments »

  • Vote: I like it
  • +74
  • Vote: I do not like it

37.
By DNR, 2 years ago, In English
Dynamic Bitset Implementation #### Disclaimer: It might have bugs, don't send me death threats if you FST. I couldn't find a nice dynamic bitset template so I wrote one. It can be found [here](https://github.com/welcome-to-the-sunny-side/libra/blob/main/data/bitset.cpp). It has additional functionality as compared to `std::bitset` (you can answer many kinds of range queries on it, for example: "Find $k$-th set bit in range $[l, r]$). <spoiler summary="Some poor documentation"> #### General - It is used to store a 0-indexed boolean array. - Just like regular bitset, index 0 is the rightmost (sense of direction is important for `>>` and `<<`). - It uses $\lceil n/B \rceil$ blocks of size $B$ (which should be equal to bitwidth of $T$) to represent a boolean array of length $n$. Note that there may be some unused bits at the end of the last block. We will always have these unused bits set to 0. #### Functions For most functions, their use is obvious. For others: <spoiler summary="hel...

Full text and comments »

  • Vote: I like it
  • +113
  • Vote: I do not like it

38.
By THE_FOOL_ON_THE_GREY_FOG, history, 9 months ago, In English
Bahnasy Tree [cut] ** بسم الله والحمدلله والصلاة والسلام على رسول الله ** Bahnasy Tree ================== **GitHub Repository:** [Bahnasy-Tree](https://github.com/Mostafa-Bahnasy/Bahnasy-Tree) Bahnasy Tree is a dynamic tree that represents a **sequence of length $N$** (positions $1..N$). It is controlled by two parameters: - $T$ ( **threshold** ): the maximum fanout a node is allowed to have before we consider it "too wide". - $S$ ( **split factor** ): used when splitting; computed from the node size using the smallest prime factor (SPF). If $S > T$, we fallback to $S = 2$. The tree supports the usual sequence operations (find by index, insert, delete) and can be extended to support range query / range update by storing aggregates (sum, min, etc.) and optionally using lazy propagation. --- ## 1) Node meaning and the main invariant Each node represents a contiguous block of the sequence. If a node represents a block of length `sz`, then its children partition this block into...
## Benchmark results, /src/Bahnasy%20Tree%20src/competitive%20programming/non_generic_version.cpp) --- ##Benchmark, Full benchmark logs and automated testing scripts are available in the GitHub repository under

Full text and comments »

39.
By ATSTNG, history, 5 years ago, In English
What is efficient number system conversion for big integers? Number system conversion algorithm is well-known and taught in almost every basic programming course. To get $y_b = x_{10}$ (number $y$ written in base $b$ equal to number $x$ base $10$) we have to iteratively chop the lowest digit in base $b$ from number $x$ using division and remainder operators: ~~~~~ def naive_conversion(x, base): y = "" while x > 0: y = str(x % base) + y x //= base return y ~~~~~ This works in $\mathcal{O}(\log x)$ for all $x$ that fit into machine word $(\log x < w)$. However this becomes inacceptably slow when we consider numbers of length $n$ that is large enough and we cannot use $\mathcal{O}(1)$ division. Let's define $n$ as length of converted number $x$ in some number system $(w \ll \log x = n)$. Still, base of number systems $b$ and all digits in it can be stored in usual integer. So we can implement conversion above in $\mathcal{O}(n^2)$ with some efficient implementation of big-number-by-small-number division. ...

Full text and comments »

  • Vote: I like it
  • +39
  • Vote: I do not like it

40.
By Igorjan94, 4 years ago, In English
Typescript SDK for codeforces ## Hello codeforces! You know you are a programming competitions addict when [this blog](https://codeforces.me/blog/entry/12968) was 9 years ago, but you thought it was no more than 3... More than month ago or, to be more precise from 15 to 19 December 2022, codeforces has five contests in five days. I participated in all of these contests and I thought how many contestants took part in all 5 contests? **TLDR**: If you don't want to read why I decided to implement SDK on typescript and how I struggled with python, just scroll down to Typescript paragraph. **TLDR2**: Links are below. ## Python Historically I have some python scripts to work with codeforces API, so I've created `allContests.py` file, imported my old library code with method `cf` and paused for a while. Which arguments does this method have? Let's look into source code. Ah, clear, `def cf(method, **kwargs)`. F**k. OK, let's go to [API](https://codeforces.me/apiHelp/methods#contest.standings) page. O...
Mike's [heap benchmark](https://github.com/MikeMirzayanov/binary-heap-benchmark ) js is only three, ### Performance According to Mike's [heap benchmark ](https://github.com/MikeMirzayanov/binary-heap

Full text and comments »

  • Vote: I like it
  • +10
  • Vote: I do not like it

41.
By hydroshiba, 5 years ago, In English
Weird sorts #1 — LIS sort I like sorting algorithms very much, and I usually come up with weird ideas for sorting. Sometimes I wonder would those work properly, and now when I finally have the time from social distancing, I decided to start a series on my eccentric ideas &mdash; Weird sorts. As an introductory problem for Dynamic Programming, you all probably know about the Longest Increasing Subsequence problem (LIS). But what if we apply this… to sorting? Today in the first blog of the Weird sorts series, I introduce to you… the LIS sort. #### **Basic idea** The core idea is to extract the LIS from the current array and repeat it until the current array is empty. It can be shown that this process always terminates, because there will always be a LIS that have a size of at least 1, thus at each pass, we will always take at least 1 element away from the array. In the implementation, we will first find the LIS of the array and separate the LIS from the rest of the array. We will then recursively perfo...
from the average of 20 values. Here are all the source codes I used to benchmark: [link](https, Here are all the source codes I used to benchmark: [link](https://github.com/hydroshiba/Weird-sorts

Full text and comments »

  • Vote: I like it
  • +184
  • Vote: I do not like it

42.
By drdilyor, history, 3 years ago, In English
[C++] Use basic_string for graphs to speedup code and reduce memory usage **TL;DR**: Simply use `vector<basic_string<int>> adj(n);` instead of `vector<vector<int>> adj(n);` for graphs. Don't use it anywhere else. Hey Codeforces! I learned from our template lord [user:nor,2023-12-24] about basic_string. Contrary to vector, it has memory optimization. When you use a vector, it will allocate on heap and the structure of vector is similar to this: ``` struct vector { size_t size; size_t capacity; T* data; } /* 64 bits - size 64 bits - capacity 64 bits - data */ ``` (Not to mention, [the overhead of malloc](https://stackoverflow.com/a/3083006/13449712)) Which means if you are using `vector<int>` with size 1, it will be using at least 28 bytes and accessing it requires indirection to a completely different part of memory, which is bad for cache. On 32-bit systems, memory usage is lower since they are 32-bits each, but the cache unfriendliness still holds. Also, as nor mentioned, this isn't exactly how the struct vector is imp...
enough benchmark) Bear in mind that basic_string requires the element types to be "simple" types, (Problem 2 doesn't require storing adjacency list but I guessed it's a good enoughbenchmark)

Full text and comments »

  • Vote: I like it
  • +45
  • Vote: I do not like it

43.
By AkiLotus, history, 2 years ago, In English
Codeforces Round 983 (Div. 2) Polygon Resources (AkiLotus side) <b><i>Disclaimer: I only prepared ABCD and a little bit of F. For materials from other setters, please reach them and ask politely for permissions first.</i></b> All codes in this blog were initially written by me, and got standardized by [user:Artyom123,2024-11-07] (thank a ton!). I will later attach a link with all the source codes below ready for download (I don't have access to my PC right now for this). Arguments used in problems is not available &mdash; I don't think mine was ever perfect, and you're free to experiment yourself. [problem:2032A] <spoiler summary="Briefings"> Nothing much in this problem, just standard preparation: an exhaustive gen, a random gen, and a maxima gen for $n = 50$. Maxima generator was done with the main idea of the solution in mind: the answer only depends on $\text{cnt}_1$, so iterate each such value, generate the desired amount for each array, and shuffle it. </spoiler> <spoiler summary="thresholds.h"> ```cpp namespace variable...

Full text and comments »

  • Vote: I like it
  • +43
  • Vote: I do not like it

44.
By willy108, history, 6 years ago, In English
std::stable_sort vs std::sort This is my first blog post, so it probably will end up being scuffed. ============================== The problem ============================== So I was working on [CF 472D, Design Tutorial: Inverse the Problem](https://codeforces.me/contest/472/problem/D) and it requires an MST (sorry for spoiling) and I chose to use Kruskals MST to do this (just note that I could've avoided this issue by using any other MST alg, but that's not the point here). So I just coded vanilla Kruskals where I [std::sort](http://www.cplusplus.com/reference/algorithm/sort/)'ed the edges and used a DSU with path compression and union by size. And I submitted the code and lo and behold, [it was TLE on tc 39](https://codeforces.me/contest/472/submission/109422457)! I entered into a state of depression and decided to change my std::sort to [std::stable_sort](http://www.cplusplus.com/reference/algorithm/stable_sort/) and wow, it ac'ed ([with 1934ms on a 2 second TL](https://codeforces.me/contest/472/subm...
stable_sort - TLE tc 39, c++11 with sort also note I did not benchmark memory since that was not, also note I did not benchmark memory since that was not something that bothered me in all of this

Full text and comments »

  • Vote: I like it
  • +73
  • Vote: I do not like it

45.
By Redpo, 3 years ago, In English
[C++] Some programming language tips and tricks Hello, Codeforces! Here are some language tips and tricks I have discovered that could (hopefully) help you write more concise or efficient code. Note that all of the below tips are specific to the C++ programming language and the STL library. ## Creating a `std::set` or `std::map` from sorted data in $O(n)$ time The sorted containers `set` and `map` are usually implemented as red–black trees, meaning that their `insert` operation runs in $O(\log n)$ time by default. Naturally, repeating the `insert` operation $n$ times would result in a time complexity of $O(n\log n)$. ~~~~~ vector<int> a = /* ... */; set<int> s1; for (int e : a) { s1.insert(e); } // O(n log n) ~~~~~ However, `set` and `map` also provide a constructor method, that directly constructs the data structure from a given pair of iterators. In most implementations of C++, if the data contained within the range is already sorted, the constructor instead runs in $O(n)$ time. ~~~~~ vector<int> a = /* some...
*/; set s3(&arr[1], &arr[n] + 1); // ditto ~~~~~ Here is a simple benchmark code that I, ~~~~~ #include #include #include, Here is a simple benchmark code that I have written to illustrate the above performance difference

Full text and comments »

  • Vote: I like it
  • +75
  • Vote: I do not like it

46.
By chromate00, 3 years ago, In English
Breakthrough in 1955G — Bitset where you least expect Two days ago, the Div.3 ([contest:1955]) suffered from severe issues of hacks, because the problem G ([problem:1955G]) did not have proper validation for the sum of $nm$ in hacks, which was specified as at most $2 \cdot 10^5$ in the statements. Sure, I won't ask about why that happened, that is not constructive discussion. Instead, I will discuss about something very interesting about the task. During that incident, I was wondering. There has to be a way to solve this without the constraint on $n \cdot m$, right? Of course, $7\times 10^8$ bytes of input is impossible anyways, but if we ignore that, $10^8$ is not a very "dreaded" number under these ages of optimizations. There has to be a way to do this. Then the idea came to me. ------ Before we cover the solution, we cover a few basic facts on number theory &mdash; it might not be necessary to know this to understand the solution, but it will be helpful. Basically, every integer is a point on the grid of infinite dimension...
. ------ [submission:255932465] is the accepted submission, and the benchmark is as follows. For all, [submission:255932465] is the accepted submission, and the benchmark is as follows. For all cases

Full text and comments »

  • Vote: I like it
  • +15
  • Vote: I do not like it

47.
By SPyofgame, history, 6 years ago, In English
C2/A2-Binary Table minimize operations ### Original Problem - Easy Version: [Div 2](https://codeforces.me/contest/1440/problem/C1), [Div 1](https://codeforces.me/contest/1439/problem/A1) - Hard Version: [Div 2](https://codeforces.me/contest/1440/problem/C2), [Div 1](https://codeforces.me/contest/1439/problem/A2) ------- You are given a binary table of size $n×m$. This table consists of symbols $0$ and $1$ You can make such operation: select $3$ different cells that belong to one $2×2$ square and change the symbols in these cells (change $0$ to $1$ and $1$ to $0$) Your task is to make all symbols in the table equal to $0$. You dont have to minimize the number of operations. **(It can be proved, that it is always possible)** -------- And the constraints are - $2 \leq N, M \leq 100$ - Easy Version: Limited in $3 \cdot N \cdot M$ operations - Hard Version: Limited in $1 \cdot N \cdot M$ operations <spoiler summary="Code solution without minimizing (with comments)"> <spoiler summary="Problem ...

Full text and comments »

  • Vote: I like it
  • +56
  • Vote: I do not like it

48.
By Spheniscine, history, 7 years ago, In English
Addendum: Optimized variant of Barrett reduction + proof re: ultimate NTT article This is an extension of [my article proposing the "ultimate" NTT](https://codeforces.me/blog/entry/75326). Here I will present a simplified and optimized variant of the Barrett reduction algorithm on that page. As it relaxes certain bounds of the standard parameters of the algorithm, I will also present a proof of the correctness of the variant, at least for this specific case. First, the algorithm: ~~~~~ function mulMod(a: Long, b: Long): Long { xh = multiplyHighUnsigned(a, b) // high word of product xl = a * b // low word of product g = multiplyHighUnsigned( (xh << 2) | (xl >>> 62) , BARR_R) t = xl - g * MOD - MOD t += (t >> 63) & MOD return t } ~~~~~ Notice that the middle routine has been greatly simplified; instead of computing the high and middle words of $xr$, we simply take the top 64 bits of $x$, in effect computing $\displaystyle \left\lfloor \left\lfloor \frac{x}{2^{62}} \right\rfloor \frac{r}{2^{64}} \right\rfloor$ in place o...

Full text and comments »

  • Vote: I like it
  • +47
  • Vote: I do not like it

49.
By lrvideckis, history, 21 month(s) ago, In English
on minimizing the expected number of recursive calls for segment tree For the longest time, this comment https://codeforces.me/blog/entry/112755#comment-1004966 was bugging me (the part about how the 'complete' segment tree is 20% slower (complete, because it’s a complete binary tree)). Instead of benchmarking, this blog calculates the expected number of recursive calls visited between segment tree implementations. Thanks to [user:camc,2025-03-03] for giving valuable feedback. This blog will study 2 implementations of segment trees. <spoiler summary="'standard' segment tree"> ~~~~~ void dfs(int v, int l, int r) { // [l, r) if (r - l == 1) { return; } int m = (l + r + 1) / 2; dfs(2 * v, l, m); dfs(2 * v + 1, m, r); } // dfs(1, 0, n); ~~~~~ </spoiler> And <spoiler summary="'complete' segment tree"> ~~~~~ int split(int l, int r) { int pw2 = 1 << __lg(r - l); return min(l + pw2, r - pw2 / 2); } void dfs(int v, int l, int r) { // [l, r) if (r - l == 1) { return; } int m = split(l, r); dfs(2 ...

Full text and comments »

  • Vote: I like it
  • +52
  • Vote: I do not like it

50.
By dsogari, 2 years ago, In English
Reusable modular integer for C++ (with static/dynamic moduli) <spoiler summary="A little bit about myself"> This is my first blog post on CF, and is probably a good starting topic for someone of my rating. Technically I'm not a CS, but an engineer who worked professionally as a software developer. CP was uncharted territory to me until recently, though now I find myself studying algorithms and working to improve my math skills so I can have fun solving difficult problems. :) </spoiler> So here's what I present: a structure for modular arithmetic operations which is short, reusable across static and dynamic moduli, supports 64-bit moduli and is as efficient as performing the operations manually. It requires the C++17 standard or newer. ### Motivation For the most part, there's obviously nothing novel about this idea: it was inspired by other blog posts ([63903](https://codeforces.me/blog/entry/63903), [23365](https://codeforces.me/blog/entry/23365)), as well as by various submissions to CF problems. On the other hand, I haven't come a...
### Benchmark, This article wouldn't be complete without a benchmark, so I'm putting here the result of a test

Full text and comments »

  • Vote: I like it
  • +45
  • Vote: I do not like it

51.
By Gornak40, history, 15 months ago, translation, In English
The Fastest String Shuffle Imagine you need to iterate through many random permutations of a string and perform some quick check for each one. The check is so fast that the bottleneck in your solution becomes the shuffling. *For simplicity, in the snippets, I've sped up the check to a no-op and added printing the final string.* #### Implementation with `random_shuffle` ~~~~~ #include <bits/stdc++.h> using namespace std; #define ITER 10000 int main() { string s; cin >> s; for (int i = 0; i < ITER; ++i) { random_shuffle(s.begin(), s.end()); // do_something(s); } cout << s << '\n'; } ~~~~~ We'll benchmark this on a random `[a-zA-Z0-9]` string of length $2 \cdot 10^5$. <spoiler summary="How to generate such a string on Unix?"><pre>tr -dc '[:alnum:]' < /dev/urandom | head -c 200000 > stroka.txt</pre> </spoiler> Compile the code with **g++ 14.2.1** using the standard `-O2` flag common in most judging systems. On my laptop, the user CPU time was $26.78$ se...
<< s << '\n'; } ~~~~~ We'll benchmark this on a random `[a-zA-Z0-9]` string of length $2 \cdot, the benchmark?, We'll benchmark this on a random `[a-zA-Z0-9]` string of length $2 \cdot 10^5$.

Full text and comments »

  • Vote: I like it
  • +36
  • Vote: I do not like it

52.
By -WIDA-, history, 16 months ago, In English
NowCoder Summer Multi-School Training Camp 2025 Hello, Codeforces! As the official team of NowCoder (China's leading programming competition platform), we are pleased to introduce the 2025 NowCoder Summer Multi-School Training Camp! This annual event has been running for eight years. Since the summer of 2018, we have collaborated with top competitors from algorithmic competitions such as ICPC, NOI, and IOI, aiming to enhance participants' programming skills through competitions, lectures, and exchanges, and to prepare for upcoming competitions like ICPC and CCPC in the second half of the year; simultaneously, we seek to foster learning and exchange among university training teams worldwide. <center> <h2 style="border-bottom: 1px solid #000;">Details</h2> </center> 1. **Schedule**. Consistent with last year, this year's training camp will consist of ten ICPC-style competitions, starting on [Tuesday, 15 July 2025<sup title="timezone offset" style="font-size:8px;" data-immersive-translate-walked="24cdac9c-eeae-41da-aef2-9dcf...
reference benchmark below is all the teams that answered more than or equal to 8 questions in this

Full text and comments »

  • Vote: I like it
  • +116
  • Vote: I do not like it

53.
By Zachary_Gao, history, 2 months ago, In English
Linear Basis over Composite Moduli: Timestamped $p$-adic Echelon Table > This article presents an algorithmic research result developed by GPT-6-ASTRA. > The complete code, formal proofs, benchmarks, and experimental results are available in the repository: [ASTRA4OI](https://github.com/Zi-Gao/ASTRA4OI). ## Conclusions The algorithm achieves a time complexity close to that of standard interval linear bases over fields. Let: $$m=\prod_{s=1}^{w}p_s^{k_s},\qquad K=\sum_s k_s.$$ | Mode | Dominant Modular Ops (Preprocessing) | Dominant Modular Ops (Per Query) | Basis Structure Space | | --- | --- | --- | --- | | Prime power, offline by right endpoint | $O(nd^2k)$ | $O(d^2)$ | $O(d^2k)$ | | General composite modulus, offline by right endpoint | $O(nd^2K)$ | $O(wd^2)$ | $O(d^2K)$ | | Persistent prefixes, online queries on arbitrary historical intervals | Same as above | Same as above | $O(nd^2K)$ | In particular, when `m = p²`, each column requires only two slots, achieving the same dominant asymptotic complexity as a standard linear basis ov...

Full text and comments »

  • Vote: I like it
  • +25
  • Vote: I do not like it

54.
By wrick, history, 11 years ago, In English
Fastest Scanner in Java In my [previous post](http://codeforces.me/blog/entry/21074), I discussed a fast Scanner for Scala. To benchmark it, I wrote the fastest possible Scanner I could in Java: ~~~~~ package better.files; import java.io.BufferedReader; import java.io.IOException; import java.io.UncheckedIOException; import java.util.Arrays; /** * Hand built using a char buffer */ public class ArrayBufferScanner extends AbstractScanner { private char[] buffer = new char[1 << 4]; private int pos = 0; private BufferedReader reader; public ArrayBufferScanner(BufferedReader reader) { super(reader); this.reader = reader; } @Override public boolean hasNext() { return pos != -1; } private void loadBuffer() { pos = 0; while (true) { int i; try { i = reader.read(); } catch (IOException e) { throw new UncheckedIOException(e); } if (i == -1) { pos = -1; break; } ...
Benchmark results: https://github.com/pathikrit/better-files/tree/master/benchmarks, To benchmark it, I wrote the fastest possible Scanner I could in Java:

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it

55.
By c1729, history, 8 years ago, In English
Python Performance++ I've listed my findings on experimenting with Python below, I hope they are useful to someone else who uses Python too. **TL;DR:** Links for the [master template](https://github.com/cheran-senthil/PyRival/blob/master/template/template.py) and [algorithms](https://github.com/cheran-senthil/PyRival). #### __Python Version__ Based on [prior benchmarking](https://codeforces.me/blog/entry/21851) on Codeforces, it is quite conclusive that PyPy 2 is the fastest version of Python available on Codeforces. PyPy 2 also has features not present in PyPy 3 such as random, and numpypy. Moreover, in Python 2, bytes and strings are equivalent, this is not the case in Python 3 and results in significant input and output slowdowns unless you use Bytes in Python 3. #### __Input & Output__ Though there are faster ways to read input for specific types (integers and non-strings). The safest way to redefine input/print while maintaining the same functionality is to use the following code, ...

Full text and comments »

  • Vote: I like it
  • +46
  • Vote: I do not like it

56.
By raoxj, history, 23 months ago, In English
Performance Ratings vs Ratings of Solvable Problems for the Recent GPT Models The GPT models have made great advancements in competitive programming recently. I saw from [user:Qingyu,2024-12-21]'s [blog](https://codeforces.net/blog/entry/137534) earlier that the new o3 model claims to achieve a 2727 performance rating. However, I'm slightly uncertain of how this 'rating achieved' should be interpreted. There is very little detail publicly available on how the performance ratings are computed. The only available detail I could find regarding their benchmark methodology is the following quote from the ['reasoning with LLMs' blog](https://openai.com/index/learning-to-reason-with-llms/): > Finally, we simulated competitive programming contests hosted by Codeforces to demonstrate this model’s coding skill. Our evaluations closely matched competition rules and allowed for 10 submissions. This does not really offer any detailed computation methods. Given the limited details, I'm hypothesising that the LLM doesn't need to solve problems anywhere close to the 270...
detail I could find regarding their benchmark methodology is the following quote from the ['reasoning, performance ratings are computed. The only available detail I could find regarding theirbenchmark

Full text and comments »

  • Vote: I like it
  • +157
  • Vote: I do not like it

57.
By MikeMirzayanov, 12 years ago, translation, In English
TODO: Open addressing hash table on C++ Hello, Codeforces! In late December and early January, I wrote a proof-of-concept of separate service in C ++, to take out heavy data from the Codeforces Java-code to C++. Long time I have not written in C ++, experienced a funny sense of immersion into another world. I was surprised to find the lack of open-addressing hashmap in the C++ standard library, and indeed in the boost, and in other popular libraries. It is strange somehow, because often open addressing should be better than separate chaining both in time and memory. And since I intend to keep small objects, then sure. I quickly sketched a prototype that actually shows that open addressing in 2-3 times faster than the standard std::unordered_map. Here's the output of the benchmark on my laptop: ~~~~~ std :: map takes 15779 ms std :: unordered_map takes 4698 ms oaht :: hash_map takes 1473 ms ~~~~~ I think that there is no good implementation of such container in stl-style with the support of C++11 (move sema...
standard std::unordered_map. Here's the output of the benchmark on my laptop: ~~~~~ std :: map, the standard std::unordered_map. Here's the output of the benchmark on my laptop:

Full text and comments »

  • Vote: I like it
  • +140
  • Vote: I do not like it

58.
By slycelote, 13 years ago, In English
Performance of hash set iterators in different programming languages **Update: Turns out that both C# and Mono actually have the same problem as Java.** I don't know C# though, so it would be great if someone reviewed the code of the benchmark (bottom of the post). Recently I noticed that switching from `HashSet` to `TreeSet` in a Java program increased performance by several times. Since it didn't make any sense, I decided to investigate the issue, and here is what I found. In my program I extracted an arbitrary member from a set in the following manner: ~~~~~ Integer elem = set.iterator().next(); set.remove(elem); ~~~~~ It turns out that implementation of `HashSet.iterator()` method in Java is poor: it always scans the bucket table from the very beginning. An excerpt from JDK code: ~~~~~ HashIterator() { expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ...
# though, so it would be great if someone reviewed the code of the benchmark (bottom of the post

Full text and comments »

  • Vote: I like it
  • +35
  • Vote: I do not like it

59.
By jlahcejlot, history, 3 months ago, In English
Mindrift is looking for competitive programmers — get paid to break AI-generated code ### Mindrift is looking for competitive programmers — get paid to break AI-generated code **Who we are:** Mindrift connects specialists with project-based opportunities for leading tech companies, focused on testing, evaluating, and improving AI systems. We're not a product company — we build the training and evaluation data that makes AI models actually good at their job. Right now, we're looking for competitive programmers to help with coding models specifically. We're looking for competitive programmers to help build problems and graders used to train AI coding models. If you enjoy problem-setting, hacking weak solutions, and writing brutal test cases — this might be for you. **What you'd actually do:** - Write original algorithmic problems (statement, constraints, intended solution) - Write correct solutions in C++ and Python - Write realistic wrong solutions — the kind of bugs real contestants actually submit - Build generators, edge cases, stress tests, and testlib...

Full text and comments »

  • Vote: I like it
  • -19
  • Vote: I do not like it

60.
By kfx, history, 11 years ago, In English
Python performance tips Python is a great programming language: simple, expressive, compact. In Codeforces, Python is often the best choice for Div 2 A and B problems. For example, problem [problem:600A] is very easy to write in Python: first tokenize the string with the built-in `split()` function, then try to parse the integers with the built-in `int()`, then output the comma-separated strings of results with `",".join(lst)`. For the more complex problems, writing fast-enough Python code is often a challenge. Here is a list of tips to improve performance. - Use PyPy instead of the standard Python interpreter. According to [20 offical benchmarks](http://speed.pypy.org/) it is on average 7 times faster than Python 2. PyPy2 is in my opinion the best option at the moment for competitive programming. - Append to an existing string with "+=" instead of concatenating **more than two** strings with "+" and storing the result with "=". (With two strings, both ways work fine. `s1 = s1 + s2` is fast becaus...

Full text and comments »

  • Vote: I like it
  • +124
  • Vote: I do not like it

61.
By wrick, history, 11 years ago, In English
Faster Scanner in Scala We all know that `java.util.Scanner` [is slow](https://www.cpe.ku.ac.th/~jim/java-io.html). Here is a version in Scala that is idiomatic (you can do all the Collections API e.g. `.take`, `.map`, `.filter` etc) and supports line numbers too and is much faster than the Java Scanner: ~~~~~ import java.io._ import java.nio.file.{Files, Path} import java.util.StringTokenizer import scala.io.Codec /** * Scala implementation of a faster java.util.Scanner * See: http://codeforces.me/blog/entry/7018 */ class Scanner(reader: LineNumberReader) extends Iterator[String] with AutoCloseable { def this(reader: BufferedReader) = this(new LineNumberReader(reader)) def this(reader: Reader) = this(new BufferedReader(reader)) def this(inputStream: InputStream)(implicit codec: Codec) = this(new InputStreamReader(inputStream, codec.charSet)) def this(path: Path)(implicit codec: Codec) = this(Files.newBufferedReader(path, codec.charSet)) def this(file: File)(implicit cod...

Full text and comments »

  • Vote: I like it
  • +47
  • Vote: I do not like it

62.
By Addy, history, 10 years ago, In English
How to start Competitive Coding. "Where do I start?" "How do I get better?" Stuck here? Don't worry, here is a guide that will help you answer these questions . "Where do I start?" Step 0: Prerequisites: Determination / Dedication. Step 1: Choosing your language. Which: The language should be preferably C++ or Java, the last preference should be Python (due to its unavailability on many official coding platforms, e.g., the ACM ICPC). We will focus on C++, Java is slow, but more importantly lacks shorthand generic implementations of standard templates (one big advantage of Java is Big Integers, which we will see later) Why: Java, C++, Python have libraries that would cut the time to write the code, as well as increase the efficiency most of the times. Example: sort(a,a+n); //in C++ would sort the array of n elements in O(nlogn) time. It is both simpler to implement and more efficient than the O(n^2) sorts. If you know C, it is very easy to switch to C++. With almost no effort, you can use v...

Full text and comments »

  • Vote: I like it
  • +33
  • Vote: I do not like it

63.
By Marco_L_T, history, 4 months ago, In English
OpenFrontierCS Challenge: the AHC for Human-AI agent Collaboration on Open-Ended Tasks **Hello Codeforces!** Today, our team (me, [user:JoyeMang,2026-07-10], [user:Tohsaka_Sakura,2026-07-10], along with other amazing collaborators), with the support from Eigen Labs, are officially launching the **FrontierCS** AutoResearch challenge which is live at [http://openfrontiercs.com](http://openfrontiercs.com)! [Simply link your GitHub account and join!](http://openfrontiercs.com) Think of this as an **AtCoder Heuristic Contest where AI agents are fully allowed and actively encouraged and the duration is much longer for space to fully optimize.** **The Goal: Pushing the Ceiling of Human-Machine Collaboration** We want to measure the limits of human-AI collaboration on complex, ICPC challenge-style problems. While the open-source AI community is already heavily involved, we believe **human intelligence from competitive programmers is the missing key**. We want to see **how top algorithmic minds can guide, improve, and integrate their problem-solving wisdom into the...
problems from FrontierCS benchmark (which was recently presented at ICML 2026). * **Open Science

Full text and comments »

  • Vote: I like it
  • +13
  • Vote: I do not like it

64.
By quynhnhu.111207, history, 9 months ago, In English
Is this a new segment tree variant or a rediscovery ? ### Hello Codeforces As the title states, I think I may have discovered a very nice segment tree variant, but I am not sure whether it corresponds to something already known. ## Supported Features And Time Complexity - Range query (RMQ): O(log n), more precisely O(log r) - Point update: O(log n) - Push back (append new element at the end): amortized O(1) - Pop back (remove last element): O(1) - 2n+1 memory complexity These are theoretical algorithmic complexities , not including CPU-level behavior (cache effects, branch prediction, etc.) into account. ## Memory | Structure | Memory (units) | |---------------|----------------| | IterSegment | 2000000 | | ForestSegment | 2000001 | ## Benchmark (n = 1,000,000 ; q = 10,000,000) In its optimized version, it has performance comparable to the iterative segment tree, as shown in the benchmark below. You are welcome to copy the benchmark code and test it yourself. | Operation | IterSegment (m...
the benchmark below. You are welcome to copy the benchmark code and test it yourself., ## Benchmark (n = 1,000,000 ; q = 10,000,000), ## Full Benchmark Source (Iterative Segment Tree vs Forest), ##Benchmark (n = 1,000,000 ; q = 10,000,000), ##Benchmark Source Code, cout << "Benchmark with n="<<<", q="<<<"\n";

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

65.
By Trace_X1729, 16 months ago, In English
A New Way (supposedly) to answer Range Queries with Point Updates. Hello everyone :) I am going to present a new way(I couldn't find it on the internet) to do range queries with point updates, back story and all other details later: It is very intuitive and easy to understand, also I have included a lot of examples so please read till the end, it will be especially useful for those who are reluctant to study segment trees (I think). You are given an array A of size N, and Q queries involving both point updates and range queries. First we will have to do some pre-computation.I will call the precomputed structure as SST (full form later) from now. Also, for the sake of simplicity, just assume that we are constructing the structure for sum right now, the language is going to be cpp throughout the blog. ### **Declare SST:** ~~~~~ int N = A.size() - 1;//this is assuming that the array passed is 1-indexed. vector<vector<int>>SST(N + 1); //It is basically a 2-D vector of size N + 1, where N is the size of the array. It is N + 1 to ha...

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

66.
By Qualified, history, 6 years ago, In English
Weird Sieve Running Time Disclaimer: Make sure to get yourself comfortable before reading this comment. I was intrigued by the earlier discussion on sieves and decided to benchmark some sieves. There are 2 that I benchmarked with surprising differences in running time. One of them can be found here. [https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html](https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html). Under the "Different optimizations of the Sieve of Eratosthenes". The optimization is sieving to the root. Another one is [user:Nisiyama_Suzune,2021-01-01]'s https://codeforces.me/blog/entry/54090. Under the section "Linear sieve". It is a direct copy-paste from the CodeForces blog. Now, here comes the surprising part. https://cp-algorithms.com/algebra/prime-sieve-linear.html. Under the section "Runtime and Memory" it says "and the optimized versions of the sieve run as fast as the algorithm given here." Note: the optimized versions is the one that I used in my benchmarking. This states tha...
the earlier discussion on sieves and decided to benchmark some sieves. There are 2 that I benchmarked

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it

67.
By urbanist, 11 years ago, In English
Competitive Programming Platforms Benchmark: CodeForces, TopCoder, HackerRank, CodeChef Lately I have been participating in various competitive programming contests online, and there are some major platforms available now, that were not there several years ago. I have decided to compile a benchmark for these platforms: hopefully it might be useful for other contestants as well. This list is by no means exhaustive, and more contests can be found through the following link, although information provided there is not always complete/accurate: [www.hackerrank.com/calendar](https://www.hackerrank.com/calendar) <table> <tr> <th style="width:20%">CATEGORY</th><th style="width:20%">CodeForces</th><th style="width:20%">TopCoder</th><th style="width:20%">HackerRank</th><th style="width:20%">CodeChef</th> </tr> <tr> <td>SHORT CONTEST NAME & DURATION</td><td>Codeforces Round: 2 hours</td><td>Single Round Match (SRM): 1.5 hour</td><td>101 Hack: 2 hours,<br/>HourRank: 1 hour</td><td>Cook-Off: 2.5 hours</td> </tr> <tr> <td># OF DIVISIONS</td><td>2</td><td>2</td><td>1</td><t...
Competitive Programming Platforms Benchmark: CodeForces, TopCoder, HackerRank, CodeChef, a benchmark for these platforms: hopefully it might be useful for other contestants as well. This

Full text and comments »

  • Vote: I like it
  • +36
  • Vote: I do not like it

68.
By elnazar, history, 3 years ago, translation, In English
Optimize Your Python Codeforces Solutions: Say Goodbye to str += str and Time Limit Hello dear python-codeforcers! ###Introduction Python is a popular language among Codeforces enthusiasts due to its simplicity and ease of use. However, one common pitfall many Python Codeforces participants fall into is the inefficient use of string concatenation using str += str that leads to get Time Limit. In this blog post, we'll explore why this can be problematic and introduce a more efficient alternative using lists. ###The Issue with str += str When building strings iteratively, it's a common instinct to use the += operator to concatenate strings. However, what many Python developers may not realize is that this operation has a time complexity of approximately O(n^2). Consider the following code snippet (solution for [problem:1927B]): this solution is correct, however you are going to get Time Limit due to str += str ~~~~~ def solve(): n = int(input()) nums = list(map(int, input().split())) letters = [0] * 26 answer = '' for i in ra...
###Benchmarking the Difference Let's put the two approaches to the test with a simplebenchmark, . ###Benchmarking the Difference Let's put the two approaches to the test with a simplebenchmark

Full text and comments »

  • Vote: I like it
  • -9
  • Vote: I do not like it

69.
By SecondThread, history, 6 years ago, In English
Algorithms Dead Episode 2: RMQ Tricks! Algorithms Dead Episode 2: RMQ Tricks ================== [Episode 2 of Algorithms Dead](https://youtu.be/GWXf3vVtf-c) is out now! In it, I talk about: - How to find the min in a range of an array on O(1) - How to build an RMQ in O(n) - How to use an RMQ to find the lowest common ancestor in a tree If you're new to these ideas, or looking for a refresher, it might be worth checking out. If you have questions, feel free to post them below instead of DMing me, so that other people with the same questions can see the answers. Further Reading ------------------ [user:brunomont,2020-06-20] and [user:tfg,2020-06-20] showed me their fantastic (and recently published) blog post here: [https://codeforces.me/blog/entry/78931](https://codeforces.me/blog/entry/78931). This didn't influence this episode or anything (my stuff was based on [user:jcg,2020-06-20]'s comment on [this post from 7 months ago](https://codeforces.me/blog/entry/71706)), but [user:brunomont,2020-06-20] d...

Full text and comments »

  • Vote: I like it
  • +181
  • Vote: I do not like it

70.
By phpduke, history, 13 months ago, In English
[Guide] Meta HackerCup AI Meta HackerCup is unique, as it is the only place as far as I know that allows anyone to compete their AI models against top human competitors live! Without a lot of introductory blogs on how to get started competing in AI track, it becomes daunting to start & hence this blog. Received a dozen messages asking how we built a winning solution to last year's Meta Hacker Cup, will write separate post on that maybe. A lot has changed from last year to this, thinking models are already very good at competitive programming model out of the box. This is good because it lowers bar of entry participation while pushing bar for creating a differentiated top solution. Goal of contest is to build an automated system that generates solution to competitive programming problems WITHOUT any human intervention. That is you cannot nudge/hint your AI system leveraging your human intuitions. Anatomy of a typical solution ============================= A lot of the solutions/ideas can be dissect...
effectively create verifiable test environment, you can smoke that benchmark with RL. Coding & Math both, verifiable test environment, you can smoke that benchmark with RL. Coding & Math both fit very

Full text and comments »

  • Vote: I like it
  • +33
  • Vote: I do not like it

71.
By xsc, history, 10 years ago, In English
Again, low-level i/o C++. I decided to rewrite this post, previously has been deleted. I know there a many of posts low-level i/o. scanf/printf solves slowly i/o, partially, but not always. Most generic usage i/o &mdash; is read and write integers, so I'll write about it without a hundred lines of source code. 1. Read integers. =================== For simplicity, all input file content loaded to a big buffer, and it will be parsed. ~~~~~ char in[1<<23] ; // a big buffer char const* o ; // pointer to buffer. ~~~~~ And for detecting end of buffer, put '\0' &mdash; terminating symbol to end of buffer ( as plain c-string). #### Now loading the file: ~~~~~ void load(){ o = in; in [ fread(in, 1, sizeof(in ) - 4 , stdin ) ] = 0; } ~~~~~ `fread - returns number of reading symbols, we just use this for put '\0' terminating symbol to end of buffer.` #### Reading a unsigned integer: ~~~~~ unsigned readUInt(){ unsigned u = 0; while( *o &...
[submission:24133798] ### Benchmark: read and write 10^6 numbers took [120~150 milliseconds](https, ### Benchmark: read and write 10^6 numbers took [120~150 milliseconds](https://github.com

Full text and comments »

  • Vote: I like it
  • +33
  • Vote: I do not like it

72.
By jamjury, history, 2 years ago, In English
Memory-mapped i/o Memory-mapped input file is the fastest possible input method I know of. I used it for [last ICPC Challenge](https://codeforces.me/blog/entry/127855). Unfortunately, it is not possible &mdash; without exploiting Windows kernel bugs &mdash; to also map output file into memory on CF, because the handle lacks `GENERIC_READ`, which is required for `FILE_MAP_WRITE` mapping. So the best we can do for output is to write the whole buffer at once (but it doesn't really speed things up). ~~~~~ #include <Windows.h> // GetStdHandle, GetFileSize, CreateFileMapping, MapViewOfFile, UnmapViewOfFile, WriteFile, CloseHandle #include <charconv> // from_chars, to_chars #include <cstring> // memcpy #include <cstdlib> // malloc, free #include <cstddef> // size_t // #define FREE_IO_ON_EXIT struct input { LPVOID view; const char *first, *last; input() noexcept { HANDLE input_handle = GetStdHandle(STD_INPUT_HANDLE); DWORD input_size = GetFileSize( ...
() { out.put_int(in.take_int()); } ~~~~~ [The benchmark ](https://codeforces.me/blog/entry/5217, [The benchmark](https://codeforces.me/blog/entry/5217) ([webarchive](https://web.archive.org/web

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it

73.
By marwanMJH, history, 5 weeks ago, In English
I benchmarked std::set, std::map, unordered_set and my own RB/AVL trees at 60M ops Hi Codeforces! I wrote hand-rolled **Red-Black** and **AVL** trees in C++ and benchmarked them against `std::set`, `std::map` and `std::unordered_set` with 10M inserts, 10M searches and 10M removes per structure (plus a 1M random preload). My first write-up concluded that *"my RBTree beats std::set by ~2.5x"*. Then I noticed my Makefile had `CXXFLAGS = -Wall -std=c++17` — **no `-O2`**. Codeforces compiles with `-O2`, so those numbers said almost nothing about contest performance. Here's the corrected comparison, plus a small anti-hash experiment, since that's where `unordered_map` really bites in contests. ### Setup - 1,000,000 random `int` keys preloaded from a file, then $$$10^7$$$ inserts, $$$10^7$$$ finds and $$$10^7$$$ erases with **sorted** keys (`k * 13`). - Single-threaded, `std::chrono` wall time, GCC 13, `-std=c++17`. - Code: [github.com/marouaneMJH/cpp-software-design](https://github.com/marouaneMJH/cpp-software-design) ### Results (ms, int keys) | Struct...
takeaways for contests - **Always benchmark with the judge's flags.** `-O0` numbers can reverse your, - **Always benchmark with the judge's flags.** `-O0` numbers can reverse your conclusions

Full text and comments »

  • Vote: I like it
  • -7
  • Vote: I do not like it

74.
By Gleefre, history, 4 years ago, In English
Please add support for Common Lisp language Hello, I have posted this as a comment to big old post [About the programming languages](https://codeforces.me/blog/entry/79), but this was probably not the best place to post to. So I am repeating it here with hope to get some kind of answer to it. Common Lisp is a very powerful language that can run at speed of c++ and is even more expressive than python (IMHO). I think that it is really worth adding as supported language because it is a very mature language, which has a very reach set of features. It was asked to add it as supported language for quite a few times now, starting from 13 years ago every 1-2 years. --- In hope that it will be able to help (judging by comment to Julia request): Here is an implementation of **binary heap sort benchmark** in common lisp: https://github.com/Gleefre/binary-heap-benchmark/blob/master/common-lisp/heap.lisp (and I'll be glad to create a PR if wanted). One of the best open source common lisp implementations is probably [...
to Julia request): Here is an implementation of **binary heap sort benchmark** in common lisp, Here is an implementation of **binary heap sort benchmark** in common lisp: https://github.com, On my computer, `heap.lisp` benchmark results in a range of `[693..846] ms` with an average time of

Full text and comments »

  • Vote: I like it
  • +75
  • Vote: I do not like it

75.
By z4120, history, 7 years ago, In English
Faster modular multiplication Note: This technique had been used before at https://codeforces.me/blog/entry/60851 (editorial code of problem F) and https://codeforces.me/problemset/submission/1017/41357847 . While this solution is faster than using `int64_t` (because Codeforces machines are 32-bit), the time limit should be loose enough for solution that does not use this trick to pass. However, this trick may be useful if you want to be very fast or implement an unintended/suboptimal brute force solution. (the same thing can be said about fast input/output methods. On Codeforces, cin/cout is usually fast enough) This is definitely faster than the usual `return (long long)a * b % mod`, but it might be slower than Montgomery multiplication. ------- Given a positive integer `md`, and two positive integers `a` and `b` in range `[0, md-1]`, the following function will compute `(int) ((long long) a * b % md)`: (the quotient of the division is stored in variable `d`) ```cpp int mul(int a, int b) { un...
Benchmark code: (you can copy-paste that to https://codeforces.me/problemset/customtest ), ](https://stackoverflow.com/questions/13187629)) ------------ Benchmark code: (you can copy-paste

Full text and comments »

  • Vote: I like it
  • +25
  • Vote: I do not like it

76.
By samraat1, history, 16 months ago, In English
Benchmarking LLM This blog is in extension of https://codeforces.me/blog/entry/145192 to gain wider attention for the issue as it has been 7 weeks since the user accepted his unethical practices and yet no action. The user [user:ckuhn222,2025-08-01] found cheating claim to be benchmarking LLMs and not aim to cheat &mdash; https://codeforces.me/blog/entry/143656?#comment-1283045. He argue that such benchmarking can be done only during live contest as once the contest is over and the editorial is available, LLM can just scrap the web to find the answer and its core capabilities are not tested. So, should we not have option for unrated participation in all contests like Div3 so that users honest enough and interested in such experimentation can do so without affecting the genuine standing. Also it has been 7 weeks since the user posted such comment and yet no action has been taken (rating for round 1040 updated for the user as well). Codeforces should be proactive in identifying such blatant viola...

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

77.
By _QuantumBifrost_, 20 months ago, In English
Faster Square Root Computation Using an Optimized Binary Search Hello there, welcome to my first Codeforces blog post! Today I’d like to share an educational — and frankly a fun observation — on optimizing the process of finding the square root of large integers using binary search. This may not be something you’d use in your everyday code (after all the built-in `sqrtll()` is hard to beat in speed), but it’s a neat mathematical trick that can literally save you seconds when processing many numbers. Before we dive in, a huge thanks to [user:chromate00,2025-03-13]. An answer of mine getting hacked in one of his contests sparked this discovery. --- ## Aim In a typical binary search algorithm for computing the integer square root of a number `S`, we initialize the search range with: - `low = 0` - `high = S` This approach finds the square root in **O(log(S))** iterations. But if we have to compute square roots for too many numbers (like $10^8$), it can become laggy. However, if we can choose `low` and `high` more intelligently based ...

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

78.
By iimoc, history, 7 months ago, In English
Participate in IIMOC × FrontierCS 2026! **Hello Codeforces!** Following the massive success of IIMOC (International Math Optimization Challenge) 2025, which saw over 200 teams and 9,500+ iterative submissions, we are back with something significantly more ambitious. This year, IIMOC is moving from a standard contest to a month-long, research-grade optimization marathon. ## About IIMOC x FrontierCS The IIMOC is a global high-school contest focused on heuristic problem solving. It is problemset by the FrontierCS team, a PHD research team of former competitive programmers, including CP legends and problemsetters like [user:zhoukangyang,2026-04-10] and [user:ZhouShang2003,2026-04-10]. Teams from around the world are invited to tackle a single large-scale optimization problem that is intentionally approachable but unsolvable in exact form. Over the course of one month, each team develops algorithms and heuristics to minimize loss and maximize performance. ## Dynamic Scoring and "King of the Hill" We have designe...
get a head start on the environment, check out the general benchmark and evaluation infrastructure on, For those who want to get a head start on the environment, check out the general benchmark and

Full text and comments »

  • Vote: I like it
  • +13
  • Vote: I do not like it

79.
By IceKylin, 9 months ago, In English
Segment Add Get Min – 2x Faster Than the Second Fastest <spoiler summary="UPD on 03/03/2026"> The same approach also achieves top performance on "Line Add Get Min". [58 ms, offline ver.](https://judge.yosupo.jp/submission/357336) / [72 ms, online ver.](https://judge.yosupo.jp/submission/357124) vs [77 ms](https://judge.yosupo.jp/submission/95121) </spoiler> Hi, On Library Checker's "Segment Add Get Min", my offline Li Chao Tree implementation runs about **2x faster than the second fastest submission** (as of 15/02/2026). ### Key optimizations - Radix sort for discretization - Bottom-up, segment-tree-based structure - Reduced unnecessary computations ### Results **Library Checker** [64 ms](https://judge.yosupo.jp/submission/352949) vs [128 ms](https://judge.yosupo.jp/submission/162868) → **2x faster** **QOJ** [57 ms](https://qoj.ac/submission/2037318) vs [157 ms](https://qoj.ac/submission/1962123) → **~2.75x faster** Benchmarks were measured on the latest official test data under `-std=c++23 -O2`....

Full text and comments »

  • Vote: I like it
  • +42
  • Vote: I do not like it

80.
By Dragonado, 4 years ago, In English
[Tutorial] CMS trick — an alternate solution for ABC217D and CF1567E Hello everyone, Recently [user:peltorator,2023-01-17] created a [challenge](https://codeforces.me/blog/entry/110840) to create interesting educational blogs. This gave me the motivation to write about a trick I discovered a while back. The trick is simple and I wouldn't be surprised if it already exists with some other name. But I couldn't find any blog on it so I'm making my own. I have made a data structure that deals with the partition of an array. I call it Cut-Merge-Stick (CMS) trick. A partition of an array is a grouping of its elements into non-empty subarrays, in such a way that every element belongs to exactly one subarray. I refer to every segment in this partition as a "stick". Some operations on this data structure are merging two consecutive sticks, cutting a single stick into two smaller sticks, getting the longest stick in a range, counting the number of sub-sticks in a range, etc. ## Problem statement You are given a stick of length $N$ units, placed on ...
alternate implementation is very ugly and laborsome. - I haven't tried any benchmark tests between, this alternate implementation is very ugly and laborsome. - I haven't tried any benchmark tests

Full text and comments »

  • Vote: I like it
  • +80
  • Vote: I do not like it

81.
By Klein, 12 years ago, In English
BigNum arithmetic in Java — Let's outperform BigInteger! Long story short, I've created a class called [BigInt](https://github.com/bwakell/Huldra) purely written in Java, which is pretty neat and outperforms `BigInteger`. There are most likely (many) bugs, but since it's pretty basic at the moment, it'll be a great opportunity for the Codeforces community to learn how to do arbitrary-precision arithmetic. ^^ ###Introduction The standard library `BigInteger` class in Java is known to be notoriously slow (at least for Java 7 and earlier, and I doubt Java 8 is any different). There are faster alternatives like Gnu Classpath providing support for GMP (which is optimized beyond infinity), but this is probably not a viable option for competitive programming. When it comes to pure Java we also have the `Apint` class provided by the [Apfloat library](http://www.apfloat.org/apfloat_java/) and the `LargeInteger` class provided by the [JScience library](http://jscience.org/), but these two are probably not only clunky for competitive programming ...
number, $100000$ times. (MidBig-size cumulative benchmark.) - **Sub**: Same as the addition, $ times. (MidBig-size cumulative benchmark.) - **Sub**: Same as the addition experiment, but with

Full text and comments »

  • Vote: I like it
  • +49
  • Vote: I do not like it

82.
By eval_apply, history, 5 years ago, In English
[highly opinionated] Template for Go on CodeForces.com What? ================== A small, lean and efficient template for writing code on CodeForces.com using Go. Mostly consists of input/output improvements and helper functions. Why? ------------------ Because I needed my code to be more compact, wanted more clarity and ease of use. And to speed-up a bit too. And now I share this template to you guys, to make Go a bit more appealing to use in competitive programming. P.S.: Mike even updated Go compiler to the current latest version (1.17.3), so using Go can be quite worth a candle :) How you've made it? ------------------ I've got rid of the rather slow group of simple scanners from "fmt", namely: - fmt.Scan - fmt.Scanln - fmt.Scanf because of their clumsiness and their slowness compared to other available options in Go. To learn more, start with checking some benchmarks from [this](https://codeforces.me/blog/entry/94245) post. Instead, there is a reader from bufio, which reads from os.Stdin and is much ...

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

83.
By bhikkhu, 13 months ago, In English
Super efficient RMQ alternative with updates If we build an interval tree as shown in the following picture, we can get super effective RMQ data structure as good as iterative segment tree. I have benchmarked against Fenwick RMQ and it turns out this is much much better time complexity wise than log square range decomposition. All queries take 3 logn at most because the search interval is halved every third step in worst case once we determine the offshoot segment which exceeds our leftmost point l. ![ ](https://codeforces.me/predownloaded/51/8b/518bf3fce31a2ba3677e2fff7d625d6ac7e63f92.jpeg) https://cses.fi/problemset/task/1649/ <spoiler summary="skewed range decomposition"> ~~~~~ #include <iostream> using namespace std; const int N = 200000; int tree[N + 1]; int leaf[N+1]; int len[N+1]; int par[N+1]; int n, q; void build_links(const int i){ const int L=len[i-1]; len[i]=1; if(L==len[i-1-L]){ len[i]+=2*L; par[i-1]=i; par[i-1-L]=i; } } void combine(const i...

Full text and comments »

  • Vote: I like it
  • -19
  • Vote: I do not like it

84.
By M_Sameer, history, 7 weeks ago, In English
Yet another AI tool: SMS AI for text, code, and document processing has major update. ![SMS AI Platform Screenshot](/predownloaded/3e/9f/3e9fcbf2650418a66c5efe5ea813f0c645135b2c.png) Hello Codeforces. Recently, I have been building a project called SMS AI. It is a simple but fast multimodal workspace to chat, generate code snippets, and parse documents. Now it has major update. I noticed that a lot of general web tools have quite high latency when streaming code blocks or rendering formatting properly. I wanted to see if I could optimize the processing structure to bring the time-to-first-token down under 100 milliseconds. [cut] The current implementation is live and can be tested here: [SMS AI](http://sms-ai-delta.lovable.app). Core implementation details The platform is lightweight and split into a few basic utilities that might be helpful if you are working on problems or analyzing long reference texts: • Syntax Highlighting & Code Generation: It outputs and formats raw scripts in standard languages (C++, Python, etc.) with clean sy...

Full text and comments »

  • Vote: I like it
  • -16
  • Vote: I do not like it

85.
By sufiyankhan27764, history, 14 months ago, In English
LLM(large language model) Large Multimodal Models (LMMs) – Detailed Overview 1. Introduction to LMMs Large Multimodal Models (LMMs) are an evolution of Large Language Models (LLMs). Unlike LLMs, which process only text, LMMs handle multiple modalities such as text, images, audio, video, and sometimes even structured data. Their core idea is to unify representation learning across modalities, allowing cross-modal reasoning and understanding. They are foundational models powering systems like GPT-4V (vision), Gemini, LLaVA, Kosmos, Flamingo, CLIP, and ImageBind. The ability to reason over multimodal data makes them crucial for AI applications in robotics, autonomous driving, healthcare imaging, multimodal search, and interactive AI systems. 2. Why Multimodality? Human intelligence is inherently multimodal. We process language, vision, sound, and spatial reasoning together seamlessly. LMMs aim to replicate this ability in artificial systems. A single modality (e.g., text-only) limits...

Full text and comments »

Tags llm
  • Vote: I like it
  • -37
  • Vote: I do not like it

86.
By d0j1a_1701, history, 3 years ago, In English
Fully-featured Ultra-Fast Input/Output for C++ [中文文档](https://www.d0j1a1701.cc/p/d420019/) > Hello, CodeForces! The following is a fast input/output template suitable for C++11 or higher versions. It not only supports reading and writing of all integer types, but also supports strings and floating point types. It can also set output precision, flush write buffers, format output, and other functions. NOTE: keyboard input will be ignored if the acceleration switch is enabled. You should use the template with `using namespace std;`. ## Original version ```cpp /* d0j1a_1701 FastIO full ver. 4.2 */ //#define FIO // Cache acceleration switch, DO NOT enable in interactive problems. struct IO { #ifdef FIO const static int BUFSIZE = 1 << 20; char buf[BUFSIZE], obuf[BUFSIZE], *p1, *p2, *pp; inline char getchar() { return (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, BUFSIZE, stdin), p1 == p2) ? EOF : *p1++); } inline void putchar(char x) { ((pp - obuf == BUFSIZE && (fwrite(obuf, 1, BUFSIZE, stdout), pp = o...
## Benchmark Read 5 million long long integers, repeat the test five times., ."); ``` ## Benchmark Read 5 million long long integers, repeat the test five times. Without-acceleration

Full text and comments »

  • Vote: I like it
  • -9
  • Vote: I do not like it

87.
By Rishav_raj_, history, 2 years ago, In English
Introducing My New Tool : Clever-code **[Clever Code](https://clever-code.vercel.app/)** ================== **Hello everyone!!** ------------------ In the competitive programming world, one of the most effective ways to improve is by learning from others who have tackled similar challenges. Have you ever wondered how someone else, perhaps a mentor or a peer, has approached problems in a specific tag on **Codeforces**? To make this process easier and more insightful, I’ve developed a tool that allows you to compare your practice with that of others.<br> What Does This Tool Do? ------------------ This tool on my website lets you gain insights into how others have practiced by filtering problems they've solved by specific tags.<br> ### **Here’s how it works:** - **Enter a Codeforces ID**: Start by entering the Codeforces handle of the user whose practice history you want to explore. This could be anyone—from a senior programmer to a peer whose problem-solving skills you admire. ![ ](/predownloaded/c9/03/c90352a8...
already tackled. - **Benchmark Your Progress**: Compare your problem-solving journey with others, your network have already tackled. - **Benchmark Your Progress**: Compare your problem-solving journey

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it

88.
By dipu_sust, 11 years ago, In English
Benchmark test of different GCD functions. I got a few implementation of GCD algorithm and wondered which would run faster! The result somehow surprised me. The implementations I used are- 1. C++ STD's `__gcd` functions. 2. GCD using assembly code. 3. Parameters and inside variable are both register variables. 4. Parameters are normal but inside variable is register. 5. Parameters and inside variable are both normal vairables. 6. Recursive GCD function. The code goes here- http://ideone.com/ztG05G In my Core i7 CPU with 8GB RAM the above code gives following output for `SIZ=5000`: ~~~~~ /* STD's gcd: Time: 0.841000 sec ASM GCD: Time: 0.582000 sec parameter and variable both registers: Time: 0.607000 sec parameter normal, variable register: Time: 0.701000 sec parameter and variable both normal: Time: 0.811000 sec recursive gcd: Time: 0.858000 sec */ ~~~~~ The cruelity of nature is STD's g...
Benchmark test of different GCD functions.

Full text and comments »

  • Vote: I like it
  • +10
  • Vote: I do not like it

89.
By akifpatel, history, 6 years ago, In English
Macro Combinatorics I'm sure other people have already come up with similar ideas, but I wanted to share this cool trick. ## Introduction C++ has `next_permutation()` which is very nice, but what about all the other combinatorics functions like Python has in the very nice `itertools` library. How should you go about writing a C++ brute force solution that uses things like combinations, Cartesian product/power, etc. Will you have to write the annoying (and quite large overhead) recursive backtracking? In this blog I show a light, efficient, and quite general way to do this type of thing using macros. ## Cartesian Power Let's start with the most simple example to introduce the idea. We want to enumerate $[0, a)^N$. To do this, we first set up an array `int c[N]` to hold the current element. Then, the critical part is do define a macro as follows: `#define F(i) for (c[i]=0; c[i]<a; ++c[i])`. This lets us loop any one of our indices. The full code to use this looks as follows (for $N=10, a=3$): ...

Full text and comments »

  • Vote: I like it
  • +15
  • Vote: I do not like it

90.
By priyanshu-thapliyal, history, 2 years ago, In English
Codeforces and LeetCode: Maintaining Competition Integrity with Coders One (Cheat Detector) Codeforces and LeetCode: Maintaining Competition Integrity with Coders One ### **The Competitive Edge of Codeforces and LeetCode** Codeforces and LeetCode are renowned for their challenging problems and dynamic contests, providing a platform for coders to test their skills and gain recognition. However, with high stakes come the inevitable attempts at gaining unfair advantages, making the need for robust cheat detection systems essential. ### Introducing the Cheat Detectors Coders One is proud to present dedicated cheat detectors for both Codeforces and LeetCode. ### Codeforces Cheat Detector: Our Codeforces cheat detector operates with an 85% accuracy rate. It uses simple observation based algorithms to scrutinize user activities and detect anomalies that indicate cheating. By ensuring that only legitimate efforts are rewarded, it helps preserve the integrity of the Codeforces community. ### LeetCode Cheat Detector: With a 70% accuracy rate, our LeetCode cheat detector i...

Full text and comments »

91.
By loyalixa, history, 2 years ago, In English
Congratulations tourist! The legendary Gennady Korotkevich, known as "<a href="/profile/tourist" title="Tourist tourist" class="rated-user user-4000"><span class="user-4000-first-letter">t</span>ourist</a>" has once again redefined the limits of competitive programming! In an extraordinary display of skill and determination, he broke his own record of **3979**, achieving an astounding new rating of **4009**—the highest ever reached in history. This achievement not only cements his status as the greatest but also sets a new benchmark for excellence in the field. In recognition of his unparalleled accomplishments, Codeforces has introduced a new rank above the "Legendary Grandmaster" titled "Tourist," celebrating his unmatched contributions and impact on the competitive programming community. This new rank stands as a testament to his exceptional talent, relentless spirit, and the legacy he continues to build. The **[Loyalixa](https://www.facebook.com/loyalixa/)** team proudly congratulates Gennady...
new benchmark for excellence in the field.

Full text and comments »

  • Vote: I like it
  • +34
  • Vote: I do not like it

92.
By PalashTaneja, history, 10 years ago, In English
Introducing Code Blogs and Human Benchmark Hi there, I am starting to get serious about competitive programming and I am constantly trying to solve harder problems and progress further on my coding and problem solving journey, However I am doing things a bit differently here, I am starting Code Blogs on my personal website and will post the solutions and hints to the problems I have solved to help beginners. Some of you may wonder that why am I doing this when the editorials exist, there are 2 things about the blog that would be different from the editorials. 1. I would be providing progressive Hints so that someone who is stuck on the problem may get a helpful jump start. 2. The explanation I would be writing would be more comprehensive and easier to understand. [This post](https://palashtanejapro.github.io/topics/codeforces-478c-table-decorations.html) is a good example of what I would be doing. I would also like to introduce to you another project of mine called Human Benchmark, a platform where some fellow coders...
Introducing Code Blogs and Human Benchmark, introduce to you another project of mine called Human Benchmark, a platform where some fellow, I would also like to introduce to you another project of mine called Human Benchmark, a platform

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

93.
By shibam_2002, history, 4 years ago, In English
The Beginner’s Guide to Kaggle How do I even start? Will I be up against teams of experienced Ph.d researchers? Is it worth competing if I don't have a realistic chance of winning? Is this what data science is all about? (If I don't do well on Kaggle, do I have future in data science?) How can I improve my rank in the future? Well, if you've ever had any of those questions, you're in the right place. In this guide, we'll break down everything you need to know about getting started, improving your skills, and enjoying your time on Kaggle. Kaggle competitions By nature, competitions (with prize pools) must meet several criteria. Problems must be difficult. Competitions shouldn't be solvable in a single afternoon. To get the best return on investment, host companies will submit their biggest, hairiest problems. Solutions must be new. To win the latest competitions, you'll usually need to perform extended research, customize algorithms, train advanced models, etc. Performance must be relative. Competiti...
previous benchmark. Kaggle competitions encourage you to squeeze out every last drop of performance, simply beats a previous benchmark. Kaggle competitions encourage you to squeeze out every last drop

Full text and comments »

  • Vote: I like it
  • +12
  • Vote: I do not like it

94.
By brdy, history, 9 years ago, In English
When does std::stable_sort outperform std::sort? Hello, I was doing this [problem](http://www.usaco.org/index.php?page=viewproblem2&cpid=623) and was getting TLE on the last two test cases. On a whim, I decided to replace my sort() functions with stable_sort(), and the solution passed. According to this [benchmark](https://stackoverflow.com/questions/810951/how-big-is-the-performance-gap-between-stdsort-and-stdstable-sort-in-practic), stable_sort uses less iterations overall in g++ 5.3.0 and clang++ 3.7.0 than sort on average. In the problem I sorted a vector<pair<int, pair<int,int>>>, which would take up to three comparisons each time. I considered this a possibility for the lower constant factor of stable_sort for this problem, but was not able to replicate the results. You can try to submit my [solution](https://pastebin.com/37m5cVGX) and it should AC. But if you replace "stable_sort" with "sort" it will TLE. Does anyone know which types of cases stable_sort can outperform sort? Edit: Programs are compiled w...
with stable_sort(), and the solution passed. According to this [benchmark ](https, According to this [benchmark ](https://stackoverflow.com/questions/810951/how-big-is-the-performance

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it

95.
By melan_, history, 21 month(s) ago, In English
Codeforces Submission Analyzer – Analyze Your Coding Performance! Hi, this is my first post on Codeforces! I have built a Codeforces Submission Analyzer, a tool that helps you analyze and visualize your submission history using the Codeforces API. It provides insights into your coding efficiency, memory usage, and performance trends. #### Why you should install this extension? - Analyze your submissions – Track time & memory usage. - Visual insights – Interactive charts & graphs. - Compare with others – Benchmark your performance. - Clickable data – Open submissions directly from graphs. #### How to install: - Download the extension from GitHub: [my GitHub repo] (https://github.com/melan-variya/Codeforces-Submission-Analyzer) - Extract the ZIP file to a folder. - Open Chrome and go to chrome://extensions/. - Enable Developer Mode (top-right corner). - Click "Load unpacked" and select the extracted folder. - Done! The extension is now installed and ready to use. Please, give it a try. If you find any kind of bug, please let ...
– Interactive charts & graphs. - Compare with others – Benchmark your performance. - Clickable data, . - Visual insights – Interactive charts & graphs. - Compare with others – Benchmark your

Full text and comments »

  • Vote: I like it
  • +33
  • Vote: I do not like it

96.
By z4120, 7 years ago, In English
A bug in the code that only make the answer wrong on 32-bit machines Note: Depends on your coding convention, you may not encounter this bug at all. --------- I have had a bug in a code similar to this: ``` void process(long long x) { /* ... */ } for (auto i = a.size(); i-->0; ) { for (auto j = b.size(); j-->0; ) { process(i - j); } } ``` Can you see the bug? Both `i` and `j` are unsigned, therefore the result will be computed modulo `2^32` or `2^64`, depends on the computer architecture. However, because `process` function takes a `long long` as input, the input is converted to `long long`. On 64-bit machines, the result ends up being correct, but on 32-bit machine, if `i - j == -1` then the received `x` value is `2^32-1`. In this particular case, there's no undefined behavior, so turning on `-ftrapv -fsanitize=undefined -D_GLIBCXX_DEBUG` etc. does not help. But compiling the code as 32-bit, enabling `-Wsign-compare`, or never using unsigned integer types would work. **How to compile for 32-bit machine with ...
**Another use of 32-bit compiling**: Benchmark with Codeforces speed., -application-using-gcc-64-bit-linux.html)) **Another use of 32-bit compiling**: Benchmark with

Full text and comments »

  • Vote: I like it
  • +27
  • Vote: I do not like it

97.
By supreme_999, history, 16 months ago, In English
A new idea to curb cheating... incorporating arc agi elements So I know this is not a popular idea but how about changing the problem statements a bit atleast at lower division/ elo. So as we all know that general llms can still not solve the arc agi test with a very high success rate <16% for the best model which in my opinion even a newbie will be able to solve with atleast >80% accuracy. So my idea is simple incorporating arc agi benchmark style in the new problem statements. one particular example problem statement from today's arc agi test puzzle (Puzzle ID: 36a08778): ![Today's arc agi test](/predownloaded/3e/cd/3ecd94770d7ac9567e32d596e1a3d00bba89c248.png) This can easily be solved with a simple dfs/bfs given the input prompts and output the resulting solution. The input colors can obviously be replaced by numbers and the idea itself is pretty simple. I dont think this question should be harder than 1300 probably and can definitely used as a div 2 b atleast. We can also flag accounts which have not solved the easier que...
to solve with atleast >80% accuracy. So my idea is simple incorporating arc agi benchmark style, So my idea is simple incorporating arc agi benchmark style in the new problem statements. one

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it

98.
By Meaf, history, 4 years ago, In English
Suffix Automaton Implementation I've recently been working on suffix automaton code and I have an implementation that I believe to be more intuitive and easier to type (certainly shorter) than the implementation I've seen circulating around (mainly adapted from cp-algorithms). It also appears to benchmark a little faster than the cp-algorithms implementation as well, which is a nice perk. Please, let me know if you can find some improvements to make, either making the code shorter, faster, etc. Edit: The primary purpose of this code is for ICPC-style contests which limit printed material and have no digital materials (unlike codeforces which allows copy/paste during contests). Thus, my primary focus is brevity and speed, not necessarily readability. There's always tradeoffs; for example, if 20 characters would be added to make the code much more readable, than that's a valid consideration, but I want the number of lines and number of characters to be as small as reasonable without making the code completely arcane...
circulating around (mainly adapted from cp-algorithms). It also appears to benchmark a little faster than the

Full text and comments »

  • Vote: I like it
  • +58
  • Vote: I do not like it

99.
By madkite, 15 years ago, In Russian
MS C++ vs GNU C++ vs MinGW — простой I/O benchmark [Тут](http://codeforces.me/blog/entry/10#comment-80979) стал вопрос производительности операций чтения/записи. Напомню, что в С++ есть замечательная функция-флаг ios_base::sync_with_stdio() с помощью которой можно отключить синхронизацию стандартных потоков C и С++, и тем самым повысить производительность. Замечательный компилятор от не менее замечательной фирмы Microsoft этот флаг тупо игнорирует. Т.к. я не директор Microsoft и даже не ответственный за выпуск Visual Studio --- мне глубоко всё равно кто в этом виноват. Для меня главное --- результат. Простой тест показал: [submission:1255626] --- G++ с выключенным sync_with_stdio --- 50 мс [submission:1255624] --- G++ c включенным sync_with_stdio --- 200 мс [submission:1255627] --- MS C++ с проигнорированным sync_with_stdio --- 230 мс Но, т.к. на этом сайте GNU C++ используется через одно место, т.е. через Microsoft Windows, используя непонятный порт под названием MinGW, то мне стало интересно какова реальная ситуация. Я...
MS C++ vs GNU C++ vs MinGW — простой I/O benchmark

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

100.
By MikeMirzayanov, 12 years ago, In Russian
Встречайте PyPy на Codeforces Привет, Codeforces! Рад представить вам PyPy на Codeforces. Прошу любить и жаловать. Хорошие новости состоят в том, что JIT в самом деле работает &mdash; PyPy зачастую оказывается существенно быстрее классического Python. Похоже, что обычно PyPy быстрее в 2-60 раз. Например, PyPy 2 показывает 60 кратный прирост производительности на [binary-heap-benchmark](https://github.com/MikeMirzayanov/binary-heap-benchmark), а PyPy 3 &mdash; 85-ти кратный. Кроме того у PyPy хорошая совместимость с Python, то есть в большинстве случаев вы можете просто отправить программу на PyPy. Не уходите далеко &mdash; скоро вас ждут еще хорошие новости :)
показывает 60 кратный прирост производительности на [binary-heap-benchmark ](https://github.com

Full text and comments »

  • Vote: I like it
  • +119
  • Vote: I do not like it

101.
By dhuamanilu, history, 9 months ago, In English
Gemini 3 Deep Think claims 3455 Elo on Codeforces (Legendary Grandmaster?) Just saw the news regarding the release of Gemini 3 Deep Think (12 Feb 2026) and the benchmarks are getting crazy. According to their latest technical report, this new model achieves a Codeforces Elo of 3455. ![ ](https://storage.googleapis.com/gweb-uniblog-publish-prod/original_images/gemini_3_deep-think_evals_charts_1.gif) That puts it deep into Legendary Grandmaster territory. What makes this more impressive is that the benchmark specifies this was achieved with "No tools", meaning it's raw generation without code execution support during the contest simulation. ![ ](https://storage.googleapis.com/gweb-uniblog-publish-prod/original_images/gemini_3_deep-think_evals_table_1.gif) Has anyone with early access tested it on recent Div 1 rounds?
makes this more impressive is that the benchmark specifies this was achieved with "No tools", meaning, benchmark specifies this was achieved with "No tools", meaning it's raw generation without code

Full text and comments »

  • Vote: I like it
  • +70
  • Vote: I do not like it

102.
By MusselPie, history, 6 years ago, In English
About 711D Hello Codeforces! Today I participated in [contest:1498]. I solved the first few problems relatively quickly and then got the idea for the subject of this blog, Problem D ([problem:1498D]), a fairly simple solution based on BFS. After coding my solution I submitted it, but I was unfortunately greeted by an unfavorable verdict: Time limit exceeded on pretest 8. No problem, I thought, and got to work on speeding up some parts of my solution. Time limit exceeded on pretest 8 again. At this point, I was desperate and started trying all sorts of stuff to speed my program up, to no avail. The wrong submissions piled up and pretest 8 still stood strong. ![ ](https://i.imgur.com/6zzLWmh.png) I don't remember what I tried next, but it somehow worked, and I excitedly saw my submission make it past pretest 8... only to get Time Limit Exceeded again, on pretest 15. Ugh. In my desperation, and seeing how the contest was almost over, I decided to submit my solution again, but with the in...
something to benchmark against, and to my surprise, it was also really close to the time limit, tried submitting the editorial solution to have something to benchmark against, and to my surprise

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

103.
By StarSink, history, 14 months ago, In English
Implementing the new SSSP algorithm on CP problem As the title suggests, I’m curious whether anyone has successfully implemented the single-source shortest path (SSSP) algorithm introduced in this recent [paper](https://arxiv.org/pdf/2504.17033). It would be exciting to see someone put this breakthrough to the test on a real competitive-programming benchmark, specifically the classic [CSES “Shortest Routes I” problem](https://cses.fi/problemset/task/1671/). To make things more fun, I’m offering $100 (not a lot, but just for motivation) to the first person who can demonstrate a correct solution using this new algorithm that ranks within the top five fastest submissions on the CSES leaderboard. If you’ve experimented with the paper’s approach or have an implementation that can compete with the best, please share your results!
-programming benchmark, specifically the classic [CSES “Shortest Routes I” problem](https://cses.fi

Full text and comments »

  • Vote: I like it
  • +15
  • Vote: I do not like it

104.
By iimoc, history, 7 months ago, In English
IIMOC x FrontierCS 2026 Practice Problems Hello Codeforces! ================= Following up on our initial announcement, we are excited to share that the Practice Phase for the IIMOC × FrontierCS 2026 Global Optimization Marathon is now officially open! The practice problems are a curated subset of the FrontierCS benchmark designed to help you set up your local environments and testing pipelines, understand the relative scaling (0–100) scoring system in action, and test your submissions. Head over to [iimoc.org](iimoc.org) to access the practice datasets and evaluation infrastructure, the real contest starts May 1.
officially open! The practice problems are a curated subset of the FrontierCS benchmark designed, The practice problems are a curated subset of the FrontierCS benchmark designed to help you set up

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

105.
By harshvardhanbablani, history, 2 months ago, In English
AIforces Its been a few months since i have started to take codeforces seriously. I practice almost everyday, try to learn and improve with every problem. When i first started, my first fancy aim was to achieve a rating of 1200. Aiming for Div 2 A,B problems under 30 minutes. With enough practice, I finally can do those problems in that time, but guess what? its apparently not enough anymore. Thanks to the wonderful AI specialists of our community. Codeforces contests now feel more like LLM benchmarks. People from all over the world register for contests to test their favourite AI models against OTHER AI models and newbies like me. I think we should rename this platform to AIforces soon, and i should get back to my frustration now.

Full text and comments »

  • Vote: I like it
  • -24
  • Vote: I do not like it

106.
By ashish.vasava, 14 years ago, In English
Bitwise IIT Kharagpur 2013 (Annual algorithm intensive online programming contest) **Computer Science and Engineering Department Society, IIT Kharagpur and Google Inc. present Bitwise — 2013,** an annual state of the art online programming contest hosted by the 4th year undergraduate students of Department of CSE, IIT Kharagpur, a premier institute in India. Bitwise has become a pioneer in this field, and has over the years established its popularity in both the national and international programming fraternity. This algorithm intensive programming contest aims to provide programmers across the globe, a platform to compete, testing their ability to develop efficient algorithms to problems. The event will be held on the February 10, 2013 (starting 1600 IST). The contest is time constrained and posed with some of the toughest programming and algorithms challenges in a short span of 12 hours. The contest will provide a great opportunity to showcase individual talent at an international platform and benchmark oneself with the best in the world. Many other events would...
at an international platform and benchmark oneself with the best in the world. Many other events, platform and benchmark oneself with the best in the world. Many other events would act as a pre

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

107.
By Qualified, history, 6 years ago, In English
Doubt in KACTL ModMul [KACTL ModMul](https://github.com/kth-competitive-programming/kactl/blob/master/content/number-theory/ModMulLL.h). It says that it runs around 2x faster than naive ~~~~~ (__int128_t)a * b % M ~~~~~ When I ran my benchmarks with -O2, the results were similar. Am I mistaken?

Full text and comments »

  • Vote: I like it
  • -29
  • Vote: I do not like it

108.
By Venus_Led, history, 20 months ago, In English
i asked chat gpt about artificial intelligence's impact on cping and this was his answer!!! In conclusion, AI's impact on competitive programming will undoubtedly be transformative, offering new opportunities for learning, innovation, and efficiency. While it may democratize the process by assisting with problem-solving and optimizing code, there are also potential downsides. The reliance on AI tools could reduce the emphasis on individual coding skills and critical thinking, making the competitive programming space less about creativity and more about machine-assisted solutions. The most controversial aspect, however, might be the future of human versus AI competitions. Will AI become the new benchmark in competitive programming, leading to a scenario where human participants are competing against machines? And if AI becomes too advanced, could it overshadow human involvement entirely, diminishing the value of the human-driven aspect of the competition? As AI continues to evolve, these ethical and fairness issues will undoubtedly spark debates about the integrity of comp...
AI become the new benchmark in competitive programming, leading to a scenario where human, become the new benchmark in competitive programming, leading to a scenario where human participants

Full text and comments »

Tags cp
  • Vote: I like it
  • -43
  • Vote: I do not like it

109.
By jAckAL_1586, 5 years ago, In English
On creating an opensource dataset from the source codes from codeforces. We have scrapped submissions for different users randomly for all problems upto 1457E. We are interested in using this data to work on different benchmark tasks in NLP. [code-translation](https://github.com/google/BIG-bench/pull/430), and [code-compilation](https://github.com/google/BIG-bench/pull/429) are two of the tasks we have prepared so far, and we plan to create more tasks. Thus we plan to share our scrapped codes publicly. This dataset will be very beneficial for the machine learning and deep learning community. We want the attention of [user:MikeMirzayanov,2021-06-22] on this issue of sharing the codes publicly. Is it okay with codeforces to share the dataset (after anonymizing) publicly strictly for research purposes?
interested in using this data to work on different benchmark tasks in NLP. [code-translation](https

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it

110.
By I_lOVE_ROMAN, history, 2 years ago, In English
How much map STL in C++ leads to MLE? Today I used two maps like that ~~~~~ map<pair<char,int>,int>mp1; map<pair<char,int>,int>mp2; ~~~~~ It leaded to MLE-Memory Limit exceeded. I guess some solutions with like this below got accepted- ~~~~~ map<int,vector<int>>mp1 map<int,vector<int>>mp2; ~~~~~ Then a question comes to my mind is there some anticpated benchmarks for using maps.How less complex it should be to avoid MLE?Is there some suggestions?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

111.
By randomQuestionsAcc, 5 years ago, In English
Nootropics Caffeine and l-theanine (basically the stuff in green tea) seems to noticeably improve my performance but I have never used any of the harder stuff like amphetamines (which [Erdős](https://en.wikipedia.org/wiki/Paul_Erd%C5%91s#Personality) is a well known user of). Just wondering if anybody have done experiments on this before. For example, do some rounds on one account while on whatever drugs and do some rounds clean on another alt, then compare the performances. I feel like CF rating converges fast enough that it'll probably be a somewhat reliable benchmark? Anyone have any anecdata?
converges fast enough that it'll probably be a somewhat reliable benchmark? Anyone have any anecdata?, performances. I feel like CF rating converges fast enough that it'll probably be a somewhat reliablebenchmark?

Full text and comments »

112.
By swcai, 16 years ago, In English
Random thoughts on codeforces I think one major difference of CodeForces.com from other ACM and programming contest is the support of python, ruby, php, haskell and etc. It makes things more interesting. But from my observation, few people used these new languages. Part of the reasons is people in the community are not familiar with these languages and some of the languages are hard to debug. And another reason, I believe, is CodeForces.com measures the submission with same criteria, same memory limits, same time limits. But the performance of the language are very different. It makes it impossible practically. Probably codeforces.com could consider to give different criteria for different language, based on some kind of language performance benchmark. This could encourage people to use different language and be more fair.
of language performance benchmark. This could encourage people to use different language and be more

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it