Hull Trick](https://codeforces.me/blog/entry/51684) - [A range query convex
hull problem](https, ) - [Some method for solving RMQ](https://codeforces.me/blog/entry/48994) -
[Rangequery data, ://codeforces.com/blog/entry/51684) - [A range query convex hull
problem](https://codeforces.me/blog/entry, Query Based Rerooting Technique](https://codeforces.me/blog/entry/76150) -
[Almost-LCA in Tree\n
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3857 |
| 2 | jiangly | 3810 |
| 3 | maroonrk | 3534 |
| 4 | tourist | 3528 |
| 5 | Kevin114514 | 3510 |
| 6 | turmax | 3411 |
| 7 | Um_nik | 3387 |
| 8 | Radewoosh | 3367 |
| 9 | heuristica | 3322 |
| 10 | strapple | 3317 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | maspy | 150 |
| 3 | Um_nik | 145 |
| 4 | Errichto | 139 |
| 5 | adamant | 136 |
| 6 | maroonrk | 134 |
| 7 | DNR | 133 |
| 8 | nik_exists | 132 |
| 9 | AmShZ | 130 |
| 10 | Dominater069 | 129 |
→ 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.
I compiled a list of almost all useful blogs ever published on Codeforces [update: till 09.06.2021] <h3 style="color:red">If there are any blogs that I have missed, please tell in the comment section. Thank you.</h3>
# Mathematics Stuff
- [Number Theory in Competitive Programming [Tutorial]](https://codeforces.me/blog/entry/46620)
- [Number of points on Convex hull with lattice points](https://codeforces.me/blog/entry/62183)
- [FFT, big modulos, precision errors.](https://codeforces.me/blog/entry/48465)
- [Number of ways between two vertices](https://codeforces.me/blog/entry/19078)
- [Mathematics For Competitive Programming](https://codeforces.me/blog/entry/76938)
- [FFT and NTT](https://codeforces.me/blog/entry/19862)
- [Burnside Lemma](https://codeforces.me/blog/entry/51272)
- [Number of positive integral solutions of equation 1/x+1/y=1/n!](https://codeforces.me/blog/entry/76836)
- [On burnside (again)](https://codeforces.me/blog/entry/64860)
- [Simple but often unknown theorems/lemmas/formula? Do you know?](https://codeforces.me/blog/entry/55912)
- [Probabili...
2.
Pro Tips - get them while they are free More tips to use while studying under my tutoring [here](https://um-nik.notion.site/Pro-Tips-8b923b0dc7c94770824bdf4184afc43c).
## Stop caring about the rating
Unless there are prizes involved, your position in the standings makes no difference. I can feel awful after winning a contest if I know that I could solve one more problem. Or I can feel OK losing a bunch of rating points knowing that I solved everything I could. Because rating is just a number. It is highly volatile and it depends on other people, not only on your skill. But solving problems is totally up to you. And you should evaluate yourself not based on some random metric, but on your honest feeling whether you performed up to your expectations. Your sense of self should be under your control, don't get hung up on some imaginary value, you cannot reduce your progress to a single number.
## Don't use more than one account
Rating is just a number. Do not be afraid to lose your colour. You’ll get it back in no t...
how to calculate the answer for one query with $n < 1000$. Do not take your
allen wrench out of the, version too? - How to answer one query? - How would I solve a small case on
paper? How would I, Do not write a segment tree if you don’t know how to calculate the answer for
onequery with $n
3.
Blogewoosh #6 Hello, codeforces!
Sorry for the long break, but the last weeks of holidays and the first weeks of academic year took my attention. I hope today's trick will make you forgive me. :P
I invented this trick a few years ago, but for sure I wasn't first, and some of you already know it. Let's consider the following **interactive** task. There are $n$ ($1 \leq n \leq 10^5$) hidden integers $a_i$, each of them from range $[1, 10^{18}]$. You are allowed to ask at most $103000$ queries. In one query you can choose two integers $x$ and $y$ ($1 \leq x \leq n, 1 \leq y \leq 10^{18}$) and ask a question ''Is $a_x \geq y$?'' The task is to find the value of the greatest element in the hidden array. The checker **isn't** adaptive.
Unfortunately, this task is only theoretical, and you cannot solve it anywhere, but it'll turn out, that solution can be handy in many other, much more complicated problems.
[cut]
$ $
Even beginners should be able to quickly come up with a solution which ask...
. In one query you can choose two integers $x$ and $y$ ($1 \leq x \leq n, 1
\leq y \leq 10^{18, query you can choose two integers $x$ and $y$ ($1 \leq x \leq n, 1 \leq y \leq
10^{18}$) and ask a
4.
[Tutorial] Collection of little techniques #### Introduction
There are a number of "small" algorithms and facts that come up again and again in problems. I feel like there I have had to explain them many times, partly because there are no blogs about them. On the other hand, writing a blog about them is also weird because there is not that much to be said. To settle these things "once and for all", I decided to write my own list about about common "small tricks" that don't really warrant a full tutorial because they can be adequately explained in a paragraph or two and there often isn't really anything to add except for padding.
This blog is partly inspired by [user:adamant,2022-03-15]'s [blog](48417) from a few years ago. At first, I wanted to mimic adamant's blog structure exactly, but I found myself wanting to write longer paragraphs and using just bolded sentences as section headers got messy. Still, each section is short enough that it would not make much sense to write separate blogs about each of these things.
A...
answer a query before reading the next one. $n \le 10^5$., )$ time, potentially at the expense of query time. How the data structure
actually works is actually, -called "virtual trees". In some problem, such as [problem:613D], you are given
many queries, eachquery
5.
Editorial for Hello 2024 ### [problem:1919a]
Author: [user:maomao90,2024-01-02]
<spoiler summary="Hint 1">
When does the game end?
</spoiler>
<spoiler summary="Solution">
Depending on whether the player chooses to exchange wallets with their opponent on step $1$, $1$ coins will be removed from either the opponent's wallet or the player's wallet. This means that if either of the players still has remaining coins, the game will not end as at least one of the choices will still be valid.
The only way that the game ends is when both players have $0$ coins. Since each operation decreases the total amount of coins by exactly $1$, the only way for Alice to win the game is if $a + b$ is odd.
</spoiler>
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int a, b; cin >> a >> b;
if ((a + b) % 2 == 0) {
cout << "Bob\n";
} else {
cout << "Alice\n";
}
}
...
$a$ or $b$, we can make use of one type 2 query to find the distance between
one of the edges in $S_a, Use $n - 2$ of query $2$ to find the distance of every edge to the root, We will root the tree at edge $1$. Then, use $n - 2$ of query $2$ to, single type 1 query for each non-root edge. We used $n - 2$ type 2 queries at
the start, and we only used, the query edge and force the diameter to pass through the leaf edge and the
query edge. Then, only 1, For convenience, the edge weights used in query $1$ will be $1$ by default
unless otherwise stated, int main() { cin >> n; for (int i = 2; i < n; i++) { lvl[i] = query(1, i, ll query(vector a) { cout << "? 1"; for (int i = 1; i < n; i++) { cout
Tutorial of Hello 2024
6.
Blogewoosh #7 Hello, codeforces!
Long time no see, right? So maybe it's a good idea to try to return to my blogs slowly. This time the blog will be about a trick, which usually isn't necessary to solve a task, but can be useful to make implementation much more comfortable.
Let's look at [this](https://codeforces.me/contest/932/problem/F) problem. It is about some DP on a tree in which we have to use convex hull trick to improve the complexity. The task requires merging two convex hulls with "smaller to bigger" trick. I recommend you to read the statement before reading the rest of the blog (and the [editorial](https://codeforces.me/blog/entry/57796) if you don't know how to solve it).
[cut]
$ $
So, how to merge two convex hulls? If we keep them in something like the set from C++, then we can just take every element from the smaller one and try to add it to the bigger one. Unfortunately, adding one element in this way requires some ifology and care. It's hard to implement it, especiall...
7.
A simple introduction to "Segment tree beats" Hi, I’d like to introduce a simple trick about segment tree in this blog as I promised in [this comment](http://codeforces.me/blog/entry/54750?#comment-387957). Sorry for the long delay, as a sophomore in Peking University, I've just finished a tired semester and a painful final exam. And now I finally have enough time to do a simple introduction to this interesting algorithm.
It may be a huge project for me since my English is not good. I think I will finish this blog in several steps and I will try to finish it as soon as possible :)
In China, all of the 15 candidates for the Chinese National Team are asked to write a simple research report about algorithms in informatics Olympiad, and the score will be counted in the final selection. There are many interesting ideas and algorithms in these reports. And I find that some of them are quite new for competitors in CF although they are well known in China from the final standings of some recent contests. For example, In the last co...
$A_i$ to $x$ 3. Query for the sum of $A_i$ in $[l,r]$, $A_{a,i}$ to $A_{a,i} + x$, $x$ can be a negative number 3. Query for the max
$A_{1,i} + A_{2,i, $\max(A_i - x,0)$. 3. For all $i \in [l,r]$, change $A_i$ to $x$. 4. Query for
$A_i$. 5.Query for, 4. Query for the sum of $A_i$ in $[l,r]$, 4. Query for the sum of $B_i$ in $[l,r]$, )$: interval **min** operation, query for the interval sum., **Task 3**. And we can query for some other things:, 1. For all $i \in [l,r]$, change $A_i$ to $\max(A_i, x)$ 2. Query for the sum
of $A_i$ in $[l,r]$, 1. For all $i \in [l,r]$, change $A_{i}$ to $A_{i} + x$, $x$ can be a negative
number. 2.Query, Now, let use consider such a kind of problems (Part1. Task 5): interval
add/subtract,query for the, The query for $B_i$ can be solved in $O(n \log^2 n)$ and the query for $C_i$
can be solved in $O(n, {i}$ to $A_{i} + x$, $x$ can be a negative number. 3. Query for the sum of
$B_i$ in $[l,r]$.
8.
[Tutorial] On Range LIS Queries, Part 1 Hello, Codeforces!
At some point of life you want to make a new data structure problem with short statement and genius solution. LIS (Longest Increasing Subsequence) is a classic problem with beautiful solution, so you come up with the following problem:
* Given a sequence $A$ of length $N$ and Q queries $1 \le i \le j \le N$, compute the length of Longest Increasing Subsequence of $A[i], A[i + 1], \ldots, A[j]$.
But on the other hand this looks impossible to solve, and you just give up the idea.
I always thought that the above problem is unsolved (and might be impossible), but very recently I learned that such queries are **solvable** in only $O(N \log^2 N + Q \log N)$ time, not involving any sqrts! The [original paper](https://arxiv.org/abs/0707.3619) describes this technique as *semi-local string comparison*. The paper is incredibly long and uses tons of scary math terminology, but I think I found a relatively easier way to describe this technique, which I will show in t...
for LIS query. The All-Pair LCS problem can be a problem of independent
interest. For example, initialize with $S = [1, 2, \ldots, N], T = A$, we obtain a data structure for
LISquery., Here, you can observe that the answer to the query $(i, j)$ corresponds to the
longest path from
9.
[Tutorial] Matroid intersection in simple words **[This article is also available in [Russian](https://codeforces.me/blog/entry/69287?locale=ru)]**
Hello, CodeForces.
I think that matroids are beautiful and powerful concept, however, not really well known in competitive programming.
I’ve discovered matroids at 2019 Petrozavodsk Winter Training Camp. There was a problem that clearly cannot be solved using usual techniques I knew, editorial for this problem was just these three words “just matroid intersection”. Back then it took me more than 2 days of upsolving to find all the information and details I need and implement solution that gets Accepted on this. And it took way longer to actually understand why does it work and exactly how does it work. (I still hesitate in some details.)
Of course, it is not hard to google up all the definitions and some related articles, but in my opinion they all are focused more on mathematical part of theory, strict proofs in some not really obvious but short ways, and observing only ke...
and allows checking presence of edge in $\mathcal{O}(1)$. Great balance
between prepare andquery, $. We can reduce checking presence of edge in exchange graph to one query to
check that some edge $(x
10.
Matrix Exponentiation tutorial + training contest tl;dr — video tutorial https://www.youtube.com/watch?v=eMXNWcbw75E and codeforces GYM training https://codeforces.me/gym/102644 (register by finding this contest in GYM instead of using the link directly)
video editorial: [part 1 (ABCDEF)](https://www.youtube.com/watch?v=kQuCOFzWoa0) and [part 2 (GHI)](https://www.youtube.com/watch?v=RA_SpxP2t54)
codes to all 9 problems: https://github.com/Errichto/youtube/tree/master/matrix-exponentiation
Prerequisites: binary exponentiation and iterative dp (you don't need to know matrices)
The youtube tutorial ([link](https://www.youtube.com/watch?v=eMXNWcbw75E)) focuses on intuition and graph-like visualization . Or, if you prefer, below is a shorter (less detailed) text tutorial instead.
You can practice by solving a set of 9 educational problems in GYM https://codeforces.me/gym/102644. ABCD are easy, EF medium, GHI are hard. If you are stuck, see hints below or watch the full solution analysis — [part 1 (ABCDEF)](https:...
If you do matrix exponentiation for every query, that's
11.
[Tutorial] Li Chao Tree Extended Hello everyone! I discovered a new (?) trick on how to apply lazy propagation on the Li Chao Tree and decided to write a blog about it. I've personally never seen it before (outside of myself), nor have I seen a problem that needs the Extended Li Chao Tree specifically, but it *can* overkill some problems. Of course, I might not be looking hard enough...
You can learn about the basics of Li Chao Tree from [cp-algorithms](https://cp-algorithms.com/geometry/convex_hull_trick.html) or [this simple blog](https://robert1003.github.io/2020/02/06/li-chao-segment-tree.html).
The Extended Li Chao Tree can do the following problems (and other variations):
## Problem 1
There is an array $A$ of size $N$. There are $Q$ online operations:
- Range Line Insertion. Given $l$, $r$, $a$, $b$, do $A_i = \max(A_i, a \cdot i + b)$, $\forall i \in [l, r]$ in $O(\log^2 N)$
- Range Line Addition. Given $l$, $r$, $a$, $b$, do $A_i += a \cdot i + b$, $\forall i \in [l, r]$ in $O(\log^2 N)$.
- Po...
+ b$, $\forall i \in [l, r]$ in $O(\log^2 N)$. - Point Query. Given $i$,
return $A_i$ in $O(\log N)$., R$ and $\max\limits_{ql \leq i \leq qr} (H_i, i) = (H_M, M)$. Consider a query
$[ql, qr]$ on this, \in [l, r]$ in $O(\log^2 N)$. - Range Maximum Query. Given $l$, $r$, return
$\max\limits_{\forall i, **Problem.** Given an array $H$ of size $N$. You are given $Q$ queries $[ql,
qr]$. For eachquery, If we have such values, for a query $[ql, qr]$, the answer is $\min(opt_{ql, M
- 1} + (qr - M + 1, Let $opt_{l, r}$ be the answer for the query $[l, r]$. Assume we have values
$opt_{L, M - 1}, opt_, Let's focus on the Li Chao Tree that solves Problem 1. Range line insertion and
pointquery can be, data_t Query(Node* &n, data_t tl, data_t tr, data_t x) { if (n == nullptr)
return -inf; if, data_t Query(data_t x) { return Query(root, 0, sz - 1, x); } ~~~~~
12.
Tutorial on Permutation Tree (析合树） So my O level Chinese exam is in 2 days so I decided to learn a data structure that I can only find [resources](https://oi-wiki.org/ds/divide-combine/) for in Chinese. I thought I might as well write a tutorial in English.
This data structure is called 析合树, directly translated is cut join tree, but I think permutation tree is a better name. Honestly, after learning about it, it seems like a very niche data structure with very limited uses, but anyways here is the tutorial on it.
Thanks to [user:dantoh,2020-06-16] and [user:oolimry,2020-06-16] for helping me proofread.
### Motivation
Consider this [problem](https://codeforces.me/contest/526/problem/F). We are given a permutation,$P$ of length $n$. A good range is a contiguous subsequence such that $\max\limits_{l \leq i \leq r} P_i - \min\limits_{l \leq i \leq r} P_i = r-l$. This can be thought of the number of contiguous subsequence such that when we sort the numbers in this subsequence, we get contiguous values. Count the...
->query(i,j); else if (mquery(i,j); else return l->query(i,m)+r->query(m+1,j, Furthermore, when the lowest node that contains the given query is a join node,
we still need to, ans+=root->query(0,x);, if (s==i && e==j) return val; else if (j<=m) return l->query(i,j); else if (m, ll query(int i,int j){ propo();, nodes.pop_back(); curr=idx++; } } else if (x-(length(curr)-1) && root->query(0,x, query, we go to a arbitrary node that is contained in the query then using
binary lifting, jump to the
13.
Codeforces Round #333 — editorial ### Hints:
[div2A](#div2A): Try conversions between bases.
[div2B](#div2B): Solve a simpler version of the problem where $A_{i+1} \neq A_i$ for all $i$.
[div1A](#div1A): What are the shortest paths of the vehicles? what's the shorter of those paths?
[div1B](#div1B): Forget about the ceiling function. Draw points $(i,A[i])$ and lines between them — what's the Lipschitz constant geometrically?
[div1C](#div1C): Some dynamic programming. Definitely not for the exp. score of one person — look at fixed scores instead.
[div1D](#div1D): Compute $dif(v)$ in $O(N)$ (without hashing) and then solve the problem in $O(N^2)$. You need some smart merges.
[div1E](#div1E): Can you solve the problem without events of type 1 or 2? Also, how about solving it offline — as queries on subsets.
### <a name="div2A"></a>Div. 2 A: Two Bases
------------------------------------
It's easy to compare two numbers if the same bas...
intersection, but present in one query (so it'll be one of the elements added
using knapsack DP), ifquery, intersections of pairs of queries $2q,2q+1$ (intersection of the first and the
secondquery, of the third and, over time. We'll solve it offline — each query (event of type 3) is asked
about a subset of, the $m$-th and $b$-th query have to be added and in the second case, it's only
elements added between, All we have to do to answer a query is check all differences, take $a_i$, $b_i$
(as the max/min, If we're left with just one query, we can solve it in $O(Nk)$ as the usual 0-1
knapsack., Let's have $q$ queries numbered $1$ through $Q$ in the order in which they're
asked;query $q$ is, {i = a}^{b} S_i$ if and only if it was displayed before the $a$-th query and
remained displayed at
Tutorial of Codeforces Round 333 (Div. 1)
Tutorial of Codeforces Round 333 (Div. 2)
14.
crazySegmentTree: Segment Tree implementation with 5x faster queries than bottom-up tree Hello, Codeforces!
A few days ago [user:MohammadParsaElahimanesh,2021-04-06] posted a blog titled [Can we find each Required node in segment tree in O(1)?](https://codeforces.me/blog/entry/89377) Apparently what they meant was to find each node in $\mathcal{O}(ans)$, according to [ecnerwala's explanation](https://codeforces.me/blog/entry/89377?#comment-777885). But I was too dumb to realize that and accidentally invented a parallel node resolution method instead, which speeds up segment tree a lot.
A benchmark for you first, with 30 million RMQ on a 32-bit integer array of 17 million elements. It was run in custom test on Codeforces on Apr 6, 2021.
- **Classic implementation from cp-algorithms:** 7.765 seconds, or 260 ns per query
- **Optimized classic implementation:** (which I was taught) 4.452 seconds, or 150 ns per query (75% faster than classic)
- **Bottom-up implementation:** 1.914 seconds, or 64 ns per query (133% faster than optimized)
- **Novel parallel implement...
cp-algorithms:** 7.765 seconds, or 260 ns per query - **Optimized classic
implementation:** (which, once, which means that the core of the query should run about 8 times faster., - **Classic implementation from cp-algorithms:** 7.765 seconds, or 260 ns per
query - **Optimized, In a segment tree, a range query is decomposed into 'red' nodes. Classic
segment tree, In bottom-up segment tree, we find the node corresponding to the leftmost
element of thequery, i.e
15.
My own algorithm — offline incremental strongly connected components in O(m*log(m)) Hello Codeforces!
As all of you know, there are so many known algorithms named after people who invented them — from the easiest ones, like Dijkstra, to the harder ones, like Berlekamp–Massey algorithm. These algorithms were innovative when they were invented, so of course, it's good that they are named after their inventors.
But, today, I've seen a blog about the solution to the problem "compute LCS of two strings in time $O((n + k) \cdot \log(k))$, where $n$ is the sum of lengths of the strings, and $k$ is the number of pairs of matching positions in them". To be honest, it a bit pissed me off that even this algorithm is named after its creators. Is it ok to name the solution to every possible problem after its author? I won't judge it. Anyway, I want my very own Radecki algorithm, so let me give it a try. If anyone has ever heard about it — it's cool. Let me know, and it'll be just another helpful blog on Codeforces.
Let's imagine the following problem: there is...
16.
Algorithm Gym :: Data structures Today I want to introduce you some very very useful data structures.
In this lecture, we are trying to improve your data structures skills, stay with us and click on **read more**.
[cut]
Important data structures :
Trees
-----
Trees are one of the most useful data structures.A tree is a connected-acyclic graph.There are too many types of trees, like : rooted trees, weighted trees, directed trees, tries, etc.
Partial sum
-----------
There are two types of problems solvable by partial sum.
1.Problems which you are asked to answer some queries about the sum of a part of elements (without modify queries).
Solution of all of this problems are the same. You just need to know how to solve one of them.
Example : You are asked some queries on an array $a_1,a_2,...a,_n$. Each query give you numbers $l$ and $r$ and you should print $a_l + a_{l+1} + ... + a_r$ .
Solution : You need to build another array $s_1, s_2, ..., s_n$ which $s_i = a_1 + a_2 + ... + a_i$ ...
(range minimum query) problem, initially $0$, for each query, you should increase $p_l$ by $v$ and decrease
$p_{r+1}$ by $v$ ., queries. Each query gives you numbers $l$ and $r$ ($l \leq r$) and you should
print the value of $min, $ (for nodes) which are initially $0$ and every time we want to perform increase
query, increase $lazy[id, (For the first query (with index 0) we should run $root[0] = upd(p,\ v,\ ir)$
and for the rest of, )$ ) after performing each query and a number $ir = 0$ which is its index in
the initial segment tree, **Problems** : [Hamro and tools](/group/L1Sf9F4uBt/contest/200499/problem/E),
[TROYQuery](/gym, **Problems** : [Strip](/contest/487/problem/B),
[GCDSSQ](/contest/475/problem/D), [LCMQuery](/gym, ,...a,_n$. Each query give you numbers $l$ and $r$ and you should print $a_l +
a_{l+1} + ... + a_r, A red-black tree is a kind of BST that after each query, BST will be balanced
in such a way that, And then for each query, first of all, find the maximum $x$ such that $2^x \leq
r-l+1$ and answer, Each ask query, gives you three numbers $i$ and $x$ and $y$ and asks you to
print the value of $a_x, Each update query gives you numbers $p$ and $v$ and asks you to increase $a_p$
by $v$ ., Each update query, changes the value of $O(log(n))$ nodes in the segment tree,
so you should keep, Example : You are asked some queries on an array $a_1,a_2,...a,_n$. Each query
give you numbers $l, Example : You need to perform some queries on an array $a_1,a_2,...a,_n$. Each
query give you, Hard problem of partial sum : [Troynacci Query](/gym/100571/problem/B), If you update a node, you should assign a new index to its interval (for $i-th$
query)., So preprocess will be in $O(n.log(n))$ and query will be in $O(1)$, We keep tools in a vector (or an array) and when we have a query to merge two
boxes, we put all the, We perform each query in $O(log(n))$. Code : (1-based)
17.
[Tutorial] The DFS tree and its applications: how I found out I really didn't understand bridges #### Introduction
This is a tutorial/exploration of problems that can be solved using the "DFS tree" of a graph.
For a way too long time, I didn't really understand how and why the classical algorithm for finding bridges works.
It felt like many tutorials didn't really explain how it works, kind of just mentioned it in passing and quickly
just moved on to implementation. The day someone explained what the DFS tree is, I finally understood it properly.
Before, it took me ages to implement bridge-finding properly, and I always had to look up some detail. Now I can
implement it at typing speed.
But more importantly, I began to see how the same techniques can be used to solve graph problems that have more or
less nothing to do with bridges. The thing is, when you have a black box, you can only ever use it as a black box.
But if you have a box that you understand well, you can take it into pieces, repurpose the pieces for completely
different things, all without getting lost...
$; denote this $\mathrm{cnt}[u]$. 4. the answer to query $(p, q)$ is either
$2^{\mathrm{cnt}[p] + \mathrm
18.
Analyzing how good O1-Mini actually is I would like to thank [user:redpanda,2024-09-13] and [user:qmk,2024-09-13] for their great help in writing and reviewing this blog. They are also the users who queried O1-mini for all the following problems.
We tried O1-mini on several problems, from a variety of sources. Let's list the results first.
**Note** :
- Some of the WA verdicts here actually means that the AI just "stopped thinking" which means the AI thought for a long enough time without any useable results so it ran into an error.
- All ratings mentioned are Codeforces ratings, the Atcoder ratings have been converted to codeforces rating. To measure the approximate codeforces rating of the atcoder problems mentioned here, you can use https://kenkoooo.com/atcoder/#/table/ + https://silverfoxxxy.github.io/rating-converter.
<h4> D2ABs </h4>
- [problem:1762B] [<a class="rated-user user-gray" title="Gray">1100</a>] <a class="rated-user user-green" title="Green AC">AC</a>
- [problem:1998B] [<a class="rated-...
19.
Sqrt-tree: answering queries in O(1) with O(NloglogN) preprocessing. Hello, Codeforces!
Some time ago I invented an interesting data structure and I'd like to share it with the community. Maybe, it was known before, and if you knew about it before my blog post, please share the link to the source.
# What can the data structure do?
Given an array $a$ that contains $n$ elements and the operation $op$ that satisfies associative property: $(x\ op\ y) op\ z = x\ op (y\ op\ z)$ is true for every $x$, $y$ and $z$.
So, such operations as $gcd$, $\min$, $\max$, sum, multiplication, $and$, $or$, $xor$, etc. satisfy these conditions.
Also we have some queries $l, r$. For each query, we need to find $a_l\ op\ a_{l+1}\ op\ \dots op\ a_r$. Let's call such queries $q(l, r)$.
My data structure can process such queries in $O(1)$ time with $O(n \cdot \log \log n)$ preprocessing time and $O(n \cdot \log \log n)$ memory.
# How it works?
[cut]
#
## 1. Sqrt
Let's do a sqrt-decomposition. We divide our array in $\sqrt{n}$ blocks, each block ha...
easy to choose the layer on which we can process the query easily. We can also
use a precalculated, have much smaller layers and we still have $O(1)$ per query., in which our query doesn't fit entirely into one block. See the first section
on how to answer the, queries $l, r$. For each query, we need to find $a_l\ op\ a_{l+1}\ op\ \dots
op\ a_r$. Let's call such, single element. But in this case, query complexity becomes $O(\log \log n)$.
You can think how to do, ## 3. Optimizing the query complexity, , we can reach the $O(\log \log \log n)$ complexity per query. Can we do it
even faster?, 3. `between[i, j]` $i \le j$ -- answer to the query that begins at the start of
block $i$ and ends, Also we have some queries $l, r$. For each query, we need to find $a_l\ op\
a_{l+1}\ op\ \dots op, Now, we can easily check if the query fits entirely into a block with size
$2^k$. Let's write the, OK, now we can do $O(\log \log n)$ per query. Can it be done faster?, Using this observation, we can find a layer that is suitable to answer the query
quickly. How to do, We already can answer some queries using these arrays. If the query doesn't fit
into one block, we
20.
One-letter variables Complete shitpost, don't take it seriously. We were discussing `#define int long long` and I suggested defining it to one letter if you want to save on typing so desperately. [user:jeroenodb,2025-10-11] said that those are reserved for variables, which prompted me to think, "Is there a letter I don't standardly use for some particular purpose?" Then I compiled the following list, and then I thought, "Well, I already wrote it, let's put it on cf", so here we are.
~~~~~
a - array, but also all sorts of stuff
b - second array
c - third array / count
d - delta / divisor
e - event / edge
f - flag
g - graph / second flag
h - third iterator / third flag / height
i - iterator
j - second iterator
k - third input size / some parameter (i know, those are all parameters, but for some reason k is parameter)
l - left
m - number of edges / second input size
n - input size
o - ???
p - permutation / position
q - number of queries / query / second permutation / second position
r - r...
- permutation / position q - number of queries / query / second permutation /
second position r, size n - input size o - ??? p - permutation / position q - number of queries /
query / second
21.
[Tutorial] FFT If I was a YouTuber, this would be the place where I fill the entire screen with screenshots of people asking me to make this. Anyway, not so long ago I gave a lecture on FFT and now [user:peltorator,2023-01-11] is giving away [free money](https://codeforces.me/blog/entry/110840), so let's bring this meme to completion.
In this blog, I am going to cover the basic theory and (competitive programming related) applications of FFT. There is a long list of generalizations and weird applications and implementation details that make it faster. Maybe at some point I'll write about them. For now, let's stick to the basics.
**The problem.** Given two arrays $a$ and $b$, both of length $n$. You want to quickly and efficiently calculate another array $c$ (of length $2n - 1$), defined by the following formula.
$$c_k = \displaystyle \sum_{i + j = k} a_i \cdot b_j.$$
Solve it in $O(n \log n)$.
First of all, why should you care? Because this kind of expression comes up in combinatorics a...
$n$ and $q$ queries. Each query consists of two integers $1 \le x < y \le n$.
For eachquery
22.
CodeTON Round 5 Editorial ### [problem:1842A]
<spoiler summary="Tutorial">
Let's view it as when monsters $x$ and $y$ fight, their health changes into $\max(x-y,0)$ and $\max(y-x,0)$ respectively. So any monster with $0$ health is considered dead. Therefore, a player loses when the health of his monsters are all $0$.
Notice that $\max(x-y,0)=x-\min(x,y)$ and $\max(y-x,0)=y-\min(x,y)$. Therefore, after each step, the sum of the health of monsters decrease by the same amount for both players.
Therefore, we only need to know $\sum a_i$ and $\sum b_i$ to determine who wins. If $\sum a_i > \sum b_i$, Tsondu wins. Else if $\sum a_i < \sum b_i$, Tenzing wins. Else, it is a draw.
</spoiler>
<spoiler summary="Code">
~~~~~
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, m, a[50], b[50];
long long sumA = 0, sumB = 0;
cin >> n >> m;
for (int i = 0; i < n;...
Use a Disjoint Set Union to query the smallest $i\ge l$ such that $cnt_i\ne 0$.
The time complexity
23.
Editorial — Codeforces Round #648 [problem:1365A]
<spoiler summary = "Tutorial">
[tutorial : 1365A]
</spoiler>
<spoiler summary="Code">
<pre><code>
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
const int N = 51;
int n, m;
int a[N][N];
int32_t main()
{
IOS;
int t;
cin >> t;
while(t--)
{
cin >> n >> m;
set< int > r, c;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> a[i][j];
if(a[i][j] == 1)
r.insert(i), c.insert(j);
}
}
int mn = min(n — r.size(), m — c.size());
if(mn % 2)
cout << "Ashish" << endl;
else
cout << "Vivek" << endl;
}
return 0;
}
</code></pre>
</spoiler>
This problem was prepared by [user:Ashishgup,2020-06-07]
[problem:1365B]
<spoiler summary = "Tutorial">
[tutorial : 1365B]
</spoiler>
<spoiler summary="Code">
<pre><code>
#include <bits/stdc++.h>
us...
for(int i = 0; i < Q; i++) if(!ask[i].empty()) or_value[i] = query(ask[i]);, ll query(vint v){ cout << "? " << v.size() << ' '; for(ll i : v) cout << i + 1
Tutorial of Codeforces Round 648 (Div. 2)
24.
How to sweep like a Sir ### Cutting to the chase
Clearly you don't need a PhD in Computing to sweep in the yard , but one might be useful in order to know linear and radial sweep algorithms. So , what's all about ? It's just what it sounds it is , sweeping linear ( up to down , for example ) or radial ( making a 360 degrees loop ).
How this can help? [cut] Well...
### Linear sweep
Suppose you a set of objects in an Euclidean plane. We need to extract information about some objects. The method of linear sweeping takes a line and moves it on a fixed direction. Usually the line taken would be vertical and the direction would be left to right or up to down.
Quite abstract for the moment , huh ? Let's go to a more specific example.
#### Rectangle union area
This example is well known. You have a set of rectangles with edges parallel to the OX and OY axes. What is their union area.
Well , first of all , let'...
25.
The Time Complexity Lower Bound for Segment Tree Beats is log^2 Original Post: https://jiry-2.blog.uoj.ac/blog/1404
The following content is translated by Gemini 2.5 Pro.
## Part 1: Introduction to the Hacking Method
### How to Map the Hack Sequence to a Segment Tree
First, we are given a Hack sequence of length $len$. After $O(1)$ range addition operations and $\Theta(\log len)$ global $\text{chkmax}$ operations, this sequence becomes a cyclic shift (rotation) of the original sequence. Since a cyclic shift does not affect our range addition and global $\text{chkmax}$ operations (we can simply shift the indices for the range addition accordingly), we can consider the sequence as unchanged.
If we have such a sequence, let $len=n^{\frac{1}{3}}$, and place such a sequence at intervals of $n^{\frac{2}{3}}$. Each sequence corresponds exactly to a segment tree interval. A subtree of size $n^{\frac{2}{3}}$ contains exactly one such segment tree interval.
For the Hack sequence, the range addition operations are performed one by one on eac...
26.
An alternative sorting order for Mo's algorithm Hello, Codeforces!
I think many of you know about Mo's algorithm. For those, who don't know, please read this [blog](https://codeforces.me/blog/entry/7383).
Here, I consider an alternative (and faster) approach of sorting queries in Mo's algorithm.
# Table of contents
* [Canonical version of the algorithm](#s1)
* [Achieving a better time complexity](#s2)
* [Relation to TSP](#s2-1)
* [Hilbert curve](#s2-2)
* [Benchmarks](#s3)
* [Applicability](#s4)
<div style="font-size: 1pt">
[cut]
</div>
<a name="s1"></a>
# Canonical version of the algorithm
The canonical version of this algorithm has $O((n + q)\cdot\sqrt{n})$ time complexity if insertions and deletions work in $O(1)$.
Usually, the two comparators for query sorting are used. The slowest one:
~~~~~
struct Query {
int l, r, idx;
inline pair<int, int> toPair() const {
return make_pair(l / block, r);
}
};
inline bool operator<(const Query &a, const Query &b) {
re...
one query to another in $O(2^{k-l})$, so we process all such groups of queries
in $O(q\cdot2^{k-l, Usually, the two comparators for query sorting are used. The slowest one:, inline bool operator<(const Query &a, const Query &b) { return a.toPair() <
b.toPair(); } ~~~~~, ~~~~~ struct Query { int l, r, idx;
27.
On Multidimensional Range Queries The following question is frequently asked in Codeforces ([46390](https://codeforces.me/blog/entry/46390), [45157](https://codeforces.me/blog/entry/45157), [11324](https://codeforces.me/blog/entry/11324)): _Is there a 2D segment tree that supports range addition and range minimum?_ In this blog post I give evidence that such a data structure does not exist, or if it did exist it would not generalize to higher dimensions. In particular I show that if for all $d$ a $d$-dimensional data structure that performs such queries in $O(polylog(N))$ time did exist, then the [exponential time hypothesis](https://en.wikipedia.org/wiki/Exponential_time_hypothesis) would fail. Such a data structure exists for range addition and range sum, so this is a non-trivial claim separating the hardness of these problems.
## Update 2021:
A paper " Algorithms and Hardness for Multidimensional Range Updates and Queries" in ITCS 2021 by Joshua Lau and Angus Ritossa ([https://arxiv.org/abs/2101.02003](https:...
different query and update operations. For range addition and range minimum in
2D they show a lower, use a single $min$-operation where $l_j = 0$ and $r_j = N$ for all dimensions
$j$ toquery if there, -01-08]) gives an overview of the complexity of multidimensional range queries
with differentquery, [2] L. Duraj, K. Kleiner, A. Polak, V. V. Williams. Equivalences between
triangle and rangequery
28.
[Tutorial] Square Root Techniques _This is my 100th CF blog!_
This is a list of techniques with $O(\sqrt n)$ time complexity.
Watch the lecture https://youtu.be/BJhzd_VG61k, with timestamps!
1. Square root decomposition — split the sequence into blocks of fixed size.
2. Splitting objects (e.g. vertices) into light and heavy.
3. Square root decomposition by the time of queries & rebuilding the structure.
4. Mo's algorithm — processing queries in proper order and updating the answer by erasing/inserting new elements. https://cp-algorithms.com/data_structures/sqrt_decomposition.html
5. Strings — if the sum of lengths is $S$ then there are at most $\sqrt{S}$ distinct lengths.
6. Birthday paradox & baby-step giant-step. See P4 and P6 [here](https://codeforces.me/blog/entry/95571), and see https://cp-algorithms.com/algebra/discrete-log.html.
P1. [problem:398D]
P2. [problem:220B]
P3. <s>[problem:86D]</s> (actually, skip this one because it's boring)
P4. Count triangles in a graph, i....
29.
Editorial — Codeforces Round #651 [problem:1370A]
<spoiler summary = "Tutorial">
[tutorial : 1370A]
</spoiler>
<spoiler summary="Code">
<pre><code>
#include < bits/stdc++.h >
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
const int N = 1e5 + 5;
int32_t main()
{
IOS;
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
cout << n / 2 << endl;
}
return 0;
}
</code></pre>
</spoiler>
This problem was prepared by [user:the_hyp0cr1t3,2020-06-20]
[problem:1370B]
<spoiler summary = "Tutorial">
[tutorial : 1370B]
</spoiler>
<spoiler summary="Code">
<pre><code>
#include < bits/stdc++.h >
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
const int N = 2e5 + 5;
int n;
int a[N];
int32_t main()
{
IOS;
int t;
cin >> t;
while(t--)
{
cin >> n;
vector< int > even, odd;
for(int i = 1; i ...
if(node_set.empty()) en = mid — 1; else{ pair< int, int > res = query(node_set, pair query(vector< int > nodes){ cout << "? " << nodes.size() << ' '; for(int i, pair< int, int > res = query(nodes); root = res.first, dist = res.second;, }); } pair< int, int > second_node = query(candidate_second); cout << "! " <<
first_node
Tutorial of Codeforces Round 651 (Div. 2)
30.
[Tutorial] Voronoi Diagram and Delaunay Triangulation in O(n log n) with Fortune's Algorithm What's a Voronoi Diagram?
------------------
Given a set $S$ of $n$ points in the 2D plane, the Voronoi diagram is a partition of the plane into regions. The region associated with a point $p\in S$ contains precisely the points $q$ such that $q$ is closer to $p$ than any other point in $S$. In other words, a point $q$ belongs to the region of its nearest neighbor.
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/54/Euclidean_Voronoi_diagram.svg/1024px-Euclidean_Voronoi_diagram.svg.png" width="300px" height="auto"/>
The Voronoi diagram can be represented by the planar graph of boundaries between regions. A vertex in this graph is where three or more segments meet (or a point at infinity), and an edge is a segment connecting two of these vertices. The way the regions were defined, we see that a segment contains the points equidistant to two points in $S$, so it is part of their perpendicular bisector. Similarly, a Voronoi vertex is equidistant to three or more v...
$n$ points and $m$ query points $p_1,\ldots, p_m$, we can answer for each query
point, its nearest
31.
Solving IOI2020 D2P2 (Mushroom) within 203 Queries (Step by Step) The statement and dataset of this problem can be found [here](https://ioi2020.sg/ioi-2020-tasks/).
Short statement: there are $ N \le 20000 $ objects with value $ 0 $ or $ 1 $. Each time you can select some objects and permute them to form a 0-1 sequence, then the interactor will tell you the total number of 0-1 and 1-0 shifts in the sequence(i.e. `011000` has 2 shifts and `000101` has 3 shifts). It is guaranteed that the value of the 1st object is $ 0 $. You are required to find out the number of objects with value $ 0 $ within $ 226 $ queries ($100\%$) / $ 904 $ queries ($>25\%$), and the total length of the sequence in the queries is bounded by $ 10^5 $.
When encountering the problem, a linear algorithm comes directly. We can check whether there is a shift in value sequence $ 0, x $. If so $ x = 1 $, otherwise $ x = 0 $. Hence we can solve the problem within $ N $ queries, getting $ 10\% $ as a result.
We then can come up to do some tiny optimizations, without changing the ...
extend the length of our query) when we count the objects. Directly apply this
approach enables us to, given in the problem. A tiny optimization reducing the number of ones required
in the lastquery of, our query) when we count the objects. Directly apply this approach enables us
to solve for $ N \le, sequence we can recover within $ 2^m $ steps, and $ q_m $ be the query
sequence of it, with the last, query to solve $ p $ and $ q $, then why not ask $ p $ and $ q $ individually.
This may make us
32.
[Tutorial] Supporting Priority-Queue-like Undoing on DS _Good morning!_
In this blog, I will present an online algorithm that can perform priority-queue-like undoing on a data structure, given a few assumptions. I will also present and solve a generalization of that problem.
For context, I highly recommend reading this blog that shows how to solve the easier problem of queue-like undoing. That blog gave me the inspiration for the trick I will describe here, but I will still try to write this blog so that it can be understood without it. Thank you [user:Noam527,2023-01-08] for introducing such a great trick to the competitive programming community.
[[Tutorial] Supporting Queue-like Undoing on DS](https://codeforces.me/blog/entry/83467)
Acknowledgment
-----------------
Huge thanks go to [user:peltorator,2023-02-20] for hosting a [blog contest](https://codeforces.me/blog/entry/110840). His generous prize of $300 got many people to write blogs on new, interesting ideas, and it was one of the main reasons I wrote this blog. I'm...
$. When we answer a query, we don't touch the stack at all., **, meaning that if we apply a set of updates and then a query, the answer to
thequery will be the, . Answer a query about $D$.
33.
[Tutorial] Supporting Queue-like Undoing on DS In many data structures, the operation of "undo" on the last update can be implemented easily: we can (usually) maintain a stack of the updates, where each update on the stack holds the memory cells it changed, and their original values. To undo an operation, just revert all changes from the top update on the stack. To maintain good complexity, we require the updates to operate in non-amortized time. I've seen this being used multiple times on DSU (without path compression).
If we imagine the updates as a sequence, then we can push an update to the end, and pop an update from the end by undo. Then, this sequence is a stack of updates. Here we discuss the idea of having a queue of updates: we can add a new update, or undo the oldest update still active. Specifically, this blogpost attempts to solve the following problem:
Given a data structure that can support some updates, some queries and an "undo" operation (each with their own time complexity), how can we create a data structu...
any sequence of updates, and a query afterwards, the result we want from the
query remains the same
34.
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...
35.
(Rolling) Range Sum Query of binomial coefficients This is absolutely a well known trick. However, I simply find no blogs discussing this (with a searchable title), so I hope to fill this gap in references.
This blog consists of one sentence
<blockquote>
Range Sum Query of binomial coefficients is almost doable in a MO's rolling manner.
</blockquote>
The details are easy to derive on your own. For the completness of the blog, they are included:
Consider the following simple range sum query problem on binomial coefficients
**Problem** Find the following sums , $B(l,r,n)=\sum_{i=l}^{r}\binom{n}{i}$, evaluated mod a prime.
It seems like there is no simple and realistic way to answer a single query any faster than $O(r-l+1)$. (Though as pointed out by [user:Elegia,2025-01-07], you could do something in $O(\sqrt{r-l})$ times log factors using some P-recursive concepts).
However, in many situations where we need to answer many such queries (e.g. as part of a counting process), the values of $B(l,r,n)$ we need chang...
(Rolling) Range Sum Query of binomial coefficients, Range Sum Query of binomial coefficients is almost doable in a MO's rolling
manner, Consider the following simple range sum query problem on binomial coefficients, It seems like there is no simple and realistic way to answer a single query any
faster than $O(r-l, })$ precalculation and $O(\sqrt{n})$ per query, for queries with $n'\leq n$.
36.
[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 ...
LIS Query](https://judge.yosupo.jp/problem/static_range_lis_query) * [Ptz
Winter 2014. Circle Clique, a similar 2D query and it can also be solved with Fenwick trees. Note that
same strategy works for, the upper edge of dotted box and ends in the lower edge of dotted box. This is
a 2Dquery, and can
37.
Hybrid Tutorial #-1: Heavy-Light Decomposition **[Here](https://www.youtube.com/watch?v=_G_LMuLWMaI&list=PLDjGkpToBsYDx4GWu2u87sTqt6ICELz-T) is a playlist of all hybrid tutorials I've done.**
# "Intro"
_Timestamp: [00:00](https://youtu.be/_G_LMuLWMaI)_
Hi! Definitely not inspired by [this comment](https://codeforces.me/blog/entry/81086?#comment-675431), I've decided to try something that seems relatively novel — combining a blog and video tutorial into one, in a "hybrid" fashion. Both should be usable independently, but they will have the same "flow" and structure so you can reference both for concepts that are harder to grasp, and the two will supplement each other. The goal of these is to be **complete** — beneficial for both video and blog lovers, as well as full of enough information that anyone without much of an idea of what the concept is should be able to fully understand. There will be code as well, however, I very highly recommend not looking at it, but rather working out the implementation for yours...
`lca` is done with binary lifting and defined in, /QRYLAND) (CodeChef) - [MONOPLOY](https://www.codechef.com/problems/MONOPLOY)
(CodeChef) - [QUERY, And you're done! Now you can call `query` and `update` with the endpoints of
paths (also $0, This is exactly the same as computing a query, but replace `seg_query_header`
with, To get the answer for the full query, we combine the answers for the two
vertical chains and, ~~~~~ long long query(int u, int v) { int lc = lca(u, v); long long val =
query_chain(u, lc
38.
On "is this greedy or DP", forcing and rubber bands #### Introduction
When it comes to "problem-solving techniques", there are roughly 3 levels:
1. Concrete algorithms (Kruskal's algorithm, Li-Chao tree, fast Fourier transform)
2. General patterns (dynamic programming, greedy, square-root decomposition)
3. Meta-strategies ("how do I even go about solving this problem?")
There is some grey area, but in general this classification works well.
[Many tutorials](https://codeforces.me/catalog) have been written about ideas that fall into 1 or 2.
But very little has been written about the third category. On the catalog, I think the
only blogs that really qualify are [this](62730) and [this](20548). There is also
[this](92248?#comment-809401) valuable comment. As to why there is so little written,
I think I can identify two reasons.
- Most strong contestants don't really consciously think about these.
After solving a problem with FFT, it's hard not to know you used FFT.
If you used DP, even if you did it without thinki...
39.
[Tutorial] Range minimum query in O(1) with linear time construction <spoiler summary="TL; DR">
Build a sparse table over blocks of size $b = 30 \geq \log{n}$. Now we only need to answer queries of size smaller than $b$. For that, simulate a minqueue of size $b$ over the array, and store a mask of the elements that are currently active in the minqueue. Let $\text{mask[r]}$ be the minqueue mask when the simulation is at position $\text{r}$. Now we can see that, if $r-l+1 \leq b$, then `query(l, r) = r - most_significant_set_bit(mask[r] & ((1<<(r-l+1))-1))`.
~~~~~
template<typename T> struct rmq {
vector<T> v;
int n; static const int b = 30;
vector<int> mask, t;
int op(int x, int y) { return v[x] < v[y] ? x : y; }
int msb(int x) { return __builtin_clz(1)-__builtin_clz(x); }
int small(int r, int sz = b) { return r-msb(mask[r]&((1<<sz)-1)); }
rmq(const vector<T>& v_) : v(v_), n(v.size()), mask(n), t(n) {
for (int i = 0, at = 0; i < n; mask[i++] = at |= 1) {
at = (at<<1)&((1<<b)-1);
while (at and op(i, i-msb(at&-at)) == i) at ...
[Tutorial] Range minimum query in O(1) with linear time construction, $\mathcal{O}(g)$ query time., $r-l+1 \leq b$, then `query(l, r) = r - most_significant_set_bit(mask[r] &
((1<<(r-l+1))-1))`., Table and Sqrt-tree, but a little slower than Segment Trees. Its query time
seems to be roughly the, sparse table query) int ans = op(small(l+b-1), small(r));, , if $r-l+1 \leq b$, then `query(l, r) = r - most_significant_set_bit(mask[r] &
((1<<(r-l+1))-1, - Query range is large and doesn't align with block limits:, - Query range is too small, so it fits entirely inside one block:, // 'x' and 'y' are the blocks we need to query over int x = l/b+1, y = r/b-1;, Here I'll share an algorithm to solve the classic problem of Range Minimum Query
(RMQ): given a, Note that, on the second case, we can use our sparse table to query the middle
part (in gray). In, Obviously, $\text{query}(6, 6) = 6$. Since $\text{query}(5, 6) = 5 \neq \text{
query}(6, 6)$, we can, Query time for $10^6$ queries (ms):, So, if our query indices happen to align with the limits of the blocks, we can
find the answer. But, ] = op(t[n/b*(j-1)+i], t[n/b*(j-1)+i+(1<<(j-1))]); } // query(l, r) returns the
actual minimum of v
40.
Good Bye 2025 Editorial We'd like to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated!
<!-- You lost the game. -->
<spoiler summary="Rate the contest">
- Great contest:
- Good contest:
- Average contest:
- Bad contest:
</spoiler>
---
<spoiler summary="Did Franklin (from problem D) succeed in massacring a village of innocent elves like Frieren and Dilhan (from problem E)?">
The official lore is that he got lost in a forest of oddly colored Christmas trees (from problem F) and decided instead to write this editorial.
</spoiler>
<!-- ########### -->
<!-- #PROBLEM A# -->
<!-- ########### -->
<h2>[problem:2178A]</h2>
<spoiler summary="Did you like the problem?">
- Great problem:
- Good problem:
- Average problem:
- Bad problem:
- Did not solve:
...
found by a range XOR query over $[x_j, y_j]$ because any chord not
intersecting chord $j$ will either
Tutorial of Good Bye 2025
41.
Squarepoint Challenge (Codeforces Round 1055, Div. 1 + Div. 2) Editorial Thank you for your participation!
Problem A, B were authored by [user:djm03178,2025-10-03].
Problem C was authored by [user:As_dfsdf,2025-10-03].
Problem D was authored by [user:qwerasdfzxcl,2025-10-03].
Problem E, F, G, H1, H2 were authored by [user:ko_osaga,2025-10-03].
[problem:2152A]
<spoiler summary="Spoiler">
[tutorial:2152A]
</spoiler>
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
set<int> s;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
s.insert(x);
}
cout << s.size() * 2 - 1 << '\n';
}
}
~~~~~
</spoiler>
[problem:2152B]
<spoiler summary="Spoiler">
[tutorial:2152B]
</spoiler>
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
wh...
) - 1, 1, seq); cout << query() << "\n"; int q; cin >> q; while (q, int query() { return tree[1].M[1].nxt[0] / 2; }
42.
IICPC Global Codefest 2026 Hello!
Registrations for IICPC Global Codefest 2026 are opening soon. This is the first global edition of India's largest offline competitive programming competition.
**About IICPC Codefest**
IICPC (Intercollegiate Informatic and Competitive Programming Camp) is an academic and industry-backed organization focused on identifying, evaluating, and nurturing high-potential students in competitive programming, algorithms, and computer science fundamentals through rigorously designed, large-scale competitive examinations and camps.
We organize Codefest, a multi-stage competitive programming competition conducted across India. This year, we are opening participation to international students from 50+ countries.
**The prelims is individual participation, and online for international students. The deadline for registration is 15th January, 23:59 IST**.
<img src="https://i.ibb.co/bRJt7y44/codefest-banner.png" height="50">
**Competition Structure**
Prelims — Janua...
43.
Editorial for Codeforces Round #761 (Div. 2) Thanks for participating, hope you enjoyed the problems! Implementations for the problems are chosen randomly among testers, and I made some changes to their codes (for example, deleted meaningless comment lines). Please do not hesitate to provide feedback in the comments, so I can improve in setting problems next time.
**UPD**: Sorry but there is a checker bug in problem E. All submissions of problem E will be rejudged soon.
**UPD2:** Rejudge done, the round remains rated.
<spoiler summary="Statistics">
Number of FST for rated participants:
- Problem A: $29$
- Problem B: $90$
- Problem C: $12$
- Problem D1: $4$
- Problem D2: $0$
- Problem E: $6$
Number of AK: $22$
Number of clarifications: $85$
</spoiler>
[problem:1617A]
<spoiler summary="Hint">
When is the lexicographically smallest permutation of $S$ (i.e. the sorted string) not the answer?
</spoiler>
<spoiler summary="Solution">
If there are no occurrences of `a`, `b` or `c` in $S$, ...
Consider splitting the $n$ players into groups of $3$ (and query each, Firstly query ($1, 2, 3$), ($4, 5, 6$), $\dots$, ($n-2, n-1, Key observation: if result of query ($a, b, c$) $\ne$ result of query, just naively query for each unknown role in the tuple, since we won't use more
than $2$ queries, std; int query(int a, int b, int c) { cout << "? " << a << ' ' << b << ' ' <<
c << endl, , we instantly know the roles of the two players that are only included in one
query — one is a, After we know one crewmate and one impostor (let's call them $a$, $d$), we can
query these two, In each query, reduce half of the possibilities. , Let's say we picked ($i, i+1, i+2$) and ($i+3, i+4, i+5$). Then, we query
($i+1, i+2, i+3$) and ($i, The first step is to query players ($1, 2, 3$), ($2, 3, 4$), $\dots$, ($n-1, n,
1$), ($n, 1, 2$).
Tutorial of Codeforces Round 761 (Div. 2)
44.
[Tutorial] Proving the inverse Ackermann complexity of Union-Find #### Introduction
Most of us are familiar with the union-find data structure and the two optimizations one can do on it: _union by rank_ and _path compression_. Most tutorials will introduce these methods and state that if both optimizations are used, the complexity will be $\mathcal{O}((n + m) \alpha(n))$. Here, $n$ and $m$ are the number of vertices and queries respectively. What is $\alpha$? Generally, we are told that $\alpha$ is some mysterious function that grows very slowly: $\alpha(N) < 5$ where $N$ is the number of subsets of particles in the observable universe and whatnot. What it is is usually not clarified very much. And there is typically no proof (or intuition and other such justifications) as to why the complexity is like that: usually we're told that the complexity analysis is quite long and complicated. At the time of writing, both [cp-algorithms](https://cp-algorithms.com/data_structures/disjoint_set_union.html) and [Wikipedia](https://bit.ly/3EvnzrI) are like th...
more descendants than there are vertices in the graph. Thus in any query we
have to traverse only, visited during some `find` query. Notice that, for example, the red find-path
jumps over some vertices, **Find-paths and find-edges.** Imagine what vertices are visited in some "find"
query. If we call, After a query to `find(u)`, for all vertices that used to be on the path from
$u$ to the current
45.
Codeforces Round #723 (Div. 2) Editorial [problem:1526A]
------------------
Setter: [user:antontrygubO_o,2021-05-28]
Preparer: [user:errorgorn,2021-05-28]
<spoiler summary="Hint 1">
Notice that the array size is even length. Usually in such problems, we would split the array into $2$ equal parts. Can you figure out what those $2$ parts are?
</spoiler>
<spoiler summary="Hint 2">
We sort the array and split it into the big half and the small half.
</spoiler>
<spoiler summary="Solution">
The main idea is that we can split the numbers into the two halves, the big half and small half, we can place the bigger half at the odd positions and the smaller half at the even positions.
This works because the smallest big number is larger than the biggest small number. Hence, the mean of any two small numbers is smaller than any big number, and the mean of any two big numbers is bigger than any small number.
</spoiler>
<spoiler summary="Code (C++)">
```c++
//雪花飄飄北風嘯嘯
//天地一片蒼茫
#include <bits/stdc++.h>
#inc...
# Now, we assume P[c] = 1 # There always exists another index d such that query
(a, b, d, We will spend the first queries to find a tuple $(a,b,c)$ such that the return
value of thisquery, d = -1 if len(d2) == 1: d = d2[0] elif len(d2) == 2: temp1 = query(a, c, int hv=(*m.begin()).fi; if (sz(m[hv-1])>=2){ //there must be exactly 2 if (query
(m[hv][0],m[hv, long long query(int S, int E){ push(); if(s == S && E == e) return val; else
if(E <= m
Tutorial of Codeforces Round 723 (Div. 2)
46.
Editorial of Global Round 15 We hope you liked the problems!
Before we go ahead with the editorial, let us make some general comments about this round.
Problems A, B, C, D, E, F are "div 2" problems, while problems G, H, I are meant to be solved by Grandmasters.
Overall, our goal was to provide a problemset that could be enjoyable for a wide range of participants and such that the winner could solve all the problems.
There were three big "jumps" in the difficlty gaps between consecutive problems.
Problems A and B are meant to be easy, many contestants have the skills and the techniques to attack them (and, maybe, to solve them).
Problems C, D, E, F are gradually harder but the difficulty gap between C and F is not as large as usual (and this is reflected in the score distribution).
The same holds for problem G, H, I; the difficulty gap between G and I is relatively small (but there is a big score difference because coding I is much harder).
Sadly, we discovered 14 minutes into the round that problem I...
Ask a query with all points. The result is a simple expression in terms
Tutorial of Codeforces Global Round 15
47.
A Beautiful Technique for Some XOR Related Problems ## Inspiration
I'm very excited about this blog, as it took me quite a lot of effort and scavenging through the internet to completely grasp the concept of this technique(That's probably because I have almost zero knowledge in Linear Algebra or I'm just plain dumb). So I feel like I genuinely conquered a challenge, and I really want to share it with someone. But there's no way my CP friends circle will believe it, they'll think I'm just trying to show off :P
So here I am, sharing it on CF. I also created a [personal blog](https://drschwad.github.io/), so that if I ever feel like sharing something again(not only about CP), I can write a blog there. I also added this same post [there](https://drschwad.github.io/2019-08-06-z2-space-xor-trick/), you can read it there if you prefer dark theme. I'll be pleased to hear any thoughts on the blog or if I can improve it in some way ^\_^
## Introduction
Since it concerns Linear Algebra, there needs to be a lot of formal stuff going on ...
remember the basis vectors of that prefix. Then, iterate through the queries.
To answer aquery, we, technique can also be used in some online-query problems: the problem can
provide queries of first, if (t == 1) insertVector(k); else printf("%d\n", query(k)); }, int query(int k) { int mask = 0;
48.
[Tutorial] Theoretically Faster HLD and Centroid Decomposition This blog was going to be translation of $[1]$ (which is in Chinese) but I think I ended up deviating too much from the source material that it would not be appropriate to call this a translation. Anyways, I am honestly amazed by how ahead of its time this paper is. In its abstract, it starts by saying that the state of art for tree path queries is $O(n \log n + q \sqrt n \log n)$, which I honestly can't fathom how one would arrive, then proceeds to claim that it has found an $O((n+q) \log n)$ algorithm. All the more, in 2007.
While I was in the process of writing this blog, [user:smax,2022-07-18] sniped me and posted $[9]$. However, we will focus on static trees **only**.
Thanks to [user:oolimry,2022-07-18], [user:everule,2022-07-18] and [user:timreizin,2022-07-18] for proofreading.
Note to reader: I am expecting the reader to be familiar with what a splay tree and HLD is. You do not really need to know why splay trees are $O(\log n)$ amortised but you should know what the z...
actually perform queries in our HLD structure. We know from HLD+segment tree
ourquery loop is for, the underlying splay tree as the earlier section. If we need to query the
prefix of a splay tree, - if $a$ and $b$ are in the same heavy chain, query $in[a]$ to $in[b]$ - if $a$
is deeper than $b, Benchmarks when there are all $4$ query types., Benchmarks when there are only query types $1$ and $2$., Of these $3$ queries, only the first query type is a sub-array query on the
heavy chain, the rest, With our normal HLD+segment tree query, we can easily handle both path and
subtree queries $[7]$.
49.
Algorithm Gym :: Everything About Segment Trees In the last lecture of **Algorithm Gym** ([Data Structures](/blog/entry/15729)), I introduced you Segment trees.
In this lecture, I want to tell you more about its usages and we will solve some serious problems together.
[cut]
Segment tree types :
Classic Segment Tree
--------------------
Classic, is the way I call it. This type of segment tree, is the most simple and common type. In this kind of segment trees, for each node, we should keep some simple elements, like integers or boolians or etc.
This kind of problems don't have update queries on intervals.
Example 1 (Online):
Problem [problem:380C] :
For each node (for example $x$), we keep three integers :
1.`t[x]` = Answer for it's interval.
2. `o[x]` = The number of $($s after deleting the brackets who belong to the correct bracket sequence in this interval whit length `t[x]`.
3. `c[x]` = The number of $)$s after deleting the brackets who belong to the correct bracket sequence in this interval whi...
keep the answer to the $i-th$ query in $ans_i$ ., And the function for the second query is :, First of all, we will read all queries, store them and for each query of type
$A$, we will insert, For each query of first of type, if $u$ is in subtree of $v$, its value
increasing by $x + (h_u, Function for 2nd type query :, We can use interval $1, 2, ..., k$ instead of that (each query is running in
this interval, in code
50.
Unofficial Editorial for Educational Round 95 (Div. 2) Here are my approaches to the problems today:
#### [problem:1418A]
Since the second trade is the only way to get coal, we clearly need to perform the second trade $k$ times. So how many times do we need to do the first trade? We can see that in order to end up with enough sticks and coal by the end, we need to obtain $ky + k$ sticks ($ky$ to convert to coal and $k$ to save as sticks). Since the first trade really just gives us $x - 1$ new sticks each time, we'll need to make $\displaystyle \left \lceil \frac{ky + k - 1}{x - 1} \right \rceil$ first trades ([reference to floor and ceiling functions](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions) for anyone unfamiliar).
For implementation details, note that for positive integers $a$ and $b$, $\displaystyle \left \lceil \frac{a}{b} \right \rceil = \left \lfloor \frac{a + b - 1}{b} \right \rfloor$. Code: [submission:92851684]
#### [problem:1418B]
We can think about the problem as follows: we want to order the $a_i$ to...
range query on $y_{low}$, $y_{high}$, and $b$ where we want to find the
smallest factor $a$ of any $y
51.
Mo's Algorithm on Trees [Tutorial] Introduction
------------
Mo's Algorithm has become pretty popular in the past few years and is now considered as a pretty standard technique in the world of Competitive Programming. This blog will describe a method to generalize Mo's algorithm to maintain information about paths between nodes in a tree.
Prerequisites
-------------
Mo's Algorithm — If you do not know this yet, read this amazing [article](http://blog.anudeep2011.com/mos-algorithm/) before continuing with this blog.
Preorder Traversal or DFS Order of the Tree.
Problem 1 — Handling Subtree Queries
------------------------------------------
Consider the following problem. You will be given a rooted Tree $T$ of $N$ nodes where each node is associated with a value $A[node]$. You need to handle $Q$ queries, each comprising one integer $u$. In each query you must report the number of distinct values in the subtree rooted at $u$. In other words, if you store all the values in the subtree rooted...
In this case, our query range would be $[EN(u), ST(v)]$ + $[ST(P),ST(P)]$., In this case, our query range would be $[ST(u), ST(v)].$ Why will this work?, Let a query be $(u,v).$ We will try to map each query to a range in the
flattened array. Let $ST(u
52.
Codeforces Round #703 (Div. 2) Editorial [problem:1486A]
<spoiler summary="Hint1">
What's the lower bound for the amount of blocks for the answer to be $\texttt{YES}$?
</spoiler>
<spoiler summary="Hint2">
Check the predicate for every prefix.
</spoiler>
<spoiler summary="Solution">
Let's consider the smallest amount of blocks we need to make the first $i$ heights ascending. As heights are non-negative and ascending the heights should look like $0, 1, 2, 3, ..., i - 1$, so the minimum sum is $\frac{(i - 1) \cdot i}{2}$. It turns out that this is the only requirement. If it's not the case for every prefix the answer is $\texttt{NO}$ because we can't make some prefix ascending. Otherwise the answer is $\texttt{YES}$ because you can move the blocks right till there is at least $i$ blocks in the $i$-th stack and this would make the heights ascending.
</spoiler>
Solution using C++: [submission:107892022]<br>
Solution using Python: [submission:107892053]
[problem:1486B]
<spoiler summary="Hint1">
Is proble...
find the smallest $m$ such that the answer to the query $[smax, m]$ is $smax$.
The smallest such $m
Tutorial of Codeforces Round 703 (Div. 2)
53.
Efficient and easy segment trees This is my first attempt at writing something useful, so your suggestions are welcome.
Most participants of programming contests are familiar with segment trees to some degree, especially having read this articles http://codeforces.me/blog/entry/15890, http://e-maxx.ru/algo/segment_tree (Russian only). If you're not — don't go there yet. I advise to read them after this article for the sake of examples, and to compare implementations and choose the one you like more (will be kinda obvious).
Segment tree with single element modifications
==================
Let's start with a brief explanation of segment trees. They are used when we have an array, perform some changes and queries on continuous segments. In the first example we'll consider 2 operations:
1. modify one element in the array;
2. find the sum of elements on some segment.
[cut]
.
### Perfect binary tree
I like to visualize a segment tree in the following way: [image link](http://i.imgur.com/GGBmcEP....
54.
CSES Range Queries section editorial **UPD:** some video editorials on range query data structures: [youtubePlaylist](https://www.youtube.com/playlist?list=PLb3g_Z8nEv1isaHPaXL1j-pSo60812JtY)
Hello Codeforces, In this blog I will try to write a well detailed editorial for the CSES Range Queries section. The motivation for this editorial comes from https://codeforces.me/blog/entry/70018.
Quoting [user:icecuber,2020-05-09] "I think [CSES](https://cses.fi/problemset/) is a nice collection of important CP problems, and would like it to have editorials. Without editorials users will get stuck on problems, and give up without learning the solution. I think this slows down learning significantly compared to solving problems with editorials. Therefore, I encourage others who want to contribute, to write editorials for other sections of CSES."
So here I am writing an editorial for the range queries section.
If you find any error or maybe have a better solution to some problem please do share.
Range Sum Queries I
=...
Build a range sum query segment, );} SegmentTree < int > rangeMinQueries(dataVector,INT_MAX,small); For query of
type 1, **UPD:** some video editorials on range query data structures:
[youtubePlaylist](https, ;} SegmentTree < ll > rangeSumQueries(dataVector,0,sum); For query of type 1 :
rangeSumQueries.update(idx, > : number of employees with the salary i
We may now build a range sum query segment tree on this, AC code : https://ideone.com/vBZpYx
Time complexity per query is logN., ANSWER TO QUERY (x1,y1,x2,y2) : DP[x2][y2] — DP[x1-1][y2] — DP[x2][y1-1] +
DP[x1-1][y1-1], Can we use DP matrix to evaluate answers for every query?, Finally we have the answer to our query as DP[x2][y2] — DP[x1-1][y2] —
DP[x2][y1-1, So for every query simply output Prefix[R] — Prefix[L-1]., So here is the algorithm : For every range update query (l,r,u):
, Time complexity : O(N) to build prefix array and O(1) per query., Time complexity for build O(N*N) and time complexity per query is O(1).
AC code : https, Two possible ways are as follows :
1. Build a Range minimum query segment tree in O(N) time
55.
Codeforces Round #813 (Div. 2) Editorial Thanks for participating in the round, we hope you liked the problems!
<spoiler summary="Solve count predictions (official div. 2)">
Handle | A | B | C | D | E1 | E2 | F
--- | --- | --- | --- | --- | --- | --- | ---
[user:Vladithur,2022-08-13] | 16K | 8K | 3K | 900 | 500 | 50 | 4
[user:_dlbm17,2022-08-13] | 14K | 9K | 5K | 500 | ? | ? | ?
[user:thanhchauns2,2022-08-13] | 14K | 8K | 2K | 1K | 500 | ? | ?
[user:QuangBuiCP,2022-08-13] | 14K | 7K | 2K | 1K | 500 | 24 | 5
[user:welleyth,2022-08-13] | 16K | 10K | 4K | 1.5K | 600 | 130 | 2
[user:Kon567889,2022-08-13] | 14K | 10K | 5K | 2K | ? | ? | 5
</spoiler>
[problem:1712A]
<spoiler summary="Hint">
The smallest possible sum is $1 + 2 + \ldots + k$.
</spoiler>
<spoiler summary="Tutorial">
[tutorial:1712A]
</spoiler>
<spoiler summary="Solution">
~~~~~
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())
const ch...
// Get Answers while (ti >= 0 && queries[ti][0] == i) { ans[queries[ti][2]] -=
query(0, 0, int query(int v, int tl, int tr, int l, int r) { if (l >= r) return 0; if (tl
== l && tr == r
Tutorial of Codeforces Round 813 (Div. 2)
56.
Codeforces Round #638 (Div. 2) Editorial [problem:1348A]
<spoiler summary="Tutorial">
[tutorial:1348A]
</spoiler>
<spoiler summary="Solution">
~~~~~
#include <bits/stdc++.h>
using namespace std;
void solve(){
int N;
cin>>N;
//note: 1<<X means 2^X
//we put largest coin in first pile
int sum1=(1<<N), sum2=0;
//we put n/2-1 smallest coins in first pile
for (int i=1;i<N/2;i++)
sum1+=(1<<i);
//we put remaining n/2 coins in second pile
for (int i=N/2;i<N;i++)
sum2+=(1<<i);
cout<<sum1-sum2<<endl;
}
int main(){
int t; cin>>t;
while (t--)
solve();
}
~~~~~
</spoiler>
[problem:1348B]
<spoiler summary="Tutorial">
[tutorial:1348B]
</spoiler>
<spoiler summary="Solution">
~~~~~
#include <bits/stdc++.h>
using namespace std;
void solve(){
int N,K;
cin>>N>>K;
set<int>s;
for (int i=0;i<N;i++){
int a;
cin>>a;
s.insert(a);
}
//if more than K distinct numbers, print -1
if (s.size()>K){
cout<<-1<<endl;
return;
...
int query(int l,int r){ l--; pair res{INF,INF}; for(l+=N,r+=N;l>=1,r>>=1
Tutorial of Codeforces Round 638 (Div. 2)
57.
Huawei IOI Camp 2022 Hi. I'm organizing an online IOI-preparation camp in collaboration with Huawei.
Every day will be a 5-hour virtual contest, then my problem analysis, and sometimes a lecture.
There will be at least 4 contests and 2 lectures.
We will do some old IOI contests (2013?) from the [IOI archive](https://codeforces.me/blog/entry/104593), CEOI (2015-2016?), or maybe JOI/JOISC — to be decided this weekend.
I don't want to do recent years like 2021 because most participants already covered it.
The example lecture topics are those from Range Queries or Trees in [Usaco Guide Platinum](https://usaco.guide/plat).
The camp is free for IOI 2022 participants.
For everybody else, the video recordings will be posted on Youtube after the camp.
By participating you get the live experience (Discord, asking questions, competing with others, leaderboards).
**Dates**: 25.07-2.08 (updated)
**Time** of every analysis/lecture: [14:00 UTC / 16:00 CEST](https://www.timeanddate.com/worldclock...
58.
A simple introduction to "Segment tree beats" **This blog is just a back up of [http://codeforces.me/blog/entry/57319](http://codeforces.me/blog/entry/57319) to prevent this tutorial from discarding after [user:jiry_2,2018-10-17] is banned.**
Hi, I’d like to introduce a simple trick about segment tree in this blog as I promised in [this comment](http://codeforces.me/blog/entry/54750?#comment-387957). Sorry for the long delay, as a sophomore in Peking University, I've just finished a tired semester and a painful final exam. And now I finally have enough time to do a simple introduction to this interesting algorithm.
It may be a huge project for me since my English is not good. I think I will finish this blog in several steps and I will try to finish it as soon as possible :)
In China, all of the 15 candidates for the Chinese National Team are asked to write a simple research report about algorithms in informatics Olympiad, and the score will be counted in the final selection. There are many interesting ideas and algorit...
$\max(A_i - x,0)$. 3. For all $i \in [l,r]$, change $A_i$ to $x$. 4. Query for
$A_i$. 5.Query for, **Task 3**. And we can query for some other things:, 1. For all $i \in [l,r]$, change $A_{i}$ to $A_{i} + x$, $x$ can be a negative
number. 2.Query, The query for $B_i$ can be solved in $O(n \log^2 n)$ and the query for $C_i$
can be solved in $O(n
59.
Codeforces round #649 editorial ### [problem:1364A]
Let's start with the whole array. If every element in it is divisible by $x$, the answer is $-1$; if its sum isn't divisible by $x$, the answer is $n$. Otherwise, we must remove some elements. The key idea is that removing an element that is divisible by $x$ doesn't do us any benefits, but once we remove an element that **isn't**, the sum won't be divisible by $x$. So let the first non-multiple of $x$ be at index $l$, and the last one be at index $r$. We must either remove the prefix all the way up to $l$ or the suffix all the way up to $r$, and we'll clearly remove whichever shorter.
Code link: https://pastebin.com/j2Y8AJBA
Alternatively, we can notice that this means the answer is either a prefix or a suffix, so we can simply bruteforce them all.
### [problem:1364B]
TL;DR the answer contains the first element, last element, and all the local minima and maxima, where a local minimum is an element less than its 2 adjacents, and a local maximum is an e...
. Building our magic function with it turns out to be very easy. We'll just
return $query(i,z_0)$\&$query(i, The common idea is: if we find the index that contains $0$, we can query it
with every element in
Tutorial of Codeforces Round 649 (Div. 2)
60.
Caveats of using optimize("Ofast") with target("avx2") Hi everyone!
As you may know, it is often recommended to put these lines in your header:
```cpp
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
```
And they're usually great!<sup>[1]</sup> Well, until they aren't. For last 2-3 days I was riddled with the issue that [CP-Algorithms Library](https://lib.cp-algorithms.com) would perform very well on Library Checker, but whenever I tried to also apply it on Codeforces, it will fail to speed up the code, and sometimes would even make it much slower. As I finally figured out the cause, I'd like to write a blog about it, so that other people don't waste as much time.
Mitigating these issues improved my running time on [problem:1975G] from **1530 ms** in [submission:316602668] to **203 ms** in [submission:352602775].
##### Tl'dr
See the "Takeaway" section at the bottom.
[cut]<br>
##### Example problem
I will reproduce the issue on a simple example:
<hr>
**[problem:911G]**: You are given an...
query is to go over $a_i$ for $l \leq i \leq r$ such that $a_i = x$ and change
it to $a_i = y$.
61.
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...
First we solve the problem with only 1 query on the whole array $A$.
Tutorial of Codeforces Global Round 21
62.
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...
13172 UVA (5) //6*DJ per query + permutations, http://codeforces.me/contest/46/problem/B (3) //[EASY][SEARCH-EACH-QUERY], http://www.spoj.com/problems/NNS/ (5) Closest points query [fake geometry]
{__128}[NICE], http://www.spoj.com/problems/RTREE/ 3 //longest path tree — query
63.
Theoretical grounds of lambda optimization Hi everyone!
This time I'd like to write about what's widely known as "Aliens trick" (as it got popularized after 2016 IOI problem called [Aliens](https://ioinformatics.org/files/ioi2016problem6.pdf)). There are already some articles about it here and there, and I'd like to summarize them, while also adding insights into the connection between this trick and generic Lagrange multipliers and Lagrangian duality which often occurs in e.g. linear programming problems.
Familiarity with a [previous blog](https://codeforces.me/blog/entry/98524) about ternary search or, at the very least, definitions and propositions from it is expected.
Great thanks to [user:mango_lassi,2022-01-01] and [user:300iq,2022-01-01] for useful discussions and some key insights on this.
Note that although explanation here might be quite verbose and hard to comprehend at first, the algorithm itself is stunningly simple.
Another point that I'd like to highlight for those already familiar with "Aliens tr...
,\dots, a_n$ and $q$ queries. Each query is a triple $l,r,k$ and you need to
compute the maximum sum on
64.
Algorithm Gym :: Graph Algorithms Welcome to the new episode of [user:PrinceOfPersia,2015-01-31] presents: Fun with algorithms ;)
You can find all the definitions here in the book "Introduction to graph theory", Douglas.B West.
[cut]
Important graph algorithms :
DFS
---
The most useful graph algorithms are search algorithms. DFS (Depth First Search) is one of them.
While running DFS, we assign colors to the vertices (initially white). Algorithm itself is really simple :
~~~~~
dfs (v):
color[v] = gray
for u in adj[v]:
if color[u] == white
then dfs(u)
color[v] = black
~~~~~
Black color here is not used, but you can use it sometimes.
Time complexity : $O(n + m)$.
#### DFS tree
DFS tree is a rooted tree that is built like this :
~~~~~
let T be a new tree
dfs (v):
color[v] = gray
for u in adj[v]:
if color[u] == white
then dfs(u) and par[u] = v (in T)
...
Query :, Query:
65.
Counting primes in $\tilde{{\cal O}}(n^{2/3}\,\,)$ _Some time ago I read [this](https://projecteuler.net/thread=10;page=5#111677) post about calculating prime-counting function in $O(n^{3/4})$ (you have to solve problem 10 to access the post). And in the end author mentioned that there is $O(n^{2/3})$ solution. To my surprise I was not able to find any more or less relevant information on the internet about that. Maybe there is a beautiful blog describing all of this on 10-th page of google, but I decided to collect information I found in this post._
###Prerequisites
- From [distribution of prime numbers](https://en.wikipedia.org/wiki/Prime_number_theorem) $n$-th prime is approximately $n \ln n$, I will use it while proving complexities.
###$\tilde O(n^{3/4})$
Let's start with $O(n^{3/4})$ approach from Project Euler. We will need some definitions:
- $\pi(n)$ — prime counting function, i.e. number of primes which are not greater than $n$.
- $S(n, a)$ — suppose we take all numbers from $1$ to $n$ and sieve them w...
// the order in fenwick will be reversed, because prefix sum in a fenwick is
just onequery
66.
1/phi Halving in Interactive Tree Problems Thanks to [user:toxicpie9,2025-04-22] for proofreading and emotional support.
Recently, I was thinking about JOISC 2025 Space Thief. And there is a part where you need to do divide and conquer on a tree, where you need to split the edges of the tree into two components where the edges are both connected.
Basically, we consider an interactive problem on a tree where there is a hidden edge. We are allowed to ask queries of the form $(v,N_v)$ where $v$ is a vertex of the tree and $N_v$ is a set of neighbouring edges of $v$. Then the query returns to us whether the hidden edge is in the subtree of one of $N_v$ when we root the tree at $v$.
We maintain a set of edges that the hidden edge can be in. In each query, we try to split the set of edges into two parts and ask a query to separate them.
In the worst case, we replace the set of edges by the larger component.
Let $R$ be the maximum ratio of the larger component.
In [this blog](https://codeforces.me/blog/entry/120446)...
The restriction on being allowed to query only subtrees in funnyhat also kind
of doesn't matter, We maintain a set of edges that the hidden edge can be in. In each query, we
try to split the set
67.
Tricks Which Will Increase Your Rating! Hello Codeforces! I got some interesting tricks to share with you.
### 1. a_i := (a_i + x)%mod Range Updates, Max Range Queries
Apply usual range addition, but after each update run the following code:
```cpp
void normalize(int l, int r) {
while(getmax(l, r).max >= mod) {
set(getmax(l, r).pos, getmax(l, r).max%mod);
}
}
```
What is the complexity of this code? We all know that each time we %%=mod$ number which is $\geqslant mod$ it halves, that means each number will be updated $O(log)$ times, we will perform $O(n\cdot\log{n}\cdot\log{a})$ operations in total. So each update will be $O(\log{n}\cdot\log{a})$ amortized!
### 2. $O(\log^2{\log{n}})$ Segment Tree
Segment tree queries are queries on path. Instead of doing them in the usual brute force-ish way we can use HLD! Since maximum path length is $2\cdot\log{n}$, thus operations are now operations are $O(\log^2{\log{n}})$, which is better than $O(\log{n})$.
### 3. Faster Dinic's
We know t...
68.
General ideas **// Finally translated!**
Hi everyone!
Do you like ad hoc problems? I do hate them! That's why I decided to make a list of ideas and tricks which can be useful in mane cases. Enjoy and add more if I missed something. :)
[cut]<br>
**1. Merging many sets in $O(n\log{n})$ amortized.** If you have some sets and you often need to merge some of theme, you can do it in naive way but in such manner that you always move elements from the smaller one to the larger. Thus every element will be moved only $O(\log{n})$ times since its new set always will be at least twice as large as the old one. Some versions of DSU are based on this trick. Also you can use this trick when you merge sets of vertices in subtrees while having dfs.
**2. Tricks in statements, part 1.** As you may know, authors can try to hide some special properties of input to make problem less obvious. Once I saw constraints like $\relax 1 \leq a \leq b \leq 10^5, \dots, ab \leq 10^5$. Ha-ha, nice joke. It is actually...
block you can add elements from its end to the end of the array. If you found
some right end ofquery
69.
[Contest] Statement Not Found: Season 2 #### Do you think you can solve CP problems without reading the problem statements? Let's find out!
On [August 28, 2022 (Sunday) 19:30-22:00 GMT+8](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Statement+Not+Found+-+Season+2&iso=20220828T1930&p1=122&ah=2&am=30), I will hold an unofficial fun contest called Statement Not Found. As you can deduce from the title, there will be no problem statements (except title and samples). Your goal is to collect as many points as possible within 2.5 hours :)
Obviously, this round is **unrated**. It is somewhere between April Fools contest and a legitimate contest.
The contest will be OI-style, meaning there will be no time penalty. You are allowed to use any resources online to help solve the problems. There will be **12** problems.
**Scoring Distribution:** 200-400-700-700-700-800-800-900-1100-1100-1100-1500 (Total: 10000)
**Please read all problems** as problem difficulty is very subjective and a 1100-point problem might b...
70.
Finding a billion factorials in 60 ms with SIMD Hi everyone!
_This blog is not about asymptotic optimization. Refer to [this comment](https://codeforces.me/blog/entry/63491?#comment-474051) for those._
There is a problem on Library Checker that goes as follows:
<hr>
**[Many Factorials](https://judge.yosupo.jp/problem/many_factorials)**: You're given $n_1,\dots,n_t$, where $t \leq 10^5$. For each $i$, find $n_i! \bmod M$, where $M = 998\;244\;353$.
<hr>
In this blog, we will learn how to solve this task in 61 ms, without precalc and **without** FFT. That's right, we will take the dumbest solution we can imagine, and will improve its constant factor until its decent enough. How much decent? Well, let's use the following baseline:
<spoiler summary="Naive solution">
```cpp
vector<int> facts(vector<int> args) {
const int block = 1 << 16;
vector<int> args_per_block[mod / block + 1];
vector<int> res(size(args));
for(auto [i, x]: args | views::enumerate) {
args_per_block[x / block].push_b...
a lot of strain on storing these queries, as well as actually multiplying the
sub-query results
71.
Efficient 3D Convex Hull Tutorial _Warning: The following contains graphic depictions of geometry, precision errors, and degenerate cases. Viewer discretion is advised._
### Prerequisites
I assume the reader is familiar with:
- 2D Convex Hulls
- 3D Vector Operations (dot and cross products)
### Introduction
Recall that in the 2D convex hull problem, you are given a set of 2D points, and you must compute the smallest convex polygon containing all the given points. By convex, we mean that for any two points $A$ and $B$ inside the polygon, the entire line segment $AB$ is also inside the polygon.
The problem in 3D is completely analogous. You are given $n$ 3D points, and you must compute the smallest convex polyhedron containing all the given points. Similarly, a polyhedron is convex if for any two points $A$ and $B$ inside the polyhedron, the line segment $AB$ is also inside the polyhedron.
In the 2D case, it is more obvious what the output is. We can simply output a circular list of vertices on the ...
72.
3 Hard Interactive Problems Hi. I think these are nice medium-hard interactive problems. I will discuss solutions in a stream today at https://www.twitch.tv/errichto.
UPD, recording is here https://youtu.be/9oEihYrAR5kUPD and I added text solutions in this blog.
P1. **Mostly A** — You're given two integers $N$ and $K$ ($N \leq 50\,000$, $K \leq 10$). You need to find a hidden string of length $N$ with lowercase English characters a-z. At most $K$ characters are different than 'a'. You can choose your own string of length $N$ and you will get info YES/NO whether your string is lexicographically smaller than the hidden one. There is no explicit limit on the number of queries. There's still some time limit (say, 2 seconds).
Hard version: Minimize the number of queries.
<spoiler summary="slow solution">
It seems reasonable to discover characters one by one from left to right.
Let's say that we already know the prefix `raay` and we're looking for the fifth character.
We can binary search it in $...
character is at most `m`. We need $N \cdot \log 26$ queries, and every query
prints a string of length $N, from all queries so far, then we need to query the $X/2$-th lexicographically
smallest of those strings.
73.
Good Bye 2016 — hints and codes You can download my codes to all problems [here](http://www.filedropper.com/codes_1).
I will write a full editorial in the next few days.
Now you can read hints and short solutions.
[problem:750B]
<spoiler summary="hint">
Create a variable that will denote your current distance from the North Pole.
What are allowed values of this variable?
When can't we go West or East?
</spoiler>
[problem:750C]
<spoiler summary="hint1">
Let $x$ denote the initial rating (or his final rating, whatever is easier for you to think about).
The information that Limak is in some division in the $i$-th contest gives us some inequality for $x$.
Can you see it?
</spoiler>
<spoiler summary="hint2">
For every contest we know that the current rating is $x$ increased by some prefix sum of c_i (changes of rating).
If Limak is in the division 1, we have inequality x+prefSum >= 1900 so we have x >= 1900-prefSum.
If Limak is in the division 2, we have inequality x_prefSum <= 1899 so it is ...
Tutorial of Good Bye 2016
74.
Merging Queries Trick Credits to [user:VPurice,2022-03-07] for teaching me this trick.
#### Introduction
Recently I learnt an interesting trick I wanted to share with others. I'm not sure if this trick is well known, but I didn't know about it and didn't find any other articles on it so decided to write this blog.
#### Problem statement
We have a connected undirected graph with $n$ nodes and $m$ edges between them, each node having a value $w_i$ ($1 <= n, m <= 10^5$), ($1 <= w_i <= 10^9$).
Let's denote $f(a, b)$ as the minimum value of a node on a path from node $a$ to node $b$.
We have to answer $q$ queries about this graph. Each query contains $2$ nodes $a$, $b$ and asks for the maximum $f(a, b)$ over all possible paths from node $a$ to node $b$. ($1 <= q <= 10^5$).
#### Notes
This problem can be solved in another (more optimal) way, which is described in these comments:
[1](https://codeforces.me/blog/entry/100666?#comment-893646), [2](https://codeforces.me/blog/entry/100666?...
are responsible for a query then the answer for the query is the weight of the
other node, otherwise, through all queries the node is responsible for and check if it also appears
in thequery of the other, We have to answer $q$ queries about this graph. Each query contains $2$ nodes
$a$, $b$ and asks for
75.
Codeforces Round #616 Editorial Hello everyone, this is the editorial for [contest:1290] and [contest:1291]! Along with the solution to each problem, we will have the theme and easter egg solution as well! I hope you all enjoyed our problems ( ´ ▽ ` )b
[problem:1291A]
Author: [user:265918,2020-02-02]
<spoiler summary="Tutorial">
[tutorial:1291A]
</spoiler>
<spoiler summary="Implementation">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n; cin >> n;
string s; cin >> s;
int odd = 0;
for (char c : s) if ((c - '0') & 1) odd++;
if (odd <= 1) { cout << "-1\n"; continue; }
int cnt = 0;
for (char c : s) {
if ((c - '0') & 1) { cout << c; cnt++; }
if (cnt == 2) break;
}
cout << '\n';
}
return 0;
}
~~~~~
</spoiler>
[problem:1291B]
Author: [user:hugopm,2020-02-02...
, the ! query gives you page $6$ of the sauce. ( ͡° ͜ʖ ͡°)
Tutorial of Codeforces Round 616 (Div. 1)
Tutorial of Codeforces Round 616 (Div. 2)
76.
[Tutorial] Diameter of a tree and its applications Hello everyone,<br>
finding the diameter is one of the most frequent ways to solve problems about trees. In this tutorial we will see how to find a diameter and some of its properties, and we will use them to solve some problems of increasing difficulty.<br>
The first part of the tutorial is quite basic, so feel free to skip it and jump to the problems if you already know the concepts.
Target: rating $[1400, 2300]$ on CF<br>
Prerequisites: basic graph theory, greedy
The diameter
------------------
Given an unweighted tree, let's define $\text{dist}(a, b) =$ the number of edges in the simple path $a \rightarrow b$.
A diameter of the tree $a \rightarrow b$ is the longest path, i.e., the one that maximizes $\text{dist}(a, b)$ over all pairs of nodes. If there are multiple diameters, let's pick any of them.
The same definition is valid for a weighted tree with nonnegative weights (with $\text{dist}(a, b) =$ the sum of the weights of the edges in the simple path $a \rightar...
After each query, you have to find the maximum $\text{dist}(a, i)$ among all
$i$ such that $\text
77.
Codeforces Round #884 (Div. 1 + Div. 2) Editorial Video editorials for [B](https://www.youtube.com/watch?v=5nzUni8dFLQ), [C](https://www.youtube.com/watch?v=8mz7gnAJ5QM), and [D](https://www.youtube.com/watch?v=ahnNAwpGwHc) are available on [user:ak2006,2023-07-11]'s channel.
### [problem:1844A]
<spoiler summary="Hint 1">
There exists a small $n$ where the second player can win.
</spoiler>
<spoiler summary="Hint 2">
If $a \ge 2$, then $n = 1$ works.
</spoiler>
<spoiler summary="Solution">
[tutorial:1844A]
</spoiler>
<spoiler summary="Implementation">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
int t,a,b;
scanf("%d",&t);
while (t--) {
scanf("%d %d",&a,&b);
printf("%d\n",a+b);
}
return 0;
}
~~~~~
</spoiler>
### [problem:1844B]
<spoiler summary="Hint 1">
In order for $(l,r)$ to contribute to the primality, we must have $\operatorname{MEX}(a_l,\dots,a_r) \ge 2$, so there is some value $1$ between indices $l$ and $r$.
</spoiler>
<spoile...
Tutorial of Codeforces Round 884 (Div. 1 + Div. 2)
78.
Codeforces Round #709 / Technocup 2021 Final Round - Unofficial Editorial As the editorial for round #709 has yet to be released, I thought I'd write up and post my solutions to the problems (with the exception of Div. 1 F). My code may not be especially useful, since it's a bit messier than necessary in some cases, but I'm hoping that the written explanations will be fairly helpful. Feel free to comment if you have any questions!
---
#[2A — Prison Break](https://codeforces.me/contest/1484/problem/A)
By simply playing around with a few small test cases, you might guess that the answer is always equal to $ab$. This intuition is correct; let's prove it formally.
Consider a graph with $ab+1$ vertices including one vertex representing each cell of the prison, one vertex representing the outside world, and an edge for each wall of the prison connecting the two vertices on either side of the wall. Then, observe that a set of walls we can remove such that the outside world is accessible from every cell is equivalent to a set of edges that s...
$[lo, hi].$ Then, we might query $lo$ until our balance exceeds
$\frac{lo+hi}{2}$, at which point
79.
A Brief Inquiry into Online Connectivity This question striked my head: *"How can I solve dynamic $k$-connectivity efficiently?"*
And then I tried to answer it, but I realized that my question was open to a lot of different interpretations.
Two vertices are $k$-connected if there are $k$ edge-disjoint paths connecting two vertices. For $k = 1$, it is the usual definition of *connectivity*.
## Solve?
If I say, "I solved the graph connectivity problem", what can it possibly mean?
**First Interpretation ($s$-$t$ connectivity)**. I can respond to the following query efficiently: Given two vertices $s, t$, determine if there is a path between them. In the case of $k = 1$, graph search suffices.
What about higher $k$? You can find $k$ edge-disjoint path by reducing it into a flow problem. Each edge-disjoint path corresponds to a flow from $s$-$t$, so make all edges to capacity one, and find a flow of total capacity $k$ from $s$ to $t$. This algorithm takes $O(\min(k, m^{1/2}) (n + m))$ time.
**Second Interpre...
. Sometimes, you are concerned about the **worst-case** query time, where you
have to answer all
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/03/2026 23:40:48 (h1).
Desktop version, switch to mobile version.
Supported by
