$I$'s connectivity will not be influenced., When $a,b$ are in the same CC, the link will have no influence on its
connectivity., connectivity. Case2: $I$ contains $[x,y]$. If $[a,b]$ becomes connected after
the linking
→ 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 |
| 7 | nik_exists | 133 |
| 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.
Codeforces Round #810 Editorial Sorry for the late editorial. May this editorial help you. If you have questions, feel free to ask.
[problem:1711A]
<spoiler summary="hint1.">
The minimal weight is at least $1$ since $1$ divides any integer (so $1$ divides $p_1$).
</spoiler>
<spoiler summary="solution">
Since $k+1$ does not divide $k$, a permutation with weight equal to $1$ is: $[n,1,2,\cdots,n-1]$.
</spoiler>
<spoiler summary="code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
void work()
{
int n;
cin>>n;
cout<<n<<' ';
for (int i=1;i<n;i++)
cout<<i<<' ';
cout<<endl;
}
int main()
{
int casenum=1;
cin>>casenum;
for (int testcase=1;testcase<=casenum;testcase++)
work();
return 0;
}
~~~~~
</spoiler>
[problem:1711B]
<spoiler summary="hint1.">
See the party as a graph.
</spoiler>
<spoiler summary="hint2.">
Divide the vertices into two categories according to their degrees' parity.
</spoiler>
<spoiler summary="solution">
Let's consider ...
Tutorial of Codeforces Round 810 (Div. 1)
Tutorial of Codeforces Round 810 (Div. 2)
2.
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...
Theorem](https://codeforces.me/blog/entry/78255) - [Dynamic connectivity
problem](https, connectivity problem](https://codeforces.me/blog/entry/15296) - [Flow
Series](https://codeforces.me/blog
3.
[Tutorial] Online Dynamic Connectivity The World Finals are right ahead, and if everything works as I expect, you will probably have to wait a lot of time before the contest, dress rehearsals, or anything else. I prepared this blog post so that you have something to keep yourself occupied.
# Goal
Our goal is to maintain connectivity in fully-dynamic query streams. In other words, we want to solve this problem:
* Insert an edge $e = (u, v)$ into a graph
* Delete an edge $e = (u, v)$ into a graph
* Find if two vertices $u, v$ are connected
* Find the size of connected components where the vertex $u$ belongs.
The *offline version*, where you can *cheat* (aka, read all queries before answering, and answer everything at the very end of the program) has a very cool solution commonly known as *Offline Dynamic Connectivity*. This is enough in most CP problems, where this *offline* solution is rarely considered cheating.
Unfortunately, people in the academia are not chilling and consider this a kind of cheating (n...
[Tutorial] Online Dynamic Connectivity, *Online Dynamic Connectivity* or *HDLT Algorithm*. I think it is as well-known
as the offline algorithm, Connectivity*. This is enough in most CP problems, where this *offline*
solution is rarely, Our goal is to maintain connectivity in fully-dynamic query streams. In other
words, we want to, The dynamic connectivity problem can be solved if the underlying graph is
guaranteed to be a forest, connectivity in fully-dynamic query streams. In other words, we want to solve
this problem: * Insert an
4.
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...
A Brief Inquiry into Online Connectivity, = 1$, it is the usual definition of *connectivity*., Cut Tree are good examples) that preserves the connectivity structure without
a few changes and can, it is especially prevalent in competitive programming. For example, the
connectivity problem can be, ## Solve? If I say, "I solved the graph connectivity problem", what can it
possibly mean?, $ (connectivity), $2$ (biconnectivity), $3$ (triconnectivity), $4$ (??), $O(1),
O(\text{poly}(\log n))$, $O(n, $-connectivity by flood-fill. * \[2]: Generic augmenting path algorithm such as
Ford-Fulkerson. * Solves, **First Interpretation ($s$-$t$ connectivity)**. I can respond to the following
query efficiently, **Second Interpretation (Graph connectivity)**. I can't respond to an
individual query, but I can, **Still more interpretation?** You can define connectivity as the minimum
number of *vertex* to, **Third Interpretation (Connectivity Certificate).** It sucks to have only one
of them, why not, , disjoint set union (DSU) solves the connectivity problem in case the updates
are *incremental*., This question striked my head: *"How can I solve dynamic $k$-connectivity
efficiently?"*
5.
[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...
edge). As we care only about connectivity, compress $l$ and $p$ together. Now
we have eliminated one
6.
[Tutorial] Euler Tour Trees (maintaining dynamic trees through their euler tour) Good morning Codeforces!
Today's post regards a well-known, but surprisingly hard to learn topic, Euler Tour Trees.
Prerequisites:
------------------
- Basic tree knowledge, e.g. general vocabulary
- Balanced Binary Search Tree Knowledge (e.g Treaps/Splay trees). In my opinion, learning treaps is the easiest, and [user:SecondThread,2022-02-03] has a great video/problemset on treaps, so go check it out [here](https://codeforces.me/blog/entry/84017)! The BBST must store parent pointers, so make sure your implementation supports it.
#### Disclaimer
This idea will definitely not show up in easy problems, and is pretty uncommon. Nevertheless, it's a cool concept and it can be used to “cheese” somewhat difficult problems, and I haven't found any resources that describe it well.
Brief Description of Operations
------------------
A Euler Tour Tree is a representation of a dynamic forest of trees. This means that, as long as the graph never contains any cycles, you can su...
#### Connectivity Checking
7.
Dynamic connectivity problem Hi everyone!
Recently, at the MIPT: The Fall training camp on the contest from Alexander [user:Milanin,2014-11-22] was a problem from Petr Mitrichev Contest 7. We were given a graph and a set of queries like "suppose we removed from the graph $k \leq 4$ edges. Check whether graph is still connected?" I want to talk further about the solution of a more general problem, when the edges are added and removed without additional constraints in $O (k \log k)$ offline. The first algorithm with such an assessment was offered by David Eppstein in 1992, reducing it to fully dynamic minimum spanning tree problem, but here we will focus on a simple algorithm, proposed in 2012 by Sergei [user:Burunduk1,2014-11-22] Kopeliovich.
[cut]<br>
Let's assume that there are three types of queries & mdash; add the edge (`+`), remove the edge (`-`) and find out some information about the graph (`?`) (in this case, let it be the number of connected components of the graph). We assume that we received a...
Dynamic connectivity problem
Discussion of Dynamic connectivity contest
8.
Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2) Editorial Thank you for participation and we hope you enjoy this round ヽ(^ o ^)/.
During the contest, there was a small issue in problem D. For those affected, we have skipped your duplicate submissions (if your duplicate submissions were not skipped, please let us know). We apologize again for any inconvenience caused.
In addition, we are honored to invite you to our unofficial round tomorrow (*╹▽╹*) [Invitation to TheForces Round #22 (Interesting-Forces)](https://mirror.codeforces.com/blog/entry/119771)
### [1864A-Increasing and Decreasing](https://mirror.codeforces.com/contest/1864/problem/A)
Idea : [user:wuhudsm,2023-08-27]
<spoiler summary="Tutorial">
We use the following greedy construction:
For all $i$ ($1<i<n$), set $a_i=a_{i+1}-(n-i)$. If $a_2-a_1 \geq n-1$, we've found a solution, otherwise there is no solution.
Proof. Assume there's a solution which includes an index $i$ ($1<i<n$) such that $a_{i+1}-a_i>n-i$. We can make $a_j:=a_j+\Delta$ for all $j$ ($2 \le j ...
of the cell being fixed, we need to segregate them based on the remaining
connectivity, considering, Firstly, if this vertex is not an articulation point, it will not cause any
change inconnectivity, This problem is based on a method of online edge deletion and querying
connectivity of a planar
9.
Counting perfect matchings Thanks to [user:t.ravnushkin,2024-09-27] for helping in writing contents of this blog. Thanks to [user:Alexdat2000,2024-09-27] for proof-reading and to [user:bashkort,2024-09-27] for announcing the month of blog posts. Even though I have started writing this blog before the announcement it would have probably been left in a trash bin due to my laziness.
# Introduction
Matching is a beloved topic throughout competitive programming community due
to its simple nature and fun applications. Matchings are not only useful
in graph theory, but are also essential in topics such as game theory,
partially ordered sets and combinatorics. In this blog we are gonna talk
about less known applications of the subject. The main goal of the blog
is explaining the intuition behind being able to associate the number of some
combinatorial species to the amount of perfect matchings and understanding
when it is possible to efficiently compute their counts. The blog mainly
consists of two parts: ...
algorithms mostly rely on careful analysis of higher order connectivity
properties (i.e. $3, removing 2-connectivity. I would recommend trying to coming up with solution
yourself but here I, the place where we use 2-connectivity. Each edge is incident to exactly $2$
planes (including, we use 2-connectivity. Each edge is incident to exactly $2$ planes (including
outer one
10.
Divide and conquer. Dynamic connectivity offline and DP optimization. Divide
and conquer by queries.
Divide and conquer. Dynamic connectivity offline and DP optimization. Divide and conquer by queries. Hello, Codeforces! I have wanted to write an educational blog for a long time, but I couldn't find a topic for it. And recently I remembered that Codeforces doesn't have a good blog on one of my favorite topics: the "divide and conquer" technique. So I want to talk about it. The outline will be something like this:
1) Divide and conquer. What this technique is and what it is for. Example.
2) Dynamic connectivity offline with divide and conquer. Divide and conquer dp optimization.
3) Let me tell you about a method I invented myself: divide and conquer by queries. In this case, we divide not only the array, but also the queries into groups.
So, here we go.
First, about what this technique is. The point is about the following: let's say we have an array. Then, if we know how to calculate the answer for two parts of it, and if we know how to get the answer for the whole array from the answers of two parts, we can apply the divide and conquer technique. Let me show you the si...
Divide and conquer. Dynamic connectivity offline and DP optimization. Divide
and conquer by queries., Разделяй и властвуй. Dynamic connectivity offline и ускорение ДП. Разделяй и
властвуй по запросам., each segment: indeed, this is just the number of different connectivity
components on the segment. We, ) Dynamic connectivity offline with divide and conquer. Divide and conquer dp
optimization. 3, , dynamic connectivity offline. Задача состоит в том, чтобы обрабатывать в
offline такие запросы:, 2) Dynamic connectivity offline with divide and conquer. Divide and conquer dp
optimization., 2) Dynamic connectivity offline при помощи разделяй и властвуй. Разделяй и
властвуй dp оптимизация., Some other algorithms, such as dynamic connectivity offline, are also based on
the divide and, connectivity offline при помощи разделяй и властвуй. Разделяй и властвуй dp
оптимизация. 3
11.
Cooperation between Universal Cup and Huawei In the interest of contributing to the community and bridging the gap between competitive programming and industry, we are happy to announce that in the future, Universal Cup will be cooperating with Huawei in many areas.
Huawei will support Universal Cup in future seasons. In the meantime, we will explore the cutting-edge challenges from the industry together as an additional activity during the Universal Cup season. These events might also serve as parts of other official programming competitions. Moreover, we intend to run some interviews and other events together, providing opportunities for communication between participants and the industry. We also hope that in the future, we can invite the top competitive programming teams to compete in the Universal Cup Onsite Final. It will definitely be one of the best events ever! Please stay tuned and support Universal Cup!
### About Universal Cup
The Universal Cup is a non-profit organization dedicated to offering training resour...
connected, intelligent world. To this end, we will work towards ubiquitous
connectivity and inclusive, towards ubiquitous connectivity and inclusive network access, laying the
foundation for an intelligent
12.
My Solutions to Spectral::Cup 2026 Round 1 (CF Round 1094) Since the editorial for today's Div. 1 hasn't been published yet, I thought I'd share solution sketches. Some of these won't include all of the specific details, but hopefully they should communicate the main ideas. (I didn't compete officially, but I got AC on all of the problems using the below approaches, so I'm fairly confident in correctness.) Feel free to leave questions below and I'll respond if I have time.
## A — A Wonderful Contest
If any problem has $100$ subtasks, the answer is yes: we can achieve an arbitrary score by solving some of the other problems fully and by solving the right number of subtasks of the $100$-subtask problem. Otherwise, there is no way to achieve a score of 1, so the answer is no.
## B — Artistic Balance Tree
Note that each of the reversal operations swaps odd positions with odd positions and even positions with even positions, as $u-i$ and $u+i$ differ by $2i$ and thus have the same parity. Thus, when we are to mark an od...
iteratively construct the connectivity state of the original graph with edges
of weight $w$ excluded, for
13.
Ear decomposition tutorial ##### Introduction
This tutorial is about ear decomposition, a simple but powerful technique for finding graph connectivity, including 2-vertex-connectivity, 2-edge-connectivity, and strong orientation.
In this tutorial we assume we have a connected graph. If the graph is disconnected, the algorithm can be run on each connected component.
An _ear_ consists of a path where the endpoints (the first and last vertices) could be the same or different. So a cycle can be an ear. (It is called an "ear" because it is shaped like the human ear.)
An _ear decomposition_<sup>1</sup> is a decomposition of a graph into a sequence of ears $C_1, C_2, \dots, C_n$. $C_1$ must be a cycle and each later ear must be either a path between two vertices that are on previous ears, or a cycle with one vertex on a previous ear.
Since every edge in an ear belongs to a cycle, an ear decomposition has no bridges. So, a connected graph is 2-edge-connected **iff** it has an ear decomposition containing ...
finding graph connectivity, including 2-vertex-connectivity, 2-edge-
connectivity, and strong, -Vertex- and 2-Edge-Connectivity](https://arxiv.org/abs/1209.0700), -connectivity implies 2-edge-connectivity., connectivity, including 2-vertex-connectivity, 2-edge-connectivity, and strong
orientation.
14.
Introduction to Graph Algorithms - Topic Stream #1 Hi,
We had our first topic stream on graph algorithms yesterday.
Since this was the first stream on this topic, I started with the very basics. We’ll cover more advanced topics in the upcoming streams. My goal is to eventually cover every graph algorithm from basic to advanced. In future streams, I plan to explain some of the hardest graph problems I’ve ever encountered.
If you’re already at an advanced level, the first topic stream is not for you, as I started from the very beginning to ensure that no prior knowledge is needed to follow along.
### What is a Graph
In this section, I introduce what a graph is and how it can be useful. I also discuss the basic types of graphs (un/directed, un/weighted).
<spoiler summary="Video">
<iframe width="800" height="450" src="https://www.youtube.com/embed/l1JQhPBwrsY?si=RxTXxwSptznWn1Nx&start=296" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture...
" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen> ###
Connectivity in, ### Connectivity in Graphs and DFS, Here, I discuss the connectivity of a graph, and we solve a problem related to
it. At the end, I
15.
Разбор Codeforces Round #319 Задача A. Div2.
Заметим, что число $x$ может встречаться в столбце $i$ только один раз — в строке $x / i$. Переберем столбец $i$, проверим, что $x$ делится нацело на $i$, а также $x / i \le n$. Если все условия выполнены, обновим ответ.
Асимптотика — $O(n)$
[Код](http://pastebin.com/yGMTt9KZ)
Задача B. Div2.
Рассмотрим два случая: $n > m$ и $n \le m$.
Пусть $n > m$, рассмотрим суммы на префиксах. По принципу Дирихле, найдутся две равные суммы по модулю $m$. Пусть $S_l mod m = S_r mod m$. Тогда сумма чисел на отрезке с $l + 1$ по $r$ по модулю $m$ равна нулю, то есть ответ точно "YES".
Пусть $n \le m$, то решим задачу динамикой за $O(m^2)$. Пусть $can[i][r]$ — можем ли мы, используя первые $i$ предметов, получить остаток $r$ от деления на $m$. Переходы в динамике понятны: либо мы берем предмет и переходим в состояние $can[i + 1][(r + a_i)\ mod\ m]$, либо не берем и переходим в состояние $can[i + 1][r]$.
Асимптотика — $O(m ^ 2)$.
[Код](h...
Then we could write a solution, which is pretty similar to solution of Dynamic
Connectivity Offline, Тогда мы могли бы применить решение, похожее на решение задачи Dynamic
Connectivity Offline за $O(n
Tutorial of Codeforces Round 319 (Div. 1)
Tutorial of Codeforces Round 319 (Div. 2)
16.
Отбор в кружок олимпиадного программирования «Тинькофф» 2021-2022 Всем привет!
Начинается новый учебный год, вместе с ним стартует и сезон олимпиад. Этот пост будет полезен школьникам, которые хотят заниматься олимпиадным программированием, но не знают где.
Сейчас открыт отбор в кружок по олимпиадному программированию «Тинькофф Поколение». Один из классных плюсов кружка — он абсолютно бесплатный, но нужно написать вступительный контест, который открыт **до 12 сентября включительно**. Зарегистрироваться и начать решать можно здесь: [algocode.ru](https://algocode.ru).
Ниже мы постараемся подробнее описать как все устроено в кружке. Если у вас останутся вопросы, задать их можно в комментариях к посту или в telegram (внизу есть наши контакты).
Каждый год мы стараемся быть лучше и действительно полезными, так что в этом году кружок будет еще интереснее.
## Про формат занятий
По результатам отборочного контеста мы разделим участников на учебные параллели. У каждой параллели есть своя группа преподавателей, которые будут читать лекции, п...
, heavy-light, ladder. - Задачи на графах: паросочетания, потоки, dinamic
connectivity problem
17.
Сodeforces Round 512 (and Technocup — Elimination Round 1) Editorial [problem:1030A]
<spoiler summary="Tutorial">
[tutorial:1030A]
</spoiler>
<spoiler summary="Solution">
~~~~~
#include<bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
int curMax = 0;
for(int i = 0; i < n; i++) {
int curAns; cin >> curAns;
curMax = max(curMax, curAns);
}
puts(curMax > 0 ? "HARD" : "EASY");
return 0;
}
~~~~~
</spoiler>
[problem:1030B]
<spoiler summary="Tutorial">
[tutorial:1030B]
</spoiler>
<spoiler summary="Solution">
~~~~~
#include<bits/stdc++.h>
using namespace std;
int n, d;
int m;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> d;
cin >> m;
for(int i = 0; i < m; ++i){
int x, y;
cin >> x >> y;
bool ok = true;
if(!((x - y) <= d && (x - y) >= -d))
ok = false;
if(!((x + y) <= n + n - d && (x + y) >= d))
ok = false;
if(ok) puts("YES");
else puts("NO");
}
return 0;
}
~~~~~
</spoiler>
[problem:...
Tutorial of Technocup 2019 - Elimination Round 1
18.
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...
connectivity).
19.
Validators with testlib.h If you have written some programming problems, and have prepared test cases, you will probably experience the terrible feeling that some test cases may be invalid (meaning it does not agree with the constraints in problem statement): upper bound can be violated, your graph not satisfied connectivity requirements or is not at tree... It is reasonable to feel that way. Even experienced problem setters make mistakes sometimes (for example, in the prestigious ACM ICPC World final 2007).
It is strictly recommended to write a special program (called _validator_) to formally check each test to satisfy all requirements from problem statements. Validators are strictly required for problems on Codeforces. [Polygon](https://polygon.codeforces.com) has built-in support of validators.
It is really easy to write a validator using testlib.h.
## Example
Following is a validator that could be used for problem [problem:100541A]:
~~~~~
#include "testlib.h"
int main(int argc, char* argv...
connectivity requirements or is not at tree... It is reasonable to feel that
way. Even experienced problem
20.
Codeforces Round #146 Tutorial ### [problem:236A]
It is a very simple problem, just count how many distinct chars in the input and output the correct answer.
### [problem:236B]
First of all, we can make a table of size a*b*c to store every number's d value. Then we can just brute force through every tripe to calculate the answer.
### [problem:235A]
It is a simple problem, but many competitors used some wrong guesses and failed. First of all, we should check if n is at most 3 and then we can simply output 1,2,6.
Now there are two cases: When n is odd, the answer is obviously n(n-1)(n-2). When n is even, we can still get at least (n-1)(n-2)(n-3), so these three numbers in the optimal answer would not be very small compared to n. So we can just iterate every 3 number triple in [n-50,n] and update the answer.
### [problem:235B]
Let us take a deep look at how this score is calculated. For an $n$ long 'O' block, it contributes $n^2$ to the answer.
Let us reformat this problem a bit and consider ...
they're selected, A and B lost connectivity, let us call them X.
Tutorial of Codeforces Round 146 (Div. 1)
Tutorial of Codeforces Round 146 (Div. 2)
21.
Segment tree on Time First of all, this technique isn't anything new, it's a fairly known one, but I couldn't find any resources on this topic other than [this comment](https://codeforces.me/blog/entry/15296?#comment-203606) which is somewhat hard to find, so I decided to write a full blog.
With that being said, let's begin with the blog.
The problem
==================
Lets consider the following problem:
A graph is given with $N$ nodes and $Q$ queries. Each query is one of the following:
- Add edge $(u,v)$
- Remove edge $(u,v)$
- Query the number of connected components in the graph
The timeline
==================
Lets imagine a timeline, from time $1$ to time $Q$, at each moment either some edge gets added, removed, or a query gets asked.
Now the main idea of this technique is instead of dealing with deletions, for each edge we determine some intervals during which it exists. Namely if edge $(u, v)$ gets added at time $A$ and then later removed at time $B$ then that edge will ob...
wondering by this point how this is useful at all since Dynamic Connectivity
can be solved both online, You may be wondering by this point how this is useful at all since Dynamic
Connectivity can be
22.
An editorial for IOI 2023: Closing Time While upsolving this problem, I noticed that there appears to be a dearth of editorials; I couldn't find any official ones, and the only unofficial one I found is [this one](https://codeforces.me/blog/entry/121499), which is unfortunately rather poorly formatted. Thus, I've decided to try my hand at writing my own editorial for future reference. Feel free to comment with any questions!
**NOTE:** You can also read this editorial on [my blog](https://danielz.fyi/thoughts/closing-time), which has slightly better formatting.
## Basics
First, consider how we might solve the problem if $X=Y$. Actually, if we let $d(u,v)$ denote the distance between nodes $u$ and $v$, it turns out the following algorithm works:
> In order of increasing $d(u,X)$ and while we have not exceeded the $K$ threshold, set the closing time of node $u$ to be $d(u,X)$.
*Proof.* We can use a bounding argument.
1. If we want $k$ nodes to be reachable from $X$, then the closing times of each of these no...
23.
Virtual trees method This article explores the concept of *virtual trees*, proves their key properties, describes an efficient algorithm for their construction, and then applies the method to solve a specific problem using dynamic programming (DP) on trees.
## Introduction
Many tree-related problems require working with a subset of vertices while preserving the tree structure induced by their pairwise lowest common ancestors (LCA). The concept of a *virtual tree* allows us to transition from the original tree $T$ with $N$ vertices to a substructure whose size linearly depends on the size of the selected set $X$. This significantly accelerates algorithms, particularly for DP computations.
## Definition of a Virtual Tree
Let $T$ be a given rooted tree, and $X$ be some subset of its vertices. A **virtual tree** $A(X)$ is defined as follows:
$$
A(X) = \{ \operatorname{lca}(x,y) \mid x,y \in X \},
$$
where $\operatorname{lca}(x,y)$ denotes the lowest common ancestor of vertices $x$ and $y$ in tr...
., all LCAs for pairs of vertices from $X$), and connectivity is inherited from
the original tree.
24.
Data structure stream 
From [Friday 14:00 UTC+9 Korea Standard Time](https://www.timeanddate.com/worldclock/fixedtime.html?msg=koosaga+stream+%232&iso=20191130T14&p1=235&ah=10), I will stream solving problems in [Baekjoon OJ](https://www.acmicpc.net/). All problems will be only about doing some queries on sequences or graphs.
<spoiler summary="Problem list">
[Query on a sequence 2](https://www.acmicpc.net/problem/13543)
[Query on a sequence 19](https://www.acmicpc.net/problem/14899)
[Query on a sequence 25](https://www.acmicpc.net/problem/17473)
[Query on a sequence 26](https://www.acmicpc.net/problem/17474)
[Query on a sequence 27](https://www.acmicpc.net/problem/17475)
[Query on a sequence 28](https://www.acmicpc.net/problem/17476)
[Query on a sequence 29](https://www.acmicpc.net/problem/17477)
[Query on a sequence 30](https://www.acmicpc.net/problem/17486)
[Query on a sequence 31](https://www.acmicpc.net/problem/17607)
[Query on a seq...
tree 13](https://www.acmicpc.net/problem/17936) [Dynamic connectivity and
query](https, [Dynamic connectivity and query](https://www.acmicpc.net/problem/17465)
25.
CEOI 2025 discussion Since CEOI 2025 is over and the tasks and test data have been published, can we discuss the solutions here?
Here are the [tasks](https://ceoi2025.utcluj.ro/category/13).
Upd: you can find the tasks [here](https://codeforces.me/blog/entry/144670?#comment-1293960) (for now)
Upd: https://github.com/asociatia-sepi/archive/tree/main/CEOI-2025
Upd: I was upsolving this CEOI now for practice and I decided to write some solutions because I couldn't find them.
## Boardgames
### Solution 1
This is the approach from the official editorial. The core idea relies on a **divide and conquer** strategy:
1. Initially, we invoke the function $f(1, n)$.
2. Find the position $i$ closest to the border such that $i$ and $i+1$ are not in the same connected component.
3. If the subgraph from $L$ to $R$ is connected, we can just return $1$.
4. Otherwise, we split the problem and return $f(L, i) + f(i+1, R)$.
The main implementation challenge here is to efficiently maintain graph con...
The main implementation challenge here is to efficiently maintain graph
connectivity while
26.
[Tutorial] Persistent DSU made trivial ### Introduction:
This blog covers how a DSU can save all of its previous versions after several union operations which there seems to be a lack of resources to discuss. Thanks to [user:MinaRagy06,2023-09-02] for helping me write this blog!
A basic DSU can be implemented in the following way:
<spoiler summary="DSU Code">
~~~~~
int parent[MAX_N], size[MAX_N];
int get_root(int node){
if(node == parent[node])
return node;
return get_root(parent[node]);
}
void union_sets(int u, int v){
u = get_root(u);
v = get_root(v);
if(u == v)
return;
if(size[u] > size[v])
swap(u, v);
size[v] += size[u];
parent[u] = v;
}
~~~~~
</spoiler>
Next, I will explain how to store more information to answer queries that require time travelling.
### Main Idea:
#### Problem 1 (Easy) :
Let's start by solving a simple [CSES Problem](https://cses.fi/problemset/task/2101/).
The problem can be reduced to binary searching on the first time nodes $a$ and $b$ are conn...
. Now let's learn how to check connectivity during any time using persistent
DSU.
27.
Maintaining mst with online edge insertions — no LCT needed This blog is about maintaining mst with online edge insertions (or msf — minimum spanning forest to be exact) by using a data structure I came up with in $O(\log n)$ for edge insertion. although this problem can solved quite easily for anyone who knows LCT (link-cut tree), coding LCT is not really practical and has really bad constants. The data structure I present has very good constants because as you'll see all it does is manipulation on arrays. For obvious reasons that will be shown later I have called this data structure "weighted DSU".
**Warmup problem**
==================
The problem is stated as follows: you are given an undirected graph where each edge has a time $t_i$. you are asked to answer queries of the form "what is the smallest time t such that you can get between u and v with all edges in time $<= t$". This problem is analogous to calculating the msf of the graph where the weights are the times and being able to answer what is the maximum on the simple path ...
Problems ================== [Offline Dynamic Connectivity
](https://cses.fi/problemset/task/2133/)
28.
TeamsCode Spring 2025 Contest Editorial Sorry for the long wait. All problems were written, prepared, and editorialized by [user:Yam,2025-03-23], [user:hyforces,2025-04-14], [user:culver0412,2025-04-15], [user:HaccerKat,2025-03-23], [user:alexlikemath007,2025-03-23], [user:jay_jayjay,2025-03-23], [user:n685,2025-03-23], [user:Mustela_Erminea,2025-03-23], [user:Jasonwei08,2025-03-23], [user:eysbutno,2025-03-23], [user:training4usaco,2025-03-23], [user:Nyctivoe,2025-03-23], and [user:gggg0,2025-03-23]. The problems (with problem credits) can be found in the [Novice Gym](https://codeforces.me/gym/105819) and [Advanced Gym](https://codeforces.me/gym/105818). Also thanks to our testers for providing valuable feedback and to our logistics and web team for making TeamsCode possible!
[Novice A/](https://codeforces.me/gym/105819/problem/A)[Advanced A: Lily Pads](https://codeforces.me/gym/105818/problem/A)
=================================================================================================================
<spoi...
Note that Floyd-Warshall can be modified to check for connectivity in, However, Floyd-Warsahll can also be used to check for connectivity. Define
$\text{connected}[i][j, connectivity of nodes in the subgraphs for each color using DFS, BFS or DSU,
and if two nodes are connected in
Tutorial of TeamsCode Spring 2025 Advanced Division
Tutorial of TeamsCode Spring 2025 Novice Division
29.
TheForces Round #43 (DIV2-Forces) Editorial Reminder: We welcome you to participate in the official DIV1/DIV2 round scheduled on the 31st!
[A](https://codeforces.me/gym/106014/problem/A)
Idea:[user:tamzid1,2025-07-25]
<spoiler summary="solution">
We can see if $x$ is a perfect square, $x^x$, $x^{(x^x)}$, $\ldots$ are also perfect square.
Proof: assume $x=y^2$, $x^z=(y^z) \cdot (y^z)$.
So the answer is the number of perfect squares not greater than $n$.
There are exactly $\lfloor \sqrt{n} \rfloor$ integers $x$ (with $1 \leq x \leq n$) such that $x$ is a mystic number.
</spoiler>
<spoiler summary="code(C++)">
```cpp
#include <iostream>
#include <cmath>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << static_cast<int>(sqrt(n)) << '\n';
}
return 0;
}
```
</spoiler>
<spoiler summary="Rate the Problem">
Amazing problem:
Goo...
Why is this algorithm correct? Let's analyze: we define the connectivity
component of "fine" as
Tutorial of TheForces Round #43 (DIV2-Forces)
30.
[Editorial] Codeforces Round 939 (Div. 2) Thank you for taking part in our contest, we know leaves a lot to be desired. But we believe that you can find interesting among our problems.
## [A. Nene's Game](https://codeforces.me/contest/1956/problem/A)
Idea: [user:Otomachi_Una,2024-04-13]
<spoiler summary="Tutorial">
Obviously, a person at place $p$ will be kicked out if and only if $p \ge a_1$.
Therefore, the answer is $\min(n,a_1-1)$.
</spoiler>
<spoiler summary="Solution">
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
int a[105];
void solve(){
int q,k,n;cin>>k>>q;
for(int i=1;i<=k;i++) cin>>a[i];
for(int i=1;i<=q;i++){
cin>>n;
cout<<min(a[1]-1,n)<<' ';
}
cout<<endl;
}
int main(){
ios::sync_with_stdio(false);
int _;cin>>_;
while(_--) solve();
}
```
</spoiler>
## [B. Nene and the Card Game](https://codeforces.me/contest/1956/problem/B)
Idea: [user:Otomachi_Una,2024-04-13]
<spoiler summary="Hin...
The last issue is, the graph contains $O(n^2)$ edges. but since we only care
aboutconnectivity
Tutorial of Codeforces Round 939 (Div. 2)
31.
Good Blog Post Resources about Algorithm and Data Structures There are many good blogs in **Codeforces Blog** where people describes about different **Algorithm and Data Structures** .
Lets gather all the resources about **Algorithm and Data Structures** Explanations. You can comment bellow the link and about it . I will always update that post gather new resources.Hope ,its help all and inspire all to write new blog post in future :)
Last added blogs link will have a tag **(New)**
Resources:
**C++ STL**
[C++ STL: Policy based data structures]( /blog/entry/11080)
[C++ STL: Policy based data structures. Part 2]( /blog/entry/13279)
**String Processing**
[Suffix tree. Basics. Building in O(nlogn)]( /blog/entry/11337)
[Z Algorithm]( /blog/entry/3107)
[Great resource for string algorithms]( /blog/entry/8008)
[Aho-Corasick algorithm. Construction]( /blog/entry/14854)
[Suffix tree. Ukkonen's algorithm](/blog/entry/16780)
[On suffix automaton (and tree)](/blog/entry/22420) **New**
**Data Structur...
[Dynamic connectivity problem]( /blog/entry/15296)
32.
Codeforces Round 1105 (Div. 1, Div. 2) Editorial Thanks everybody for participating in the round!
### [Div2A. Another Popcount Problem](https://codeforces.me/contest/2240/problem/A)
Author: [user:wangmarui,2026-06-27] Preparation: [user:wangmarui,2026-06-27]
<spoiler summary="Hint 1">
Consider each binary bit independently.
</spoiler>
<spoiler summary="Hint 2">
Think about a greedy approach.
</spoiler>
<spoiler summary="Solution">
[tutorial:2240A]
</spoiler>
<spoiler summary="Code (by wangmarui)">
~~~~~
/*
author: Yuneko
time: 2026/5/5
contest:
Tips:
RE, MLE?
greedy, dp?
natural time?
map, umap?
giveup rating, get score.
brute force, right solution?
%mod? std/run/maker/checker?
add bruteforce?
clear?
double, long double?
O(n)? O(n^2)!
make data!
last but not least.
bruteforce -> SegTree?
Think more.
*/
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/st...
Consider modifying the dynamic graph connectivity approach.
Tutorial of Codeforces Round 1105 (Div. 1)
Tutorial of Codeforces Round 1105 (Div. 2)
33.
Teamscode Spring 2026 Contest Official Editorial Sorry that this is really late.... Thanks for participating in TeamsCode, and I hope you enjoyed the problems!
All problems were written and prepared by [user:culver0412,2026-08-13], [user:justin_g_20,2026-08-13], [user:jay_jayjay,2026-08-13], [user:theyashb,2026-08-13], [user:Buzzy2,2026-08-13], Bryan Zhu, [user:alexlikemath007,2026-08-13], [user:n685,2026-08-13], [user:naturalselection,2026-08-13], [user:AksLolCoding,2026-08-13], [user:eysbutno,2026-08-13], [user:pilliamw,2026-08-13], [user:dutin,2026-08-13], [user:willy108,2026-08-13], [user:gg_gong,2026-08-13], and [user:HaccerKat,2026-08-13]. Also thanks to our testers for valuable feedback, and the Teamscode web and logistics teams for making this contest possible!
[Novice A/](https://codeforces.me/gym/106507/problem/A)[Advanced A: Digits](https://codeforces.me/gym/106507/problem/A)
===
[user:justin_g_20,2026-08-13] is still writing the editorial, for now the solution code is below:
<spoiler summary="Python Code"...
quadrants and in this problem, we try to maintain the connectivity problem
between the quadrants of the, -quadrants edges, as the inner connectivity cannot be changed with the outside
information and only
Tutorial of TeamsCode 2026 Spring Contest
34.
Connectivity Issues # Connectivity Issues
## Strong Connectivity and Strong Connectivity Components
- Point biconnected: In an undirected graph, if deleting a point (not $x$ or $y$) allows $x$ and $y$ to still reach each other, then $x$ and $y$ are called point biconnected;
- Edge biconnected: In an undirected graph, if deleting an edge allows $x$ and $y$ to still reach each other, then $x$ and $y$ are called edge biconnected;
- Property $1$: Point biconnected does not have transitivity, but edge biconnected does;
- Cut vertex: In an undirected graph $G$, if deleting $x$ increases the number of connected components, then $x$ is called a cut vertex (cut vertex) of $G$.
- Conclusion: At least $3$ points are required for an undirected graph to **possibly** have a cut vertex;
- Cut vertex determination:
- If there is an edge from $x$ to $y$ in the search tree, when $low_y \ge dfn_x$, it means that the minimum timestamp $low_y$ that $y$ can reach is above the timestamp of $x$, $y$ is "separated" f...
Connectivity Issues, ## Strong Connectivity and Strong Connectivity Components
35.
Valentine's Day Contest 2020 Editorial I hope you enjoyed the contest!
Expected problem difficulty is F < A < (G ~ D) < (C ~ E) < B (though it might be different for different people).
I will mainly focus on explaining the full solution to the problems but I will briefly mention how to pass certain subtasks.
### Problem A — Leakage
<spoiler summary="Solution">
This is unfortunately the most standard problem of the set. Obviously, we can model the friends as vertices and friendships as edges in an undirected graph. The problem basically asks us to answer queries of the form: "For a pair of vertices $u, v$, find the number of vertices $w \neq u, v$ such that removing $w$ from the graph disconnects $u$ and $v$".
Removing vertices and disconnecting graphs should remind one of articulation points. The data structure to solve this problem is [block-cut tree](https://en.wikipedia.org/wiki/Biconnected_component#Block-cut_tree). Each biconnected component is considered as a block. An articulation point might be...
articulation points have an effect on the connectivity of $u$ and $v$. With
the block-cut tree, it can
Tutorial of Valentines Day Contest 2020
36.
All-Ukrainian School Olympiad in Informatics: editorial (A,B,C,D,E,F) <p></p><div>The editorial is now completed.</div><div><br></div><div><div><b>Problem A: Gift (Roman Iedemskyi)</b></div><div><br></div><div>Suppose that the pair $(A,B)$ is an optimal solution, where $A$ is the number of gold coins in a gift and $B$ is a number of silver coins. It is easy to see that there exist two (probably equal) indexes $i$ and $j$ such that $g_i=A$ and $s_j=B$. It is true, because in the other case we could decrease either $A$ or $B$ without changing connectivity of the graph.</div><div><br></div><div>Let $R(A,B)$ be the graph in which for all $i$ the following statement holds: $g_i \leq A \wedge s_i \leq B$.</div><div><br></div><div>Let $T(A)$ be the weighted graph in which for all edges $g_i \leq A$. For each edge $i$ we will assign a weight equal to $s_i$. Let's find a spanning tree of this graph, which has the property that its maximal edge is minimal possible. It can be shown that for the fixed $A$ the minimal value of $B$ for which graph $R(A,B)$ is st...
could decrease either $A$ or $B$ without changing connectivity of the graph.
Tutorial of All-Ukrainian School Olympiad in Informatics
37.
Codeforces Round 1063 Editorial <spoiler summary="Comment">
B turned out to be harder than expected. I apologize for this, but I hope there are still problems that are fun and educational for you to solve in this round.
Regardless, I hope this round encourages authors to include communication problems in their future rounds, and in earlier positions as well.
</spoiler>
[Problem A — Souvlaki VS. Kalamaki](https://codeforces.me/contest/2163/problem/A)
<spoiler summary="Solution">
Suppose it Kalamaki's turn on some even round $2k$. Kalamaki can swap element $a_{2k}$ with $a_{2k+1}$. If $a_{2k} > a_{2k+1}$, he will not swap the elements, but if $a_{2k} < a_{2k+1}$, he will swap them. In both cases he wins the game, because the array will never be sorted. Therefore, if $a_{2k} \neq a_{2k+1}$, Kalamaki will win no matter what.
Now assume every time Kalamaki plays, the two elements he can swap have the same value, because otherwise we have shown that he wins. Suppose that it is Souvlaki's turn on round...
one $1$ in the grid, as mentioned in the statement (connectivity would not be
well defined otherwise
Tutorial of Codeforces Round 1063 (Div. 2)
38.
Codeforces Round #119 — Editorial ### Problem [189A --- Cut Ribbon](http://www.codeforces.com/problemset/problem/189/A)
The problem is to maximize _x+y+z_ subject to _ax+by+cz=n_. Constraints are low, so simply iterate over two variables (say _x_ and _y_) and find the third variable (if any) from the second equation. Find the maximum over all feasible solutions.
Other approaches: Use dynamic programming with each state being the remainder of ribbon. Select the next piece to be _a_, _b_ or _c_.
### Problem [189B --- Counting Rhombi](http://www.codeforces.com/problemset/problem/189/B)
Observe that lots of rhombi have the same shape, but are in different locations.
What uniquely determines the shape of a rhombus? Its width and its height.
Is it possible to build a rhombus with every width and every height such that the vertices of the rhombus are in integer points? [cut] No, it is possible only if the width and the height are both even.
How many places we can put a rhombus of width _w0_ and height ...
_x_. As we are only dealing with connectivity, this approach is correct.
(Proof of correctness is, connectivity.
Tutorial of Codeforces Round 119 (Div. 2)
39.
Editorial: OPC Good Bye Thank you for taking part in $\textbf{OPC Goodbye 2025}$.
This editorial walks through the core ideas and solution strategies behind each problem.
We hope it helps you learn something new and refine your approach to competitive programming.
If you have any reviews please put them in this [Google Form](https://docs.google.com/forms/d/e/1FAIpQLSeguT9leXrI3tyrmjwhXSfqj4LVF16zE5AIzKx-bcLHJclDRQ/viewform?usp=sharing&ouid=115085258461331858898).
Contest Link: [Link](https://codeforces.me/group/hUywLYmr80/contest/660904)
### [A. Make It Organised](https://codeforces.me/group/hUywLYmr80/contest/660904/problem/A)
<spoiler summary="Hint 1">
For each position, think: *how many times do I divide this number by 2 until it becomes the parity I need (even/odd)?* If it never reaches that parity, this pattern is impossible.
</spoiler>
<spoiler summary="Solution">
We observe that there are only two possible valid arrangements of parities in the final array:
even, odd, ev...
### [E. Connectivity
Issues](https://codeforces.me/group/hUywLYmr80/contest/660904/problem/E)
40.
[Tutorial] Auxiliary Trees for QlogQ offline queries about Dynamic Forest _This blog post is a submission for the [Codeforces Month of Blog Posts Pt. III](https://codeforces.me/blog/entry/149422) challenge. Thank you [user:cadmiumky,2026-02-09] for the initiative!_
Hello, Codeforces! Recently I heard a short tale about one idea on algocourses.ru (from [user:teraqqq,2026-02-01]) and I realized the idea is powerful, so probably it should be more recognized.
**This post has been written with my best knowledge. If something is incorrect, please let me know!**
#### **Intro**
Dynamic Forest queries are usually solved with [Link Cut Tree (LCT)] (https://youkn0wwho.academy/topic-list/lct). However, for offline queries there's a powerful Divide&Conquer technique that avoids the heavy implementation of LCT. This blog explains this technique. Spoiler: LCT is faster.
<hr>
Related techniques <span style="color: gray; font-size: 70%;">($N$ denotes the number of vertices and $Q$ denotes the number of queries.)</span>:
- [Auxiliary/Virtual tree](https:...
throughout the current time segment can be compressed, provided we preserve the
connectivity between
Tutorial of Practise Dynamic Forest offline queries
41.
Codeforces Round #857 Editorial [problem:1802A]
------------------
Idea: [user:Aleks5d,2023-03-13], Preparation: [user:vaaven,2023-03-13]
<spoiler summary="Solution">
Let's show a construction that maximizes the number of likes. We need to first leave all the likes that we can put, and only then delete them.
To minimize the number of likes, we need to delete the like (if we can) immediately after we post it.
The code below implements these constructs.
</spoiler>
<spoiler summary="Code">
~~~~~
#include "bits/stdc++.h"
using namespace std;
void solve() {
int n;
cin >> n;
int likes = 0, dislikes = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > 0) likes++;
else dislikes++;
}
for (int i = 1; i <= n; ++i) {
if (i <= likes) cout << i << ' ';
else cout << likes * 2 - i << ' ';
}
cout << '\n';
for (int i = 1; i <= n; ++i) {
if (i <= dislikes * 2) cout << i % 2 << ' ';
el...
Let's start with a slow solution of the problem. We will store the connectivity
components (in each
Tutorial of Codeforces Round 857 (Div. 1)
42.
Анонс кружков и дистанционных туров от Тинькофф Поколение Всем привет!
У нас начались вступительные экзамены в образовательные программы Тинькофф Поколение. Я приглашаю вас принять в них участие. В этом году мы хотим попробовать новый формат, который (как мы надеемся) поможет школьникам из регионов начать заниматься и повысить скил решения задач.
**Upd.: хорошие новости для тех, кто любит все откладывать на последний момент: мы продлили вступительные испытания на курс «Алгоритмы и структуры данных» до 13 сентября.**
### Для кого?
Для школьников, которые увлекаются программированием и хотят достигнуть результатов на соревнованиях по информатике. Учим алгоритмическому мышлению и решению олимпиадных задач.
### Форматы проведения занятий
В этом учебном году занятия будут проводиться в 3 разных форматах.
#### 1. Очный
Очные занятия будут проходить по субботам для школьников в Москве и Санкт-Петербурге, с 16:00 до 21:00.
- Москва: Штаб-...
, heavy-light, ladder. - Задачи на графах: паросочетания, потоки, dinamic
connectivity problem
43.
CodeNite 2025 Editorial Thanks for participating in the contest!
Link to access contest: [CodeNite 2025](https://codeforces.me/contestInvitation/faea095b1d894b75d7f176efbe96c6d3f5e09d7a)
[problem:644977A]
Author: [user:jay_jani_0011,2025-10-25]
<spoiler summary="Solution">
$101$
</spoiler>
<spoiler summary="Code - aryansanghi">
~~~~~
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int a, b, c;
cin>>a>>b>>c;
cout<<101<<"\n";
}
}
~~~~~
</spoiler>
[problem:644977B]
Author: [user:aryansanghi,2025-10-25]
<spoiler summary="Hint 1">
Decompose $k$ into its prime factors, i.e. $k=p_1^{x_1}\cdot p_2^{x_2}\ldots p_r^{x_r}$. A subarray $a_l, a_{l+1},\ldots,a_r$ has $LCM$ equal to $k$ if and only if for each $i\in[1\ldots r]$, there exists $a_j, l\leq j\leq r$ such that $p_i^{x_i}$ divides $a_j$, and for no $j$ does $p_i^{x_i+1}$ divide $a_j$.
</spoiler>
<spoiler summary="Solution...
/** @return whether the merge changed connectivity */ bool unite(int x, int y)
{ int
44.
An Interactive Graph Algorithms Visualizer ** Introducing: Graph Algorithm Visualizer**
============================================
A tool to see algorithms in action — built for learners, developers, and competitive programmers.
Hi Codeforces!!
===============
I'm excited to share a project I’ve been building — a fully interactive Graph Algorithm Visualizer that helps you learn and understand common graph algorithms through intuitive visualizations.
Whether you're preparing for contests, brushing up on data structures, or exploring graph theory for the first time, this tool can help you see how algorithms actually behave.
Try it out:
-----------
Live Demo →[See live](https://niravpokiya.github.io/Network-graph-visualizer/)
GitHub Repo → [Github Repo](https://github.com/niravpokiya/Network-graph-visualizer)
Features:
---------
Draw and edit custom graphs (add/remove/move nodes and edges)
Supports both Directed and Undirected graphs
Handles Weighted and Unweighted edges
Toggle Light/Dark mode
...
algorithms are animated in real time, preserving the connectivity of the graph
and clearly showing, All algorithms are animated in real time, preserving the connectivity of the
graph and clearly
45.
Еще о запросах на прямоугольниках… В детстве мне очень нравилась задача 1147 с тимуса [statements](http://acm.timus.ru/problem.aspx?space=1&num=1147). Нравилась в первую очередь тем, что я знал кучу решений, но никак не мог придумать ни одного быстрее, чем за $N^2$. Сейчас у меня наконец появились мысли, как решать эту задачу за NlogN.
Обобщим сперва задачу, чтобы асимптотику оценивать только через N: пусть $A, B < 10^9, color < 10^6$
Я знаю следующие решения, все они используют сжатие координат:
1. Квадродерево за O($N^2$)
2. Решение одномерной задачи деревом отрезков за O(NlogN) => O($N^2$ logN)
3. Решение одномерной задачи проходом слева направо с кучей за O(NlogN) => O($N^2$ logN)
4. Решение одномерной задачи с помощью СНМ за O(N) => O($N^2$) [здесь в оценке я опускаю обратную функцию Аккермана]
5. **Новое:** Решение за O(NlogN) [использует разделяй и властвуй по X и сжатие координат при переходе к подзадаче].
Если кто-то знает что-то еще, расскажите, пожалуйста, в комментариях, мне это буде...
P.S. Это решение просто переиспользует все ту же мою любимую идею из [dynamic-
connectivity](http
46.
Codeforces Beta Round #80 tutorial <p>It will be fully translated later, sorry for slowpoking :(</p>
<table border="0" cellpadding="5" cellspacing="0" width="100%">
<tbody><tr>
<td bgcolor="#cccccc" nowrap="nowrap" width="2%"><div align="center"></div><br></td>
<td bgcolor="#cccccc"><div align="center"> <p><strong>Blackjack (<a href="http://codeforces.me/contest/104/problem/A">problem A, div-2</a>). The problem's author is <span class="Apple-style-span" style="font-family: verdana, arial, sans-serif; font-size: 12px; "><a href="http://codeforces.me/profile/Alex_KPR" title="Подполковник Alex_KPR" class="rated-user user-red" style="font-family: arial; text-decoration: none !important; font-weight: bold; color: rgb(0, 0, 204); ">Alex_KPR</a></span></strong></p>
</div></td>
<td bgcolor="#cccccc" nowrap="nowrap" width="2%"> </td>
</tr>
<tr>
<td bgcolor="#eeeeee"><p align="justify"> </p> </td>
<td bgcolor="#eeeeee"><p align="justify">Obviously, suits are not chan...
graph that a) and b) properties. There is a simple solution: let's check graph
forconnectivity (we
Tutorial of Codeforces Beta Round 80 (Div. 2 Only)
47.
Codeforces Round #334 Editorial Problem 0: Richard has been infected with bovine spongiform encephalopathy. Help Kevin understand what he's saying!
[Div 2 A](http://codeforces.me/contest/604/problem/A)
------------------------------------------------------
**Hint:**
Just do it! But if you're having trouble, try doing your computations using only integers.
This problem is straightforward implementation---just code what's described in the problem statement. However, floating point error is one place where you can trip up. Avoid it by rounding (adding $0.5$ before casting to int), or by doing all calculations with integers. The latter is possible since $250$ always divides the maximum point value of a problem. Thus when we rewrite our formula for score as $\max\left(3\cdot x/10, \left(250-m\right)\cdot x/250\right)$, it is easy to check that we only have integers as intermediate values.
**Code:** http://codeforces.me/contest/604/submission/14608458
[Div 2 B](http://codeforces.me/contest/604/problem/B...
and delete edges from a forest while handling path and connectivity queries.
All of these operations
Tutorial of Codeforces Round 334 (Div. 1)
Tutorial of Codeforces Round 334 (Div. 2)
48.
Strong orientations, and a nice proof of Robbins' theorem **NOTE:** As always, you can also read this on [my blog](https://danielz.fyi/thoughts/strong-orientations)!
---
## Introduction
Per [Wikipedia](https://en.wikipedia.org/wiki/Strong_orientation):
> In [graph theory](https://en.wikipedia.org/wiki/Graph_theory), a **strong orientation** of an undirected graph is an assignment of a direction to each edge that makes it into a [strongly connected graph](https://en.wikipedia.org/wiki/Strongly_connected_graph "Strongly connected graph").
A natural question that follows: *which undirected graphs have a strong orientation?*
## Robbins' theorem
Robbins' theorem states that the set of graphs with strong orientations is precisely the set of *bridgeless* graphs.
*Lemma.* This condition is necessary (i.e. any graph with a bridge cannot have a strong orientation).
*Proof.* This picture should make the argument clear:
If the edge is di...
bridge, we always assign a direction to this edge such that all-pairs
connectivity is preserved. If, , we always assign a direction to this edge such that all-pairs connectivity is
preserved., Our all-pairs connectivity condition means that all nodes $w \in G$ must be
reachable from $u
49.
Testlib and Polygon Updates (June, 2015) Hello, Codeforces!
Previously, my contribution to the development of Codeforces was limited only by rounds preparation ([contest:508], [contest:518], [contest:525]). But a month ago, I joined the wonderful Codeforces team led by Mike Mirzayanov ([user:MikeMirzayanov,2015-06-29]). Traditionally, to understand all the niceties of this project, my work begun from Polygon system. I would like to tell you about its changes.
[Polygon](https://polygon.codeforces.com/) is a system for the preparation of programming problems. All Codeforces rounds and many other olympiads prepared in Polygon. Everyone at any time can use this system.
To edit the files in Polygon now used [Ace Editor](http://ace.c9.io/). It has a nice looking syntax highlighting and autocompletion (you have to press Ctrl + Space). Soon planned to implement this editor in Codeforces.
[cut] <br/>
Unfortunately, [Ace Edito...
("big-tree");`. In the main part of validator after read graph you can check
him onconnectivity and if, connectivity and if the graph is disconnected you may fix it by calling
`feature("disconnected
50.
Кружки и дистанционные туры Tinkoff Generation для школьников Привет! Скоро начнется новый учебный год, а вместе с ним и разные олимпиадные кружки. Я хочу рассказать об одном из них, Tinkoff Generation, а если еще точнее — о курсе алгоритмов в Москве, преподавателем которого являюсь. Мы открылись в прошлом году, получили много фидбека и за лето провели работу по улучшению, так что надеемся, что в этом году кружок будет еще интереснее и полезнее.
Курс алгоритмов проводится еще и в Санкт-Петербурге, Новосибирске, Рязани, Нижнем Новогороде, Екатеринбурге и Ижевске. О других направлениях и городах можете прочитать [здесь](https://fintech.tinkoff.ru/junior). Подробности можете спрашивать у Татьяны Колинковой, контакты которой даны ниже.
### Какой уровень занятий?
В этом году у нас будет пять параллелей: C, B', B, A' и A. Параллели примерно соответствуют соответствующим параллелям в ЛКШ по начальному уровню учащихся, но в среднем программа сложнее, потому что занятий за год сильно больше, чем за одну смену в ЛКШ, практики тоже сильно бол...
, heavy-light, ladder. - Задачи на графах: паросочетания, потоки, dinamic
connectivity problem
51.
Codeforces Round #257 Editorial #### [problem:450A]
You can simply simulate it or find the last maximum $ceil(a_i / m)$.
#### [problem:450B]
We can easily find that every $6$ numbers are the same. It's like ${x, y, y - x, -x, -y, x - y, x, y, y - x, ...}$.
#### [problem:449A] / [problem:450C]
We assume that $n \leq m$ (if $n > m$, we can simply swap $n$ and $m$).
If we finally cut the chocolate into $x$ rows and $y$ columns $(1 \leq x \leq n, 1 \leq y \leq m, x + y = k + 2)$, we should maximize the narrowest row and maximize the narrowest column, so the answer will be $floor(n / x) * floor(m / y)$.
There are two algorithms to find the optimal $(x, y)$.
1. Notice that if $x * y$ is smaller, the answer usually will be better. Then we can find that if $k < n$, the optimal $(x, y)$ can only be ${x = 1, y = k + 1}$ or ${x = k + 1, y = 1}$. If $n \leq k < m$, the optimal $(x, y)$ can only be ${x = 1, y = k + 1}$. If $m \leq k \leq n + m - 2$, the optimal $(x, y)$ can only be ${x = k + 2 - m, y = m}$...
$ in the new graph is more than $1$, because the connectivity of the new graph
won't be changed after
Tutorial of Codeforces Round 257 (Div. 1)
Tutorial of Codeforces Round 257 (Div. 2)
52.
Educational Codeforces Round 38 — Editorial <spoiler summary="A. Word Correction">
Hint: When does some vowel stay in string?
<spoiler summary="Solution">
Iterate over the string, output only consonants and vowels which don't have a vowel before them.
[Model solution](https://pastebin.com/J0py2Gef)
</spoiler>
</spoiler>
<spoiler summary="B. Run For Your Prize">
Hint $1$: It's never profitable to go back. No prizes left where you have already gone.
<spoiler summary="Hint 2">
Hint $2$: The optimal collecting order will be: some prefix of prizes to you and the other prizes to your friend (some suffix).
<spoiler summary="Solution">
You can find the total time with the knowledge of the prefix length. The final formula is $\min(a_n - 1, 10^6 - a_1, \min \limits_{i = 1}^{n - 1} (\max(a_i - 1, 10^6 - a_{i + 1})))$.
[Model solution](https://pastebin.com/mKhxYUxK)
</spoiler>
</spoiler>
</spoiler>
<spoiler summary="C. Constructing Tests">
Hint: At first we will solve the problem mentioned in the statem...
To solve the problem we consider now, you have to use a technique known as
dynamicconnectivity
53.
A brief introduction of Tarjan and E-DCC（EBC) The algorithm of Tarjan is used to solve some problems which is about the connectedness of the Graph. Today I am going to introduce the key to solving E-DCC by Tarjan.
[This problem](https://www.luogu.com.cn/problem/P8436) is the template of E-DCC.
Defination : What is E-DCC?
---------------------------
The full name of E-DCC is **edge double connectivity component**.
Some people call it EBC (Edge Biconnected Component).
An E-DCC is a component that you cut any one of the edges, the graph is still connected.
For example, in this graph, nodes in same color are in the same E-DCC, and there are $3$ E-DCCs in this graph. They are:
- node $1$
- node $2$, $3$, $4$, $5$, $6$
- node $7$
Solution : How to find E-DCC by Tarjan?
------------------
### Bridge
First, we should know what **BRIDGE** is.
- A bridge is an edge in the graph, and if you cut the edge off, the graph is not connected.
...
The full name of E-DCC is **edge double connectivity component**.
54.
A brief introduction of Tarjan and V-DCC The algorithm of Tarjan is used to solve some problems which is about the connectedness of the Graph. Today I am going to introduce the key to solving E-DCC by Tarjan.
[This problem](https://www.luogu.com.cn/problem/P8435) is the template of V-DCC.
Defination : What is V-DCC?
===========================
The full name of E-DCC is vertex double connectivity component.
An E-DCC is a component that you cut any one of the vertexs, the graph is still connected.
For example, in this graph, nodes in same color are in the same V-DCC, and there are $3$ V-DCCs in this graph. They are:
- node 1, 3
- node 2, 3, 4, 5, 6
- node 2, 7
Solution : How to find V-DCC by Tarjan?
=======================================
### Cut vertex
First, we should know what "cut vertex" is. A "cut vertex" is a vertex in the graph, and if you cut the vertex off, the graph is not connected.
### Tarjan
Tarjan is one of the al...
The full name of E-DCC is vertex double connectivity component.
55.
Need help for 100551E.Disconnected Graph Hello lady/bros, I am struggling with [100551E.Disconnected Graph](https://codeforces.me/gym/100551/problem/E).
I have considered:
(1) Online fully dynamic graph connectivity. I copied a piece of code here: https://www.luogu.com.cn/problem/solution/P5247. I passed [LuoguP5247](https://www.spoj.com/problems/DYNACON2/) and [SPOJDYNACON2](https://www.spoj.com/problems/DYNACON2/), however I could not pass this problem;
<spoiler summary="SPOJ Code">
~~~~~
#include <iostream>
#include <unordered_set>
#include <stack>
#include <unordered_map>
#include <cstring>
#include <vector>
#define GUARANTEE_LEGAL 0
#define fastio std::cin.tie(0) -> sync_with_stdio(0)
struct LCT {
std::vector<std::array<int, 2>> c;
std::vector<int> fa, sta, subtree_size, subtree_size2;
std::vector<char> r;
struct Tag {
// Only stores edges of this level.
std::unordered_set<int> edges;
int tag;
std::unordered_set<int> tagged_non_preferred_children;
};
std::vector<Tag> tag_tr...
I have considered: (1) Online fully dynamic graph connectivity. I copied a
piece of code here
56.
Codeforces Round #111 (Div. 2) Solution UPD:Minor mistakes in grammar and expression fixed.
Disclaimer: This is not an official editorial.
If you have better or easy-to-understand solutions and thoughts, feel free to share your idea. Also welcome to point out mistakes so I can fix it.
### [problem:160A]
It's obvious that you should take the most valueable coins. so sort values in non-decreasing order, then take coins from the most valueable to the least, until you get **strictly** more than half of total value.
Time complexity depends on the sorting algorithm you use. O(n^2) is also acceptable, but if you use bogosort which runs in O(n!)...
### [problem:160B]
Deal with the situation that "first half is strictly less than second half" first. the other one can be solved accordingly.
You can use greedy here: sort digits in first and second half seperately. then if the i-th digit in first half is always less than i-th in second half for 1<=i<=n, answer is YES.
Time complexity is as same as problem A. Count...
compoment), this edge must not appear in any MSTs. If after deleting an edge V
in G', G'sconnectivity, union here to maintain connectivity.
Tutorial of Codeforces Round 111 (Div. 2)
57.
Codeforces Trainings Season 1 Episode 4: Editorial ### A. Arrangement of RGB Balls
(difficulty: easy)
If, among 3 consecutive balls, there are no two of the same color, then there's exactly one ball of every color among them. Thereforce, the sequence is determined by the order of the first 3 balls. Imagine these are RGB; then, the sequence continues as RGBRGBRGB...
There are only $3!=6$ possible initial triples, so we can try all the sequences defined by them, and for every one of them, check if it can be constructed.
[cut]
When is it possible to construct such a sequence? Take the initial triple to be "GRB", for example (the idea for other triples is analogous). It's clear that the sequence is "GRB" repeated some $K$ times, and after that, there are the first 0, 1 or 2 balls from that triple (for example, "GRBGRBGR" or just "G"). It's clear that $K=min(R,G,B)$. So it's possible to construct iff $1\ge G-K \ge R-K \ge B-K$.
Testing the existence of any sequence can be done in $O(1)$ time like this. There are $O(1)$ possib...
Let's say we have $C$ connected components. We can remove $M-(N-C)$ edges so
that theconnectivity
58.
Topic wise Coding Resources So I made this listing for topic wise coding resources.
It is open sourced [here](https://github.com/hkirat/awesome-competitive-coding)
Thought of sharing it here too!
# Awesome Competitive Coding [](https://github.com/sindresorhus/awesome)
A Curated list of Topic wise Theory and Questions to Get You Started On Competitive Coding.
*Inspired by the [awesome](https://github.com/sindresorhus/awesome) list thing. You might also like to read complete [awesome-list](https://github.com/sindresorhus/awesome).*
### Contributing
Kindly Go Through [Contribution Guidelines](https://github.com/hkirat/awesome-competitive-coding/blob/master/CONTRIBUTING.md) First.
Topics
---
- Binary and Ternary Search
- Dynamic Programming
- Flow
- Game Theory
- Graphs
- Greedy
- Maths
- Matrix Exponentiation
- Miscellaneous
- Prefix and Suffix Trees
- Segment Trees...
involve finding shortest distance, connectivity and flow.*
59.
A2SV G6 — Round #17 (Editorial) [Here](https://codeforces.me/contestInvitation/d0fa2e52f2536e5772ccae5a4ce5e5258fbadba7) is the contest link.
All problems are from Codeforces' Problemset.
#### [A. Friendship is magic!^^](https://codeforces.me/gym/613323/problem/A)
<spoiler summary="Solution">
Keep two counters, one for Mishka and one for Chris. For each round, compare the two dice values and if Mishka’s is higher, increment her counter; if Chris’s is higher, increment his. At the end, compare the totals: if Mishka has more, she wins; if Chris has more, he wins; if they’re equal, it’s a draw, so print “Friendship is magic!^^”.
</spoiler>
<spoiler summary="Code">
```python3
from collections import Counter
wins = Counter()
for _ in range(int(input())):
a, b = map(int, input().split())
if a > b:
wins['Mishka'] += 1
elif a < b:
wins['Chris'] += 1
if wins['Mishka'] > wins['Chris']:
print("Mishka")
elif wins['Chris'] > wins['Mishka']:
print("Chris")
e...
maintain connectivity., significant. For each bit, decide if it *must* be set in the final answer to
maintainconnectivity, # Check connectivity: can we connect the graph using only edges with i-th bit =
0, 3. **Connectivity Check**: Use DSU to check if all $N$ vertices can be
connected using only these
60.
Yandex.Algorithm Online Round 1 Analysis In the first online round of Yandex.Algorithm competition 609 participants submitted at least one solution and 396 submitted at least one correct solution. Problems _Non-Squares_ and _Kingdom Division_ were fairly easy, both resulted in approximately 300 correct submissions. Problem _Stacks of Coins_ was moderately easy and was solved by 145 participants. The three other problems proved to be more difficult. _Stickers_ could be a very challenging string problem, but small input size allowed for dynamic programming solution, which 22 contestants got right. _Assistants_ was solved by 13 participants; it required binary search, greedy, and some basic data structures to get it under time limit.During the contest, nobody was able to solve _State Roads_, which was a neat graph-theoretical problem with a simple to code, but a quite tricky solution.
Congratulations to [user:Kenny_HORROR,2013-07-15] who was the only one to solve five problems, and to [user:Petr,2013-07-15], [user:tourist,20...
In the first step we forget for a moment about the requirement of connectivity
and ask what sizes
61.
Editorial of ICPC de Tryst 2026 I hope you enjoyed the contest!
[Contest link](https://codeforces.me/contestInvitation/f8ab858a73f3627f85787c828e7ba84d12495ce9)
<spoiler summary="Rating Predictions and Tags for the Problem">
| Problem | Expected Rating | Tags|
| :---: | :---: | :---: |
| [A. Game is Game](https://codeforces.me/gym/675631/problem/A) | 1500 | games, math |
| [B. Hakurei Shrine's Purification Ritual](https://codeforces.me/gym/675631/problem/B)| 1600 |number theory, binary search|
| [C. Permutation Game](https://codeforces.me/gym/675631/problem/C) | 2600 | dp, greedy, implementation,brute force |
| [D. Path Blow-up?](https://codeforces.me/gym/675631/problem/D) | 2400|bitmasks, trees, dp, combinatorics, implementation|
| [E. Coffee Date of MEX](https://codeforces.me/gym/675631/problem/E)|2100|constructive algorithms, brute force|
| [F. Wordleforces](https://codeforces.me/gym/675631/problem/F) |1800 |math, combinatorics|
| [G. Adaptive Guessing](https://codeforces.me/gym/675631/probl...
maintain connectivity with its parent, and the remaining $size(u)−1$ labels
must be distributed among
62.
Minimize pairwise connectivity after removal of a node Problem:
You are given an undirected connected graph and a set of Q queries. Each query involves removing a vertex 'v' from the graph. After removing vertex 'v', the subtree of 'v's child is disconnected from the rest of the graph and is treated as a separate component. For each such component, calculate the value v(v-1)/2, where v is the count of vertices in that component.
The goal is to minimize the pairwise connectivity after removing each node. The pairwise connectivity is the sum of v(v-1)/2 for all components resulting from the removal of the node 'v'.
Input:
A connected undirected graph with nodes (vertices) and edges.
Q queries, each specifying a vertex 'v' to be removed.
Output:
For each query, output the minimum pairwise connectivity after removing the specified vertex 'v' according to the rules defined above.
Constraints:
The number of nodes (vertices) in the graph is less than or equal to 20^5.
The number of queries is less than or equal to 20^5.
Queries...
Minimize pairwise connectivity after removal of a node, minimize the pairwise connectivity after removing each node. The pairwise
connectivity is the sum of v, Output: After removing vertex 1: Pairwise connectivity = 4 After removing
vertex 2: Pairwise, Output: For each query, output the minimum pairwise connectivity after removing
the specified, The goal is to minimize the pairwise connectivity after removing each node. The
pairwise
63.
Editorial - Codeguerra Editorial — Codeguerra
==================
[contest:663321]
------------------
[Problem A : Hawkins Rift](https://codeforces.me/gym/663321/problem/A) <br>
Author : [user:vishwas_16.0,2026-01-30]
<spoiler summary="Hint 1"> Notice that the rift at index $n$ is always stable, because $a_n \le n$ for every possible value.</spoiler>
<spoiler summary="Hint 2"> $n$ can be as large as $10^{18}$. Do we really need to compute factorial up to that value? Think about the modulus $69696$ </spoiler>
<spoiler summary="Solution"> We want arrays where after choosing exactly one index $i$ and setting $a_i=i$, there is exactly one stable rift ($a_i \le i$).
All other positions must be unstable $\Rightarrow a_j > j$.
Since position n is always stable eleven has no choice but to chose it. There are total of n different values for last index $\rightarrow n$ ways.
Number of choices for rest:
<ul> <li>Index 1 $\rightarrow (n-1)$ choices</li> <li>Index 2 $\rightarrow (n-2)$ choi...
connectivity.
64.
Full Java Topics (Core -> Advanced && JDBC) Here are all the Java topics from Core to Advanced (up to JDBC):
CORE JAVA
**Introduction to Java**
1. JDK, JRE, JVM
2. Data Types & Variables
3. Operators
4. Control Statements (if, else, switch)
5. Loops (for, while, do-while)
6. Arrays
7. Strings & String Methods
8. Methods & Method Overloading
9. Recursion
**OBJECT-ORIENTED PROGRAMMING (OOP)**
10. Classes & Objects
11. Constructors
12. this Keyword
13. Inheritance
14. Method Overriding
15. super Keyword
16. Polymorphism
17. Abstraction
18. Encapsulation
19. Interfaces
20. Abstract Classes
21. final Keyword
22. static Keyword
23. Instance & Static Blocks
**PACKAGES & ACCESS MODIFIERS**
****
24. Packages
25. Access Modifiers (public, private, protected, default)
26.import Statement
**EXCEPTION HANDLING**
27. Types of Errors
28. try, catch, finally
29. throw & throws
30. Custom Exceptions
31. Checked & Unchecked Exceptions
**JAVA I/O**
32. Scanner Class
33. BufferedReader
...
**JDBC (Java Database Connectivity)**
65.
Editorial Codeforces Round #266 (Div. 2) [problem:466A]
-------------
Solution of this problem is based on two claims: <br>
— If $m\cdot a\le b$ then there is no point to buy a ride ticket. <br>
— Sometimes it is better to buy summary more ride tickets for amount of rides than we need. <br>
If we receive profits bying ride tickets then number of such ones will be $x = \lfloor \frac{n}{m} \rfloor$. For the remain $n - m\cdot x$ rides we must choose the best variant: to buy separate ticket for each ride, or to buy ride ticket and use it not fully.
**Complexity**: $O(1)$<br>
**Solution**: [submission:7784793]
[problem:466B]
-------------
Let’s assume that $a\le b$.
First of all, let’s consider the situation when we can already accommodate all the students. If $6\cdot n\le a\cdot b$ then answer is $a\cdot b$ $a$ $b$.
Otherwise, we have to increase one of the walls(maybe, both). Let’s do it in the following way: iterate the size of the smallest wall $new_a$ ($a\le new_a\le \lceil \sqrt{6\c...
parent of $x$ in final graph and that $x$ and $y$ is currently belong to the
sameconnectivity, . Also, we will say that two vertexes belong to the same connectivity component
if they belong to the
Tutorial of Codeforces Round 266 (Div. 2)
66.
Everything About Dynamic Programming **I decided to gather some good material on the web related to DP and found some good explanation by svg on topcoder forums..Hence wrote this blog.Will format it when i get time.**
**Problem:**
About 25% of all SRM problems have the "Dynamic Programming" category tag. The DP problems are popular among problemsetters because each DP problem is original in some sense and you have to think hard to invent the solution for it. Since dynamic programming is so popular, it is perhaps the most important method to master in algorithm competitions.
The easiest way to learn the DP principle is by examples. The current recipe contains a few DP examples, but unexperienced reader is advised to refer to other DP tutorials to make the understanding easier. You can find a lot of DP examples and explanations in an excellent tutorial Dynamic Programming: From novice to advanced by Dumitru. The purpose ...
increase for sure but the connectivity will remain the same. So we can assume
that in optimal solution, is exact transmitter range required for connectivity and m is minimal number
of used moves possible, to check connectivity of our chain. Also not to exceed move limit we have to
include number of
67.
The Competitive Programmer Graphs Handbook Hey everyone, I'm thrilled to share with you my upcoming book on graph theory! As a former competitive programmer, I have found graph theory to be one of my favorite topics. I've curated a collection of problems to captivate you and help you dive into this fascinating subject.
By publishing this book publicly and updating it based on your early feedback, I'm offering you a unique opportunity to be part of the entire process. Your support will give you early access to the ebook at a discounted price, lifetime access to all versions and future editions, and a chance to shape the evolution of this book. Let's embark on this exciting journey into graph theory together! For more details, check out the [post](https://albexl.substack.com/p/the-competitive-programmer-graphs).
**Update**. [Here](https://albexl.substack.com/p/the-competitive-programmer-graphs-270) is the list of the topics published so far.
**Update #2:** Here are the articles covering some of the topics I am writing ab...
-graphs) - [Paths, Connectivity, and Trees](https://albexl.substack.com/p/paths-
connectivity-and, -induction-graphs) - [Paths, Connectivity, and
Trees](https://albexl.substack.com/p/paths-connectivity
68.
Notes on Codeforces Beta Round #76, Div2-A, B, C, D, E, Div1-E [problem:94A]
A simple problem with straightforward solution. Divide the given string into 8 parts with the same length 10, and convert each of them to a decimal digit according to the provided mapping relationship.
[problem:94B]
Generate all the feasible $C_5^3$ patterns, and check whether there exist any three people that are either known or unknown to each other. The mutual relationship can be represented by the connectivity of graph.
[problem:94C]
This is a horrible problem...There are a huge number of cases that should be considered. One of the cases that is likely to be ignored is shown as follows:
Suppose that $m=4, n=100$, and $a=3, b=10$. One might give $3$ as the answer. However the answer should be $2$, since we can first select $3, 4, 7, 8$, and then select $5, 6, 9, 10$.
[problem:94D]
It turns out that greedy algorithm solves this problem. Assume that we have $n$ segment lines with the same length $w$, and we put them one after another, i.e., the $i...
connectivity of graph.
69.
CC Wing Selection Contest 2026 Editorial CC Wing Selection Contest 2026
==================
[contest:709193]
------------------
</br>
[Invitation Link](https://codeforces.me/contestInvitation/6272dbd500a98e5b9fb8fdc43969fd8573242e5a)
</br>
[Problem A : Terms and Conditions](https://codeforces.me/gym/709193/problem/A) <br>
Author : [user:vishwas_16.0,2026-08-12]
<spoiler summary="Hint 1"> The input is irrelevant. The required output is fixed and must be printed exactly as given.</spoiler>
<spoiler summary="Solution"> This is a direct output problem.
We are given a single string as input, but regardless of what the input contains, we must print the four Terms and Conditions exactly as specified in the statement.
Since the required output is constant, there is no need to process the input.
Just print:
You confirm that you are a IIIT Allahabad Batch 2029 student.
You understand that providing false information, copying code may result in removal from the wing.
You accept that parties wil...
the new graph is more than 1, because the connectivity of the new graph won't
be changed after
70.
All the algorithms/techniques I have used "I'm just in a mood to shitpost. Don't take it too seriously." -Um_nik
#### Graphs
- DFS
- BFS
- 0-1 BFS
- Kruskal's
- Dijkstra's
- Bellman-Ford
- 2-Coloring
- Prim's
- Floyd-Warshall
- Johnsons
- Ford-Fulkerson
- Dinics
- Edmonds-Karp
- Level Graphs
- SCC
- 2VCC/2ECC
- 2-Sat
- Dominator-Trees
- Hopcroft-Karp
- Hungarian
- MCMF
- Top Sort
- Blossom's
- Eulerian Cycle
- Hamiltonian Cycle
- TSP
- Functional Graphs
- Augmenting Paths
#### DP
- Range DP
- Divide and Conquer DP
- Convex Hull Trick
- Space Save
- Alien Trick
- Bitmask DP
- State Switch
- Digit Descent
#### Strings
- Hashing
- KMP
- Z-function
- Trie
- Aho Corasick
- Suffix Automaton
- Suffix Tree
- Suffix Array
- Eertree
- Manachers
#### Data Structures
- Segment Tree
- Prefix Sum
- DSU
- DSU Rollback
- Treap
- Binary Indexed Tree
- Queue
- Stack
- Priority Queue
- Linked List
- Sets
- Maps
- Bitsets
- Ordered Statisic Tree
- Lazy Propagation
- Li Chao...
Connectivity - Parallel Binary Search - XOR Hashing - Coordinate Compression -
Meet in the Middle
71.
Solution should be faster due to lesser amount of operations but gives TLE? I was doing the following question:
https://codeforces.me/contest/2044/problem/F
Upon doing this question, I used a method that gives the solution in O(nq) time (about 2 * 10^5 * 5 * 10^4 = 10^10 operations). Code is as follows:
https://codeforces.me/contest/2044/submission/304178376
<spoiler summary="Spoiler">
~~~~~
// #include <bits/stdc++.h>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
// #define INT_MAX 2147483647
// #define INT_MIN -2147483648
#define HAS_TESTCASE 0
bool CHECK_FOR_TESTCASE = false;
bool CHECK_NOW = false;
bool FIRST_TESTCASE = true;
using namespace std;
// For tree, uncomment below
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// ...
/** @return whether the merge changed connectivity */
72.
Invitation to Geekhaven Contest Geekhaven the technical society of IIIT Allahabad is organising its first open contest for the year 2019. The contest will be held on Codechef and will start at 10:00 PM on 19th April, 19. We hope to see you all on the leaderboard in large numbers.
Contest Link : https://www.codechef.com/GHC22019
Prizes : Codechef Laddus for top 3 in the leaderboard.
**Update :** Hints of the questions are given below, Full editorials of the questions will be posted soon.
<spoiler summary="Round Around">
We can run a loop for every position (not A and B) and check whether this will give the minimum sum of the number of jumps and update the answer accordingly.
</spoiler>
<spoiler summary="Battle of the Bests">
Total runs scored for a delivery of speed x is max(reliability[i][p] * x + experience[i][p]) for all 1 <= i <= n. So you need to find the line with maximum value of y for a given x if you consider y = reliability[i][j] * x + experience[i][j] as a linear equation.
</sp...
the vector in increasing order of weights.Loop and get connectivity(number of
connected components
73.
CodeForces 285 & 286 Simple & Quick Summary.
#### **CF 285**
A: The key point is **Forest**. So find the vertex node with degree of 1, we can get an edge. Repeat it until no more found.
B: Conversion between Factorial base and Normal decimal base. Use a binary indexed tree to keep numbers have appeared and find the amount of numbers less than the current number. Basically:
* Normal -> Factorial `fnum[i] = num[i] - less_than_i`
* Factorial -> Normal binary search `k` that `k - less_than_k = fnum[i]`
C: I **misunderstood** the meaning during the contest: find the number of sub-strings which can be rearranged to be a palindrome.
Then I tried to use a naive method, divide the array to K(usually sqrt(n)) blocks. For each block, use `set<int>` to record its state, do a "swap line" with each start point. The complexity can be reached `O(N*sqrt(N)*log(N))`, also huge.
The right task is: find the number of sub-strings which can be rearranged to make the total string to be a palindrome.
It s...
B: Rebuild a directed graph to keep the original connectivity. It's **NOT**
necessary to use the, Hash vertex ID in each colored map, and use a disjointed set to keep the
connectivity. Then do an, connectivity. First find all the SCC(Strong Connected Component), shrink the
original map to a DAG forest
74.
Codeforces Beta Round #80 - unofficial editorial <p></p><div><b>A-div2:</b></div><div>First, we need to calculate n - 10 (because the queen of spades costs 10 points). If the difference stands in the [1;9] segment or is equal to 11, then the answer will be 4, because there are 4 cards for each cost. If the difference is 10, then the answer will be 15, i.e. 4 tens, 4 jacks, 3 queens (the queen of spades has been extracted from the pack) and 4 kings. And it's obvious that in all other cases the answer will be 0.</div><div><br></div><div><b>B-div2/A-div1:</b></div><div>We need to use the following recurrence relation: count[i] = count[i - 1] + 1 + (answers[i] - 1) * i, and remember that count[1] = answers[1]. The answers[i] array contains the count of answers for the i-th question, count[i] - count of clicks that you need to answer the i-th question.</div><div>Explanation of the formula:</div><div>To answer the first question, we need to brute-force all of the answers to it. To answer the i-th question, we need to answer the (i-1)-th qu...
We need to check the graph for connectivity and count loops in it using DFS. If
the graph is
75.
[Mini Tutorial] Memory optimization for DSU with rollbacks We'll assume that the DSU is implemented as "union by size" using two arrays, both of length equal to the number of vertices in the graph: $par_v$ to represent $v$'s parent within the DSU forest (or $v$ itself if it is a root), and $sz_v$ to represent the size of $v$'s subtree.
We note that adding an edge $\\{ u, v \\}$ to the graph we want to maintain connectivity on is implemented by walking up to the root of $u$ and the root of $v$, and if they are equal, we do nothing, otherwise we add an edge between the roots, having the root of lighter component be the child of the root of heavier component.
This introduces two changes to the underlying arrays, and implementing rollback of an array is easily achieved by storing a stack of indices and previous values. This means each change in the DSU could store four integers' worth of space.
However, you actually only need one integer: the node that was chosen to be the child, let's call it $v$. This is because to restore the previous ...
adding an edge $\\{ u, v \\}$ to the graph we want to maintain connectivity on
is implemented by walking, We note that adding an edge $\\{ u, v \\}$ to the graph we want to maintain
connectivity on is
76.
ABBYY Cup 2.0 — Hard: solutions **UPD1:**
### Editorial to Problem <<Greedy Merchants>>
First of all note that merchants will pay only for those edge which are bridges. All other edges don’t match as after their deletion graph stay connected and between any nodes of graph the way stay. So first step to solve problem is to search bridges. Use this algorithm which works at $O(n+m)$
After deletion all the graph bridges graph is divided for some components of connectivity (maybe one component). Let’s build new graph in which recieved components will be nodes and bridges --- edges. This graph will be a tree. The graph is connected therefore the tree is connected. The edges correspond to bridges therefore there is no cycles in the tree.
Note that the number of denarii means the pay of every merchant --- is a distance between some the nodes in a new graph. But as this graph is a tree this distances can be easily find out using LCA search algorithms for two nodes. In this problem one should use the simplest ...
can lose their connectivity. These problems can be solved by deletion little
black components and, components and it is not losing connectivity. However previous way is more
reliable., After deletion all the graph bridges graph is divided for some components of
connectivity (maybe
Tutorial of ABBYY Cup 2.0 - Hard
77.
Can Link Cut Trees handle subtree aggregates? I'm somewhat familiar with how Link Cut Trees work. I have watched Erik Demaine's lecture on them from MIT Open Courseware, solved a couple problems that use them with my team's (very copy-pasteable) book code, and read about them a bit, so I have an idea of how they work in general.
The code I have used supports range path update, path query, link, cut, and checkConnected queries. I read on Wikipedia that Euler Tour Trees are better for subtree queries and link cut trees are better for path queries. However, I looked through [user:ko_osaga,2020-03-18]'s code [for fully dynamic connectivity](https://loj.ac/submission/766449) and it looks like he is using a splay tree or link-cut tree of some sort. Link-cut trees use splay trees to store preferred paths, so the size of a splay tree node's subtree doesn't really mean anything, right? But for the dynamic connectivity problem he was trying to solve, I'm pretty sure you need to check, after cutting an edge, which of the trees you created...
connectivity](https://loj.ac/submission/766449) and it looks like he is using a
splay tree or link
78.
A2SV G6 — Round #13 [Editorial] [Here](https://codeforces.me/contests/607625) is the contest link. All problems are from Codeforces' problemset except problem D.
#### [A. Can I Get Your Number ?](https://codeforces.me/gym/607625/problem/A)
<spoiler summary = "Hint1">
<p>We don’t have to check the common prefixes of all the given strings</p>
</spoiler>
<spoiler summary = "Hint2">
<p>We only need to find the longest common prefixes of the lexicographically smallest and largest strings among the given <b>n</b> strings.</p>
</spoiler>
<spoiler summary = "Solution">
<p>
First let’s accumulate the given strings in an array and sort them. Then if a prefix is common for both the first and the last strings, then it’s known for sure that it’s also a prefix for all the strings in between as the array is in sorted order the strings are binary strings.
We can use one for loop and check up to which point the first and the last strings are identical and that will be our answer.
</p>
<p></p>
<p><b>Tim...
>
* This links all vertices within each tree; extra cycles don't affect
connectivity.
* Run
79.
Editorial Codeforces Round #236 ##[problem:402A]
Let's fix some value of boxes $ans$. After that we can get exactly $cnt = ans + min((k - 1) * ans, B)$ of sections. So, if $cnt * v \ge a$, then $ans$ be an answer. After that you can use brute force to find smallest possible value of $ans$.
##[problem:402B]
Let's fix height of the first tree: let's call it $a$. Of course, $a$ is an integer from segment $[1, 1000]$. After that, for the fixed height $a$ of the first tree we can calculate heights of the others trees: $a, a + k, a + 2k$, and so on. After that you should find minimal number of operations $ans$ to achive such heights. After that we can use brute force to find smallest possible $ans$ for each $a$ from $1$ to $1000$. For best height of the first tree you should print all operations.
##[problem:402C] / [problem:403A]
I will describe two solutions.
First. Consider all pairs $(i, j)$ ($1 \le i < j \le n$). After you should ouput the first $2n + p$ pairs in lexicographical order.
It's clear t...
Let's look at the matrix $a$ as a connectivity matrix of some graph with n
vertices. Moreover, if
Tutorial of Codeforces Round 236 (Div. 2)
Tutorial of Codeforces Round 236 (Div. 1)
80.
The Connectivity Problem Would you like to know what Uber, Google Maps, and your favorite airline have in common?
They all know how to solve the Connectivity Problem.
This post is the third (and last) of the introductory series in my upcoming book, The Competitive Programmer Graphs Handbook.
Take a look at the post to understand the foundations of graph traversals and connected components before we dive into more complex topics in future editions.
Enjoy.
https://albexl.substack.com/p/the-connectivity-problem
The Connectivity Problem, all know how to solve the Connectivity Problem. This post is the third (and
last) of the, They all know how to solve the Connectivity Problem., https://albexl.substack.com/p/the-connectivity-problem
81.
Codeforces Round #212 (Div. 2). Tutorial. Part 1. [problem:362A]
Autors have proposed different solutions. One can notice that if semiknights did not have a meeting after first step (it is not necessary they have a meeting in "good" square), they will not meet at all. This fact appears from board size and possible semiknight's moves. As the initial semiknight's squares are considered good for the meeting the semiknights have arrived to the one square and then they move together to one of the initial squares and meeting will count.
[problem:362B]
One has to note that the number of dirty stairs $\le 3000$. Petya can reach stair number $n$ if the first and the last stairs are not dirty and there are not three or more dirty stairs in a row. So let sort the array of dirty stairs and go through it, checking for three or more consecutive dirty stairs. Also one need to check if the first or the last stair is in this array.
[problem:362C]
The number of times swap is called equals the number of inversions in the input permutatio...
If the given graph contains less than $q$ connectivity components, then there’s
no solution
Tutorial of Codeforces Round 212 (Div. 2)
82.
A2SV Contest #23 Editorial [Here](https://codeforces.me/contestInvitation/aa5538088b7a06cee3169aeed4c171ef954ce504) is the link to the contest. All problems are from Codeforces' problem set.
[A. Verifying Access Keys](https://codeforces.me/gym/625306/problem/A)
<spoiler summary="Solution">
To determine if each access key is **secure**, we need to validate it against **three specific rules**.
1. **Digits appear before letters:**
All digits (if present) must appear before any letters. This means the transition from digits to letters can happen **only once**, and once it does, **no digit should appear afterward**.
- For example, `"123abc"` is valid, but `"a1b2"` is not.
2. **Digits are non-decreasing:**
The digits must be in **non-decreasing order**. As we read through the digits from left to right, each digit must be greater than or equal to the previous one.
- For example, `"1125"` is valid, but `"132"` is not, because `3` comes before `2`, which violates the order.
3. **...
$G$’s connectivity.** - Calculate how many connectivity fixes are needed to
make $F$ and $G, **does not respect the connectivity of $G$** and should be **removed** from
$F$. - Each such, in the future, and mastering it will make solving connectivity problems like
this much easier and, , it might have **more connected components** than $G$. - To preserve $G$’s
connectivity, the, - The **sum of edges removed** plus - The **number of connectivity fixes**
described above., Thus, the total operations to transform $F$ to have the same connectivity as
$G$ is:
83.
Graph theory problem that requires transitive reduction Hi. I am trying to solve [this](https://dunjudge.me/analysis/problems/1433/) problem.
For convenience, I have summarized the problem statement below (based on my understanding):
_Given a directed graph with $N$ vertices and $E$ edges (with cycles and not necessarily connected), find the minimum number of edges that we need to retain such that connectivity between vertices is retained as given in the original graph._
Input size: $ 1 \le N, E \le 2e5 $ <br/>
Time limit: $1s$
For example, for the following graph:
<img src="https://image.ibb.co/jox8C6/graph.png" alt="graph" border="0">
We should retain the edges:
~~~~~
0 -> 1
1 -> 2
1 -> 3
~~~~~
So we must use a minimum of 3 edges.
Note that:<br/>
`0 -> 2` is redundant as we can use the path `0 -> 1 -> 2` to get from `0` to `2`.<br/>
`0 -> 3` is redundant as we can use the path `0 -> 1 -> 3` to get from `0` to `3`. (Thanks [user:filippos,2017-12-14] for catching this mistake!)<br/>
This problem seems ...
), find the minimum number of edges that we need to retain such that
connectivity between vertices is
84.
Сборы в Ростове и Самаре: Результаты, впечатления участников Подошли к концу сборы в Самаре, [организованные фондом Виктора Шабурова Botan Investments](http://codeforces.me/blog/entry/47110) на базе Самарского университета. Артем [user:VArtem,2016-10-03] Васильев, чемпион ACM ICPC 2015, и Николай [user:Niko,2016-10-03] Ведерников в течение рабочей недели готовили участников к четвертьфиналу. В сборах приняли участие восемь команд: пять команд Самарского университета, две команды УлГТУ (ребята специально приехали из Ульяновска) и одна из ПГУТИ. Команды каждый день писали пятичасовые контесты, а после Артем Васильев проводил разбор задач, попутно рассказывая незнакомые ребятам темы.
Как отмечают все участники, сборы проходили в боевой обстановке. По итогам заключительного контеста лучшей стала команда Самарского университета **Hater** в составе Славы [user:Slamur,2016-10-03] Муравьева — поздравляем! Отсутствие сокомандников не помешало ему выиграть большую часть контестов.
Перед поездкой в Самару Артем и Николай также провели недельны...
connectivity (динамическая связность), также некоторые виды динамик, некоторые
виды просто каких-то
85.
Help in Dynamic Connectivity problem Hello Codeforces! <br>
problem link: [Connect and Disconnect](https://codeforces.me/gym/100551/problem/A)<br>
my buggy solution:
<spoiler summary="Spoiler">
~~~~~
/**
* “Experience is the name everyone gives to their mistakes.” – Oscar Wilde
*
* author : prodipdatta7
* created : Thursday 26-March, 2020 08:55:24 AM
**/
//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <iterator>
#include <bitset>
#include <assert.h>
#include <new>
#include <sstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")
using namespace std ;
using na...
Help in Dynamic Connectivity problem
86.
Notes on Codeforces Beta Round #80, Div2-A, B, C, D, E [problem:104A]
Determine the result based on each value of $n$ carefully.
[problem:104B]
We use $a[1], a[2],...,a[n]$ to denote the given $n$ values. To achieve the maximum number of clicks, it is obvious that we should first choose $a[i]-1$ wrong answers and then select the correct one, for every $i$. For $a[i]$, we have $a[i]-1$ wrong answers, and thus we start from $1$ to $i-1$ for $a[i]-1$ times, which gives $(a[i]-1)\times (i-1)$ clicks. Also remember that $i$ contributes $a[i]$ clicks, and this gives totally $(a[i]-1)\times (i-1)+a[i]$ clicks before we move to index $i+1$. Therefore, we enumerate all the elements, and add the answers together.
[problem:104C]
Let us consider what form can such a graph have. There are $n$ nodes and only one circle. This implies that we must have $n$ edges as well, i.e., $m=n$. Next, after deleting some single edge, we will surely obtain a connected tree. Therefore, we can adopt a double loop to check if we can obtain a connected tree...
connected tree by eliminating some edge. The connectivity can be simply
checked by using Union-Find.
87.
Notes on Codeforces Beta Round #122, Div2- A, B, C, D, E [problem:194A]
Suppose that we have $m$ exams with value $2$. Then, we have $2m+3(n-m)\le k \le 2m+5(n-m)$. As the problem guarantees that there is at least one reasonable answer, we have $m\ge 3n-k$. Therefore, the answer should be $max(3n-k, 0)$.
An intuitive understanding of the above result is that we can first assign $3$ to all the $n$ exams. If $3n\le k$, it means that we can assign the extra $k-3n$ values to some exams and we have zero $2$s. On the other hand, we have $3n>k$, and thus we have to “set” at least $3n-k$ exams from $3$ to $2$.
[problem:194B]
By some simple induction, one can see that we should find the minimum positive integer $k$ so that $k(n+1)$ is a multiple of $4n$. The result is that $k=\frac{4n}{gcd(n+1, 4n)}$.
[problem:194C]
Let the number of “#” is $k$. If $k\le 2$, the answer is “impossible” (check the problem description). Otherwise, we check whether there is at least one cut point or not. If yes, the answer is obviously $1$ since we can ...
connectivity (this result seems quite intuitive and one can check the tutorials
for proof). We can use
88.
[HELP] Dynamic Connectivity Problem **Problem**:[D: Stamp Rally](https://agc002.contest.atcoder.jp/tasks/agc002_d)
I implemented DSU but its exceeding time limit, I read the editorial and understood nothing, I tried to read other AC of this problem. It seems people have implemented some recursive function, I am not able to comprehend. Any resources or explanations will be of great help.
**I am posting a sample AC of this problem and I don't understand how Divide/Conquer this problem**
~~~~~
#include<cstdio>
const int MAXN = 100000;
struct edge{
int u, v;
}edges[MAXN + 5];
int fa[20][MAXN + 5], siz[20][MAXN + 5];
int Find(int x, int type) {
return fa[type][x] == x ? x : fa[type][x] = Find(fa[type][x], type);
}
void Union(int x, int y, int type) {
int fx = Find(x, type), fy = Find(y, type);
if( fx != fy ) {
siz[type][fy] += siz[type][fx];
fa[type][fx] = fy;
}
}
struct query{
int x, y, z;
int ind;
}qry[MAXN + 5], tmp[MAXN + 5];
int ans[MAXN + 5];
bool Check(query q, int type) {
...
[HELP] Dynamic Connectivity Problem
89.
Paths, Connectivity, and Trees My upcoming book covers three major topics in graph theory: **bipartite graphs**, **functional graphs**, and **Euler paths**.
For you to fully understand those topics, we need to cover some basics first.
[Here](https://albexl.substack.com/p/paths-connectivity-and-trees) is an article reflecting some of the content I shared in the Fundamental Definitions chapter of the book.
If you find this post beneficial, please consider sharing it with your network. Together, we can expand our knowledge and strengthen our community.
Have a great day,
Alberto
Paths, Connectivity, and Trees, first. [Here](https://albexl.substack.com/p/paths-connectivity-and-trees) is
an article reflecting, ://albexl.substack.com/p/paths-connectivity-and-trees) is an article reflecting
some of the content I shared
90.
Интересная задачка на структуры данных. Мне очень интересно, умеют ли сейчас люди решать вот такую задачу (я приведу сперва основную идею, а потом несколько вариаций условия):
Дана плоскость т.е. бесконечный грид точек с целыми координатами. На плоскость упали по очереди N прямоугольников (по очереди, значит, порядок важен) со сторонами параллельными осям координат и значением $value_i$ внутри. Для всех точек, покрытых прямоугольником, нужно сделать некоторую **операцию** с $value_i$. После этого вам поступают K **запросов** вида "посчитайте что-нибудь на прямоугольнике".
Предполагается, что структуру данных для N прямоугольников можно строить в Offline, а вот на запросы нужно отвечать в Online.
1. операция +=, запрос сумма
2. операция +=, запрос минимум
3. операция присваивание, запрос сумма
4. операция присваивание, запрос минимум
Утверждается, что я умею решать все 4 задачи за следующее время:
1. Time = $N log$, Memory = $N log$, AnswerQuery = $log$
2. Time = $N log^2$, Memory = $N log^2$, AnswerQuery =...
удаления я избавляюсь также, как и в Dynamic-Connectivity в Offline, далее
ссылка на условие задачи
91.
JPC Round #1 (Div. 3) Editorial [problem:451364A]
Idea: [user:yazan_istatiyeh,2023-07-05], prepared: [user:noomaK,2023-07-05]
<spoiler summary="Tutorial">
This problem was our way of saying hi:)
To solve the problem you can keep increasing n until it is divisible by k, this is a linear solution.
A constant solution is to find how much we need to add to n to make it divisible by k, so the solution becomes $x + k - (x \pmod k)$, or $(n / k + 1) * k$ taking advantage of integer (floor) division.
</spoiler>
<spoiler summary="Solution">
~~~~~
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int q;
cin >> q;
while (q--) {
int x, k;
cin >> x >> k;
cout << (x + (k - x % k)) << '\n';
}
}
~~~~~
</spoiler>
<spoiler summary="Rate the problem">
- Didn't solve
- Good problem
- Average problem
- Bad problem [l...
that, we can check for connectivity for all forbidden pairs (cities in feuds),
if all pairs were
92.
A Variant of the Dynamic Connectivity problem. I have a dynamic connecticity problem, but with a additional constraint. The edges that can be added cannot be removed, and the edges that are being removed, cannot be added back. We initially have a graph too, so basically, the edges that are present in the initial graph can be removed, and new edges can be added, but the edges that are added later cannot be removed. they are permanant. Is there a simpler solution to this problem, than the normal fully connected dynamic connectivity problem?
P.S: can someone give me a link to any problem based on online fully dynamic connectivity.
A Variant of the Dynamic Connectivity problem., a simpler solution to this problem, than the normal fully connected dynamic
connectivity problem, P.S: can someone give me a link to any problem based on online fully dynamic
connectivity.
93.
Russian Code Cup 2017 — Third Qualification Round Editorial <h2>A. Spreadsheets</h2>
<p>Let us subtract 1 from <i>k</i>, now the columns are numbered from 0.</p><p>Let us first find out how many characters are there in the name of the column. To do it let us subtract powers of 26 from <i>k</i>, one by one, until the current power is greater than the remaining number <i>k</i>'.</p><p>Now the name of the column is <i>k</i>' in 26-based notation where characters A–Z are used as digits, prepended with leading A-s to the required length. You can either convert it using standard library function (in this case you must replace digits 0–9, A–P that will be used by the required digits), or implement a textbook algorithm of conversion to another base.</p><p>Final note: a day before the round one of the testers pointed out that CF Beta 1 Round problem B was similar to this one. After a discussion, taking into account that CF1 round was long ago, the problem is actually easier than CF1B problem, and we had no well prepared and easy enoug...
condensation by compressing strongly connectivity components. In the condensed
graph each vertexi
94.
How to find articulation points and bridges in a changing graph? Greetings folks, I've been struggling with the following problem:
I don't have a clear definition of the task but in most cases, it looks something like that:
You are given a squared plane (that is every vertex has integer coordinates $1 \le x_i, y_i \le N$) with some vertices disabled, edges between vertices can only go in 8 directions (chess king moves), and are always present if the vertices are present.
The task is to answer $Q$ queries, where a query asks you to remove a small number of $X$ vertices from the graph, recalculate articulation points (cutpoints) and bridges and add them back.
The constraints are something like this:
$1 \le Q \le 8 \cdot 10^{5}$ — the amount of queries
$4 \le X \le 40$ — the amount of deleted points in the query
$1 \le N \le 200$ — borders of the bounding box of the graph (number of vertices can go up to $N^2$)
I've always been struggling with biconnected components, so I'm unsure how to solve this. I've seen [...
Queries are **not online**, thus I felt like something like dynamic-connectivity
offline which
95.
Spanner sum heuristic There seems to be some confusion reagarding this post being copied from stackexchange, but let me tell you that was my friend who posted it from his fake account without my knowledge, but now i need help genuinely, please provide input if you can.
I am currently working on a **heuristic** for a problem called the _Spanner Sum Problem(NP problem)_. I'll try and incorporate all the relevant information here, in the blog post so we can have the best of ideas and inputs from your side!
Problem Statement: To find a spanning tree of a graph such that the shortest distances between all node pairs of chord edges related to that spanning tree are as low as possible (related problem statement is: to minimise the edges while keeping the connectivity b/w the nodes as good as possible)
ref:(An edge of a spanning tree is called a branch; an edge in the graph that is not in the spanning tree is called a chord.)
Let's assume we have a Regular Un-Directed Graph **G** with **E** edges and **...
do so, you would reduce/disturb the connectivity of the smaller cycle edges
you had processed before, statement is: to minimise the edges while keeping the connectivity b/w the
nodes as good as possible), this edge, it would have a greater impact of the connectivity of the graph so
we wouldn't want to
96.
Introduction to my Blog Hi CF Community,
Here is my blog [rachitiitr.blogspot.in](http://rachitiitr.blogspot.in).
I have started to write about the interesting problems I encounter during contests. Interesting means really interesting, the problems that kept me thinking for hours or those having beautiful solution worth mentioning.
After explaining the underlying concept and solution, I usually also attach the code at the end of post.
So if you are bored and need a place where you can find good problems, see how they were solved, learn something new, you should check out the posts I make on the blog.
I suggest to read one post everyday before going to bed. Also people in DIV2 can certainly learn a lot by reading the posts.
I have **5** posts as for now:
1. [A Hard Combinatorics Problem](http://rachitiitr.blogspot.in/2017/05/a-hard-combinatorics-problem.html)
2. [A Longest SubArray Problem](http://rachitiitr.blogspot.in/2017/05/a-longest-subarray-problem.html)
3. [A Greedy, M...
://rachitiitr.blogspot.in/2017/05/a-greedy-math-problem.html) 4. [A Connectivity
Problem on Directed Graph](http, Connectivity Problem on Directed Graph](http://rachitiitr.blogspot.in/2017/05/a-
connectivity-problem-on
97.
Top-10 результатов в области алгоритмов за 2011 год <p>Пока участники Codeforces развлекались, выясняя, кто из них самый аутентичный JKeeJle30, <a href="http://11011110.livejournal.com/">David Eppstein</a> подвел итоги ушедшего года в области Computer Science. Изучив появившиеся за этот год препринты на <a href="http://arxiv.org">arxiv.org</a> в разделе cs.DS (да, поэтому результаты <a href="http://www.eecs.berkeley.edu/%7Evirgi/matrixmult.pdf">про перемножение матриц</a> сюда не попали) он выбрал десятку самых понравившихся ему. Вот они, в хронологическом порядке:<br /><br />[cut]<br /><br /><a href="http://arxiv.org/abs/1103.0534">Solving connectivity problems parameterized by treewidth in single exponential time</a>. В первую очередь обращает на себя список авторов - Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan van Rooij, and Jakub Onufry Wojtaszczyk. Немного о терминологии: декомпозиция дерева - это отображение графа на дерево, когда каждая вершина графа отображается на некоторое поддерево, причем если вер...
Solving connectivity problems parameterized by treewidth
<http://arxiv.org/abs/1103.0534>
98.
Meta Hacker Cup 2025 — Round 1 Editorial Hey everyone
I recently participated in **Meta Hacker Cup 2025 Round 1** and I’m thrilled to share that I secured **Rank 333 / 13,676** with a **perfect score of 105/105**, successfully solving every problem from **A1 → D**!
I've qualified for Round 2 of the Meta Hacker Cup 2025! Round 1 was a fantastic set of problems, and I managed to solve all of them for a full score.
This post includes **my hints, solution approaches, and final codes** for all problems — written to help learners strengthen their **DSA and problem-solving** intuition.
[A1: Snakes Scales (Chapter 1) :](https://www.facebook.com/codingcompetitions/hacker-cup/2025/round-1/problems/A1)
<spoiler summary="Hint">
Snake must walk from platform 1 to N. To get from platform $i$ to $i+1$, he needs a ladder of height $|A_i - A_{i+1}|$. Since he brings only one ladder, it must be tall enough for the hardest (i.e., highest) adjacent jump in the entire path.
</spoiler>
<spoiler summary="Solution">
The s...
platforms? Think of this as a graph connectivity problem. Use BFS/DFS starting
from all platforms
99.
Having bugs in optimizing dsu rollback Hi guys, I've been introduced to dynamic connectivity for a long time, especially dsu rollback which can be operated in O(log n) for updating and asking the root. Now, I'm facing with a problem with the edges stricting to only attach i and i + 1 and since the time limit is tight, I may have to do in O(1) (I'd tried the above one but it didn't work).
I was introduced to using left right for this at the same time, however it comes to a problem that the range that I get when updating some edges nearby isn't just what I've expected.
For example, I have 5 nodes here:
If I use edge (3, 4), (4, 5), (1, 2) and (2, 3) accordingly then there exists a position u which left[u] != 1 or left[u] != 5.
Please let me know where I implement wrong or prove that it's impossible to optimize it into O(1) for both updating and getting the longest range that u is covered.
<spoiler summary = "My implementation">
```cpp
vector <int> lef_m(n), rig_m(...
Hi guys, I've been introduced to dynamic connectivity for a long time,
especially dsu rollback
100.
Learning Notes on the Hopcroft-Tarjan planarity algorithm (With C++ Implementation) **Section 1. Introduction**
I have been struggling for weeks to understand the first linear-time planarity algorithm, the [Hopcroft-Tarjan algorithm (HT)](https://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/Efficient%20Planarity.pdf). Fortunately, I successfully understood it and implemented it. In fact it is very hard to find a verified HT implementation online. Some code, e.g., [LEDA](https://en.wikipedia.org/wiki/Library_of_Efficient_Data_types_and_Algorithms) is not open source. Other open-source planarity tests, e.g., [networkx (LR planarity)](https://github.com/networkx/networkx/blob/main/networkx/algorithms/planarity.py), [boost (Boyer-Myrvold)](https://www.boost.org/doc/libs/1_53_0/libs/graph/doc/boyer_myrvold.html), [Pigale (LR planarity)](https://pigale.sourceforge.net/), use other algorithms. There is [an implementation by Shawn Anderson](https://github.com/shawnwanderson/Hopcroft-Tarjan-Planarity-Testing), however it is partial. I would like to open a blo...
(v_1)$ is due to the 2-vertex-connectivity of the graph, and $DFN(w) =
DFN(v_1)$ iff $v_1$ belongs to
101.
Divide by Zero 4.0 Summary ##Statistics
Total Users/Teams who have made a submission: **754**
Total Submissions: **4212**
Number of distinct users/teams with correct submissions: **498**
[Contest Link]( https://www.codechef.com/DIBZ2016)
[Feedback form](http://goo.gl/forms/cMY4KZLEJV)
---
##Winners
<li>Rank 1: [user:Sumeet.Varma,2016-01-31]</li>
<li>Rank 2: [user:amankedia1994,2016-01-31]</li>
<li>Rank 3: [user:PrashantM,2016-01-31]</li>
---
The Editorials of the following problems are prepared by me, [user:aditya1495,2016-01-31] and [user:_shil,2016-01-31].
---
##Shil and RasenShuriken
(setter: [user:_shil,2016-01-31])<br>
Total number of pairs such that their product is even. Count total number of odd numbers = x.<br>
Product of two numbers is odd if the both numbers are odd.<br>
Ans = **N*(N-1)/2 — x*(x-1)/2**
---
##Shil Loves Exclusive Or
(setter: [user:_shil,2016-01-31])<br>
Use the fact that Xor of 2x and 2x+1 is 1.<br>
Therefore xo...
induction step that **F[u]** is **independent of connectivity** of graph and
just dependent on height of u
102.
Need help in this problem Previous year ihack problem
— In the vibrant kingdom of Codeopia, ruled by the wise King Algorithmus, peace is maintained by the harmonious cooperation of
its distinct clans. However, recent disturbances have threatened the stability of Codeopia, and King Algorithmus faces a daunting
challenge
Each clan, Cn, known for its skilled warriors, plays a crucial role in the kingdom's defense and prosperity. Out of all the clans that
exists, there are only a few with abundance of natural resources. The clans without the natural resources relies on these clans
for their supplies of armory and other ammun ition. Each such clan has the following attributes:
Maximum Available Resource(MAR), which depicts the current maximum amount of resources available. It also depicts the maximum request of
mining that a clan can hold. after which it won't accept any request unless it completely fulfils the existing ones. It will be re-filled once all the
mining activities are done after RT seconds
P...
connectivity provided through XML Attack on Clam with X resources providing Y
GCO Clanj has found natural
103.
Never Miss a Contest Again! Contest Alarm App for Android Hello Codeforces community!
How many times have you missed an upcoming **Codeforces Round (Div. 2 / Div. 3 / Educational)** or an **AtCoder Beginner Contest** simply because you forgot the start time or got confused with time zone conversions?
As competitive programmers, we participate in contests across multiple platforms like Codeforces, AtCoder, CodeChef, and LeetCode. Managing alarms manually for every single contest can be annoying and easy to forget.
To solve this, I built **Contest Alarm App** — a free, open-source, local-first Android app designed specifically for competitive programmers!
---
### Key Features
- **Multi-Platform Auto-Sync**: Automatically fetches live contest schedules from Codeforces, AtCoder, CodeChef, LeetCode, Clist and more.
- **Division-Wise Auto-Alarms**: Set automatic alarms for your preferred divisions (Div 1, Div 2, Div 3, Div 4, Educational, ABC, ARC, Starters) as soon as new contests appear.
- **Auto-Reschedule on Time Changes**: ...
connectivity.
104.
HKI Mock NOI 2015 problem — Graph ? Dynamic Connectivity ? ~~~~~
Hello everyone !
~~~~~
~~~~~
I've just seen this 2 problem : B/Travel & C/Lilypads in HKI Mock NOI 2015 (seems like it's a Mock contest of Singaporean coders) but I couldn't find out any fast enough solutions for them.
~~~~~
~~~~~
Here are the links to the problems :
~~~~~
~~~~~
B : https://dunjudge.me/analysis/problems/697/
~~~~~
~~~~~
C : https://dunjudge.me/analysis/problems/694/
~~~~~
~~~~~
In problem B, I tried to implement a lot of solutions (e.g. remove each edge and find the shortest path between two vertices that it connects, ...) but that is just enough to pass the first 4 subtasks (which helps me gain <= 50% of the points).
~~~~~
~~~~~
In problem C, I think it's a kind of Dynamic Connectivity problem. I've heard about some data structures that can solve this problem. If my memory is correct, link-cut tree can solve it but many people say that it's really hard to code it in a contest.
~~~~~
~~~~~
Now I'm really ...
HKI Mock NOI 2015 problem — Graph ? Dynamic Connectivity ?, ~~~~~ In problem C, I think it's a kind of Dynamic Connectivity problem. I've
heard about some
105.
Fully Dynamic Connectivity Problem Implementation Can someone provide me with a good implementation of the offline solution of the fully dynamic connectivity problem ? I think I got the idea but I'm having trouble implementing it.
UPD: Guys I found the stupid bug in my implementation. I am sharing my code right now (my implementation is with segment tree instead of divide and conquer, which is pretty much the same) and I hope you will find it helpful. [Code](https://ideone.com/eGWDFd)
Fully Dynamic Connectivity Problem Implementation, connectivity problem ? I think I got the idea but I'm having trouble
implementing it. UPD: Guys I
106.
Find number of connected components after removing a vertex from a tree Hey, I have a problem and I cannot think of any faster soltuion than $O(nm)$.
I'm given a tree with $n$ vertices and $n-1$ undirected edges. I'm also given $m$ queries ($m \le 10^5$) and each of them is an integer $x$ ($1 \le \lvert x \rvert \le n$). If $x > 0$ then we need to remove vertex $x$ from a tree and print number of connected components in that tree, otherwise if $x < 0$ then we need to add vertex $x$ to that tree (and also print number of connected components). Input data is correct i.e. no vertex will be added before it was removed.
What I thought of, was storing degree of each vertex. Then, if vertex $v$ was removed then number of connected components increases by $deg(v)-1$, but this way we also need to decrement by one degrees of vertices with edge with $v$ which can take $O(n)$ and that leads to $O(nm)$. Another idea, was to try to solve the problem using [dynamic connectivity](https://en.wikipedia.org/wiki/Dynamic_connectivity), but I'm not sure how to connect t...
to try to solve the problem using [dynamic connectivity
](https://en.wikipedia.org/wiki
107.
Standard algorithms/problems on CodeForces for testing our solutions Hi, I think it is a good idea to add standard problems (like DFS, find cycle in graph, Convex Hull...) in codeforces problemset which most of competitive programmers learn, so that we can test our solutions as we are learning the algorithm. The problems should look exactly like the original ones (for example, the problem of printing a cycle from an unweighted directed graph should look like this: "Given the vertices of an unweighted directed graph, print any of the cycles in this graph. If it has no cycles, print -1"; then we describe the limits and IO format. Formulating problems this way saves time while training). I will start writing a list of standard problems/algorithms, feel free to add:
Sorting:
1. MergeSort
2. QuickSort
3. SelectionSort
4. RadixSort
5. BucketSort
6. Binary Search
Graph Algorithms:
1. DFS
2. BFS
3. Finding Cycle
4. Checking if graph is bipartite
5. Dijkstra's algorithm
6. Floyd-Marshall's algorithm
7. Checking connectivity
8. Kruskal’s Minim...
. Dijkstra's algorithm 6. Floyd-Marshall's algorithm 7. Checking connectivity
8. Kruskal’s Minimum Spanning
108.
Solution of task е, Codeforces beta round #41 <div>First note that a valid graph of wormholes is either connected or consists of two connectivity components with one exit in each. The proof is in the end of this text. Also note that the first option is never optimal because one edge can be removed to get the second option. Let's build a minimal spanning tree of the input graph. If it contains more than two components, the answer for each query is -1. If it contains two components, the answer is -1 if both objects are in the same component, and the weight of the spanning tree otherwise. The most interesting case is one component: we need to cut the spanning tree into two trees containing one exit each and having minimal sum of weights (not actually cut but get the sum of weights of the resulting trees). It can be done by (virtually) removing the most heavy edge on the path between the exits; so the only thing we need to know is the weight of such edge. It can be done with LCA algorithm: for each node precalculate upward jumps of he...
First note that a valid graph of wormholes is either connected or consists of
twoconnectivity
Tutorial of Codeforces Beta Round 41
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/04/2026 01:24:38 (h1).
Desktop version, switch to mobile version.
Supported by
