++ compilers don't add additional checks to the program, such as checks for null
pointer dereference or out-of
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
→ Find user
→ Recent actions
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 305andrew stankevich contests— search for words "andrew", "stankevich" and "contests" at the same timeuser:mikemirzayanov title:testlib— search containing "testlib" in title by MikeMirzayanov"vk cup"— use quotes to find phrase as istitle:educational— search in title
Results
1.
Catching silly mistakes with GCC As you know, the C++ language assumes that the programmer is always correct. Therefore C++ compilers don't add additional checks to the program, such as checks for null pointer dereference or out-of-bounds array access. This is good, because C++ programs run as fast as possible, and this is bad, because sometimes we may spend a long time debugging some silly mistake. We would want that the compiler can find such mistakes automatically. And many compilers can! In this post I will show various GCC options that do this. Previously [user:zakharvoit,2015-01-02] already wrote about this [here](/blog/entry/13875).
All options that will follow should be added to the GCC command line. In various IDEs you can do it in IDE or compiler settings. Many of the options can also be used with Clang (for example, in Xcode). For MSVC++, I think, there is nothing better than Debug mode and `/W4`.
[cut]
GCC warnings
------------------
Of course, the first step to debugging is to enable compi...
2.
Editorial of Codeforces Global Round 21 Thanks for participation!
If your solution to D involves any data structures and is not $O(n)$ -- please read the "solution 1". I believe it is very interesting, but to make the difficulty suitable for D we allowed not $O(n)$ solutions.
[problem:1696A]
<spoiler summary="Hint 1">
How many operations will we perform?
<spoiler summary="Answer">
At most one. Why?
</spoiler>
</spoiler>
<spoiler summary="Solution">
Suppose we can only perform exactly one operation. In this case the answer is $S=\max_{1\le i\le n}(a_i\mathrm{\ or\ }z)$. In fact, we can prove that this is the answer.
Define $a_i'$ as the value of $a_i$ after some operations.
It suffices to prove the answer will never exceed $S$. Note that $z$ will always become a submask of itself after any number of operations, so $a_i$ will always be a submask of $(a_i\mathrm{\ or\ }z)$ after any number of operations. This leads to the conclusion that $a_i'\le (a_i\mathrm{\ or\ }z)$ for all $i$. Thus $\max_{1\le i...
prefix sums, we can pre-calculate the contribution of every $(i,j)$ in
$O(n^3)$, which isfast enough., )$, which is fast enough. You might be afraid that $600^3$ is too slow for 1.5
seconds. However
Tutorial of Codeforces Global Round 21
3.
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...
://judge.yosupo.jp/submission/279317) to the fastest submission. (we need to
steal afast I/O template
4.
On the mathematics behind rolling hashes and anti-hash tests This blog assumes the reader is familiar with the basic concept of rolling hashes.
There are some math-heavy parts, but one can get most of the ideas without understanding every detail.
The main focus of this blog is on how to choose the rolling-hash parameters to avoid getting hacked
and on how to hack codes with poorly chosen parameters.
# Designing hard-to-hack rolling hashes
## Recap on rolling hashes and collisions
Recall that a rolling hash has two parameters $(p, a)$ where $p$ is the modulo and $0 \leq a < p$ the base.
(We'll see that $p$ should be a big prime and $a$ larger than the size $\left|\Sigma\right|$ of the alphabet.)
The hash value of a string $S = s_0 \dots s_{n-1}$ is given by
$$
h(S) := \left(\sum\limits_{i=0}^{n-1} a^{n-1-i} s_i\right) \mod p
$$
For now, lets consider the simple problem of: given two strings $S, T$ of equal length,
decide whether they're equal by comparing their hash values $h(S), h(T)$. Our algorithm declares $S$ and $T$
t...
-attacks runs really fast, the resulting strings can get a little long. ($n =
2048$ for $p = 2^{61}-1, While the tree-attacks runs really fast, the resulting strings can get a little
long. ($n = 2048
5.
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...
Fast and furious C++ I/O, . But the main goal during a contest is to code fast, so I wrapped all the
efficiency into functions
6.
Разбор VK Cup Round 2 [problem:532A]
--------------
We can add $n-k$ miners with height $0$ and it won't affect answer. So we can assume that numbers of miners and caves are the same.
For every cave let's define $t_i$ as maximal possible height of miner working in cave $i$ if we wouldn't change any cave. We can calculate it from root to leaves with line $t_i = min(t_{father}, h_i)$.
Let's say we don't change anything. We will try to assign all workers if it's possible or to do the best possible assignment otherwise — the one where there are few free (not occupied) caves and they are high (value $t_i$ is big). I will say later why we want them to be high. Formal definition (you don't have to read the next paragraph):
For every assignment let's sort free caves by $t_i$. In the best assignment number of free caves is minimal possible. And for every position in such a list free cave in the best assignment has value $t_i$ not lower than in any other assignment. It can be proven that best possi...
Tutorial of VK Cup 2015 - Round 2
7.
Useless CP Information #7: How to Become an Assembly Bro (Assembly Tutorial Part 1) _If you were ever curious but were confused by the youtube tutorials. I'm going to try to make this as concise and useful as possible. Also, x86 is way easier to code in than ARM and if you disagree, you're wrong. And Intel syntax is better than AT&T syntax_
_This assumes you have a basic understanding of how pointers work in C_
First program & compiling
==================
Make a file named `hello.s`:
~~~~~
.intel_syntax noprefix
.section .rodata
mystring:
.ascii "Hello, World!\n"
mystring_end:
.section .text
.globl main
.type main, @function
main:
endbr64
push rbp
mov rbp, rsp
mov eax, 1 # write
mov rdi, 1 # stdout
lea rsi, mystring[rip]
mov rdx, mystring_end - mystring
syscall
xor eax, eax
leave
ret
~~~~~
Compile and run with
~~~~~
$ gcc -o hello hello.s
$ ./hello
~~~~~
In assembly, you are writing CPU instructions, so you only have access to low-level things:
- Registers: the...
, and `rsp`: **s**tack **p**ointer. The base pointer points to the
beginning/base of the stack frame, We also have `lea` for **load effective address**. It's typically useful for
pointer arithmetic
8.
Border Theory:There's a fast approach to bruteforce on borders UPD:Thanks to comment from [user:arvindf232,2025-12-20] and [user:pajenegod,2025-12-20],I rewrote parts of this post to improve clarity with the help of Chatgpt. I hope it reads more smoothly now.
# Preface
In this blog, I want to share Border Theory, a useful and elegant insight about string borders that often appears in competitive programming. Although this idea deserves to be as well-known as the KMP algorithm, many people today aren’t aware of it or how to use it to speed up their solutions.
# Main Theoretical Result of Border Theory
## Main Result
For a string $S$, a border is a substring that is both a prefix of $S$ and a suffix of $S$.
For a string $S$, we define that:
$$ \{b_i\}_{i=1}^n$$
is the sequence of all lengths of the border of $S$, sorted in increasing order.
According to the theory,it's garenteed that for all possible $S$, ${B_i}_{i = 1}^n$ can be partitioned into $\operatorname{O}(\log |S|)$ continuous subsequences where each subsequence f...
Border Theory:There's a fast approach to bruteforce on borders
9.
COCI 2013/14: Round #6 Note that [this Saturday](http://www.timeanddate.com/worldclock/fixedtime.html?day=08&month=03&year=2014&hour=14&min=0&sec=0&p1=0), this year's last (before the Olympiad's Open) round of [COCI](http://hsin.hr/coci/) takes place.
Registration and entry into the contest: [here](http://evaluator.hsin.hr/login.php?redirect=index.php). Watch out — don't register for HONI (local version), but COCI.
<s>Feel free to discuss problems here after the contest ends. I'll probably post my solutions here, too.</s>
The contest is over. The results are accessible in your account on [evaluator.hsin.hr](evaluator.hsin.hr) under the Results tab. The top 5 are:
1. [user:bmerry,2014-03-10]
2. [user:a_h1926,2014-03-10]
3. [user:eduardische,2014-03-10]
4. [user:svanidz1,2014-03-10]
5. Topi Talvitie
### Solutions
(all full, except the last problem; you can find the solution of that problem in the comments)
#### VJEKO
([code](http://ideone.com/KVsMMr))
Do I even have to write...
answer (quicksort is fast, but not fast enough, even if it cuts off the $2^M$
factor from complexities)., complexity: $O(2^N)$; memory: $O(2^{N/2})$. The TEST option helps a lot in
estimating what'sfast
10.
Faster Dijkstra on Special Graphs [Tutorial] You can read the latex formatted pdf [here](https://www.dropbox.com/s/03wjbvhhvqcsz3c/fast-dijkstra.pdf?dl=0).
### Pre Requisites
Dijkstra's algorithm
### Motivation Problem
You are given a weighted graph $G$ with $V$ vertices and $E$ edges. Find the shortest path from a given source $S$ to all the vertices, given that all the edges have weight $W$ $\in $ $\{X,Y\}$ where $X,Y>=0$
### Naive Solution
Most people when given this question would solve it using Dijkstra's algorithm which can solve this efficiently in $O(E*logV)$ (Let's not take Fibonacci heap implementation into consideration now). It turns out that this solution, though it will work in most cases well under the time, can be improved further to a linear time algorithm.
Before moving into the next section, try to think about how you could optimise Dijkstra's algorithm. ( **Hint :** There are only two possible values...
null pointer errors. Otherwise, everything else is same as Dijkstra when it
comes to implementation., You can read the latex formatted pdf
[here](https://www.dropbox.com/s/03wjbvhhvqcsz3c/fast
11.
UTPC Spring 2024 Open Contest Editorial Hope you enjoyed our contest! The editorial is below:
[A — Skipping Songs](https://codeforces.me/gym/105109/problem/A)
Author: [user:sg2themax,2024-04-21]
<spoiler summary="Solution">
For this problem, you maintain an index counter pointing to the current song, starting at 0. At each step, you always ensure that you mod by the length of the record.
You start off by playing the song at the index of the first number. After printing each song, you increment by one since Noah has "finished listening" to it. Then, you add the number of skips, print the next song, and repeat.
</spoiler>
[B — 6th heaven](https://codeforces.me/gym/105109/problem/B)
Author: [user:blueberryJam,2024-04-21]
<spoiler summary="Solution">
We first check whether the conditions can be satisfied, then if so compute the number of arrangements.
#### Pruning
Consider a situation in which a disk appears three times or more among all the distinct pairs. This is impossible to arrange...
for each song how many times a pointer passes over it., in the subarray). Consider the following two pointer approach: Suppose our
song is at index $i, our two pointer algorithm is actually $\mathcal{O}(n\log A)$, which is fast
enough as $A\leq10^9
Tutorial of UTPC Spring 2024 Open Contest
12.
AtCoder Beginner Contest 130 — Unofficial English Editorial Hello Codeforces! Did you enjoy the [AtCoder Beginner Contest 130](https://atcoder.jp/contests/abc130)? As usual, there was only [Japanese editorial](https://img.atcoder.jp/abc130/editorial.pdf) published, so I translated it into English. Um, actually it's already three days after the contest, it might be a bit late, but well, whatever?
**Disclaimer.** Note that this is an unofficial editorial and AtCoder has no responsibility for this. Also, I didn't do proofreading at all, so it might contain many typos. Moreover, this is the third experience I write such kind of editorial, so the English may not be clear, may be confusing, or even contain mistakes. Any minor corrections (including grammatical one) or improvement suggestions are welcome. Please do not hesitate posting a comment about it.
## A: Rounding
You can implement it straightforward: print $0$ if $X < A$, and print $10$ if $x >= A$.
An example code is shown in List 1:
Listing 1. Example Code of Rounding...
13.
Blogewoosh #3 Hello, codeforces!
This time I've decided to choose a task from my own contest which took place last April and was known as the Grand Prix of Poland. If you want to write this contest virtually in the future, then consider not reading this blog. If you've participated in this contest and maybe even solved this task, then anyway I recommend reading it, cause this task has many very different solutions, each of them being very interesting (in my opinion). It's also a reason why this blog is longer than previous ones.
I'll write about task C "cutting tree" (not uploaded to the ejudge yet :/). The statement goes as follows:
You are given a tree with $n$ vertices ($1 \leq n \leq 2 \cdot 10^5$). The task is to calculate $f(k)$ for each integer $k$ from the range $[1, n]$ where $f(k)$ is defined as the maximum number of connected components of size $k$ which we can "cut off" from the tree. A connected component of size $k$ is a set of $k$ vertices such that it's possible to traverse ...
is directly above it (if exists) to be sure that everything is OK. So, why is
itfast? For each
14.
Palindromic tree: behind the scenes Hi everyone!
As some of you may know, on this summer camp in Petrozavodsk [user:MikhailRubinchik,2014-09-25] presented a new data structure, palindromic tree. I had the honor to participate in the study of the structure for the six months before that, and I want to tell about it now :)
[cut]<br>
But firstly a brief explanation. If you alredy know basic ideas of the structure, you may go to the <a href="#inter">interest part</a>. Let's to each palindrome assign corresponding string equal to its right half, i.e., its radius and the boolean variable indicating its parity. Now let's merge all our radii of subpalindromes of string $S$ in two prefix trees for even and odd lengths separately. Claim: such trie will be $\mathit O(n)$ in memory. Indeed, there can be no more than $n$ distinct subpalindromes in the string, and each node in trie corresponds with only one unique palindrome. Therefore, we have no more than $n + 2$ nodes.
Let's show that such structure can be constructed ...
a pointer to the node corresponding to the maximum suffix-palindrome of string
on every step, an online Manacher's algorithm & mdash; let's store in each item of the array
thepointer to the
15.
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...
Beating Treaps & Splay with a Simple Idea: A Fast, Amortized Dynamic Segment
Tree with Insertion, Rebuilding, Memory Allocation, Pointer Management) is entirely isolated from
the data logic., benchmarks prove that you no longer need to pay the massive constant-factor
penalty ofpointer-based, , heavy pointer-chasing and branch-heavy rotation conditions destroy Cache
Locality and inflate the, . In modern competitive programming, heavy pointer-chasing and branch-heavy
rotation conditions, Those classic pointer-based structures remain the undisputed kings when it
comes to complex
16.
Intersting facts on scanf/cin,cout and segment tree implementation on C++20(64) and C++17(32) Problem: [1864F. Exotic Queries](https://codeforces.me/contest/1864/problem/F)
The time limit is 4s. The input size is $n,q \le 10^6$. The standard solution uses a segment tree and the input/output size is very large. The sync of cin,cout with stdio is turned off in all implementations if cin,cout is used.
### Cin,cout vs Fast IO, Scanf on C++20 (64)
* [220904724](https://codeforces.me/contest/1864/submission/220904724) Array implementation with cin,cout on C++20 (64) -> TLE
* [220952057](https://codeforces.me/contest/1864/submission/220952057) Array implementation with Fast IO on C++20 (64) -> 1762 ms
* [220950571](https://codeforces.me/contest/1864/submission/220950571) Array implementation with Scanf on C++20 (64) -> 3181 ms
* [220950753](https://codeforces.me/contest/1864/submission/220950753) Pointer implementation with Scanf on C++20 (64) -> 3868 ms
* [220947347](https://codeforces.me/contest/1864/submission/220947347) Pointer implementation with cin,cout ...
) Pointer implementation with Fast IO on C++20 (64) -> 2277ms ### C++17 (32) vs
C++20 (64, * It's better to use Pointer implementation if you use cin,cout on C++20 (64) *
If you prefer, /contest/1864/submission/220954316) Pointer implementation with Fast IO on
C++20 (64) -> 2277ms
17.
Mo's algorithm and 3D Mo Mo's algorithm
==================
<spoiler summary="Problem 1">
### the number of distinct elements on a segment of an array
Given an array $A$ of length $n$ and $q$ queries.
Queries:
- Find the number of distinct elements on the segment [l; r] of the array $A$.
</spoiler>
<spoiler summary="Problem 2">
### the number of distinct elements on a segment of an array + changing an element
Given an array $A$ of length $n$ and $q$ queries.
Queries:
- Find the number of distinct elements on the segment [l; r] of the array $A$.
- Change an element
</spoiler>
Let's solve the first problem. We can solve it using persistent data structures, but we want to be able to solve problem 2 as well.
### Algorithm 1
Let's solve the task offline. We need to sort the queries using the <$\frac{l}{k}$, r> comparator, where k is a fixed integer. It is quite obvious that we can easily add/delete one integer (we can do that using another array B, $B_{i}$ equals to the number...
**all** the change queries. We move the pointers as in the first algorithm. To
do all of thisfast, are sorted in the increasing order. In total the left pointer will move by
$O(q \cdot k)$ positions
18.
Weekly Training Farm 22 — Editorial Weekly Training Farm 22 is over. Congratulations to the winners :
1. [user:W4yneb0t,2017-01-20] (perfect score in < 1 hour!)
2. [user:aaaaajack,2017-01-20] (perfect score)
3. [user:eddy1021,2017-01-20]
Here is the editorial :
### Problem A
This problem can be solved by greedy. We list down the positive integers one by one. We keep a pointer that initially points to the first letter of $s$. Whenever the pointed character in the string $s$ matches the corresponding digit of the integer, we move the pointer one step to the right and continue. Repeat this process until the pointer reaches the end.
However, we still need to know whether the answer can be large. The key is to note that the answer will never exceed $10^{6}$, because after writing down $10$ consecutive numbers, at least one of them has last digit equals to the current digit, so the pointer will move to the right at least once when we write down $10$ consecutive numbers. Thus, in the worse case, we'll onl...
list down the positive integers one by one. We keep a pointer that initially
points to the first, them has last digit equals to the current digit, so the pointer will move to
the right at least once
19.
Codeforces Round #256 — Editorial [problem:448A]
Solution:[submission:7139559]
Because rewards of one type can be on one shelf, lets calculate number of cups — $a$ and number of medals — $b$. Minimum number of shelves that will be required for all cups can be found by formula $(a + 5 - 1) / 5$. The same with shelves with medals: $(b + 10 - 1) / 10$. If sum of this two values more than $n$ then answer is "NO" and "YES" otherwise.
[problem:448B]
Solution:[submission:7139584]
Consider each case separately. If we use only suffix automaton then $s$ transform to some of its subsequence. Checking that $t$ is a subsequence of $s$ can be performed in different ways. Easiest and fastest — well-known two pointers method. In case of using suffix array we can get every permutation of $s$. If it is not obvious for you, try to think. Thus, $s$ and $t$ must be anagrams. If we count number of each letter in each string, we can check this. If every letter appears in $s$ the same times as in $t$ then word...
in $O(N)$ time. How to find now $X_{k}$ for every $k$? The method is similar as
fast exponentiation
20.
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] ...
random insertions and 1e5 random queries. ~~~~~ pointer: 0.171485
unordered_map: 2.0646
21.
Say Goodbye to TLE: Master Two Pointers What is the Two Pointers Technique:
===================================
uses two index variables to traverse a linear data structure—like an array,
string, or linked list—to solve problems efficiently without nested loops.
Why Use it ?
-------------
Time Efficiency: It often reduces time complexity from O(n²) (using nested loops) down to linear time O(n).
Space Efficiency: It typically requires constant space O(1) because it only tracks a few indices.
##Whats Patterns of 2 Pointers ##
**Pattern 1 (Variable_Size)**
**1.1 Opposite Direction (Converging Pointers):**One pointer starts at the beginning (left = 0) and the other at the end
(right = n — 1). They move toward each other until they meet.
Best Used For: Sorted arrays, pair sum problems (ex: Two Sum on sorted input), or checking palindromes.
Problem: Can you choose two indices i , j (i≠j) and ai+aj=K
If you can choose to indices solving the equation print "YES" otherwise "NO"
**Brute Force Approa...
pointer starts at the beginning (left = 0) and the other at the end (right = n
— 1). They move, which is useful for removing duplicates or sliding windows.Fast and Slow: One
pointer moves faster
22.
Editorial of Educational Codeforces Round 11 ### [problem:660A]
The problem was suggested by Ali Ibrahim [user:New_Horizons,2016-04-09].
Note that we should insert some number between any adjacent not co-prime elements. On other hand we always
can insert the number $1$.
<spoiler summary="С++ solution">
~~~~~
const int N = 1010;
int n, a[N];
bool read() {
if (!(cin >> n)) return false;
forn(i, n) assert(scanf("%d", &a[i]) == 1);
return true;
}
void solve() {
function<int(int, int)> gcd = [&](int a, int b) { return !a ? b : gcd(b % a, a); };
vector<int> ans;
forn(i, n) {
ans.pb(a[i]);
if (i + 1 < n && gcd(a[i], a[i + 1]) > 1)
ans.pb(1);
}
cout << sz(ans) - n << endl;
forn(i, sz(ans)) {
if (i) putchar(' ');
printf("%d", ans[i]);
}
puts("");
}
~~~~~
</spoiler>
Complexity: $O(nlogn)$.
### [problem:660B]
The problem was suggested by Srikanth Bhat [user:srikkbhat,2016-04-09].
In this problem you should simply do what was written in the problem sta...
, r]$ is also good. So we can use the method of two pointers: the first pointer
is $l$ and the
Tutorial of Educational Codeforces Round 11
23.
Codeforces Newbie Round Editorial [problem:668948A]
<spoiler summary="Solution">
The square root of $x^2$ when $x$ is an integer is also an integer. We can use this and print $1^2, \ 2^2, \ 3^2, \dots, n^2$
</spoiler>
<spoiler summary="Code">
~~~~~
n = int(input())
for i in range(1, n + 1):
print(i * i, end = ' ')
~~~~~
</spoiler>
[problem:668948B]
<spoiler summary="Solution">
$A = a \cdot b \to a = \frac{A}{b}$
</spoiler>
<spoiler summary="Code">
```py
#include <bits/stdc++.h>
using namespace std;
int main() {
int A, b; cin >> A >> b;
cout << A / b;
}
```
</spoiler>
[problem:668948C]
<spoiler summary="Solution">
To find $y$ we can find the first prime factor of $x$ by checking each integer from $2$ to $\sqrt{x}$, and if there aren't any divisors of $x$ in this range, then the answer is $x$.
Why this works?
$y$ shares exactly one prime factor with $x$ ( itself ), and the first divisor of any integer $\neq 1$ is a prime.
</spoiler>
<spoiler summary="Code">
...
$ steps fast? We can use jump pointers to simulate $\ge n$ steps in O(1) time.
Let $jmp[v][k]$ = the, How to simulate at least $n$ steps fast? We can use jump pointers to simulate
$\ge n$ steps in O(1
24.
About ordered set Hi everyone! I think many of you know about such data type as set. It must support such operations like:
* Insert an element into set;
* Check if the set contain some element;
* Delete element from set.
If we talk about ordered set, then elements (what a surprise!) must be kept in some order. As I think, there is also very important next operations:
* Find the k-th element in a set;
* Find the order of element in a set.
Most of all, for the implementation of such functional some may use binary balanced trees (AVL- tree , red-black tree , cartesian tree , etc). However, in this article I would like to talk about some of the features in the implementation of an ordered set with other structures. In particular, I'll show the implementation with the segment tree and with the Binary Indexed Tree (Fenwick tree). But I just want to note that it only allows you to build the set of natural numbers. For all other types of elements such methods will not work :(
The basic id...
the advantages and disadvantages of this approach. Pros: * We can write it
reallyfast
25.
Binary Search: A way to solve problems faster! Binary Search
-------------
Hello everyone!
Today I'm going to talk you about a useful problem-solving method, **binary search**. If you have seen, in some problems we can't use an algorithm with $O(n^2)$ (because your program would be too slow to solve such problems). In those cases, you can use faster algorithms, but one of the popular algorithm is binary search. In binary search, you assume an integer as the answer, and you try that to see if it is the real answer or not. In this algorithm, you have an answer range, with usually starts with 0 and the end of the range will be maximum possible answer (i.g. 1e9). Let's play a game to understand better. One of your friends choose an integer from 1 to 100 and you need to ask some questions of your friend to find the number your friend had chosen. If you work smart (you will because you are smart) you start with this question: Is it less than 50? Do you agree if the friend's answer is yes, your range will be divided by 2 and also if ...
of current range by moving the pointer } else { right = middle; //and also
similar thing, ; //if yes, remove the left part of current range by moving the pointer } else
{ right
26.
[ASK] Huge performance problem: C++ is faster than C++ 64 bit! Hello!
Recently I've faced a confusing problem:
I've accidentally re-submitted my solution for problem [problem:1554E] on different compiler. Suddenly I've noticed that its running time has significantly increased.
- This solution [submission:128134170] takes 1263 ms under GNU C++17 compiler.
- This solution [submission:128134185] takes 2277 ms under GNU C++17 (64) compiler.
- You can see that their codes are fully identical.
So, common code with some vectors, self-written modular class and lambdas causes that much time difference — approximately 2 times. The memory also increased (1.5x times), it is also kinda suspicious because I haven't used any pointers.
I've re-written it without lambdas — lifted `dfs` out of `solve` ([submission:128134438] and [submission:128134426]), both execution times have increased in about 200 ms.
I had somewhere heard that `vector<bool>` is very problematic structure. I even have changed it to `vector<int>` and resubmitted...
27.
[Discussion]: Solutions for IOI 2023 tasks + My solution to IOI23 Day1 P1 — Closing Time Apologies for the immense lack of math typing — this dummy have precisely 0 idea of how that works out (whoops).
Google Sheets that sorts IOI task by amount of AC, average score, max score and stuffs, definitely not hand — typed by yours truly over 3 hours or something: https://docs.google.com/spreadsheets/d/14v9jfFU0hZ47uAvut27_YdZ9FQmp78rP7Rm48tRzPQQ/edit?usp=sharing (Data taken from https://stats.ioinformatics.org/tasks/)
I know, this is definitely a weird thing for a Gray to make a blog out of all things, but yeah. For some reason there's no official editorial even after 1.5 months since the official contest, and no discussion blogs as well. So, yeah, I want to bring this up in order to actually see people discussing about the tasks of IOI23, as the task discussion blogs are always fairly interesting (to read) for me. Besides, I would love to see people actually explaining their ideas (how do you people even come up with that 40-line O(n^2) solution for Soccer, WHY ...
28.
Mo online and how to solve problem from a recent Educational Round Hello everyone!
In contests, problems involving range queries appear quite often. Most problems provide queries offline, which allows for greater flexibility in solving them, but often they reduce to using a segment tree or Mo's algorithm. However, sometimes a problem that is easily solvable offline with Mo's algorithm becomes interesting in the online version. In such cases, some people try to maintain something like $500$ different states of Mo's algorithm — I never really understood what was meant by that.
Today, I managed to come up with an online version of Mo's algorithm that works in $O(n^{\frac{5}{3}})$ time and memory for usual problems (where moving the pointers is done in $O(1)$). For asymptotic analysis, I'll assume $n = q$. I'm not the first to come up with this idea. As it turns out, [here](https://codeforces.me/blog/entry/44711?) и [here](https://codeforces.me/blog/entry/135134) was a discussion where this idea was proposed, but I also want to do this as I'...
traversal: We traverse the squares left to right, top to bottom. The $R$
pointer moves from $1$ to
29.
Codeforces Round 983 (Div. 2) Editorial <spoiler summary="README: Notice about solutions">
All editorial codes contain solutions wrapped in classes. I'll only paste the important part (`namespace solution` in C++, `class Solution` in Python 3) as plaintext in the solution code section (along with the corresponding AC submission link). You might want to see the code template here.
<spoiler summary="C++ template">
```cpp
#include <bits/stdc++.h>
using namespace std;
namespace solution {
bool hasMultipleTests = true;
void preprocess() {
// something
}
void input(int testcase) {
// something
}
void solve(int testcase) {
// something
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solution::preprocess();
int t = 1;
if (solution::hasMultipleTests) cin >> t;
for (int testcase=1; testcase<=t; testcase++) {
solution::input(testcase);
solution::solve(testcase);
}
return 0...
="Hint #5"> Is there a fast and optimal way to try all possible $(a_x, a_y,
a_z)$ triplets?
Tutorial of Codeforces Round 983 (Div. 2)
30.
My 2018 Codejam adventure Introduction
------------------
This is the story of how I failed to qualify for round 2 to in the 2018 Google Codejam. Hopefully you find it interesting and learn some things you shouldn't do in Codejam.
Qualification Round
------------------
Qualification was fairly easy due to the ample time of 24 hours. I managed to solve everything correctly apart from the large dataset for the last question. I tried to see if anyone had done mathematical analysis of Madison Cube garden from Futuruma since that seemed closely related to the last question but to no avail.
Round 1A
------------------
The ideas to solve questions just did not come to me during this round. I only managed to solve the small set for question A.
What I learnt:
Eat a good breakfast before doing a competition in the morning.
Round 1B
------------------
I looked at question A and could not think of a correct approach. Then I looked at B and decided to work on it since it seemed simpler. I saw a th...
decided a binary search should be fast enough. I also suspected a two pointer
style approach might, limits I decided a binary search should be fast enough. I also suspected a two
pointer style approach
31.
Editorial of Codeforces Round #769 You can also find video editorials for problems B-D on [user:ak2006,2022-01-30]'s [Youtube channel](https://www.youtube.com/channel/UCnZ5rC2_JY0EuYMGMiAbISg)!
####[1632A — ABC](https://codeforces.me/contest/1632/problem/A)
<spoiler summary="Hint 1">Only a few strings have the answer "YES".</spoiler>
<spoiler summary="Hint 2">
For $n \ge 3$, the answer is "NO".
</spoiler>
<spoiler summary="Solution">
Let $n \ge 3$ and the resulting string be $a$. For there to be no palindromes of length greater than $1$, at least all of these inequalities must be true: $a_1 \neq a_2$, $a_2 \neq a_3$, and $a_1 \neq a_3$. Since our string is binary, this is impossible, so the answer is "NO".
For $n \le 2$, there are 4 strings that have the answer "YES": $0$, $1$, $01$, and $10$; as well as 2 strings that have the answer "NO": $00$ and $11$.
Time complexity: $O(n)$
</spoiler>
<spoiler summary="Solution codes">
- [C++ code](https://codeforces.me/problemset/submission/1632...
Tutorial of Codeforces Round 769 (Div. 2)
32.
It's almost 2025, why are you still choosing GCC 7 (32-bit)? This is my answer to https://codeforces.me/blog/entry/137484, in which [user:-is-this-fft-,2024-12-20] asked a bizarre question. This answer is too big for a comment so I made a blog post instead.
## The question
The submission [submission:297353626] behaves normally with 180 MiB memory usage while [submission:297352244] got a runtime error due to stack overflow (with 256 MiB stack).
Both submissions have identical code, don't seem to contain bugs, and an assertion exists to make sure the recursion is at most $2\times10^5$ layers deep. What's happening?
## TL;DR
Notice that the solution with stack overflow uses GCC 7 (32-bit) while the accepted ones use GCC 13 (64-bit). This is not a coincidence.
The main reason of unreasonable stack usage boils down to two points: GCC 7, and 32-bit.
## 32-bit
First of all, the code is compiled and run in 32-bit mode.
Compiling the submission with GCC 7.5 in 32-bit on [godbolt](https://godbolt.org/z/WT9WsdeW4) shows that the `lo...
function arguments are pushed onto the stack in reverse order, as well as an
extrapointer. This extra
33.
How I thought I was smart enough to play with fire and then I wasn't [blazingio](https://codeforces.me/blog/entry/126390) cuts corners by design. It keeps the constant factor small and uses long forgotten algorithms people used before processors supported SIMD and integer division. But another limitation made this task much harder.
Size.
Professional libraries start exceeding the Codeforces limit of 64 KiB really fast. Code minification barely helps, and neither does resorting to ugly code. So I cut a corner I don't typically cut.
Undefined Behavior.
These two words make a seasoned programmer shudder. But sidestepping UB increases code size so much the library can hardly be used on CF. So I took a gamble. I meticulously scanned every instance of UB I used intentionally and made sure the compiler had absolutely no reason to miscompile it. I wrote excessive tests and run them on CI on all architecture and OS combinations I could think of. I released the library without so much as a flaw. It worked like clockwork.
And then, 3 months later, ...
libraries start exceeding the Codeforces limit of 64 KiB really fast. Code
minification barely helps, and
34.
C++ tips and tricks Hello, codeforces.
I would like to tell you about some tricks and constructions I use in C++. They are not hidden or anything, moreover, most of them are from stl or maybe well known among software engineers, but I often see codes where something is done by hand in, say, 5 lines, while in stl there is a function which does the same.
The things below are filtered by my personal sense of non-popularity (so no `__builtin` functions) and usage frequency (so there almost surely are similar things I don't know about) and are not really sorted in any reasonable order. Let's begin. [cut]
<hr>
- ### `all(x)`
This may be an exception to the rule of non-popularity -- this is quite widely used, but some next items will depend on `all(x)`, so I define it here. So, I talk about
```[c++]
#define all(x) (x).begin(), (x).end()
```
Now sorting a vector looks like `sort(all(vec))` instead of `sort(vec.begin(), vec.end())`.
However, it's not all about this define. Imagine you nee...
with a specific byte, they can use `memset`. It's quite fast and can be used
to fill some (usually
35.
Very hard bug in a very simple code Take a look at this code:
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
vector<int> k;
int f()
{
k.push_back(3);
return 3;
}
int main()
{
k.push_back(1);
k[0] = f();
cout << k[0];
}
~~~~~
</spoiler>
At first glance, it should output $3$ because that's what $f()$ returns, which is then assigned to $k_0$. But when executed, this code outputs $1$!
This code is very short and everything seems clear, we're simply assinging $k_0$ to the return value of $f()$ which is $3$, and the push_back in $f()$ clearly doesn't affect the result... or does it?
<h3>How an assingment operation really works</h3>
It may seem obvious at first, we just copying one value to another, but let's see how compiler actually handles this operation.
Consider this code. ([Source](https://en.cppreference.com/w/cpp/language/eval_order.html))
<spoiler summary="Code">
~~~~~
#include <cstdio>
int a() { return std::puts("a...
the vector's 'end()' pointer is incremented. 2) Capacity is insufficient. A
new memory block
36.
Path max queries on a tree in O(1) Inspired by the discussion at [Almost-LCA in Tree](https://codeforces.me/blog/entry/71567), I wanted to pose a similar question:
Is there a simple solution to
1. preprocess a tree with **weighted** edges in $O(n)$ or $O(n \log n)$ and
1. query the maximum edge weight along the path from $u$ to $v$ in O(1)?
Once again, jump pointers can be used to solve each query in $O(\log n)$ with bad constant factor. Are there faster solutions?
37.
Generalized Suffix Tree Prologue:
-------------------
OK, so I finally decided to learn **Suffix Tree**. It's a monster I'd never dared to look in the eyes, I had always gotten away with using Suffix Array with the tail between my legs until now. The thing is that some problems require a more efficient data structure, so I decided to leave my fears behind and learn it once and for all.
First of all, I read about it in a few books and some papers online. When I understood its final structure and how to work with it, I searched an implementation online (no, I didn't plan on coding everything from scratch). I found a good and efficient implementation on Geeks for Geeks, but unfortunately it was written in C and it worked with native types.
The tweaking and testing:
-------------------------
I worked with the code and tweaked it here and there. I removed unnecessary comments and upgraded the code to C++ to make it work with strings instead of char pointers. I also added some extra functionality th...
. Everything worked fine and very fast too. I solved a few problems, but then I
came across some
38.
Need Help Debugging a Solution for Cooperative game Game on Codeforces (TLE on Test Case 80) Hi codeforces :)
I hope you're doing well! I'm currently working on a problem from Codeforces, and I'm facing some issues with my solution.
Problem Statement can be found [here](https://codeforces.me/contest/1137/problem/D)
I was doing USACO [silver](https://usaco.guide/silver/func-graphs?lang=cpp#example---cooperative-game) when i encountered it.
My solution simply implements Floyd's cycle detection, where i use 0,1 as slow and fast pointer respectively and when the meet i use the remaining people (2,3,4,5,6,7,8,9) as the slow pointer and (0,1) as fast pointer. This should have queries less than 3(t+c) (I have calculated that). However this produces TLE on test case 80 (however the error shows query limit exceeded). When i compare it with the USACO solution it produces same output which runs fine.
MY [solution](https://codeforces.me/contest/1137/submission/294979764)
USACO [solution](https://usaco.guide/silver/func-graphs?lang=cpp#solution) , [submission](https://co...
cycle detection, where i use 0,1 as slow and fast pointer respectively and
when the meet i use the, My solution simply implements Floyd's cycle detection, where i use 0,1 as slow
andfast pointer
39.
Разбор задач Codeforces Round #137 (Div. 2) Problem A:
Note that the k-th element is copied to the end. Then the (k+1)-th element from the initial sequence is copied, then (k+2)-th, … , n-th, k-th, (k+1)-th, etc.
So all the numbers on the blackboard will become equal if and only if all the numbers from the k-th to the n-th in the initial sequence were equal.
It's now also obvious that the number of operations needed for it is equal to the index of the last number that is not equal to the n-th element of the initial sequence,
because it's exactly the number of deletions needed to eliminate the elements that are not equal to the last one.
If this number is greater than k, than answer is -1. Complexity — O(n).
Problem B:
Let’s store the order of the rows and columns of table.
Thus, row[x] is the number of the row x in the initial table and column[x] is the number of column x in the initial table.
Then, the value of an element in the row x and column y in the current table is equal to t[row[x], column[y]], where t — i...
}. We can see that b * a^(n-1) = answer. Now we can use fast exponentiation for
computing a^(n-1). We
Tutorial of Codeforces Round 137 (Div. 2)
40.
Haskell is now 64-bit on Codeforces I haven't seen any announcement about this and only found out when I saw that my stupid non-`Int64` submission [submission:137642072] to problem C in today's round didn't fail pretests. But maybe some of you would like to know.
Performance-wise, I think it's probably a nice win for some problems but not that significant overall. The convenience of not having to import `Int64` and fiddle with explicit conversions or so frequently ask myself if one of the 'unimportant' constraints I don't have at top-of-mind will cause `Int` overflow will definitely be appreciated, though.
On the plus side: Arithmetic with large integers is presumably 2-3x faster now. Also, in my experience, `Int64`-related class methods often lack the performant specializations and rewrite rules available for their `Int` counterparts, and `Int64` values tend to be unboxed less aggressively on 32-bit systems, all of which made awkward using efficiently the type. GHC's pointer-tagging magic will also probably work b...
systems, all of which made awkward using efficiently the type. GHC's pointer
-tagging magic will, which made awkward using efficiently the type. GHC's pointer-tagging magic
will also probably work
41.
need help for my code ~~~~~
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
vector<int>arr;
bool pos(ll s,ll ride){
if(s<arr.back()) return 0;
ll r = 0;
multiset<int>st(arr.begin(),arr.end());
while(st.size()){
r++;
int cur = *st.begin();
if(cur>s) return 0;
st.erase(st.begin());
if(st.size()==0) break;
auto it = st.upper_bound(s-cur);
if(it==st.begin()) continue;
st.erase(prev(it));
}
return r<=ride;
}
ll f(ll ride){
ll l = 0;
ll r = INT32_MAX;
while(l<=r){
ll mid = (l+r)>>1;
if(!pos(mid,ride)) l = mid+1;
else r = mid-1;
}
return ride*l;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n; cin>>n;
map<int,int>m;
for(int i=1; i<=n; i++){
int a; cin>>a;
m[a]++;
}
for(auto p : m) arr.push_back(p.second);
sort(arr.begin(),arr.end());
if(arr.size()==1){
cout<<arr.back();
return 0;
}
ll ans = INT64_MAX;
for(int i=(arr.size()/2+arr.size()%2); i<=arr.size(...
,int> pi; vectorarr; int pointer; bool pos(ll s,ll ride){ if(s
42.
About Constant Time TLE Picture this: Your algorithm is the correct complexity, but the verdict is TLE. You make some constant time optimizations and AC, or worse, only get an AC after contest. I think the issue of constant time TLE is something many people have faced.
Where does this stem from? The main issue surrounding this is scam solutions. Problemsetters hope that only intended, or similar to intended solutions get an AC verdict. Sometimes, it can be difficult to differentiate between highly-optimized slow code (say NlogN) and unoptimised fast code (say O(N)).
I've personally faced this issue in a big way 3 times. Twice as a problemsetter, once as a contestant. I thought I should share about some of my experiences:
Contestant: IOI 2020, biscuits, 77 points subtask
My situation: I had managed to optimize from O(200,000Qlog(10^18)) to O(200,000Q), I was highly expecting to get the points. TLE. I reasoned that recursion is slow, and recoded it iteratively. Still TLE. Finally, I gave up and coded...
code (say NlogN) and unoptimised fast code (say O(N)). I've personally faced
this issue in a big
43.
Competitive C++ Manifesto: A Style Guide # Competitive C++ Manifesto: A Style Guide
There are many style guides for C++ out there, but we can't really use them as competitive programmers. We just want to write our code correctly as fast as possible! Trying to hack people here on codeforces, I realized there is a need for a style guide! Our goal is to write correct, fast, clear and consistent code.
> #### Disclaimer
> This is not a rulebook. You can integrate parts of it into your coding style.
> Don't overthink it, especially during a contest!
I'm going to use this guide for myself and to [teach my students](https://in.harbour.space/computer-science/modern-c-programming-hossein-yousefi/). I'm planning to make some good stuff in the future following these principles! Stay tuned!
## Compiler
Make use of C++17. Use `-Wall -Wextra -Wshadow` flags for compilation, and try to eliminate all of the warning messages, this will prevent you from having some silly bugs. There are more debugging flags like `-fsanitize=un...
fast as possible! Trying to hack people here on codeforces, I realized there is
a need for a style
44.
Bitwise operations 2 — popcount & bitsets Part 1 ([link](https://codeforces.me/blog/entry/73490)) introduces basic bitwise operations.
This is part 2 and it's mainly about (in)famous bitsets and example problems.
Also, see links to very useful advanced stuff at the bottom. EDIT: here's [video version](https://www.youtube.com/watch?v=jqJ5s077OKo&list=PLl0KD3g-oDOHpWRyyGBUJ9jmul0lUOD80) of this blog (on my Youtube channel).
### Built-in functions
In C++, `__builtin_popcount(x)` returns popcount of a number — the number of ones in the binary representation of $x$. Use `__builtin_popcountll(x)` for long longs.
There are also `__builtin_clz` and `__builtin_ctz` (and their long long versions) for counting the number of leading or trailing zeros in a **positive** number. Read more [here](https://www.geeksforgeeks.org/builtin-functions-gcc-compiler/). Now, try to solve these two simple tasks in $O(1)$, then open the spoiler to check the solution:
<spoiler summary="Compute the biggest power of 2 that is a divisor o...
])`. The complexity becomes $O(N^2)$, fast enough. What if we are given the
availability for the
45.
ROI 2018 in GYM Hi.
On Wednesday at [9:05 CET / 8:05 UCT](https://www.timeanddate.com/worldclock/fixedtime.html?day=27&month=3&year=2019&hour=11&min=5&sec=0&p1=166) you can participate in the GYM version of the finals of 2017-2018 Russian Olympiad in Informatics (ROI), Day 1.
And on Thursday there will be day 2, same time.
Links to GYM contets: [day1](https://codeforces.me/gym/102147) and [day2](https://codeforces.me/gym/102154).
5 hours, 4 problems, IOI-style scoring with subtasks.
Statements will be available in three languages: English, Russian, Polish.
We wanted to use those problems in a camp in Warsaw so we had to import the problems to some system anyway.
Then why not Polygon+Codeforces and thus allowing everybody to participate?
Huge thanks to [user:MikeMirzayanov,2019-03-25] for helping me with using GYM.
And credits to problem authors: [user:Andreikkaa,2019-05-21] for Radium, [user:Endagorion,2019-05-21] for Viruses, [user:pashka,2019-05-21] for Innophone, Георгий Корнее...
new appears, and if you store a pointer to optimal element in each bucket
instead of binary
46.
Tutorial and tips to reach Master. "As mentioned earlier, practice hard. This is the only common factor that experts have. And for whom reached expert, I'll write a sequel from expert to master soon." (From my blog, Tutorial and tips to reach Expert). That soon happened to be 1.5 years after the first blog......
First, I'm sorry for the immense delay. Many bad things happened to me, like not staying in the Master rating range, having a health problem, etc. That's why I wrote the blog this late.
Introduction
------------------
This is a sequel, but I am going to write the steps to Expert from scratch since the original blog([https://codeforces.me/blog/entry/81882](https://codeforces.me/blog/entry/81882)) has poor quality.
Your journey is going to be divided into 4 sections. Each section contains the knowledge you need to have, the practice you must do, the performance you need to have in a contest, etc to advance to the specific rating.
Section 1. From the beginning to escaping Gray(1200)
---------------...
) ------------------ ####Fast solving Solving problem is often not enough to
get a higher rating. You often need to, -pointer, and number theory.** As you learn these topics, search for these
topics in codeforces, and
47.
Russian Code Cup Qual 1 — Editorial <h2>A. Martian Volleyball</h2>
<p>First note that in order to end the game as soon as possible only the currently leading team must get points.</p><p>Consider the condition that one of the teams wins. It must score at least <i>k</i> points and have at least 2 points advantage.</p><p>So the answer is <i>max</i>(<i>k</i>, <i>min</i>(<i>x</i>, <i>y</i>) + 2) - <i>max</i>(<i>x</i>, <i>y</i>).<h2>B. Painting the Wall</h2>
<p>First note that if the maximal length of the continuous segment is <i>L</i>, at least <i>L</i> colors are needed to paint the wall. On the other side <i>L</i> colors is always enough.</p><p>Consider a square <i>L</i> × <i>L</i>, fill the first line with integers from 1 to <i>L</i>, fill the following lines with all its possible circular shifts. Use these squares to cover the given wall rectangle like this (<i>L</i> = 4):</p><p><center> 1 2 3 4 1 2 3 4 1 2</p><p>2 3 4 1 2 3 4 1 2 3</p><...
for ci to get it fast.
D. Memory Manager
First for each query
, >i to get it fast.
D. Memory Manager
First for each query qi
48.
Implementing Dinitz on bipartite graphs Hi everyone!
if you read about [Dinic algorithm](https://cp-algorithms.com/graph/dinic.html) on CP-Algorithms, especially the [section](https://cp-algorithms.com/graph/dinic.html#unit-networks) about how it works on unit networks, you'll notice that its supposed runtime for bipartite matching is $O(E \sqrt V)$, where $E$ is the total number of edges, and $V$ is the total number of vertices of a bipartite graph. Let's try it out on the following problem:
**[Library Checker — matching on Bipartite Graph](https://judge.yosupo.jp/problem/bipartitematching)**. Given a bipartite graph with $V, E \leq 2 \cdot 10^5$, find the maximum matching.
The implementation of the Dinitz algorithm that I typically use looks as follows:
<spoiler summary="code">
```cpp
struct unit_network {
int n;
vector<int> to, cap;
vector<vector<int>> g;
unit_network(int n): n(n), g(n) {}
void add_edge(int a, int b, int cp) {
g[a].push_back(size(to));
...
Dinitz algorithm, we maintain a pointer to the last checked edge in each
vertex. Then, the main loop
49.
SRM 692 Seeing as there's no blogpost from [user:chrome,2016-06-10] about the round a few hours before it...
TC SRM 692 starts [soon](http://www.timeanddate.com/worldclock/fixedtime.html?&day=09&month=06&year=2016&hour=21&min=00&sec=0&p1=179). If you're up at night, you can participate!
**UPD**: Contest over! As you may have noticed, I was the writer; it's worth it to read the problem of both divisions just for the stories.
**Hints:**
<spoiler summary="TreeSums">
<spoiler summary="hint 0">
The optimal node is either centroid.
</spoiler>
<spoiler summary="hint 1">
Centroids can be computed using something like LCA or a binary search.
</spoiler>
<spoiler summary="hint 2">
Think in terms of various sums over $2^k$ ancestors of each vertex, just like the jumps to the $2^k$-th ancestor used to compute LCAs.
</spoiler>
</spoiler>
<spoiler summary="LinenCenter">
<spoiler summary="hint 1">
Solve the case $K=1$ first.
</spoiler>
<spoiler summary="hint 2">
Fast exponentiat...
summary="hint 1"> Solve the case $K=1$ first. Fast
50.
Codeforces Round #123 (Div. 2) Tutorial [problem:195A]
The whole video will be downloaded in $all = (c \cdot a + b - 1) / b$ seconds. In this problem you can choose every $1<=t<=all$ as an answer. To fulfill coditions of the problem it is enough to check the condition $t0 \cdot b >= (t0 - t) \cdot a$ at the moment of time t0 = all.
[problem:195B]
In this problem you should carefully implement the given process. Firstly note that ball number $i > m$ will be in the same basket as ball number $i - m$. Therefore it is enough to distribute first $m$ balls. It can be done using two pointers $lf$, $rg$ from the middle. Alternately put one ball to the left and to the right and shift pointers. In only case you should shift left pointer twice in the first moment of time if $m$ is odd.
[problem:195C]
In this problem you was to implement what was writen in the statement. In my solution I did the following. Erase all spaces from the text except spaces in messages in try-catch blocks. Then when we get word "try" we put nu...
pointer twice in the first moment of time if $m$ is odd. [problem:195C] In this
problem you
51.
Codeforces Round #337 (Div.2) Editorial [610A — Pasha and Stick](http://codeforces.me/problemset/problem/610/A)
If the given $n$ is odd the answer is 0, because the perimeter of any rectangle is always even number.
If $n$ is even the number of rectangles which can be construct equals to $n / 4$. If $n$ is divisible by 4 we will count the square, which are deprecated, because we need to subtract 1 from the answer.
Asymptotic behavior — $O(1)$.
[610B — Vika and Squares](http://codeforces.me/problemset/problem/610/B)
At first let's find the minimum in the given array and store it in the variable $minimum$. It is easy to understand, that we always can paint $n * minimum$ squares. So we need to find such a minimum in the array before which staying the most number of elements, which more than the minimum. In the other words we need to find 2 minimums in the array which are farthest from each other (do not forget about cyclical of the array). If there is only one minumum we need to start paint...
the symbols in $s$ from left to right and maintain the pointer to the current
position in alphabet
Tutorial of Codeforces Round 337 (Div. 2)
52.
Some constant factor difference between vector and array [Code with Vector](https://codeforces.me/contest/1957/submission/346093361)
[Code with Array](https://codeforces.me/contest/1957/submission/346095087)
### Observation
Based on my testing, arrays are significantly faster than vectors in this scenario—specifically, around 14 to 15 times faster.
### Revelation
For parameter lists with fixed lengths, use arrays for better performance. When dealing with dynamic lengths, vectors are more efficient for faster coding. However, performance can still be optimized using pointers in either case.
53.
[Tutorial] On Range LIS Queries, Part 2 ## Previous article
* [On Range LIS Queries. Part 1](https://codeforces.me/blog/entry/111625)
## Chapter 4. Fast algorithm for $\boxdot$ operator
We stopped at the point where we learned how to:
* Implement the $\boxdot$ operator in $O(N^3)$ time
* Use the $\boxdot$ operator for $O(N^2)$ time
I actually didn't introduce the name to avoid unnecessary scare, but the [original paper](https://arxiv.org/abs/0707.3619) calls this operator as *unit-Monge matrix-matrix distance multiplication*. Throughout the article, we will call it as the **unit-Monge multiplication (of permutation)** or just $\boxdot$ operator as we did before.
Let's see how to compute the $\boxdot$ operator in $O(N \log N)$ time. For a matrix $\Sigma(A), \Sigma(B)$ consider the partitioning $\Sigma(A) = [\Sigma(A)_{lo}, \Sigma(A)_{hi}], \Sigma(B) = \begin{bmatrix} \Sigma(B)_{lo} \newline \Sigma(B)_{hi} \end{bmatrix}$, where $lo$ denotes the first $N/2 + 1$ entries, and $hi$ denotes last $N/2$ entries. We ...
) ## Chapter 4. Fast algorithm for $\boxdot$ operator We stopped at the point
where we learned how
54.
VK Cup 2016 Round 1 — Editorial Codes in nicer format will be uploaded later.
[problem:658A] and [problem:639A] — [codes](http://ideone.com/NYuwV8).
[problem:639B] and [problem:639C] — [codes](http://ideone.com/GcUNZJ).
[problem:639D] — [codes](http://ideone.com/FkE3DU).
[problem:639E] — [codes](http://ideone.com/OoSLF3).
[problem:639F] — [codes](http://ideone.com/PUSLI2).
[problem:658A] — Iterate once from left to right to calculate one player's score and then iterate from right to left. It's generally good not to write something similar twice because you are more likely to make mistakes. Or maybe later you will find some bug and correct it only in one place. So, try to write calculating score in a function and run them twice. Maybe you will need to reverse the given arrays in some moment.
[problem:639A] — You should remember all friends displayed currently (in set or list) and when you add someone new you must check whether there are at most $k$ people ...
Tutorial of VK Cup 2016 - Round 1
Tutorial of VK Cup 2016 - Round 1 (Div.1 Edition)
Tutorial of VK Cup 2016 - Round 1 (Div. 2 Edition)
55.
TheForces Round #32 (2^5-Forces) Editorial [A: Short Query](https://codeforces.me/gym/105270/problem/A)
Idea:[user:yugandhar_master,2024-03-14]
<spoiler summary="solution">
If the array contains more than $2$ elements then it is definitely possible to do given operation because array will definitely contain atleast $2$ $even$ numbers or atleast $2$ $odd$ numbers, in both cases sum of the numbers is $even(even+even =even, odd+odd=even)$.
Hence, we can do the given operation until array size becomes lesser than or equal to $2$.
If the array size is $2$, we can do operation only if both elements parity is equal. If the array size is $1$, we can’t do any operation.
The below proof mentioned for an array of atleast size $2$.
The minimum size of the array we obtain is determined by the number of $odd$ elements in the array, if number of $odd$ elements is $odd$ then the minimum size of the array is 2 because $(odd+odd+…+odd).._{odd times} \rightarrow (even+odd = odd)$, so array must contain an $odd$ element ...
fast \ ios_base::sync_with_stdio(0); \ cin.tie(0
56.
How to Effectively Practice CP + Problem Solving Guide This is a slight tweak of [a practice guide](https://www.reddit.com/r/usaco/comments/pk3tjp/the_ultimate_usaco_practice_method/) I wrote a while ago on USACO reddit since I thought it could be helpful to people here. Some USACO specific sections or extra clutter I left out here that aren't needed for a general audience. This should cover all general cp advice I have so I never have to retype.
#Introduction
This is a post on how I believe is the best method to practice modern day competitive programming based on my experiences. I assume you already have some knowledge and know simple things like binary search and dfs/bfs, but **read the footnote if you are complete beginner** (never code, solved <50 problems, div2 A/B too difficult, grey or stuck low pupil).
First, a quick tl;dr of the practice strategy before a bunch of specifics and explanation:
>**In short, mostly you only need to use codeforces (no matter what contest you're training for), find a rating range where you c...
. However if you really want to improve fast, ideally practice should be daily,
no breaks.** [cut
57.
Help->O(NlogN) giving TLE(4 s) in TRIE problem. I was attempting this problem :
https://codeforces.me/contest/706/problem/D
I tried using trie and it gives TLE. I saw solutions of other people but most of them have created a TRIE by using struct and pointers. I have done it using a 2d next array following the idea from [user:Errichto,2021-06-01] topic video of trie. I cant figure out why there is TLE, maybe because of map ? Any help would be appreciated.
Here is my code :
<spoiler summary="D">
~~~~~
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const int N = 2e5+2;
int id = 0;
int nxt[3*N][2];
map<int,int> m;
int bit(int x,int p){
return ((x&(1<<p)) > 0 ? 1 : 0);
}
void add(int x){
int node = 0;
for(int i=30;i>=0;--i){
if(nxt[node][...
> using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0);
cout.tie(0); #define ll
58.
Good Observations: I will account for good observations and ideas while solving problems in codeforces/CodeChef/atcoder . The proofs of the below statements will not be mentioned here; It's advised to do such proofs on your own for exercise.
- Lets say I have a set $S$ consisting of integers, denote its $lcm(S) = L$, I add a new element $x$ to this set $S$ ,
Lets deonte the new set as $S'$,where $S' = union(S , x)$ and its $lcm(S') = L'$. Can we deduce a relation between $L$ and $L'$? We can observe $L = L'$ or $L' >= 2*L$.
<hr>
- We want to find two numbers in an array $A[]$ with maximum common prefix bits in binary representation. It's easy to show that those two numbers always occur as adjacent numbers in $sorted(A[])$
<hr>
- The number of distinct gcd prefixed/suffixed at an index in an array will never exceed $log(A_{max})$
<hr>
- Let's say I have a number $X$, And I apply modulo operation as many times as I wish, i.e $X = X \% {m_i}$ for some different values of ${m...
fixing the L pointer or 2pointer approach, does not work, try to divide and
conquer. It may be easy
59.
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...
how it works? C++03 and previous standards had a serious penalty when
returning non-pointer
60.
Randomized HLD : Smashing Growing Trees Online Hello Codeforces!
A few months ago, I wrote a blog post about [Random heavy light decomposition](https://codeforces.me/blog/entry/151250). Today, I want to discuss a powerful extension of this idea.
How do you usually solve problems where a tree grows online? That is, you process queries that attach a new vertex to the tree, while simultaneously answering queries on paths (e.g., finding the minimum on a path).
Let's try to solve this using Heavy-Light Decomposition (HLD).
### The Flaw of Naive HLD
At first glance, one might try a naive approach: when a new vertex is added, simply extend the existing HLD path into it. However, this creates a major vulnerability.
Consider the following case:
Imagine we repeatedly attach new vertices to form a long path. We extend the HLD path into each of them. But then, we attach a new vertex directly to the root, and subsequently attach all future vertice...
its suffix. Is this fast enough? Absolutely. #### Proof 2: The expected size
of the rebuilt
61.
[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...
)$ expected time per pivot with $O(V+E)$ memory, leading to an extremely fast
algorithm for most
62.
Biweekly contest 3 Editorial #### Note from Author:
Congrats to all the Winners. Glad to see so much participation. Hope to see you all participate in the next biweekly as well. You can contact [user:panda_2500,2022-12-16] (Abhijit Mishra) or [user:adityagi02,2022-12-16] (Aditya Tyagi) for any queries related to the contest or problem discussion.
I would recommend first looking at the hints for the problem if your facing logical issue, if you are absolutely clear with logic then move on to look at the solution and the code.
Efforts will be made towards making code for other languages (Python) available as well.
## [A — Xeros](https://codeforces.me/gym/416532/problem/A)
<br>
<spoiler summary="Hint">
<spoiler summary="Hint 1">
Is there any reason we will interchange the same digits?
</spoiler>
<spoiler summary="Hint 2">
To make it in non-decreasing order the 1 should be before a 0 ?
<br>
1 0 0 0 1
<br>
is there any need for replacement in this? Which elements do you think should be repl...
count the operations. The maintain 2 pointers the left pointer will be looking
for the first 1 and the
63.
Codeforces Round #219 editorial Sorry for late.
This is the editorial of Codeforces Round #219. Div2 A, Div2 B, Div1 C are made by [user:m.kagamiz,2013-12-15], and other problems are made by me.
[problem:373A] /\\_/\
First, you need to count the occurence of each number (1 through 9).
If none of them are greater than 2 * k, Cucumber boy is able to press
the panels in perfect timing.
Complexity is O(1).
My solution : http://ideone.com/CwQtBv
[problem:373B] /\\_/\
Naive simulation (subtracting S(i) * k from w while w >= 0) won't finish in 2 seconds.
At first, these two facts will make it easier to solve the problem :
1. k doesn't matter for solving this problem, so you can simply divide w with k at the first point.
2. S(10^x) + S(10^x + 1) + ... + S(10^(x+1) — 1) = 9 * x * 10^x .
There are many ways to solve this problem, and I'll show you 2 ways.
1. Binary Search
Let's define f(n) as \sum_{k=1}^{n} S(n). This problem can be solved by finding largest
x that satisfies f(x) &md...
Tutorial of Codeforces Round 219 (Div. 2)
64.
Slightly improved version of Query sorting using Sqrt Decomposition For offline queries, we can sort them using sqrt decomposition to minimize query traversal costs. This is very useful especially in situations where query answers can be generated using two pointers method.
For this, we first divide the total query range in sqn = sqrt(n) sections. We first sort the queries in order of which section the starting point fell in, than in each section we sort the queries based on the order ending point from large to small or (small to large).
I used a slightly altered implementation for this problem. Instead of using large to small or small to large endpoint at section. I sorted them in an altering structure. Therefore, if in section 1, we sort them from large to small, in section 2 we sort them from small to large, then in section 3 we again sort them from large to small. I think this implementation is quite faster on average, and in the problem I tested both the default and customized implementation. The latter proved to be almost twice as fast as the f...
both the default and customized implementation. The latter proved to be almost
twice asfast as the
65.
Binary Extended Greatest Common Divisors ? I read in [this paper](https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/) and know that Binary GCD Implementation is proven to be about 2 times faster than Normal GCD Implementation.
<spoiler summary="Binary Iterative GCD Implementation (wikipedia)">
```cpp
unsigned int gcd(unsigned int u, unsigned int v)
{
unsigned int shift = 0;
/* GCD(0,v) == v; GCD(u,0) == u, GCD(0,0) == 0 */
if (u == 0) return v;
if (v == 0) return u;
/* Let shift := lg K, where K is the greatest power of 2
dividing both u and v. */
while (((u | v) & 1) == 0) {
shift++;
u >>= 1;
v >>= 1;
}
while ((u & 1) == 0)
u >>= 1;
/* From here on, u is always odd. */
do {
/* remove all factors of 2 in v -- they are not common */
/* note: v is not zero, so while will terminate */
while ((v & 1) == 0)
v >>= 1;
/* Now u and v are b...
, the swapping is just pointer movement, and the subtraction can be done
66.
[Not tutorial] Sort before insert — A small extension to Merge sort tree Hello Codeforces!
This is my first ever blog on Codeforces, and today I wanted to <s>gain contributions</s> share my small invention during my upsolving. I don't know if there existed a similar idea yet, but as far as I can tell, the editorial for the problem that I have solved does not use my idea. I think it would be nice to share with you guys and have your opinions on this idea.
<h1>Prerequisite</h1>
You should understand what is a segment and what is a merge-sort tree first.
All the code in this blog is in <a href="https://codeforces.me/blog/entry/18051">efficient style</a>, therefore you should at least recognize part of it before reading the code.
<h1>Idea explanation</h1>
<h2>How do we build Merge-sort tree again?</h2>
Merge sort tree is a Segment tree, each node of which contains a sorted set/vector of every element in its range. We build it in a bottom-up manner. To build the parent nodes, we merge 2 sets/vectors of the children the same as we do in the merge-...
pointer technique by the following:
* Build 2 trees with `sort before insert`, one for array's
67.
Прагма Прагма это та штучка которая помогла мне на различный ИОИ контестов. Прагма то директива препроцессора в языках программирования C и C++, которая позволяет компилятору выполнять специфические инструкции. Она используется для управления поведением компилятора и может изменять определенные настройки, такие как оптимизация, предупреждения или организацию памяти. Это очень полезная штучка но иногда приносит вред занимая много памяти. #pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC op...
optimize("-fdelete-null-pointer-checks") #pragma GCC
optimize("-fdevirtualize") #pragma GCC
68.
Check if an array a is a cycle of another array b I passed problem C of round 980 (Div 1) with a sketchy code that I wrote: https://codeforces.me/contest/2023/submission/300471200
The code has a fast and slow pointer. Set an initial value called match to 0. If a[fast%n] != b[slow%n], increase fast by 1, and set match to 0. Otherwise, increase fast and slow both by 1, and increase match by 1. If fast is greater than slow by n, then a is not a cycle of b. Otherwise, if match is n, then a is a cycle of b.
I would really appreciate it if someone could send me either a test case that TLEs this code, or the proof of why this code works. Thanks.
/contest/2023/submission/300471200 The code has a fast and slow pointer. Set an
initial value called, The code has a fast and slow pointer. Set an initial value called match to 0.
If a[fast%n] != b
69.
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...
`, `size_type`, `value_type`, `pointer`, `const_reference`, `key_equal` 1.
Iterators: member types `iterator
70.
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...
located in a single big function. Everything was passed by pointer and there
were hardly any levels
71.
Operating Systems Notes If you are struggling with the right track and a 10-min read for Operating systems from beginning to end, you're at the right place. Even I am not sure where to start, but we would figure it and if you are reading this, I have successfully completed these notes or at least am on right track.
Let's start our struggle for OS:
### The Track
I found many resources to learn, let's just list all:
(Galvin Concise PPTs)[https://www.os-book.com/OS9/slide-dir/index.html]: These were great but I felt that these are a little bit too much, so here are the chapters we would do:
1. Processes
2. Threads
3. Process Synchronization
4. CPU Scheduling Algorithms
5. Deadlocks
6. Main memory
7. Virtual memory
8. Virtual Machines
> I am skipping the introduction of OS for now as it was not that important, this is going to be a fast article that works like a last night dose.
<spoiler summary="A simple introduction(May skip if you are already familiar)">
An Operating system is like a...
not that important, this is going to be a fast article that works like a last
night dose.
72.
Codeforces round #396 editorial [problem:766A]
If the strings are the same, Any subsequence of $a$ is indeed a subsequence of $b$ so the answer is "-1", Otherwise the longer string can't be a subsequence of the other (If they are equal in length and aren't the same, No one can be a subsequence of the other) so the answer is maximum of their lengths.
Code : http://pastebin.com/aJbeTTjw
Time complexity : $O(|a|+|b|)$.
Problem author : me.
Solution author : me.
Testers : me and [user:mahmoudbadawy,2017-02-07].
[problem:766B]
#### First solution :-
Let $x$, $y$ and $z$ be the lengths of 3 line segments such that $x \le y \le z$, If they can't form a non-degenerate triangle, Line segments of lengths $x-1$, $y$ and $z$ or $x$, $y$ and $z+1$ can't form a non-degenerate triangle, So we don't need to try all the combinations, If we try $y$ as the middle one, We need to try the maximum $x$ that is less than or equal to $y$ and the minimum $z$ that is greater than or equal to $y$, The easiest way to do so...
sequence, Fibonacci is a fast growing sequence, $fib(45)=1134903170$, Notice
that Fibonacci makes
Tutorial of Codeforces Round 396 (Div. 2)
73.
AtCoder Beginner Contest 139 English Solutions #A — Tenki
This is a fairly simple task--just iterate over all positions in the strings and count the ones where S[i] = T[i].
Runtime: $O(|S|)$. [Click here for my submission.](https://atcoder.jp/contests/abc139/submissions/7247680)
---
#B — Power Socket
Note that we already have one socket, so we need to fill $B-1$ more sockets. Additionally, each new outlet we add will take up one socket and add $A$ sockets, resulting in a net addition of $A-1$ sockets. We thus need to create at least $B-1$ sockets where each outlet gives us $A-1$ sockets, making our answer $\lceil \frac{B-1}{A-1} \rceil$. Since most programming languages use floor division, we can also express this as $\lfloor \frac{A+B-3}{A-1} \rfloor$.
Runtime: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc139/submissions/7249379)
---
#C — Lower
We essentially use two pointers. Maintain the starting position at zero. Then, while the next position isn't hi...
74.
Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2) Editorial Thank you for participation and we hope you enjoy this round ヽ(^ o ^)/.
During the contest, there was a small issue in problem D. For those affected, we have skipped your duplicate submissions (if your duplicate submissions were not skipped, please let us know). We apologize again for any inconvenience caused.
In addition, we are honored to invite you to our unofficial round tomorrow (*╹▽╹*) [Invitation to TheForces Round #22 (Interesting-Forces)](https://mirror.codeforces.com/blog/entry/119771)
### [1864A-Increasing and Decreasing](https://mirror.codeforces.com/contest/1864/problem/A)
Idea : [user:wuhudsm,2023-08-27]
<spoiler summary="Tutorial">
We use the following greedy construction:
For all $i$ ($1<i<n$), set $a_i=a_{i+1}-(n-i)$. If $a_2-a_1 \geq n-1$, we've found a solution, otherwise there is no solution.
Proof. Assume there's a solution which includes an index $i$ ($1<i<n$) such that $a_{i+1}-a_i>n-i$. We can make $a_j:=a_j+\Delta$ for all $j$ ($2 \le j ...
, around $O(n^2 log n)$. Firstly, for every cell, we keep a pointer that points
to the information
75.
Codeforces Round #240 Editorial Hi!
[problem:415A]
For this problem for each light $j$ you could just iterate over all pressed buttons and find the first button $b_i$ that $b_i < j$. Then you could output $b_i$ and move to next light.
[cut]
$ ~ $
[problem:415B]
For this problem you can find the number of tokens you can save if you initally have $k$ tokens in $O(1)$. Then you can calculate the answer for all of numbers in $O(n)$.
Suppose $\lfloor\frac{w \cdot a}{b}\rfloor$ by $p$. then $p * b \le w * a$. then $\lceil\frac{p \cdot b}{a}\rceil \le w$.
Suppose initially we have $k$ tokens. Let $x = \lfloor\frac{w \cdot a}{b}\rfloor$ then we need to find such maximum $k_0$ that $k - k_0 \ge \lceil\frac{x \cdot b}{a}\rceil$.
So $k_0$ will be equal to $k - \lceil\frac{x \cdot b}{a}\rceil$. so we can calculate $k_0$ in $O(1)$.
[problem:414A]
In each turn Bimokh will at least get one point so the result is at lease $\frac{n}{2}$. So if $k < \frac{n}{2}$ the answer is -1.
Let's denote $...
yields $O(nk ~ sqrt(n))$ solution which is not fast enough. But one could use
the fact that the
Tutorial of Codeforces Round 240 (Div. 1)
Tutorial of Codeforces Round 240 (Div. 2)
76.
Python TLE for Activities (Spoj) I am trying to sovle this question: https://www.spoj.com/problems/ACTIV/
I’ve written up a DP solution that I think is optimal in terms of time complexity: n * log(n)
```
'''
https://www.spoj.com/problems/ACTIV/
'''
from collections import defaultdict
def bin_search(classes, target):
hi = len(classes)-1
lo = 0
while lo <= hi:
mid = (hi + lo)//2
if classes[mid][1] > target:
hi = mid-1
else:
lo = mid+1
return hi
def num_nonoverlapping(classes):
classes.sort(key=lambda x: x[1])
dp = [0] * len(classes)
prefix_sum = defaultdict(int)
dp[0] = 1
prefix_sum[0] = 1
for i in range(1, len(classes)):
start = classes[i][0]
best = bin_search(classes, start)
dp[i] = 1 + prefix_sum[best]
prefix_sum[i] = dp[i] + prefix_sum[i-1]
return sum(dp)
def format_ans(ans):
s = str(ans)
if len(s) >= 8:
return s[len(s)-8:]
...
77.
Day 11/60: Easy brute force/meet in the middle problems and changing the plan This has not gone too well for the last week because I had several midterms, but hopefully I'll make up for it this week. Whenever I had time I tried simple brute force/meet in the middle problems.
[problem:515B]
<spoiler summary="Idea">
Simulating the process is fast enough.
</spoiler>
[problem:1249C2]
<spoiler summary="Idea">
Very simple greedy algorithm.
</spoiler>
[problem:1043D]
<spoiler summary="Idea">
We focus on the first permutation and divide it in contiguous maximum length blocks that appear in that order in all other permutations, we can do this in O(nm) if we make the first permutation $1,2,3,\dots ,n$ and adjust all others accordingly. I didn't think of this and used map, it barely passed at 997ms
</spoiler>
[problem:888E]
<spoiler summary="Idea">
I liked this one! We use meet in the middle to calculate all possible sums $\pmod{m}$ of each half. Since our sums are between $0,m-1$ for any left sum $S_i$ the best we can choose in the righ...
. [problem:515B] Simulating the process is fast enough.
78.
A Never Seen Before Data Structure -- O(log(n)) Range Queries TLDR: just take [this blog of mine](https://codeforces.me/blog/entry/121381) and sprinkle some [canonical skew-binary numbers](https://codeforces.me/blog/entry/74847) and boom, you have a weird version of the Fenwick tree that is asymptotically faster that the Fenwick tree on an obscure operation.
It also turns out that we can perform point updates without commutativity or inverse operations, which the plain Fenwick tree can't do by itself.
## The idea
I explained on [my previous blog](https://codeforces.me/blog/entry/121381) that we can think of the Fenwick tree as a set of intervals, and that we can use those intervals to answer any range query in $O(\log(N)^{2})$. But there is no real reason to use exactly the same intervals that the Fenwick tree uses. Instead we can try to use some other set of intervals to make things more efficient (at least in an asymptotic sense).
Instead, we use intervals based on the jump pointers described on [that one blog from the catalog](h...
. UPD: After some changes I measured this to be about as fast as a recursive
segment tree. (I will
79.
CSES Sorting and Searching section editorials I just completed CSES Sorting and Searching section problems. And I didn't find any editorials for this. So I am writing my own approach for the problems.Please do correct me if I made any mistakes and do share your approach for the problems.
My solutions are [here](https://github.com/Perdente/CSES/tree/main/Sorting%20and%20Searching)
complete editorial for [CSES](https://cses.fi/problemset/) coding platform of all 27 problems in Sorting and Searching section.
--------------------------------------------------------------------------------------------------------------------------------------
**1.Distinct Numbers**
<spoiler summary="Editorial">
Just use set to store the elements and answer is the size of set.
</spoiler>
<spoiler summary="idea">
~~~~~
int n,x;cin>>n;
set<int>s;
for(int i=0;i<n;++i)
{
cin>>x;
s.insert(x);
}
cout<<s.size()<<endl;
~~~~~
</spoiler>
**2.Apartments**
<spoiler summary="Editorial">
...
"> Two pointer technique-If apartment size is greater than x+k then upper
pointer will increase or
80.
Codeforces Round #355 (Div. 2) Editorial [problem:677A]
For each friend we can check, if his height is more than $h$. If it is, then his width is $2$, else $1$.
Complexity $O(n)$.
<spoiler summary="Code">
~~~~~
#include <iostream>
using namespace std;
typedef long long ll;
ll i,n,h,ans,x;
int main()
{
cin >> n >> h;
ans = n;
for (i = 0; i < n; i++)
{
cin >> x;
ans += (x>h);
}
cout << ans << endl;
return 0;
}
~~~~~
</spoiler>
[problem:677B]
The solution, that does same thing, as in the problem statement will fail with TL, because if the height of each piece of potato will be $10^9$ and smashing speed will be $1$, then for each piece we will do $10^9$ operations.
With each new piece of potato $a_i$ we will smash the potato till $a[i]$ $MOD$ $k$, so we will waste $a[i]/k$ seconds on it. If we can not put this piece of potato after that, we will waste $1$ more second to smash everything, that inside, else just put this piece. We will get an answe...
(lst.begin(), lst.end()); ll pointer = 1; j = 0; bfs.push_back(lst[0]);
d[lst[0].Y.X][lst[0
Tutorial of Codeforces Round 355 (Div. 2)
81.
Codeforces Round #222 — Problem Analysis [Link to announcement and discussion](/blog/entry/10138).
And here is the problem analysis.
#### A div 2: [problem:378A]
Make three counters: for wins of both players and for a draw. Iterate over all six ways how they can throw a dice. For each way determine who wins or there is a draw and increment the corresponding counter.
#### B div 2: [problem:378B]
You can think a bit and understand that you should consider only corner cases: $k = 0$ and $k = \frac{n}{2}$. All other cases will be something between them.
If $k = 0$, we should choose $n$ biggest elements from two sorted lists, one of the ways is to use two pointers method. And if $k = \frac{n}{2}$, we just mark first $\frac{n}{2}$ people in each list.
#### A div 1 / C div 2: [problem:377A]
Start BFS or DFS from any free cell. As the maze is connected, this search will visit all $s$ free cells. But we can stop the search when it visits $s - k$ free cells. It's obvious that these $s - k$ cells are connected to...
Tutorial of Codeforces Round 222 (Div. 1)
Tutorial of Codeforces Round 222 (Div. 2)
82.
[Tutorial] Square root decomposition and applications A brief introduction into the applications of square root decomposition
==================
Square root decomposition is the process of separating a structure of size $O(N)$ into $O(\sqrt{N})$ "blocks" of size $O(\sqrt{N})$ each, in a way that aids manipulation of the entire structure. Square root decomposition is extremely versatile. Some of its most well-known use cases are:
- answering queries on a static array, with methods such as Mo's algorithm or block precomputation
- "lazy" brute force modifications, where it is easy to query an entire block, but tag pushing isn't obvious
- separating objects based on a threshold, when there exists both an $O(x)$ algorithm and an $O(n/x)$ algorithm
In this tutorial we will walk through multiple types of square root decomposition.
Answering queries on a static array, offline (Mo's algorithm)
---
Consider a problem where we are asked to find the answer for certain intervals $[l,r]$. We can't quickly compute the answer for an ar...
arbitrary interval, but we know how to transition to $[l,r\pm1]$ and
$[l\pm1,r]$fast given some
83.
[Training] [Arabic] ACM JCPC Summer Training 2017 Hello Codeforces,
On Septemper 2017 the JCPC Summer Training 2017 was held in the University of Jordan, covers varied topics consists of 2 main levels 1 & 2 each consists of 8 Lectures and one additional lecture in level 3. The training is recorded and published on youtube on [user:SolverToBe,2018-09-14] channel
*note: language of training is Arabic.
**Level 1**
-----------
**Lecture 1** — Presented By Ibraheem Tuffaha [user:Vendetta.,2017-09-02]
<spoiler summary="ACM and Problem Solving">
Part 1 | [ACM and Problem Solving](https://www.youtube.com/watch?v=7pdNV-8BwIk)
Part 2 | [Complexity](https://www.youtube.com/watch?v=adTPPwU0w-w)
Part 3 | [Implementation 1](https://www.youtube.com/watch?v=ftZGTQxaNzQ)
Part 4 | [Implementation 2](https://www.youtube.com/watch?v=e4-m2uHOsds)
</spoiler>
**Lecture 2** — Presented By Mohammad Zuhair [user:zuhair,2018-09-14]
<spoiler summary="STL">
Part 1 | [STL Pair](https://www.youtube.com/watch?v=fR7GcvxCA...
/watch?v=xgDS8ZYi4vE) Part 3 | [Mod and Fast
Power](https://www.youtube.com/watch?v=fQA-zgrEn8g
84.
Codeforces Round #239 Editorial Sorry for my poor English. If you find a mistake, write me a private message, I'll fix it. Some problems have not been translated yet, now you can try to read the Russian version of editorial with Google Translate.
[problem:408A]
In this problem you were to find waiting the time for every queue by summing up the purchases of all the people, and return the minimum.
[problem:408B]
In this problem it is necessary to find the garland with the maximal length, which can be composed of elements that we have. <br/>
First, if you need some color, but you don't have it, then the answer is -1 <br/>
Otherwise, answer is always exists. <br/>
Let's sum the answers for all the colors separately. <br/>
Suppose we have $a$ pieces of a garland of some color, and we need $b$ pieces. Then we have to add $min(a, b)$ to the answer: if $a >= b$ we will use $b$ 1 meter pieces, in the other case if $a < b$ we will use all $a$ pieces.
[problem:407A]
In this problem you have to locate the r...
/> Let's see solutions from slow to fast. 1) Solution by $O(n^6)$:
Iterate through two
Tutorial of Codeforces Round 239 (Div. 1)
Tutorial of Codeforces Round 239 (Div. 2)
85.
I should always use const auto& inside for loops When solving AtCoder Grand Contest 044 Problem B, I wrote some O(n^3) code with n<=500 like:
~~~~~
typedef vector<int> vi;
vector<vi> dirs({{0,1}, {0,-1}, {-1,0}, {1,0}});
...
for (auto dir : dirs){ // run O(n^3) times
...
}
~~~~~
and get TLE. On my pc it runs within 4900ms.
During the contest I have no idea why.(dumb me)
After the contest I looked at other people's solution and finally get accepted solution, just add an '&' after 'auto':
~~~~~
for (auto& dir : dirs){ // run O(n^3) times
...
}
~~~~~
480 ms on my pc! 10 times faster!
I did more tests:
~~~~~
for (int dd = 0; dd<4; ++dd){ // run O(n^3) times
vi dir = dirs[dd];
~~~~~
4900 ms
~~~~~
for (int dd = 0; dd<4; ++dd){ // run O(n^3) times
vi& dir = dirs[dd];
~~~~~
480 ms
~~~~~
vi dir;
for (int dd = 0; dd<4; ++dd){ // run O(n^3) times
dir = dirs[dd];
~~~~~
1800 ms
Maybe vector is too big, I tried pair:
~~~~~
vector<pair<int, int>> dirs({{0...
86.
Good Bye 2015 Editorial [problem:611A]
There are two ways to solve this problem.
The first is to hard-code numbers of days in months, check the first day of the year and then iterate over days/months — [http://ideone.com/4TYPCc](http://ideone.com/4TYPCc)
The second way is to check all possible cases by hand.
The 2016 consists of 52 weeks and two extra days.
The answer for "x of week" will be either 52 or 53.
You must also count the number of months with all 31 days and care about February.
[http://ideone.com/Bf9QLz](http://ideone.com/Bf9QLz)
[problem:611B]
Each number with exactly one zero can be obtained by taking the number without any zeros (e.g. $63_{10} = 111111_{2}$) and subtracting some power of two, e.g. $63_{10} - 16_{10} = 111111_{2} - 10000_{2} = 101111_{2}$.
Subtracting a power of two changes one digit from '1' to '0' and this is what we want.
But how can we iterate over numbers without any zeros?
It turns out that each of them is of form $2^x-1$ for some $x$ (you can c...
something happens and our subrectangle losts one row or one column. But how to
do itfast? You
Tutorial of Good Bye 2015
87.
Why so mainstream? feat. tries Seriously, why so serious? And why so mainstream? Competitive programming is all about fun, therefore...
### Cutting to the chase
I'll talk about something that goes like that: everyone talks about it, few really know how to do it, everyone thinks everybody else knows how to do it, so everyone claims they know how to do it.Not teenage sex, but understanding data structures. In the sense of the metaphor before, I am close to a virgin but I still can give you some insight as there are some structures that are my type. I will write more on data structures, but this time we'll look at tries.
Don't get me wrong, I am talking about data structure that tend to be implemented and modeled the same way each time due to habit or even not implemented(cause STL has them).
_Note that I will put more emphasis on the steps in getting the solution than on the implementation and the way the data structure works, because there are many great articles on it._ [cut]
### The good ol' dictio...
88.
Problem Topics Good Day to you!
I've been asked to make some topic-wise list of problems I've solved. Even though I couldn't involve all problems, I've tried to involve at least "few" problems at each topic I thought up (I'm sorry if I forgot about something "easy"). I've alredy made such list once anyway I've tried to include more problems now — so here it is:
<spoiler summary="aho">
http://www.spoj.com/problems/ADAJOBS/
URI 2226 (5) //[NICE][NUMBERS][DP]
http://www.spoj.com/problems/SUB_PROB/en/
http://codeforces.me/contest/696/problem/D 8
http://www.spoj.com/problems/AHOCUR/ 5 //Aho-Corassic + DP
https://www.codechef.com/problems/LYRC (5) //Sample aho-brute-force
http://codeforces.me/problemset/problem/346/B //Proposed by [user:bradyawn,2019-08-03]
</spoiler>
<spoiler summary="automat">
6861 [LA] //CYK
UVA 10679 //Suffix Automat
http://www.spoj.com/problems/STRMATCH/ //Suffix Automat — trie might do too
http://www.spoj.com/problems/NSUBST...
://codeforces.com/contest/920/problem/F (5) //[NICE][FAST FALL][SET][DIVISORS]
7726 A Simple Math
89.
Interesting implementation of Persistent Sets *Do you really hate tree rotations? This blog post is for you!*
Recently, I've been solving [problem:768G] and I came up with a solution which is so ridiculously overengineered that I think it deserves its own blog post!
I don't want to go over all the details of the solution. Instead, I want to demonstrate a nice way to implement and apply Persistent Set and Persistent Array data structures and share a few ideas some may find interesting.
Basically, what I wanted to do is compute for each node $x$ of the rooted tree a set, which would contain the sizes of all subtrees of $x$. In other words, if we denote $sz(y)$ — the size of the subtree rooted at $y$, I want to compute the set $S(x) = \{sz(y) | y \in subtree(x)\}$ for all $x$. We also want this set to have some `lower_bound` and `upper_bound` functionality.
Obviously, just storing these sets in a normal way would require $O(n^2)$ memory, so we need another approach. Let's use the same idea that we use when building ...
to do efficiently at first, but is actually quite simple and works very fast
under some circumstances
90.
Yandex Algo 2015 (cancelled) round 2 editorial Hello :)
I was the writer for the Round 2. I'm very sad that the contest platform failed and you couldn't do your best solving them -- for me it's also sad as my work on the problems is now wasted. Hopefully you liked the problems themselves.
Here are the problem statements:
- A http://pastebin.com/raw.php?i=U8SfbSL8
- B http://pastebin.com/raw.php?i=bAi07eMm
- C http://pastebin.com/raw.php?i=R72vqKkk
- D http://pastebin.com/raw.php?i=Ar5CmJ8j
- E http://pastebin.com/raw.php?i=wiCtb0ab
- F http://pastebin.com/raw.php?i=iaMnb9cs
And below are brief solution ideas. Ask if anything is unclear.
**A (ascending the stairs)**
Dynamic programming in O(n).
Let W[x] be the number of ways to climb the first x steps of the stairs. (We will call that "state x".)
W[n] is the answer we want.
For each x, let y be the lowest state that we can go directly from state y to state x -- i.e., the sum H[y]+...+H[x-1] is still <= m. Then W[x] is simply the sum of W[y] through W[...
91.
UT Open 2025 Editorial Hope you enjoyed our contest! The editorial is below:
[A — Fishy Tank](https://codeforces.me/gym/105811/problem/A)
Author: [user:DylanSmith,2025-04-10] <br/>
Idea: [user:fishy15,2025-04-10]
<spoiler summary="Solution">
The problem asks to place $n$ fishies into a $15\times25$ tank (including the borders). One way that we can accomplish this is by placing a single fishy at the beginning of rows $2$ to $n+1$, and no fishies in rows $n+2$ to $14$. This works since at most $10$ rows will have fishies (one for each fishy) and we have $13$ rows to work with. Make sure to print the border of the tank properly.
Fun fact, the judge solution places the fishies uniformly at random into the tank. You can view this solution [here](https://gist.github.com/DylanSmith63/8340fd6bd9b7ca49f6d1c493200f954f). (It is definitely not the simplest solution, but the output looks really nice)
</spoiler>
[B — Card Counting](https://codeforces.me/gym/105811/problem/B)
Author: [us...
in the suffix automaton, where the suffix link of a node is a pointer to its
parent node. We also
92.
Efficient Data Structure for random access and random inserts I have been trying to find a efficient Linear Container Data Structure which can support:
~~~~~
1. Fast access to any index
2. Fast insert after any index
~~~~~
For example:
~~~~~
Initial structure:
~~~~~
~~~~~
Index: 0 1 2 3 4 5
Data: 7 19 1 3 12 2
~~~~~
~~~~~
Accessing index 4 gives 12
Accessing index 5 gives 2
After I insert 5 after index 2:
~~~~~
~~~~~
Index: 0 1 2 3 4 5 6
Data: 7 19 1 5 3 12 2
~~~~~
~~~~~
Accessing index 4 now gives 3
Accessing index 5 gives 12
~~~~~
**Vectors**:
Vectors perform well for operation 1 (Access index i).
**Linked lists**:
Linked lists can perform well for operation 2 (Insert after index i) if we have a pointer to the node at index i.
**Balanced binary trees**:
1. We can assign indices to every value inserted
2. If the index is a b-bit number, the first value inserted gets index 2**(b-1)-1
3. Every new value inserted is assigned an index that is an average of indices of ...
: ~~~~~ 1. Fast access to any index 2. Fast insert after any index ~~~~~ For
example
93.
Codeforces Beta Round #50: Editorial for problem E <p><img src="http://e-maxx.ru/upload/codeforces_50/E.png" style="float:right;"></p><p><br></p><p>The most important step on the way to solve this problem - is to understand that it's enough to consider only such rotations of the polygon, that one of its sides lies on the side of the room.<br><br>Let's try to understand this fact. Suppose that the fact is wrong, and there exists such a position of vacuum cleaner, that neither of its sides lies on the side of the room. Denote as $i$ and $j$ the numbers of vertices that lie on the room sides. It's easy to understand that the polygon form between vertices $i$ and $j$ doesn't make any sense itself: for each rotation we can see that from the area of triangle $OP[i]P[j]$ some constant area is subtracted, while the concrete value of this constant depends on the polygon form.<br><br>That's why we see that the polygon form doesn't influence on anything (if we have fixed numbers $i$ and $j$), and we have just to minimize the area of right-angled ...
side.
So, we've proved the fact. Then we have to invent fast enough solution. We have
Tutorial of Codeforces Beta Round 50
94.
AIM Tech Round Tutorial [problem:624A]
Width of free space is decreasing by $v_1 + v_2$ per second. It means that it'll decrease from $L$ to $d$ in $t = \frac{L - d}{v_1 + v_2}$ seconds. The moment when width gets a value of $d$ is the last when Luke is alive so $t$ is the answer.
[problem:624B]
Sort array in descending order.
Iterate over all letters, First letter is added $c_1 = a_1$ times, each other letter is added $c_i = min(a_i, c_{i - 1})$. Don't forget that if some letter is not added at all, then all next letters are not added too.
[problem:623A]
Note that all vertices "b" are connected with all other vertices in the graph. Find all such vertices and mark them as "b". Now we need to find any unlabeled vertex $V$, mark it with "a" character. Unlabeled vertices connected with $V$ should be also labeled as "a". All other vertices we can label as "c"
Finally we need to check graph validity. Check that all vertices "a" are only connected with each other and "b" vertices. After that we...
programming for all lengths — powers of two, in $O(k \log{k} \log{n})$, using
thefast Fourier
Tutorial of AIM Tech Round (Div. 1)
Tutorial of AIM Tech Round (Div. 2)
95.
How to Increase Codeforces Rating (Practical Tips) Hello everyone,
I wanted to share some practical tips that can help in improving Codeforces rating. These are simple things that worked for me and many others.
1. Focus on solving A and B problems quickly
In most contests, your rating depends a lot on how fast and accurately you solve the first 2–3 problems.
2. Learn common patterns
Many problems are based on patterns like two pointers, greedy, prefix sums, and basic math. Recognizing patterns saves time.
3. Practice regularly
Consistency is more important than solving many problems at once. Even 2–3 problems daily can help.
4. Upsolve after contests
After every contest, try to solve the problems you couldn’t solve. This is one of the fastest ways to improve.
5. Debug your mistakes
Instead of immediately checking the solution, try to understand where your logic went wrong.
6. Don’t panic during contests
Stay calm. Even if you get stuck, move to the next problem and come back later.
7. Improve i...
problems quickly In most contests, your rating depends a lot on how fast and
accurately you solve
96.
Codeforces Round 1000 (Div. 2) — Editorial <spoiler summary="Rating Predictions">
| Handles | A | B | C | D | E | F1 | F2 |
| ---------------- | --- | ---- | ----------- | ----------- | ----------- | ---- | ----------- |
| ~Proof_by_QED,2025-01-20 | 800 | 1000 | 1500 | 2200 | 2400 | 1800 | 2600 |
| ~chromate00,2025-01-20 | 800 | 1100 | 1500 | 2100 | 2300 | 1800 | 2700 |
| ~redpanda,2025-01-20 | 800 | 900 | 1400 | 2000 | 2400 | | |
| ~larush,2025-01-20 | 800 | 1100 | 1600 | 2100 | | | |
| ~FairyWinx,2025-01-20 | 800 | 900 | 1500 | 2000 | 2400 | 1800 | 2500 |
| [user:priyanshu.p,2025-01-20] | 800 | 1200 | 1500 | 2000 | 2500 | 2000 | |
| ~Intellegent,2025-01-20 | 800 | 1000 | 1400 | 2000 | 2200 | 2000 | 260...
, we add a pointer to the corresponding tree vertex. Now we can know which tree
vertex the list node
Tutorial of Codeforces Round 1000 (Div. 2)
97.
Codeforces Round #362 (Editorial) [Here](https://gitlab.com/amirmd76/cf-round-362/tree/master) is git repository to solutions of problems of this contest.
### Div.2 A
You should check two cases for YES:
1. $x\ mod\ s = t\ mod\ s$ and $t \leq x$
2. $x\ mod\ s = (t + 1)\ mod\ s$ and $t+1 < x$
Time Complexity: $\mathcal O(1)$
[Codes](https://gitlab.com/amirmd76/cf-round-362/tree/master/2A)
### Div.2 B
Nothing special, right? just find the position of letters `.` and `e` with string searching methods (like `.find`) and do the rest.
Time Complexity: $\mathcal O(n)$
[Codes](https://gitlab.com/amirmd76/cf-round-362/tree/master/2B)
### A
Do what problem wants from you. The only thing is to find the path between the two vertices (or LCA) in the tree. You can do this in $\mathcal O(lg(n))$ since the height of the tree is...
various ways (fast and slow). Suppose these automaton has $N$ states ($N =
\mathcal O(|s_1
Tutorial of Codeforces Round 362 (Div. 1)
98.
A2SV AASTU and ASTU (3rd Year) G5 — Contest #10 Editorial [Here](https://codeforces.me/contestInvitation/1bc624b933f62c931a5193ccee232c503d732093) is the mashup link (the problems are from Codeforces' problem set).
#### [A. Digit Diversity Challenge](https://codeforces.me/gym/502195/problem/A)
<spoiler summary = "Solution">
Let's see how to check if all digits of $x$ are different. Since there can be only $10$ different numbers($0$ to $9$) in single digit, you can count the occurrences of $10$ numbers by looking all digits of $x$. You can count all digits by using modulo $10$ or changing whole number to string.
For example, if $x = 1217$, then occurrence of each number will be $[0, 2, 1, 0, 0, 0, 0, 1, 0, 0]$, because there are two $1$s, single $2$ and single $7$ in $x$. So $1217$ is invalid number.
Now do the same thing for all $x$ where $l \le x \le r$. If you find any valid number then print it. Otherwise print $-1$.
Time complexity is $O((r-l) \log r)$.
</spoiler>
<spoiler summary="Code">
```python3
# Return if g...
on the left, as long as the items in the left set are unique, we use a right
pointer and move
99.
Codeforces Round #323 Editorial **Adiv2**
To solve the problem one could just store two arrays $hused[j]$ and $vused[j]$ sized $n$ and filled with false initially. Then process intersections one by one from $1$ to $n$, and if for $i$-th intersections both $hused[h_i]$ and $vused[v_i]$ are false, add $i$ to answer and set both $hused[h_i]$ and $vused[v_i]$ with true meaning that $h_i$-th horizontal and $v_i$-th vertical roads are now asphalted, and skip asphalting the intersection roads otherwise.
Such solution has $O(n^2)$ complexity.
Jury's solution: [submission:13390628]
**Bdiv2**
It is always optimal to pass all the computers in the row, starting from $1$-st to $n$-th, then from $n$-th to first, then again from first to $n$-th, etc. and collecting the information parts as possible, while not all of them are collected.
Such way gives robot maximal use of every direction change. $O(n^2)$ solution using this approach must have been passed system tests.
Jury's solution: [submission:13390612]
*...
matrix but for length $p+q$. As soon as such multiplication is associative,
next we will usefast matrix
Tutorial of Codeforces Round 323 (Div. 1)
Tutorial of Codeforces Round 323 (Div. 2)
100.
The Shortest & Most Effective Topic List for Codeforces Beginners Want to climb rating fast? Here’s the simplest 10-topic roadmap that actually works:
- Basic Programming (Fast I/O, loops, vectors, strings)
- Greedy
- Binary Search
- Two Pointers
- Sorting + Simple Math (GCD, modulo)
- Prefix Sums / Difference Arrays
- Basic 1D DP
- Graphs – BFS + DFS
- Number Theory (Sieve, primes, modular inverse)
- Basic Data Structures (Stack, Queue, Set, Map, Priority Queue)
Fastest Practice Plan:
- 1 topic per week
- Solve only 800–1200 rated problems
- Focus on Div.2 A → B → C (then D)
Start here:
https://codeforces.me/problemset?tags=800-1200&order=problem_rating_ASC
Follow this and you can go Newbie → Pupil → Specialist → Expert in just 3–6 months!
- Basic Programming (Fast I/O, loops, vectors, strings) - Greedy - Binary
Search - Two Pointers, Want to climb rating fast? Here’s the simplest 10-topic roadmap that actually
works: - Basic
101.
Is getting to 1600 about thinking, or about memorizing tricks? My unpopular take Hi everyone,
Unpopular opinion: below roughly 1700, Codeforces is mostly a pattern-recognition contest, not a problem-solving contest.
Look at what actually shows up in Div. 2 A to D:
Prefix sums, two pointers, binary search on the answer
“Sort it and greedy”
Parity, gcd, and constructive tricks you either know or don’t
DP states that are variations of problems you’ve seen before
People who’ve seen 500 problems solve them fast. People who haven’t get stuck, no matter how smart they are. That makes the rating at this level partly a measure of how much you’ve grinded, not how well you think.
The counterargument (and I half believe it): patterns are skill. Recognizing which tool fits is exactly what good problem solvers do, and the same people climb to 2000+ anyway.
So where do you stand?
A) Early rating is mostly memorized patterns
B) It’s real thinking, and grinding just builds that skill
C) It’s a mix, and the balance changes as you climb
Reply with yo...
People who’ve seen 500 problems solve them fast. People who haven’t get stuck,
no matter how smart
102.
CEOI 2025 discussion Since CEOI 2025 is over and the tasks and test data have been published, can we discuss the solutions here?
Here are the [tasks](https://ceoi2025.utcluj.ro/category/13).
Upd: you can find the tasks [here](https://codeforces.me/blog/entry/144670?#comment-1293960) (for now)
Upd: https://github.com/asociatia-sepi/archive/tree/main/CEOI-2025
Upd: I was upsolving this CEOI now for practice and I decided to write some solutions because I couldn't find them.
## Boardgames
### Solution 1
This is the approach from the official editorial. The core idea relies on a **divide and conquer** strategy:
1. Initially, we invoke the function $f(1, n)$.
2. Find the position $i$ closest to the border such that $i$ and $i+1$ are not in the same connected component.
3. If the subgraph from $L$ to $R$ is connected, we can just return $1$.
4. Otherwise, we split the problem and return $f(L, i) + f(i+1, R)$.
The main implementation challenge here is to efficiently maintain graph con...
connectivity while supporting fast addition and removal of elements from both
the front and the back
103.
[Tutorial] Fully Dynamic Trees Supporting Path/Subtree Aggregates and Lazy Path/Subtree Updates Hey everyone! Usually when I post stuff on CF I just drop an external link to my blog, but this time I would like to also paste the same content natively on CF to see if it leads to more engagement. You can read the exact same article on my blog [here](https://mzhang2021.github.io/cp-blog/ds5/).
Also, special thanks to [user:alien_lover,2022-06-10] and [user:gabrielwu,2022-06-10] for proofreading.
---
## Motivation
We will solve **[this problem](https://dmoj.ca/problem/ds5)**.
## Prologue
The original name of this problem is [SONE1](https://darkbzoj.cc/problem/3153), originating from the fiery depths of Chinese OI. Amazingly, the Chinese have figured out how to augment the link/cut tree to solve this problem (ref [1](https://www.cnblogs.com/clrs97/p/4403244.html), [2](https://blog.csdn.net/iamzky/article/details/43494481)). Maintaining subtree aggregates with a LCT isn't difficult, and there's a well-known [Codeforces article](https://codeforces.me/blog/entry/67637) ...
binary tree, so in practice it still runs fast for random data? Either way,
just use the second
104.
Prefix tree Hi. I'm beginner at competitive programming and there is 100% that this topic is not original, but, in spite of this, I decided to publish it. So, (you are still reading, that's achievement for me :D).
Sometimes we need to associate string with some object and then quickly find it by those key string. Prefix trees are good thing to do it. For more information about them read [this](http://en.wikipedia.org/wiki/Prefix_tree), or [this] (http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE).
Algorithm complexities:
Add element O(1) // iterations are equal to length of string
Remove element O(1)
Search element O(1)
Memory:
In worse case each bound's weight is 300 bytes, but you can reduce this by using function to get child id by character (see in code), and saving pointer to object you are pushing.
Need a more detailed analysis, but, in generally we can see that this structure is very fast, but n...
function to get child id by character (see in code), and saving pointer to
object you are pushing
105.
We teach wrong When I was a child, I knew software development well (though not much of C++), and my parents motivated me to try out competitive programming.
The first thing I tried was dkirienko's section. In the first 20 minutes, GCD and the Euclidian algorithm were explained, the complexity of the Euclidian algorithm was proven, and that was pretty much it. We were then asked to solve a problem set on Codeforces individually. I didn't understand much from the complexity proof, couldn't solve a single problem, failed to figure out what I was supposed to do, and left crying. So yeah, stuff like that doesn't work.
I understood simpler topics, though. I knew basic math, like how to solve linear systems and quadratic equations, and could make simple observations, so the school stage of ROI was quite easy to get through. (The hardest part was to explain to my then-informatics teacher that yes, I want the adult problems.) During the municipal stage, I had 3 hours to solve what I'd classify as a 5-t...
$O(n)$ in row 2.** > > So we are clearly making tradeoffs here. Either setting
is veryfast and
106.
CodeForces Beta Round #73 div. 1 analysis (particulary with div. 2) <span style="font-size: 10.0pt;font-family: Arial;color: rgb(0,0,0);background-color: transparent;font-weight: normal;font-style: normal;text-decoration: underline;vertical-align: baseline;">Problem DIV1-A, Div2-C. Trains.</span><br /><span style="font-size: 10.0pt;font-family: Arial;color: rgb(0,0,0);background-color: transparent;font-weight: normal;font-style: normal;text-decoration: none;vertical-align: baseline;">This
problem can be approached from two sides - from a programmer's
perspective and a mathematician's one. We consider both approaches.</span><br /><span style="font-size: 10.0pt;font-family: Arial;color: rgb(0,0,0);background-color: transparent;font-weight: normal;font-style: normal;text-decoration: none;vertical-align: baseline;"> </span><br /><span style="font-size: 10.0pt;font-family: Arial;color: rgb(0,0,0);background-color: transparent;font-weight: normal;font-style: normal;text-decoration: none;vertical-align: baseline;">First,
let's write some general propositio...
comes next, add time before the arrival of the train to one of the answers,
move thepointer and the
Tutorial of Codeforces Beta Round 73 (Div. 1 Only)
Tutorial of Codeforces Beta Round 73 (Div. 2 Only)
107.
Editorial of Codeforces Round #572 Codes have been added!
We've added challenges(mostly not hard) to some tasks. Feel free to share solutions and ask any questions in comments!
Keanu Reeves
----------
If the string is good, then answer it's itself. Otherwise, there are at least two strings in answer, and we can print substring without its last symbol and its last symbol separately. Complexity $O(n)$.
[code](https://pastebin.com/Dc0gtG9n)
Number circle
----------
Let's suppose that array is sorted. First of all, if $a_n \ge a_{n - 1} + a_{n - 2}$, than the answer is — NO (because otherwise $a_{n}$ is not smaller than sum of the neighbors). We claim, that in all other cases answer is — YES. One of the possible constructions (if the array is already sorted) is:
$a_{n - 2}, a_{n}, a_{n - 1}, a_{n - 4}, a_{n - 5}, \ldots ,a_1$
It's easy to see, that all numbers except $a_n$ will have at least one neighbor which is not smaller than itself. Complexity $O(nlog(n))$.
[code](https://past...
$. $\textbf{Challenge}$ How fast you can solve the task if you need to print
answer for all $2
Tutorial of Codeforces Round 572 (Div. 1)
Tutorial of Codeforces Round 572 (Div. 2)
108.
On DNC DP and related things This blog is not exactly a tutorial, it is more of a review of the techniques that can be used solve some DP problems involving the quadrangle inequality, and some problems related to DNC DP.
<br>
DNC DP
------
DNC DP is a well-known optimisation that can solve some DP problems from $O(N^2K)$ time to $O(NKlogN)$ time.
The key idea uses the monotonic nature of the splitting points to compute each layer in $O(NlogN)$ time. In other words, it uses the fact that $opt(N,K)<=opt(N+1,K)$, where $opt(N,K)$ is defined as the left splitting point for the $K^{th}$ segment for the first $N$ elements, for all positive integers $N$ and $K$.
Most often, the monotonic nature is satisfied when the cost function satisfies the quadrangle inequality (a.k.a. wider is worse), which is for all indices $A<=B<=C<=D$, $cost(A,C)+cost(B,D)>=cost(A,D)+cost(B,C)$ (it can also work the other way).
### [Guards] (https://codeforces.me/gym/103536/problem/A)
**Given an array of length $N$, split it into $K$ se...
function is no longer $O(1)$, we need to use Mo-like two pointer method to
move them to a desired range
109.
Notes on Codeforces Beta Round #119, Div2- A, B, C, D , E [problem:189A]
This problem asks to solve an equation $xa+yb+zc=n$. We can enumerate each $x$ and $y$ but calculate $z$ directly according to $zc=n-xa-yb$, which gives an algorithm with complexity $O(n^2)$.
[problem:189B]
The key idea is to enumerate all the feasible center points. For each center point with coordinate $(x,y)$, it contributes $min(x, w-x)\times min(y, h-y)$ to the final result.
[problem:189C]
We adopt two pointers $p1, p2$, to point to the position of array $a$ and array $b$, respectively. Before moving on to the general algorithm, we start with a simple example to obtain some intuitive understanding.
At first, we try to put the value $a[i]=b[0]$ to position $0$. If $a[0]=b[0]$, we do nothing but try to put the value $a[i]=b[1]$ to position $1$. We continue this until the first $a[i]!=b[i]$ is met, and without loss of generality, we assume that $a[0]!=b[0]$. To accomplish this, we should take out all the elements in array $a[n]$ with indices larger th...
110.
Python3 for CP Hi!
I found python to be very easy to learn but I was not able to use it for cp before because of things like io speed which I did not know how to optimize earlier
these are some things I learnt which made it much easier for me to use python for cp
Fast Input:
~~~~~
import sys
inp = [a.strip() for a in sys.stdin.readlines()] #inp is an array of input lines.
~~~~~
Reading an array
~~~~~
arr = [int(x) for x in inp[i].split()] # use float(x) if dealing with decimal values
~~~~~
Making 2d matrix ( or any n dim matrix ) of 0s
~~~~~
mat = [[0 for i in range(n)] for j in range(n)]
~~~~~
Printing without the \n:
~~~~~
print("output",end="")
~~~~~
Sorting using key (see example below)
~~~~~
arr = [[3,4],[1,2],[5,3],[-1,4]]
def fkey(a):
return a[0]*a[1]
arr.sort(key=fkey)
~~~~~
Reversing array/string
~~~~~
arr=arr[::-1]
~~~~~
Note 1:
if arr is a list,
~~~~~
brr=arr
brr[0]*=2 # this also modifies arr and bot...
which made it much easier for me to use python for cp Fast Input: ~~~~~ import
sys inp
111.
My learning note on AGC061C based on Little09's (Simplified) Chinese Blog I admit that [AGC061C](https://atcoder.jp/contests/agc061/tasks/agc061_c) is too hard for me, and I don't even understand its [official editorial](https://atcoder.jp/contests/agc061/editorial/5695). Today I see a [Luogu blog](https://www.luogu.com.cn/blog/LJA001111/agc061c-first-come-first-serve) with a very genius and clear idea on this problem. I learned a lot from it, and I would like to share it to you now. The writer of this blog is possibly [user:little09,2023-02-15], but I am not quite sure.
**Part1: Problem Statement and Constraints**
There are $N$ customers named $1$, ..., $N$ visiting a shop. Customer $i$ arrives at time $A_i$ and leaves at time $B_i$
The queue order is first in first out, so $A_i$ and $B_i$ are both increasing. Additionally, all $A_i$ and $B_i$ are pairwise distinct.
At the entrance, there's a list of visitors to put their names in. Each customer will write down their name next in the list exactly once, either when they arrive or when they leave. ...
112.
What is the difference between std::multiset and std::priority_queue Hello codeforces community,
I've just encountered a (pretty obvious) data structure task in a mini-competition held by [user:kevinxiehk,2022-03-18].
Summary of the task:
n operations, 3 types.
1. Insert ID `x` on the right side
2. Remove from the left side
3. Sort by ID
1 <= n <= 5x10^5, 0 <= x <= 10^9
During the contest, I was able to solve the subtask n <= 2000 and got TLE for the last subtask (full solution). I used `multiset` and the code is as followed.
Time limit: 2s
~~~~~
// implementation I, using multiset
// 56/100, TLE
void solve () {
int n; cin >> n;
int op, x;
multiset<int> s;
queue<int> smallest;
for (int i = 1; i <= n; i++) { // O(n)
cin >> op;
if (op == 1) {
cin >> x;
s.insert(x); // O(n log n)
smallest.push(x);
}
else if (op == 2) {
if (!smallest.empty()) {
cout << smallest.front() << "\n";
auto pos = s.find(smallest.front()); // O(log n)
s.erase(pos); // amortized O(1)
smallest.p...
113.
[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...
polynomial time and is fast enough. This is what space-filling curve based
heuristic solutions help us
114.
Generic Input/Output Implementations [First Blog] Hi y'all,
Input/output is by and far the most frequently used concept in competitive programming, so I thought it might be a good idea to cover an optimization I developed in my first blog post.
We all know cin/cout, although convenient to type up, tend to be jarringly slow in the context of CP. This is because cin and cout are tied together and synced to stdio. To evade this, many rely on the classical C methods of I/O: scanf/printf.
For example, when dealing with an int $a$, they may write the following to read and write:
~~~~~
int a;
int main() {
scanf("%d", &a);
printf("%d\n", a);
}
~~~~~
But the syntax here is painful and definitely cannot be generalized to support a wider variety of types.
To that end, it is well-known that we can keep the convenience of cin/cout without having to sacrifice for performance insofar as we untie cin from cout and unsync from stdio. For instance, we may write the below:
~~~~~
int a;
int main() {
cin.t...
() { cin.tie(0)->sync_with_stdio(0); //make cin/cout as fast as scanf/printf
cin >> a; cout << a
115.
Microsoft Q# Coding Contest – Summer 2020 — Warmup: editorial The warmup round is over; I hope you enjoyed it and learned something new in the process!
Here are the explanations for the contest problems and pointers some extra resources that can help you learn more about the respective topics before the main contest. You should also be able to see the solutions of the contest participants and to solve the problems in practice mode.
## A: "Distinguishing Unitaries" problems
Here is the editorial for the problems: https://assets.codeforces.com/rounds/1356/A1-A5.pdf.
> These problems are [published in the Quantum Katas](https://github.com/microsoft/QuantumKatas/tree/master/DistinguishUnitaries), so that you can see the testing harness used for the problems and use it for testing your solutions in the main contest.
## B: Reversible computing
Reversible computing is a branch of quantum computing that deals with expressing classical computations in a reversible manner (i.e., so that the computation has a unique input state for each ou...
116.
Editorial for Hello 2023 ## [problem:1779A]
Author: [user:n0sk1ll,2022-12-27]
<spoiler summary="Hint">
What happens when $\texttt{L}$ appears after some $\texttt{R}$ in the string?
</spoiler>
<spoiler summary="Solution">
Suppose that there exists an index $i$ such that $s_i = \texttt{R}$ and $s_{i+1} = \texttt{L}$. Lamp $i$ illuminates trophies $i+1,i+2,\ldots n$ and lamp $i+1$ illuminates $1,2,\ldots i$. We can conclude that all trophies are illuminated if $\texttt{L}$ appears right after some $\texttt{R}$. So, strings $\texttt{LLRRLL}, \texttt{LRLRLR}, \texttt{RRRLLL}, \ldots$ do not require any operations to be performed on them, since they represent configurations of lamps in which all trophies are already illuminated.
Now, we consider the case when such $i$ does not exist and think about how we can use the operation **once**. Notice that if $\texttt{R}$ appears right after some $\texttt{L}$, an operation can be used to transform $\texttt{LR}$ into $\texttt{RL}$, and we have concluded before...
the lemma again and exclude unnecessary subsets. Implementing it properly
should befast enough. A
Tutorial of Hello 2023
117.
A question about the determinability of the best time complexity of a particular problem. I was recently doing some problems on two pointers when I saw some really clever ways to use two pointers on some problems which would otherwise seem impossible to solve faster than O(n^2) complexity. So, that's when I got this thought in my mind, how do we "know" that a particular complexity is the best possible for a particular problem and that there is not a better solution possible using some clever technique that we just haven't thought of yet. For example, let's say that there is some problem which could be solved in O(n^5) time. How do we know that there isn't any n^4 solution that we just haven't discovered yet. Can we just look at any problem and surely say that yes, it cannot have a solution which is better than this particular time complexity? I would be glad if anyone could provide some insight on this topic.
118.
STL Basics – lower_bound, upper_bound, BST, Set, Multiset, Map, Priority Queue # Advanced STL Structures — A Complete Guide
Hi everyone! In this lecture we'll go deeper into STL structures that are **must-know** for competitive programming.
---
## 1. Iterators & Vectors
Iterators are like pointers that let you navigate through containers.
```cpp
vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin(); // points to first element
auto end = v.end(); // points AFTER last element
sort(v.begin(), v.end()); // sort entire vector
v.end() - v.begin(); // size of vector
```
### Key Facts
* `v.begin()` → iterator to first element
* `v.end()` → iterator AFTER last element (not the last element itself!)
* `v.size()` = `v.end() - v.begin()`
### Important Trick
Count numbers in range `[l, r]` = `r - l + 1`.
This formula appears constantly in:
- Binary search problems
- Range queries
- Coordinate compression
**Example:**
```cpp
// How many integers from 5 to 10 inclusive?
int count = 10 - 5 + 1;...
119.
Codeforces Trainings Season 2 Episode 8: Editorial [Complete problemset + tests + original presentation of solutions.](http://www.bapc.eu/problemset.zip)
[Official scoreboard](http://bapc.eu/scoreboards/bapc/), [public contest scoreboard](http://www.bapc.eu/scoreboards/public/), [used for training elsewhere](http://www.cs.ubc.ca/~acm-web/practice/2014-10-25/scores.php).
Short hints first, more detailed solutions afterwards.
### A. Avoiding the Apocalypse
(difficulty: medium-hard, [code](http://ideone.com/JQOMyq))
Maxflow in a suitably selected graph. Ford-Fulkerson is sufficient.
<hr>
The vertices of our graph need to correspond to states that one person can be in when traversing the original road network; the number of people moving in a group is then represented by flow along edges. Therefore, the most natural choice is to use vertices corresponding to states (location, time).
The rules from the problem statement say that at most $c$ people can move along an edge $e=(u->v)$ in the original at any time. That me...
)$ using fast exponentiation and its respective $b_0$. We can add any multiple
of $F_{n-1}$ to $a_0
120.
Enigma 6.0 Editorial #### [Link for the contest](https://codeforces.me/contestInvitation/c39dfd8ae99ecec885e9aaa8aa8cb5ee6366c5df)
### A. Who is happy?
Run a loop from $i=0$ to $i=N-1$ and iterate through the string $S$, maintain two variables $countA$ and $countB$ initialised to $0$. Keep incrementing $countA$ whenever you encounter letter $A$ i.e. $S[i]==A$. Similarly keep incrementing $countB$ whenever you encounter letter $B$ i.e. $S[i]==B$. In the end just check if $countA > countB$, $countA < countB$ or $countA == countB$, and print $Anirban$, $Biswa$ or $Samay$ respectively.
Time Complexity: O( N ) for each test case
<spoiler summary="Code">
~~~~~
#include<bits/stdc++.h>
using namespace std;
int main()
{
int tc; cin>>tc;
while(tc--)
{
int n; cin>>n;
string s; cin>>s;
int a=0,b=0;
for(int i=0; i<n; i++)
{
if(s[i]=='A') a++;
if(s[i]=='B') b++;
}
if(a>b) cout<<"Anirban"<<endl;
...
rating. We can also further optimize this solution by first sorting and using a
pointer to mark
121.
Useless CP Information #1: Why DSU Runs in Inverse Ackermann Time Complexity _Originally written for my analysis of algorithms class. Shoutout to Prof Mikhail Atallah for being the GOAT_
The Tarjan proof is scary. This one is hopefully explained in a way us blues and purples can understand. Might turn this into a series if I think of more random useless information to talk about. Also if you are confused anywhere please ask :)
Amortized Analysis Primer
==================
We use the **potential method** to formally prove amortized time complexity. Here's how it works:
- You start with a potential of 0. It is never allowed to go negative. Think of this as your bank account of CPU cycles.
- You can increase your potential during cheap operations. Think of this as depositing CPU cycles into your bank account that you can use later.
- You can draw your potential during expensive operations, like withdrawing CPU cycles from your bank account.
For a concrete example, consider the `std::vector` that has to reallocate its internal array if it overflows...
$, one layer lower, $x+1$ times to $x$. As you might imagine, this grows very
fast. Each "layer" is
122.
Divide and conquer. Dynamic connectivity offline and DP optimization. Divide
and conquer by queries.
Divide and conquer. Dynamic connectivity offline and DP optimization. Divide and conquer by queries. Hello, Codeforces! I have wanted to write an educational blog for a long time, but I couldn't find a topic for it. And recently I remembered that Codeforces doesn't have a good blog on one of my favorite topics: the "divide and conquer" technique. So I want to talk about it. The outline will be something like this:
1) Divide and conquer. What this technique is and what it is for. Example.
2) Dynamic connectivity offline with divide and conquer. Divide and conquer dp optimization.
3) Let me tell you about a method I invented myself: divide and conquer by queries. In this case, we divide not only the array, but also the queries into groups.
So, here we go.
First, about what this technique is. The point is about the following: let's say we have an array. Then, if we know how to calculate the answer for two parts of it, and if we know how to get the answer for the whole array from the answers of two parts, we can apply the divide and conquer technique. Let me show you the si...
is much better to store a pointer to the current element we are considering.
If you write in C++, I
123.
Complete Topic List for Competitive Programming (Re-revised && Updated) Suggestions are welcome. BEFORE ENTERING INTO THE LIST, I HAVE A SUGGESTION FOR CODEFORCES. DARK THEME BUTTON AND CODE LINTING FEATURE FOR CODEFORCES. "PROBLEM OF THE DAY" ON THE RIGHT SIDE OF THE HOMEPAGE. NEW PROBLEMS ALERT PAGE. LET ME KNOW YOUR OPINION FRIENDS :)
#### Complete Roadmap to Competitive Programming ####
** IMPORTANT CONCEPTS: **
Basic Programming
Object Oriented Programming
Time && Space Complexity
Loops, Arrays, Math, Probability
Circular Arrays, Matrices, Strings
Permutations && Combinations
Bit Masking && Bit Manipulations
Recursion && Backtracking
Dynamic Programming
Prefix Sum, Precomputations
Square Root Decomposition
Sliding Window
Modular Arithmetic
Number Theory, Geometry
Greedy Approach, Bruteforce
Two Pointer Approach
Linked Lists, Stacks, Queues
Sets, Heaps && Priority Queues
Hashing, Trees and Graphs
Binary Search Trees, Search Trees
Tries, Segment Trees, Fenwick Trees
Minimum Spanning Trees, Suffix Trees
M...
Arithmetic Number Theory, Geometry Greedy Approach, Bruteforce Two Pointer
Approach Linked
124.
A2SV Contest #23 Editorial [Here](https://codeforces.me/contestInvitation/aa5538088b7a06cee3169aeed4c171ef954ce504) is the link to the contest. All problems are from Codeforces' problem set.
[A. Verifying Access Keys](https://codeforces.me/gym/625306/problem/A)
<spoiler summary="Solution">
To determine if each access key is **secure**, we need to validate it against **three specific rules**.
1. **Digits appear before letters:**
All digits (if present) must appear before any letters. This means the transition from digits to letters can happen **only once**, and once it does, **no digit should appear afterward**.
- For example, `"123abc"` is valid, but `"a1b2"` is not.
2. **Digits are non-decreasing:**
The digits must be in **non-decreasing order**. As we read through the digits from left to right, each digit must be greater than or equal to the previous one.
- For example, `"1125"` is valid, but `"132"` is not, because `3` comes before `2`, which violates the order.
3. **...
] word2 = words[i + 1] pointer = 0 while pointer < len(word1) and
125.
Codeforces Round 1061 (Div. 2) Editorial ### Thank you for participating !
Special Thanks to [user:hxu10,2025-10-24] for giving me the chance to write the editorial and for [user:maomao90,2025-10-24] for enhancing the editorial !.
Editorial of Problems E and F are written by hxu10, and the rest are written by me. I hope they're insightful and concise, please let me hear your opinion about it or any feedback in general 💙.
#### [problem:2156A]
<spoiler summary="Hints">
<spoiler summary="Hint 1">
Since $m_1 \le m_2$, the total number of slices Alice ate is always at least as much as the total number of slices Bob ate.
What's optimal construction ?
</spoiler>
<spoiler summary="Hint 2">
We want to try to minimize the difference between the total number of slices Alice ate and the total number of slices Bob ate.
</spoiler>
<spoiler summary="Hint 3">
The optimal construction is to let both $m_1$ and $m_2$ to be equals to one. The sequence of operations, denoted by $(m_1, m...
}}$ it's already fast to process them in order because of
$\mathcal{O}(\log_2(a))$ and it reduces $a
Tutorial of Codeforces Round 1061 (Div. 2)
126.
Unknown Language Round #4: editorial <p>So here goes an editorial for the round. For me Befunge is one of the languages in which it's much easier to write code than to read it (and debugging code written by someone else is a complete torture; that's why we don't have hacking in ULRs). That's why I'll post just the general idea of the solution and my own codes — the latter just to show that I can code in Befunge too.</p>
<h3>A. Hexagonal numbers</h3>
{{{&:2*1-*.@}}}
<p>A "consolation" problem, which requires only to understand the principles of working with stack. Read $n$, duplicate it, multiply the topmost copy by 2 and decrement the result. Now the stack contains two numbers $n$ and $2n - 1$; multiply them and print the result.</p>
[cut]
<h3>B. Gnikool Ssalg</h3>
{{{> ~ : 25*- #v_ $ >:#,_ @
^ <}}}
<p>Here the easiest solution is to use the main stack property — elements are popped in reverse order compared to the order in which they were pushed. You can break the solution i...
to add (initialized by reading input). If the latter is non-zero, the
instructionpointer goes into
Tutorial of Unknown Language Round 4
127.
I think I just did something crazy? Round 889 Question B This question confused me during the contest. I thought maybe if I go till $1e6$ I should be fine, but I got a TLE, no surprises. Then I optimized the code using two pointers, added in some memoization, and prime factors, and tried again with $1e6$, It failed no surprise. By this time I realized maybe if I tried the "normal" way till $1e4$ should work and I got accepted.
But "craziness" started after the contest when I tried to submit my optimized code with a limit of $1e4$, and to my surprise it passed and it was faster than the C++ submission! Curiously, I increased the limit to $1e5$ and it passed again but it was pretty close to a TLE.
Exhibit:
[submission:216349728]
I tried to explain what I have done, but if somebody could help me point out how this code could run even till $1e5$ I'd appreciate it.
Explained Code:
[submission:216355374]
Please excuse my English :}
128.
A2SV G6 — Round #5(Editorial) [Here](https://codeforces.me/contestInvitation/f8d5427c4604e7e8b06726d6ad836a273048c363) is the contest link.
### [A. Language Identifier](https://codeforces.me/gym/591928/problem/A)
<spoiler summary="Hint">
To determine the language of a sentence, you only need to check its last few characters. Since only four possible suffixes exist, a direct string comparison is the simplest and most efficient approach.
</spoiler>
<spoiler summary="Solution">
<p> The problem provides a straightforward method for identifying the language of a sentence based on its ending. Since the constraints guarantee that each sentence ends with one of the given suffixes, we can simply check the last characters of the string and classify the language accordingly.
To implement this, we observe the following rules:
<ul>
<li>If a sentence ends with "po", it is Filipino and the last letter is “o”.</li>
<li>If it ends with "desu" or "masu", it is Japanese and the last letter is “u”.</li>
<li>...
efficiently using a two-pointer (sliding window) approach in O($n$) time:
* Maintain a
129.
AlgoThugs 2026 — Editorial ### Contest announcement blog: [Link](https://codeforces.me/blog/entry/152857)
### [problem:669000A]
Author: [user:Krishnadev44,2026-04-15]
<spoiler summary="Hint 1">
We claim that the answer is always `YES`.
</spoiler>
<spoiler summary="Hint 2">
Let the direct path from vertex $u$ to vertex $v$ consist of $d$ edges. Since $u$ and $v$ are distinct, $d \ge 1$. Let the sequence of costs along these edges be $C = (c_1, c_2, \dots, c_d)$.
We claim that there always exists a contiguous subarray of $C$ whose sum is perfectly divisible by $d$.
</spoiler>
<spoiler summary="Solution">
Let $S$ denote the prefix sum array of $C$, where the $k$-th prefix sum is defined as:
$$S_k = \sum_{i=1}^{k} c_i \quad \text{for } 1 \le k \le d$$
Consider the values of these prefix sums modulo $d$. There are two cases:
* Case $1$: There exists an index $k$ such that $S_k \equiv 0 \pmod d$.
In this case, the sum of the prefix subarray $(c_1, c_2, \dots, c_k)$ is directly divisi...
empty array of size $n$ using a two-pointer approach (filling left and right
empty slots): * $4k + 1
130.
2025 ICPC Asia Manila Regional (Gym) Editorial [problem:106262A]
<spoiler summary="Hint">
There is only one way for the leftmost piece and the rightmost piece to refer to the same object.
</spoiler>
<spoiler summary="Solution">
If $n=0$, then Alice and Bob will not fight. Since they eat $2$ pieces at a time, that means $n=2, 4, 6, 8, 10, ...$ (i.e. the even numbers) will also have them not fight.
If $n=1$, then Alice and Bob will fight over that once piece. Since they eat $2$ pieces at a time, that means $n=3, 5, 7, 9, 11, ...$ (i.e. the odd numbers) will have them fight. Since an equal number of pieces are eaten from the left and the right, we know it is the center piece that remains (when $0$-indexed, this is at index $\lfloor n/2 \rfloor$).
So, the problem is just a parity check.
</spoiler>
[problem:106262B]
<spoiler summary="Hint">
For some letter, how many times does this letter occur in the substring of $t$ that begins at position $i$ and has some length $\mathrm{len}$?
You can answer this in $O(1...
to do coordinate compression, or make your segment tree implicit (i.e. pointer
based, and you only
Tutorial of 2025 ICPC Asia Manila Regional
131.
Codeforces Round #519 Editorial #### [1043A — Elections](http://codeforces.me/contest/1043/problem/A)
<spoiler summary="Tutorial">
We can observe that result cannot exceed $201$ — Awruk gets at least $101$ votes from one person and Elodreip cannot get more than $100$ votes from one person. So we can iterate over every possible integer from $1$ to $201$ and check if Awruk wins with $k$ set to this integer. We have to remember that $k$ — $a_i$ is always at least $0$, so we have to check this condition too. Complexity $O(n * M)$, where $M$ denotes maximum possible value of $a_i$. Try to solve it in $O(n)$.
</spoiler>
<spoiler summary="Solution">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int n;
int mx = 0, sum = 0;
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; ++i){
int a; scanf("%d", &a);
mx = max(mx, a);
sum += a;
}
sum *= 2;
sum += n;
sum /= n;
printf("%d", max(sum, mx));
return 0;
}
~~~~~
</spoiler>
Author: [user:FCB1234,201...
fast(int a, int b){ int ret = 1; while(b){ if(b & 1) ret = (1LL * ret * a)%MX; b
Tutorial of Codeforces Round 519 by Botan Investments
132.
CP101 2022 Thank you for participating in the contest! We hope you enjoy the problems.This is an editorial Blog written for the Contest CP101 2022. In order to solve the problems of the contest [click here](https://p.hck.re/PUVe).
Ritam learns to Dance
==================
<spoiler summary="Problem Statement">
Kuldeep is a member of UDC. Ritam wants to learn dance from Kuldeep. Kuldeep gives Ritam a sequence of steps. He has to perform all the substrings of the steps. But he faces a problem where the substring of the string is an even number. Find out the number of step sequences where he faces problems. The substrings can have leading zeros. You have to solve the problem for “t” test cases.
First line of input consists of “t” denoting the number of test cases. Following “t” lines consist of a string containing digits between 0 and 9.
You have to output one number denoting the number of substrings which are even.
### Constraints:
1 <= t <= 1e5
1 <= length of string <= 1e5
...
use (%2) now add the LSB to score of the player. We will maintain a pointer
which tells whether the
133.
Editorial for Codeforces Beta Round #93 <p><b>div2 A.</b> In this problem you should find length of polyline, multiply it by $k/50$ and output that you will recieve. Length of polyline is sum of lengths of its segments. You can calculate length of every segment using Pythagorean theorem: $d(A,B)=\sqrt{ (x_A - x_B)^2 + (y_A - y_B)^2 }$.<br />[cut]<br /><b>div2 B.</b> Idea of this problem was offered by [[user:RAD,2011-11-10]]. It was the last problem in the problemset and I had no any easy idea:) I thank him for it.<br /><br />Here you should calculate an array $cnt[100]$. $i$-th element of it stores number of sticks whose lengths equal $i$. Now you should calculate number of pairs of sticks of equal lengths. This number is $k = \sum_{i=1}^{100} [cnt[a]/2]$, where $[x]$ is floor of $x$. For every frame you need 2 if such pairs and <span class="short_text" lang="en"><span class="hps">you can choose it in any order</span></span>. Therefore the answer will be $z = [k/2]$.<br /><br /><b>div2 С. div1 A.</b> At the first you should...
Tutorial of Codeforces Beta Round 93 (Div. 2 Only)
134.
(Intermediate Part) — Bits That Changed My CP Thinking ! This is the **Part-2** of my Bitwise Operations Blog. In this part, I focused more on intermediate-level bitwise tricks, Common CP Patterns and a few slightly advanced techniques that appear frequently in contest. — [**Part-1 — Click Here**](https://codeforces.me/blog/entry/153600)
I tried to explain the intuition and thinking process behind each trick as clearly and simple as possible.
And as always, Heartfelt thanks to `Raha Ahmed` for her endless encouragement, strongest support and constant belief in me !
---
# Core Concepts You Must Understand First :-
---
Intermediate level Bitwise Problems in CP rarely ask you to just "check" or "set" a bit. Instead, they require you to use the Mathematical Properties of bits to optimize your code. Before we jump into the 8 Master Pattern, you need to firmly understand these 5 core concepts.
If you understand these the upcoming patterns will feels like magic !
---
<spoiler summary="Core Explan...
fast $O(30 \times N)$ solutions. We stop looking at the **Whole Number** and
start looking at
135.
How to solve "Electric Charges" binary search problem [problem:623C]
Hi all! I finally managed to code the solution of this tricky problem, I needed to read the editorial (very hard to follow) and make lot of hard work to get the trick of how to do it so now I want to share my conclusion of how it can be solved properly.
Problem Statement
=================
It says you have a **list of points** with X and Y coordinates. However you need to define whether you will draw each one using its X coordinate or its Y. (and the other will be zero). Formally speaking you can draw each one on the (X,0) or in the (0,Y). The objective is to get the minimum **diameter** of the set of points, defined as the **longest distance between any of them**
Worst Solution
==================
We need to note the worst solution would be to check both coordinates for each point (two possibility for each one. This would delay around **2^N * (time to get longest distance in each chance**). As N is 100000 is impossible doing something like that.
First key...
(MAXY and MINY) we can easy and fast calculate the diameter for each chance.
However as N=100000
136.
A2SV G6 — Round #9 | Adwa Special [Here](https://codeforces.me/contestInvitation/9699a0adea6fecce903c43978811e68dee0be3aa) is the contest link.
#### [A. Escaping Prison](https://codeforces.me/gym/601269/problem/A)
Idea and preparation: [user:nahubn1123,2025-04-06]
<spoiler summary = "Solution">
Since we can only utilize either the length or width of all the blankets, the best choice for creating the longest possible rope is to first utilize all the blankets and use the longest side (length or width) of each blanket.
- Time Complexity: $O(n)$
- Space Complexity: $O(1)$
</spoiler>
<spoiler summary="Code">
```python3
import sys
input = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
n, h = map(int, input().split())
rope = 0
for i in range(n):
l, w = map(int, input().split())
rope += max(l, w)
if rope >= h:
print('YES')
else:
print('NO')
```
</spoiler>
#### [B. Empress Taytu and The Water So...
there a fast way to compute it? If we had every sorted
137.
Codeforces Round #100: problem analysis <p style="text-align: justify;"><a href="http://codeforces.me/contest/140/problem/A">Problem A. New Year Table</a></p><p style="text-align: justify;">The plates must touch the edge of the table, so their centers must lie on the circle with radius R - r (see the figure).</p><div><div style="text-align: center;"><img src="http://saveimg.ru/thumbnails/04-01-12/1853f5c6ef024fe851a0e0e55a538fba.bmp" /><br /></div><div style="text-align: justify;">In case the plates have the largest radius possible for the given table, their centers are situated in the vertices of the regular polygon (n-gon) inscribed in this circle. The problem is to find the length of the side of the inscribed regular n-gon and to compare it with 2r. The formula for the length of the side is $a = 2 (R - r) \sin (\pi / n)$, it can be easily deduced. For that you should consider the right triangle (the green one in the figure).</div></div><div style="text-align: justify;"><br /></div><div style="text-align: justify;">In impl...
points $(2 x_c - x_i, 2 y_c - y_i)$ in the order of sorting moving a pointer
in the sorted array $(x_i
Tutorial of Codeforces Round 100
138.
mBIT 2025 Editorial Thank you to everyone who competed in mBIT 2025! It was a record breaking year for us with 84 in-person participants and 135 online participants. We hoped you guys enjoyed it as much as we did.
We tried hard to make the problems fun and interesting for as wide of a skill gap as possible. In fact, this year's competition had an in-person team of middle schoolers that was unfamiliar with for loops, and an online team with all three participants in the top 15 in the world in codeforces. We are glad to contribute to all niches of the computer science community: beginner and advanced, local and global. Thank you all for your enthusiasm.
Congratulations to the winners:
**Online Advanced:**
- 1st place — HoMaMaOvo — Masaki Nishimoto, Riku Kawasaki, Yui Hosaka
- 2nd place — mathforcesbox — Brian Xue, Bing-Dong Liu, Alex Chen
- 3rd place — bluepuppygreenturtle — Rain Jiang, Kai Jiang
**Online Intermediate:**
- 1st place — NULP Lega...
. Use two pointers. The first pointer loops through tools as
139.
Manthan, Codefest'19 Editorial ### [1208A — XORinacci](https://codeforces.me/contest/1208/problem/A)
The sequence is $a$, $b$, $a\oplus b$, $a$, $b$, $a\oplus b$ $\cdots$
Since, the sequence has a period of $3$, $f[i] = f[i \mod 3]$.
<br>
<spoiler summary="Code">
```
#include<bits/stdc++.h>
using namespace std;
int main()
{
int test,a,b,n;
cin>>test;
while(test--){
cin>>a>>b>>n;
switch (n%3){
case 0:
cout<<a<<endl;
break;
case 1:
cout<<b<<endl;
break;
default:
cout<<(a^b)<<endl;
}
}
return 0;
}
```
</spoiler>
### [1208B — Uniqueness](https://codeforces.me/contest/1208/problem/B)
After removing a sub-segment, a prefix and a suffix remain, possibly of length $0$.
Let us fix the prefix which does not contain any duplicate elements and find the maximum suffix we can get without repeating the elements. We can use map/set ...
SOS-DP(fast). Once we process the positions for every $x$, let us fix some
$a[i]$ and iterate over
140.
Codeforces Round #385 Editorial Short solutions:
- Div2A: How many times do we need to do a cyclic shift to consider all possible ones? Afterwards, what data structure allows us to easily check number of distinct elements?
- Div2B: Imagine the process in reverse. What types of identical shapes can I get if I cut a rectangle into two pieces? Remember, pieces cannot be rotated or flipped.
- Div2C / Div1A: How do we handle components with special nodes? What do we do with the ones without special nodes?
- Div2D / Div1B: We don't get many questions, so is there a way to "parallelize" questions? Another approach, can we split up the condition i != j somehow using bits?
- Div2E / Div1C: First, somehow reduce it so r_i,b_i <= n. Now, we can bound the excess tokens by a small number, so we can do bitmask dp from here.
- Div1D: The optimal circle must touch a blue point. Now, either consider the inversion, or do a binary search
- Div1E: What makes a list good? How fast can we do this check, and how many times do we n...
binary search - Div1E: What makes a list good? How fast can we do this check,
and how many times do we
Tutorial of Codeforces Round 385 (Div. 1)
Tutorial of Codeforces Round 385 (Div. 2)
141.
A2SV G7 Contest Round #9 Editorial [Here](https://codeforces.me/contests/684794) is the contest link.
#### [A. Escaping Prison](https://codeforces.me/gym/684794/problem/A)
Idea and preparation: [user:nahubn1123,2025-04-06]
<spoiler summary = "Solution">
Since we can only utilize either the length or width of all the blankets, the best choice for creating the longest possible rope is to first utilize all the blankets and use the longest side (length or width) of each blanket.
- Time Complexity: $O(n)$
- Space Complexity: $O(1)$
</spoiler>
<spoiler summary="Code">
```python3
import sys
input = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
n, h = map(int, input().split())
rope = 0
for i in range(n):
l, w = map(int, input().split())
rope += max(l, w)
if rope >= h:
print('YES')
else:
print('NO')
```
</spoiler>
#### [B. Empress Taytu and The Water Source](https://codeforces.me/gym/684794/pro...
= "Hint 2"> Do we need every sorted prefix? and is there a fast way to compute
it?
142.
Binary Search or Super Binary Search Hello,
I am Ashutosh(Uzumaki_75). This is my first contribution.I came across this information a few days ago and found it worth sharing.I learned from it. Hope the same for you too :)
So, you have heard of how binary search is used to find the position of an element in a sorted array. That's not the end of the picture. Binary search is a lot more powerful than that. In this article, you will learn some non trivial applications of binary search.
Problem Statement: You are given an array a[1 ... N]. There is some k for which, a[i] = 0 for all i in the range 1 <= i <= k, and a[i] = 1 for all i in the range k + 1 <= i <= N. We want to find this position k which splits the groups of 0s and 1s
Consider this example first:
As you can see, we have a[1 .. 5] = 0 and a[6 .. 13] = 1. Our aim is to find the k (here k = 5) at which the split occurs.
A trivial algorithm would be to iterate from right to left and return the value of k at which 0 is seen for the first time. Below is an i...
143.
OMORI CONTEST Editorial Thank you for joining the [contest](https://codeforces.me/contestInvitation/fc8da6d6845e77adc452e754d3d84c1086148c59) 😊.
<spoiler summary="How did you find the contest?">
- Great
- Good
- Average
- Bad
- Trash
</spoiler>
<spoiler summary="Which problem is your favourite?">
- SUNNY
- AUBREY
- HERO
- KEL
- MARI
- BASIL
- OMORI
</spoiler>
#### [A. SUNNY](https://codeforces.me/gym/551481/problem/A)
<spoiler summary="Editorial">
<spoiler summary="Problem Tags">
`bijections` `dynamic-programming`
</spoiler>
<spoiler summary="Hint 1">
Try to find a bijection, meaning try to find another problem such that its solution is equivalent to the original problem but is easier to solve.
</spoiler>
<spoiler summary="Hint 2">
Try to notice what happens to the difference array of $a$ when Sunny plays a note.
</sp...
suffix $\text{LCM}$ each multiplied by its left pointer, as we initially put
value $i$ at leaf $i
Tutorial of OMORI CONTEST
144.
Editorial [GYM] 2018 BACS Contest replay [problem:101864A]
Setter: [user:ISwearItIsMyLastContest,2018-08-10]
Alternate Writer: [user:prophet_ov_darkness,2018-08-10], [user:s_h_shahin,2018-08-10]
<spoiler summary="Editorial">
This problem actually reflect the [josephus problem](https://en.wikipedia.org/wiki/Josephus_problem).
The main part of this problem is to find Number of possible Y such that **josephus(Y,2) = X** .
After finding this rest part is obvious calculation.
Let’s see first few values of josephus(i,2): 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15
We can see that there is a nice pattern here. **josephus(n,2)** is an increasing odd sequence that restarts with **josephus(n,2) = 1** whenever the index **n** is a power of 2.
First we will find minimum value of p such that **josephus(p,2) = X**. we can do this in **O(log n)** , because for every **q>0** **josephus(2^q-1,2) = 2q^-1** and **josephus(2^q,2) = 1**. So we can run loop through q >= 0 and find highest value of **q** such that **josephus(2...
> // for linux stack memory increase //#define gc getchar_unlocked // for linux
fast io //#define
Tutorial of 2018 BACS Contest Replay
145.
Codeforces Round 1085 (Div. 1 + Div. 2) Editorial <center>
<table class="tex-tabular bordertable"
style="border-left: none; border-right: none; border-top: 1px solid; border-bottom: 1px solid; border-collapse: collapse;">
<tbody>
<tr>
<td class="tex-tabular-text-align-center"
style="border-left: none; border-right: none; border-top: none; border-bottom: none;">
<span class="tex-font-size-small">
<span class="tex-font-style-it">
<a href="https://www.youtube.com/watch?v=HCYKLnT0UNU">Trophy Presentations — Asuka Ota, Ryo Nagamatsu, Mario Kart Wii</a>
</span>
</span>
</td>
</tr>
</tbody>
</table>
</center>
**UPD 1:** added hints, problem credits, more specific acknowledgements and some remarks. Implementations are on the way, sorry for making y'all wait!
**UPD 2:** Implementations are finally here.
[problem:2207A]
Author: [user:awang11,2026-03-09]
Preparers: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09]
Anal...
Tutorial of Codeforces Round 1085 (Div. 1 + Div. 2)
146.
CSES String Section Editorial I've seen CF tutorials for many other sections of CSES but didn't see one for strings, so I thought of writing one. Constructive criticism (or just regular criticism) is always welcome!
Note that there are many ways to do a problem. For instance, linear time string searching can be done with hashing, KMP, Z-Algorithm, Aho-Corasick Automaton, etc. . I used the way that was most intuitive for me, but there might exist other ways that have shorter code.
**1. Word Combinations**
<spoiler summary="Solution">
This problem reduces to knapsack if there exists a way to quickly match multiple strings. Precomputing the hashes is too slow ($\mathcal{O}(nk)$), so a faster method is needed. Aho-Corasick automaton suffices.
</spoiler>
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
const int MOD = 1e9 + 7;
string S;
int K, I = 1, DP[5005];
vector<int> adj[500005];
struct node {
int fail, ch[26] = {};
...
in its fail pointer tree. However, we can lazily process these visits by
marking the number of times
147.
SEATST 2026 Experience + Day 1 editorial Introduction
------------------
This last weekend, I took part in SEATST (Southeast Asia Team Selection Test) 2026. A few people (namely [user:YSH2020,2026-05-26] and [user:Tyx2019,2026-05-26]) have posted blogs on the contest.
About SEATST
------------------
SEATST is a IOI format (2 days, 3 problems in 5 hours on each day) contest made in 2025 that "replaced APIO as a crucial component of IOI selection in Singapore." (this statement is directly quoted from the SEATST website found [here](https://seatst.github.io)).
Looking at my APIO scores for these 2 years and my SEATST scores, I believe I am one of the largest beneficiaries for the shift away from APIO towards SEATST. Here are my scores:
- APIO 2025: 87/300, 10th in SG
- SEATST 2025: 380/600, 3rd in SG
- APIO 2026: 13.5/300, 21st in SG (I know my strategy was kinda screwed but whatever)
- SEATST 2026: 419/600, 4th in SG
My experience this year
------------------
I had _quite_ an interesting experience i...
, there will be only $O(N\log W)$ edges to check for in the MST. This should be
fast enough. To pull
148.
Epiphany 13.0 — Editorial ###[Epiphany 13.0](https://codeforces.me/gym/494905)
**A: Gifts**
------------------------------
[user:jaineshmachhi,2023-12-27]
<spoiler summary="Tutorial">
###[Epiphany 13.0 A — Gifts](https://codeforces.me/gym/494905/problem/A)
The minimum number of operations required to sort a list of $n$ gifts is $n−x$, where $x$ is the length of the longest sorted suffix.
**Proof:**
Let $k$ be the minimum number of steps required to sort the gifts.
Observe that if $k$ steps are optimal, the first $k$ gifts must be moved, implying that the remaining $n-k$ gifts were already sorted in ascending order.
Consider the $n-k$ sorted gifts at the end.
We can iteratively insert the unsorted gifts into this suffix to achieve complete sorting:
Pick the first unsorted gift and place it in its correct position within the sorted suffix, maintaining the sorted order.
Repeat this process for the remaining $k−1$ unsorted gifts. This takes $k$ operations.
</spoiler>
<spoiler summ...
() { // Fast I/O optimization ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, m
149.
Codeforces Round #940 and CodeCraft-23 (Div. 2) Editorial [problem:1957A]
==================
**Idea:** [user:keyurchd_11,2024-04-21]
**Problem Setting:** [user:shakr,2024-04-21] [user:lezirtin,2024-04-21]
**Editorial**: [user:shakr,2024-04-21] [user:TheRaja,2024-04-21]
There were a few solutions which passes pre-tests with the assumption that $a_i \leq n$. We apologize for the pre-tests on A not including this case.
<spoiler summary="Hint 1">
To create the most polygons, you should use as few sticks as possible per polygon. What polygon has the least number of sides?
</spoiler>
<spoiler summary="Solution">
[tutorial:1957A]
</spoiler>
<spoiler summary="Rate this problem">
-
Great Problem
-
Ok Problem
-
Bad Problem
-
Didn't solve
</spoiler>
<spoiler summary="C++ Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vector<int> a(101, 0);...
nice thing about this construction is that we can compute rolling hashes using
this ideafast. To
Tutorial of Codeforces Round 940 (Div. 2) and CodeCraft-23
150.
Help in EDU problem HELLO every one
==================
I was recently solving this [problem](https://codeforces.me/edu/course/2/lesson/5/4/practice/contest/280801/problem/F) using sparse segment trees and I got WA in TC3, so can you help me to know where is the issue in my code .
Thanks in advance .
this is my code :
~~~~~
/** * * * * * * * * * * * * * **\
* *
* Author: Haidara Nassour *
* Coded in: YYYY\M\D HH:MM:SS *
* Lang: C++ *
* *
\** * * * * * * * * * * * * * **/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define itn int
#define rep(i,x,n) for(int i=(x);i<(n);i++)
#define FOR(i,n) rep(i,0,n)
#define per(i,x,n) for(int i=(x);i>(n);i--)
#define ROF(i,x) for(int i=x;i>=0;i--)
#define v(i) vector< i >
#define p(i,j) pair< i , j >
#define p...
/assoc_container.hpp> #include #define fast ios_base::sync_with_stdio
151.
Topics Problems Good Day to you!
While a lot of us, when he begins to start competitive programming he found difficult to found problems on some topics in the beginning to practice of it, and same thing for a lot of ICPC Communites that they have started.
These are some topic not advanced and videos, problems and articles on them.
<br>
<spoiler summary="Prefix Sum & Frequency Array">
[Wonderful Coloring](https://codeforces.me/contest/1551/problem/B1)
[Do Not Be Distracted](https://codeforces.me/contest/1520/problem/A)
[Letter](https://codeforces.me/problemset/problem/43/B)
[Pangram](https://codeforces.me/problemset/problem/520/A)
[Andryusha and Socks](https://codeforces.me/contest/782/problem/A)
[Count Numbers](https://codeforces.me/group/c3FDl9EUi9/contest/262795/problem/A)
[Count Characters](https://codeforces.me/group/c3FDl9EUi9/contest/262795/problem/B)
[Range Sum Query](https://codeforces.me/group/c3FDl9EUi9/contest/262795/problem/E)
[Count a's](https...
Right](https://codeforces.me/edu/course/2/lesson/6/1/practice/contest/283911/problem/C)
[Fast Search
152.
Wharton was elected Finals MVP over the 76ers win, Wharton was elected Finals MVP, Trail Blazers to a perfect fairy tale Writing a period ending.When "I never listen to the players talk about branch 76 finals in 1977," Ramsey recalled that happened to say, "I just heard them far too difficult for most people to believe that we are not even wins four games away from the championship in their hands. "Recasting brilliant pioneerAfter a brilliant 1977, du<a href="http://www.maxsalesupras.com/nike-air-max-95-dyn-fw-c-26.html">nike air max 95 dyn fw cheap</a>
e to injuries and other reasons the Blazers could not board the top of the league longer, but they have missed several close distance championship. This season, the Blazers played impressive basketball players play a role pillar of the team use to create a shooting opportunity pass and movement, to reproduce the Ramsay era art style."This is a very good team, everyone has a clear division of labor, are able to play their role," Ramsey evaluation now Zhezhi pioneers...
the effectiveness of Gao Hongbo career longest team is the Yankees, but after
he picked up thepointer
153.
Global Round 20 Editorial Hope that everyone enjoyed the round. Feel free to ask questions in the comments if you do not understand any part of the editorial
[problem:1672A]
Author: [user:errorgorn,2022-04-23]
<spoiler summary="Hints">
<spoiler summary="Hint 1">
No matter what move each player does, the result of the game will **always** be the same.
</spoiler>
<spoiler summary="Hint 2">
Count the number of moves.
</spoiler>
</spoiler>
<spoiler summary="Tutorial">
Let us consider the ending state of the game. It turns out that at the ending state, we will only have logs of $1$ meter. Otherwise, players can make a move.
Now, at the ending state of the game, we will have $\sum\limits_{k=1}^n a_k$ logs. And each move we increase the number of logs by exactly $1$. Since we started with $n$ logs, there has been exactly $(\sum\limits_{k=1}^n a_k) - n$ turns.
Alternatively, a log of length $a_k$ will be cut $a_k-1$ times, so there will be $\sum\limits_{k=1}^n (a_k-1)$ turns.
If the...
some elements in $a$ towards the left. Using this idea, we can use the
following greedy two-pointer
Tutorial of Codeforces Global Round 20
154.
Editorial: XIII UnB Contest Mirror We hope everyone enjoyed the problems of [contest:106159]! This editorial contains the description of the solutions and their implementation. Feel free to discuss them in the comments!
#### Problem A
- Author: [user:PedroPacoca,2025-11-05]
- Coauthor: [user:duduFreire,2025-11-05]
<spoiler summary="Solution">
In this problem, we want to count the number of strings of length $n$ that have at least one occurrence of the given substring. To do this, we will use the Knuth-Morris-Pratt (KMP) algorithm and the automaton constructed from it, with a complexity of $O(m)$.
If $n$ were small, we could solve this problem using dynamic programming, calculating, for each $1 \leq i \leq n$, how many ways we can reach state $0 \leq j \leq m$ of the automaton (representing a string with the last $j$ characters equal to the first $j$ of $s$). This solution has $n \cdot m$ states with transitions of the size of the alphabet, resulting in a time complexity of $O(26 \cdot n \cdot m)$, which is...
^{n+1}$ using the fast exponentiation algorithm with matrix multiplication,
resulting in a final
Tutorial of XIII UnB Contest Mirror
155.
Editorial: OPC Good Bye Thank you for taking part in $\textbf{OPC Goodbye 2025}$.
This editorial walks through the core ideas and solution strategies behind each problem.
We hope it helps you learn something new and refine your approach to competitive programming.
If you have any reviews please put them in this [Google Form](https://docs.google.com/forms/d/e/1FAIpQLSeguT9leXrI3tyrmjwhXSfqj4LVF16zE5AIzKx-bcLHJclDRQ/viewform?usp=sharing&ouid=115085258461331858898).
Contest Link: [Link](https://codeforces.me/group/hUywLYmr80/contest/660904)
### [A. Make It Organised](https://codeforces.me/group/hUywLYmr80/contest/660904/problem/A)
<spoiler summary="Hint 1">
For each position, think: *how many times do I divide this number by 2 until it becomes the parity I need (even/odd)?* If it never reaches that parity, this pattern is impossible.
</spoiler>
<spoiler summary="Solution">
We observe that there are only two possible valid arrangements of parities in the final array:
even, odd, ev...
arrive after $x$ moves? Try to come up with a fast approach.
156.
Daily Diary (Competitive Coding in Summers) I realised that there is only one way improve one's skill, and that is through practice. So I decided to practice more topics and more problems on codeforces and different judges. This is simply a daily record for what I did through my vacation.
I also want to tell you about **stopstalk.com** . It is a good site to make and keep you daily coding record.
##**16 MAY 2017**
##### **Problems Solved** -
###### 1. http://codeforces.me/problemset/problem/535/D
This was a simple problem and it used Z function for prefix length calculation
###### **solution link** — http://codeforces.me/contest/535/submission/27152004
###### 2. http://codeforces.me/problemset/problem/551/B
Although the problem was simple, I had some trouble in understanding the language of the problem. It took time more than required.
###### **solution link** — http://codeforces.me/contest/551/submission/27160921
<br>
##### **Participated Contest** -
I participated in a v...
= "Hint"> The idea is to use two pointer and then keep updating the answer on
the go. ###### solution
157.
Editorial: VII UnBalloon Contest We hope everyone enjoyed the problems of [contest:106523]! This editorial contains the description of the solutions and their implementation. Feel free to discuss them in the comments!
#### Problem A
- Idea: [user:lucassala,2026-05-17]
- Preparation: [user:lucassala,2026-05-17]
<spoiler summary="Solution">
This is a classic problem where we can solve the queries offline. First, we receive all the queries, calculate the response for each node, and then respond. To calculate the response for each node, we will perform a DFS starting at vertex $1$ and create a map where we maintain the frequency of each color along the path from the root to the current node in the DFS. When we enter a new vertex, we add $1$ to the frequency of the current vertex's color in the map, and when we leave that node, we subtract $1$ from that color's frequency. Furthermore, we must ensure that all colors in the map have a positive frequency, removing any colors that reach a frequency of $0$ from the map...
1000$, this is fast enough. ```c++ #include
Tutorial of VII UnBalloon Contest Mirror
158.
A2SV Contest #25 Editorial [Here](https://codeforces.me/contestInvitation/89b9e7a75935f3ce18b8492441c60a79516d3719) is the link to the contest. All problems are from Codeforces' problem set
[A. Melody Perfection](https://codeforces.me/gym/628023/problem/A)
<spoiler summary="Solution">
To determine whether a melody is perfect, we check each pair of consecutive notes in the sequence. For each pair $a_i, a_{i+1}$, we calculate the interval as $|a_i - a_{i+1}|$. We then verify whether this interval is one of the allowed values, 5 or 7. If all consecutive intervals satisfy this condition, the melody is perfect and the answer is "YES". Otherwise, if any interval is not 5 or 7, the melody is not perfect and the answer is "NO".
This method ensures that every adjacent pair is validated exactly once, giving a time complexity of $O(n)$ and a space complexity of $O(1)$.
</spoiler>
<spoiler summary="Code">
```python
n = int(input())
notes = list(map(int, input().split()))
perfect = True
for i in ra...
** on an array. It is extremely useful when you need **fast queries on
subarrays**, such as sum
159.
Everything About Dynamic Programming **I decided to gather some good material on the web related to DP and found some good explanation by svg on topcoder forums..Hence wrote this blog.Will format it when i get time.**
**Problem:**
About 25% of all SRM problems have the "Dynamic Programming" category tag. The DP problems are popular among problemsetters because each DP problem is original in some sense and you have to think hard to invent the solution for it. Since dynamic programming is so popular, it is perhaps the most important method to master in algorithm competitions.
The easiest way to learn the DP principle is by examples. The current recipe contains a few DP examples, but unexperienced reader is advised to refer to other DP tutorials to make the understanding easier. You can find a lot of DP examples and explanations in an excellent tutorial Dynamic Programming: From novice to advanced by Dumitru. The purpose ...
solve this problem by DP to show how DP is accelerated by fast matrix
exponentiation. All the cycles
160.
CSES — Sliding Window Editorial Some of the most powerful techniques are also the simplest yet identifying when and how to apply them effectively can be challenging. Sliding window is one such method. Sliding window helps solve problems involving sequences, subarrays, or continuous segments by efficiently tracking changes as the window moves forward.
While tackling the CSES Sliding window problems, I noticed that many seemingly complex tasks like tracking the sum of elements in a dynamic segment, finding a subarray's minimum or maximum, or counting distinct elements can be simplified and optimized with this technique. Initially, one might consider brute-force methods iterating over every possible subarray or recomputing values from scratch. However, the core idea behind sliding window is smartly updating the state of the window rather than recalculating everything each time.
In my experience, the primary challenge while solving these problems came down to accurately managing the data structures supporting the w...
index). To solve this efficiently, we need a data structure that allows fast
insertion, deletion, and
161.
National Competitive Programming Challenge — Editorial Here is the link to the contest: [Link](https://codeforces.me/contestInvitation/6071a436743e70518e953453aadcf924bca069aa)
### [A. The Blacksmith](https://codeforces.me/gym/656191/problem/A)
<spoiler summary="Credits">
- **Problem Idea**: [user:eulmelk,2025-12-12]
- **Problem Setter**: [user:eulmelk,2025-12-12]
</spoiler>
<spoiler summary="Rate the Problem">
- **How good is this problem?**
- Very Good
- Good
- Bad
- Very Bad
- **How hard is this problem?**
- Very Easy
- Easy
- Hard
- Very Hard
</spoiler>
#### Approach 1
<spoiler summary="Tutorial">
**Step 1**<br>
$n \le 500$, so the total number of pairs is at most $\frac{n(n-1)}{2} = \frac{500 \cdot 499}{2} = 124750$. This is easily manageable within time limits.
**Step 2**<br>
By checking every possible pair, we never miss any valid combination. Therefore, keeping the maximum among all va...
162.
网络流详解 Thanks I_am_the_Lord_Voldemort.
Author: https://codeforces.me/profile/Libingyue20111
This is the English version of the article.
[https://www.luogu.com.cn/article/kw6klidj](https://www.luogu.com.cn/article/kw6klidj)
A few days ago, Libingyue2011 came across [this problem](https://www.luogu.com.cn/problem/P1004).
Wow, two paths, and you can't collect the same point multiple times.
So the novice Libingyue2011 didn't want to write dynamic programming (DP) anymore, as he found it too difficult.
Then he learned from a blue-covered book that this problem could be solved using cost flow, and even the enhanced version could be solved along with it.
So he solved it.
Therefore, this is actually a detailed explanation of network flow.
## Network Flow 1
### Some Knowledge about Networks and Flows
A network is a directed graph where each edge has a weight $c$.
In a network, there are two special nodes called the source ($S$) and the sink ($T$).
$c(x,y)$ ...
163.
Codeforces Global Round 31 Salam !
Here is the editorial for [Codeforces Global Round 31](https://codeforces.me/contest/2180). We hope you find these solutions helpful. We also have prepared a special editorial with step by step hint, examples, tables, and walkthroughs which is available [here](https://repovive.com/editorial/codeforces-global-round-31).
#### [problem:2180A]
**Idea:** [user:Amirrzwm,2025-12-18], [user:MohammadParsaElahimanesh,2025-12-18] — **Preparation:** [user:MohammadParsaElahimanesh,2025-12-18]
<spoiler summary="Solution">
<spoiler summary="Simple Simulation (Brute force)">
Since constraints are small, we can simulate the spins directly:
- Start from section $a$.
- Move the pointer by adding $b$ modulo $l$ repeatedly.
- Stop when we return to a previously visited section.
- Among all visited sections, select the section with the highest prize.
It runs in $\mathcal{O}(l)$ as we mark each section at most once.
</spoiler>
<spoiler summary="Mathematical Solutio...
the pointer by adding $b$ modulo $l$ repeatedly. - Stop when we return to a
previously visited
Tutorial of Codeforces Global Round 31 (Div. 1 + Div. 2)
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/11/2026 05:50:47 (k3).
Desktop version, switch to mobile version.
Supported by
