Perhaps today and/or tomorrow due to a power outage there may be disruptions in the work of Codeforces and Polygon. Please do not plan any important events during this time. If there are details or the exact time, we will definitely publish them. Estimated time of maintenance: from 2 Aug, 16:00 (UTC) to 2 Aug, 20:00 (UTC).
×

# | User | Rating |
---|---|---|

1 | tourist | 3819 |

2 | Benq | 3745 |

3 | ksun48 | 3560 |

4 | Radewoosh | 3511 |

5 | Um_nik | 3489 |

6 | peehs_moorhsum | 3460 |

7 | Petr | 3414 |

8 | Miracle03 | 3410 |

9 | maroonrk | 3400 |

10 | sunset | 3338 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 207 |

2 | awoo | 182 |

3 | Errichto | 180 |

4 | Um_nik | 179 |

5 | -is-this-fft- | 174 |

5 | maroonrk | 174 |

7 | Radewoosh | 172 |

7 | tourist | 172 |

9 | SecondThread | 170 |

10 | rng_58 | 166 |

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

`305`

— search for 305, most probably it will find blogs about the Round 305`andrew stankevich contests`

— search for words "andrew", "stankevich" and "contests" at the same time`user:mikemirzayanov title:testlib`

— search containing "testlib" in title by MikeMirzayanov`"vk cup"`

— use quotes to find phrase as is`title:educational`

— search in title

1.

I compiled a list of almost all useful blogs ever published on Codeforces [update: till 09.06.2021] <h3 style="color:red">If there are any blogs that I have missed, please tell in the comment section. Thank you.</h3>
# Mathematics Stuff
- [Number Theory in Competitive Programming [Tutorial]](https://codeforces.com/blog/entry/46620)
- [Number of points on Convex hull with lattice points](https://codeforces.com/blog/entry/62183)
- [FFT, big modulos, precision errors.](https://codeforces.com/blog/entry/48465)
- [Number of ways between two vertices](https://codeforces.com/blog/entry/19078)
- [Mathematics For Competitive Programming](https://codeforces.com/blog/entry/76938)
- [FFT and NTT](https://codeforces.com/blog/entry/19862)
- [Burnside Lemma](https://codeforces.com/blog/entry/51272)
- [Number of positive integral solutions of equation 1/x+1/y=1/n!](https://codeforces.com/blog/entry/76836)
- [On burnside (again)](https://codeforces.com/blog/entry/64860)
- [Simple but often unknown theorems/lemmas/formula? Do you know?](https://codeforces.com/blog/entry/55912)
- [Probabili...

Propagation](https://codeforces.com/blog/entry/20528) - [Sort before insert —
A small, yet powerful

2.

[Tutorial] 2-SAT Introduction
==================
In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case of the general Boolean satisfiability problem, which can involve constraints on more than two variables, and of constraint satisfaction problems, which can allow more than two choices for the value of each variable. But in contrast to those more general problems, which are NP-complete, 2-satisfiability can be solved in polynomial time. -[Wikipedia](https://en.wikipedia.org/wiki/2-satisfiability)
If you have not heard of propositional logic before, plead read about it [here](https://brilliant.org/wiki/propositional-logic/). Wikipedia links have been provided wherever a term has been used for the first time in this tutorial. The whole algorithm is based on graph theory so it will help to be familiar with direc...

) { add_clause_xor(i, !f, j, g); } // Topological sort void dfs(int u) { vis[u, // Topological sort void dfs(int u) { vis[u] = true;

3.

CodeCraft-21 and Codeforces Round #711 (Div. 2) Editorial [problem:1498A]
==================
#### [**Video Editorial**](https://www.youtube.com/watch?v=lV5cb8wh3sE)
**Author and Problemsetting:** [user:ninja_28,2021-03-29]
**Editorialist:** [user:sigma_g,2021-03-29]
<spoiler summary="Hint">
Can you think of the simplest properties that relate a number and its sum of digits?
</spoiler>
<spoiler summary="Hint 2">
Note that if $X$ is a multiple of 3, then **both** $X$ as well as the sum of digits of $X$ are a multiple of 3! Can you put this property to use here?
</spoiler>
<spoiler summary="Hint 3">
If $X$ is a multiple of 3, then $\texttt{gcd-sum}(X) \ge 3$. Therefore, we are guaranteed that at least every third number will satisfy the constraints required by our problem $(\texttt{gcd-sum}(X) > 1)$.
</spoiler>
<spoiler summary="Solution">
Therefore, for the input $n$, we can simply check which one of $n$, $n+1$, and $n+2$ has its gcd-sum $> 1$, and print the lowest of them.
</spoiler>
<spoi...

$a$ lies in the same SCC or to the SCC of higher enumeration in topological
sorting. In both cases, between node $a$ to node $b$, then node $a$ comes before node $b$ in the
topological sort. So, possible topological sorting of this compressed SCC. , $ in the topological sort. So for every pair of nodes of compressed SCC, we
know which node would come first, Property: Consider two consecutive strongly connected components in the
topological sorting

Tutorial of CodeCraft-21 and Codeforces Round #711 (Div. 2)

4.

Algorithms with link for Bengali Programmers **C Language (সি প্রোগ্রামিং শেখার বিভিন্ন লিংক)**
[সুবিন স্যার এর বই](http://cpbook.subeen.com/)
[শিক্ষক ডট কম এর কোর্স](http://www.shikkhok.com/%E0%A6%95%E0%A7%8B%E0%A6%B0%E0%A7%8D%E0%A6%B8-%E0%A6%A4%E0%A6%BE%E0%A6%B2%E0%A6%BF%E0%A6%95%E0%A6%BE/%E0%A6%B8%E0%A6%BF-%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82/)
**C++ STL (সি++ STL শেখার বিভিন্ন লিংক)**
[cplusplus.com](http://www.cplusplus.com/reference/stl/)
[প্রোগক্রিয়া](http://www.progkriya.org/gyan/stl.html)
[হাবিজাবি হিজিবিজবিজ](https://zobayer2009.wordpress.com/)
[PRIORITY QUEUE](http://abuasifkhan.me/2012/05/cplusplus-priority-queue/#more-3)
**GRAPH THEORY (গ্রাফথিওরি)**
**BFS**
[BFS-1](http://www.shafaetsplanet.com/planetcoding/?p=604)
**DFS**
[DFS-1](http://www.shafaetsplanet.com/planetcoding/?p=973)
[DFS-2](http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm)
**Minimum Spanning Tree(MS...

**Topological Sort**, [Topological Sort-1](http://www.shafaetsplanet.com/planetcoding/?p=848), [Topological Sort-2](http://www.shafaetsplanet.com/planetcoding/?p=973), [Topological Sort-3](https://www.sites.google.com/site/smilitude/topsort)

5.

Topological Sort + Strongly Connected Components Topological Sort:
Resource:
1. https://www.geeksforgeeks.org/topological-sorting/
Practice:
1. https://vjudge.net/contest/425567#overview
Strongly Connected Components:
Resource:
1. https://www.geeksforgeeks.org/strongly-connected-components/
Practice:
1. https://www.spoj.com/problems/CAPCITY/
2. https://www.spoj.com/problems/TFRIENDS/
3. https://codeforces.com/contest/427/problem/C

Topological Sort + Strongly Connected Components, 1. https://www.geeksforgeeks.org/topological-sorting/, Topological Sort:

6.

Topological Sort Question I was working on this problem: http://codeforces.com/contest/510/problem/C
I spent a fair bit of time on it, and I knew while solving it that it was a topological sorting problem. However, I have gone through the USACO training pages to learn my algorithms, which doesn't have a section on topological sorting. I know standard graph algorithms like bfs,dfs,warshall,dijkstra, etc. but I don't know how to solve these topological sorting problems. The editorial mentions that this is a classic topological sort problem.
My question is, how can dfs be applied to solve this problem, and where can I find more theory/practice problems to practice topological sorting.
Thanks!

Topological Sort Question, that this is a classic topological sort problem., /practice problems to practice topological sorting., topological sort problem. My question is, how can dfs be applied to solve this
problem, and where

7.

(almost) Every Algorithms & Data Structures you needed to learn , with practice problems Hello guys this is <a href="https://www.youtube.com/channel/UC0zvY3yIBQTrSutsV-4yscQ?view_as=subscriber"> CodeNCode </a>
and as you guys know I have been working for more than 3 years on Data Structures and algorithms courses.
So I thought let's compile it to one place and share so it can be helpful to everyone.
<h3>List of Courses</h3>
<div class="spoiler">
<b class="spoiler-title"><h5> Basic Algorithms </h5></b>
<div class="spoiler-content" style="display: none;">
<ul>
<li><a href="https://www.youtube.com/watch?v=NoDYJ7Ks_M0">L01 : Why you should learn binary search</a></li>
<li><a href="https://www.youtube.com/watch?v=3vMpagKkqrc">L02 : Understanding Core of Binary Search</a></li>
<li><a href="https://www.youtube.com/watch?v=-IMyOkNLRoY">L03 : Monk's encounter with polynomial (HackerEarth)</a></li>
<li><a href="https://www.youtube.com/watch?v=FJXZ4Zt8SOk">Ternary String (Codeforces)</a></li>
...

=2m9_kLaxQio">L14 : Topological Sorting Introduction
* , >
* L14 : Topological Sorting <https://www.youtube.com/watch?v=2m9_kLaxQio>

8.

Number of topological sort How to calculate number of topological sort?
Brute force not acceptable: number of vertex N is 10^3; number of edges M: 3 * 10^5.
Time limit of calculation isn't critical: 1 hour is acceptable.
Can you help me with this problem? I can't find solution.
~~~~~
Trivial example:
N = 6; M = 7
V: 1 2 3 4 5
E:
1 2
1 3
1 4
1 5
2 4
2 5
3 5
Answer:
5
(1 2 3 4 5)
(1 3 2 4 5)
(1 2 4 3 5)
(1 2 3 5 4)
(1 3 2 5 4)
~~~~~

Number of topological sort, How to calculate number of topological sort?

9.

The lexicographically largest topological sort of a given graph? This is a problem in a past contest and its link is:
http://codeforces.com/gym/101102/problem/K
The statement is: Consider a directed graph G of N nodes and all edges (u→v) such that u < v, find the lexicographically largest topological sort of the graph after removing a given list of edges. (nodes are numbered 1 to n)
I tried an approach which is :
First i assume a graph sorted with the initial sorting which is 1,2,3,.....,n in array named permutation, so initially permutation[1] = 1, permutation[2] = 2, ....., permutation[n]=n.
Then this pseudocode:
loop from i=2 to i=n {
j = i //the initial index of i in permutation
while(j>1 and the edge between i and permutation[j-1] is removed) {
swap permutation[j] and permutation[j-1] //permutation[j] = i before the swap, and permutation[j-1] = i after the swap
j = j-1 //the new index of i in permutation
}
}
The final answer is represented by the elements of permutation, for example if n=3...

The lexicographically largest topological sort of a given graph?, is finally: permutation[1] = 3, permutation[2] = 1, permutation[3] = 2, so the
topological sort here, the lexicographically largest topological sort of the graph after removing a
given list of edges, , find the lexicographically largest topological sort of the graph after
removing a given list of edges

10.

Codeforces Round #345: editorial [problem:651A]
------------------
Idea author: [user:fcspartakm,2016-03-09], preparation: [user:fcspartakm,2016-03-09].
Main idea is that each second we need to charge the joystick with lowest power level. We can just emulate it or get an $O(1)$ formula, because process is very simple.
[problem:651B]
------------------
Idea author: [user:fcspartakm,2016-03-09], preparation: [user:fcspartakm,2016-03-09].
Lets look at the optimal answer. It will contain several segment of increasing beauty and between them there will be drops in the beautifulness. Solution is greedy. Lets sort all paintings and lets select which of them will be in the first increasing segment. We just go from left to right and select only one painting from each group of several paintings with the fixed beauty value.
We continue this operation while there is at least one painting left.
With the careful implementation we will get $O(n \log n)$ solution.
But this solution gives us the whole sequence, but...

We can do this with topological sort or with lazy computations., [v] = max(dp[v], dp[u] + 1); } ~~~~~ We can do this with topological sort or
with lazy

Tutorial of Codeforces Round #345 (Div. 1)

11.

Topological Sort on Complementary DAG Hello, friends. Recently, I was solving this problem[Topological Sort](https://codeforces.com/gym/101102/problem/K), but got stuck on it.
I thought a lot for solving but couldn't come up with any efficient approach.
There is even no tutorial available for it.
My Approach (May or must be wrong, that's why i am getting wrong answer)-:
For every node I am finding the first node greater than it to which it will be connected and also the largest node smaller than it which will connect to it. After forming a DAG in this way with no more than 2*n edges I ran toposort on it. But it's giving me wrong answer.
See the drawing for understanding my approach.
[This one](/predownloaded/b2/f9/b2f9db71de93408e0db4d99fd950630b9a8a0ce6.png)
Can someone help me figuring out the way to solve this problem? I bet this is one of the most nice problems on graph theory.

Topological Sort on Complementary DAG, Hello, friends. Recently, I was solving this problem[Topological Sort
](https://codeforces.com/gym

12.

How to check cycles inside a Topological Sort Hi, I'm in doubt in how to check if there's cycles in a graph meanwhile I do a topological sort.
The only way to implement a topological sort is this one:
~~~~~
void dfs(int x) {
vis[x] = true;
for(int u = 0; u < n; u++) {
if(!vis[u] && graph[x][u] == 1) {
dfs(u);
}
}
order.push_back(x);
}
~~~~~
but this implementation doesn't check if there's cycles, which modification can I do to check for cycles ?

How to check cycles inside a Topological Sort, Hi, I'm in doubt in how to check if there's cycles in a graph meanwhile I do a
topological sort, The only way to implement a topological sort is this one:

13.

Codeforces Round #410 (Div. 2) Editorial [problem:798A]
==============
Let $cnt$ be the number of $1 \le i \le \frac{n}{2}$ such that $s_i \neq s_{n - i + 1}$.
If $cnt \ge 2$ then the answer is NO since we must change more than 1 character.
If $cnt = 1$ then the answer is YES.
If $cnt = 0$ and $n$ is odd answer is YES since we can change the character in the middle, otherwise if $n$ is even the answer is NO because we must change at least one character.
Complexity is $O(|s|)$.
Solution: [Link](http://ideone.com/RHLhXu)
[problem:798B]
==============
First of all, you must notice that the operation of removing the first character and appending it to the left is equivalent to cyclically shifting the string one position to the left.
Let's denote by $dp_{i,j}$ the smallest number of operations for making the first $i$ strings equal to string $s_i$ moved $j$ times.
Let $f(i,j)$ be the the string $s_i$ moved $j$ times,then $dp_{i,j} = \min \limits_{k = 0,f(i-1,k) = f(i,j)}^{|s_n| - 1} dp_{i - 1,k} + ...

) of topological sort.

Tutorial of Codeforces Round #410 (Div. 2)

14.

Codeforces Round #168 Editorial Hi :)
Here's the editorial for round #168. This time I tried to do my best to prepare a good contest. In some parts I failed but I still learned many things which will surely help me to do better next times! ^.^ I hope you've liked the problems. :)
## [problem:275A]
Author: [user:havaliza,2013-02-22]
For each light you should count the number of times it’s been toggled. Consider a light is toggled $k$ times. If $k$ is even then the final state of the light is ‘on’ otherwise it’s ‘off’. The implementation would be easy. You may look at the accepted solutions as reference.
## [problem:275B]
Author: [user:havaliza,2013-02-22]
Consider a pair of black cells. There exist at most two different valid paths we can take between these two cells. The naïve solution would be to check the existence of at least one of these paths for each pair of black cells. There are $O(n^{2} m^{2}) $ such pairs and each pair can be checked in $O(n+m)$. So the time complexity will be $O(n^{2} ...

add an edge from the column of $x$ to the column of $y$ in our graph. Then
topological sorting, would be preserved in topological sorting. We do the same thing for each row,
sotopological sort, But still the idea to solve this problem is to implement topological sort in a
such way, topological sort in a such way that the graph we make has less edges or to make
less processing

Tutorial of Codeforces Round #168 (Div. 1)

Tutorial of Codeforces Round #168 (Div. 2)

15.

cses graph session editorial(incomplete) I got bored with solving and wanted to do something which is related to cp and also very fun so i decided to write this tutorial.bare me for my bad English .
### how to solve grid problems
<spoiler summary="trick">
here is my template to solve grid problems
~~~~~
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
string ds="RLDU";
int n,m;
bool possible(int x,int y){
//cout<<n<<" "<<m<<" "<<x<<" "<<y<<" possible"<<endl;
return (x<n&&x>=0&&y<m&&y>=0);
}
~~~~~
here we cand do just x+dx[i],y+dx[i] to move the four <br>
directions and ds helps if we want to record path.<br>
we can easily extend it to include four diagonals
</spoiler>
1) counting rooms
------------------
<spoiler summary="explanation">
For each unvisited '.' cell we have to make dfs(or bfs)<br>
and keep on coloring the visited nodes.We keep track number<br>
of dfs by count variable .our answer would be count.
</spoiler>
<spoiler summary="code">
~~~~~
void dfs(...

the problem is about simple topological sort.
more about

16.

Unofficial Editorial for Round 532 (Div. 2) Just finished this contest in virtual mode and noticed the editorial is missing, so I thought I would share my approaches.
#### [problem:1100A]
Loop over all values of $b$ and take the sum of all indices that are not equivalent to $b \bmod k$. Remember to take the absolute value at the end. Runtime is $\mathcal{O}(n^2)$. Code: [submission:48374675]
#### [problem:1100B]
Maintain a frequency array of size $n$ and track the number of distinct values seen so far as we loop through the array. Once the number of distinct values reaches $n$, we hold a round and decrement each index of the frequency array. Note that this takes $n$ time, but this is fine since we can only hold at most $\displaystyle \frac{m}{n}$ rounds. Runtime is $\mathcal{O}(m)$. Code: [submission:48374608]. Note that `x++` means use the value of `x` and then increment, whereas `++x` means increment and then use. Similar for `x--` and `--x`.
#### [problem:1100C]
Draw the line segments between the center of the inn...

) (or DAG), and we can perform a [topological sort
](https://en.wikipedia.org/wiki/Topological_sorting, /wiki/Directed_acyclic_graph) (or DAG), and we can perform a [topological sort
](https://en.wikipedia.org

Tutorial of Codeforces Round #532 (Div. 2)

17.

2-SAT Tutorial Hi codeforces community.
I thought there is no good _2-SAT_ tutorial in the internet, so I decided to write one.
_2-SAT_ is a special case of boolean satisfiability.
![ ](http://8pic.ir/images/ujgx3rzj2uqm85z8sfgz.jpeg)
Good question! Boolean satisfiability or just _SAT_ determines whether we can give values (<samp>TRUE</samp> or <samp>FALSE</samp> only) to each boolean variable in such a way that the value of the formula become <samp>TRUE</samp> or not. If we can do so, we call formula <i>satisfiable</i>, otherwise we call it <i>unsatisfiable</i>. Look at the example below:
$f = A \; ∧ \; ¬B$, is <i>satisfiable</i>, cause A = <samp>TRUE</samp> and B = <samp>FALSE</samp> makes it <samp>TRUE</samp>.
but $g = A \; ∧ \; ¬A$, is <i>unsatisfiable</i>, look at this table:
<center>
<table style="text-align:center">
<thead style="background-color:gray">
<tr>
<td>$A$</td>
<td>$¬ A$</td>
<td>$A \; ∧ \; ¬A$</td>
</tr>
</thead>
<tr>
<td><samp>TRUE</samp></td>
<td><...

$f$. It can be done with a topological sort of vertices of the graph we made.
If $¬x_i$ is after $x_i, with a topological sort of vertices of the graph we made. If $¬x_i$ is after
$x_i$ intopological sort, $x_i

18.

How to prepare for ACM ICPC? Well I would suggest you to check out Programming Competition,Programming Contest,Online Computer Programming. Here is the details about as the codechef team promote the students for ACM-ICPC or you can also check out the actual university site which conduct ICPC The ACM-ICPC International Collegiate Programming Contest
And to practice problems you can you can refer following sites
1. http://codechef.com
2. http://spoj.com
3. http://hackerrank.com
4. http://codecademy.com
5. http://topcoder.com
6. http://codeforces.com
Good Luck...
for the details about ACM-ICPC 2015 you can read the details ACM ICPC 2015 | CodeChef.
I hope you'll find most of the things...
Here are some steps to get started and be good at it.
Get comfortable writing code in either of one of these languages C, C++ or Java. Why only C, C++ or Java? Because these are the standard languages allowed in any programming competition.
If you are already good at C, it is suggested to learn C++. It...

components(SCC), Dijkstra, Floyd-Warshall, Minimum spanning tree(MST),
Topological sort., connected components(SCC), Dijkstra, Floyd-Warshall, Minimum spanning
tree(MST),Topological sort. 2

19.

help in topological sort (C. Fox and Names) Topological Sorting Help !!!
==================
I read in tutorial to use the topological sorting in this question [Fox and Names](http://codeforces.com/contest/510/problem/C) . I know that we have to find if there exists a order of alphabets such that name1<name2, name2<name3, name3<name4,and so on... but i could not help out how it is implemented and what is the basic idea behind this topological sorting algorithm? Can someone please help . ? Thanks in advance.

help in topological sort (C. Fox and Names), I read in tutorial to use the topological sorting in this question [Fox and
Names](http, Topological Sorting Help !!! ==================

20.

Topological Sort Recently I have learned topological sort using defth first search(dfs). I am trying to solve the problem for a while but cant understand, What should be my first approach? Can anyone explain me step by step. Any hint would be greatly appreciated. Thanks. :)
Problem Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2001

Topological Sort, Recently I have learned topological sort using defth first search(dfs). I am
trying to solve

21.

Codeforces Round #286 Editorial (Complete) **Edit (Jan 22, 2:45 AM UTC):** Added Div1E and the editorial is now complete. I am sorry for the delay.
**Edit (Jan 21, 9:45 AM UTC):** Added the explanation for Div1C/2E, and the problem setters' codes. Div1E will need several more hours. Thank you again for your patience.
First, here are some statistics on this round:
<table>
<tr>
<td>Division</td>
<td>Registrants</td>
<td>Participants</td>
<td>A Accepted</td>
<td>B Accepted</td>
<td>C Accepted</td>
<td>D Accepted</td>
<td>E Accepted</td>
</tr>
<tr>
<td>1</td>
<td>1364</td>
<td>572 (*)</td>
<td>294</td>
<td>199</td>
<td>8</td>
<td>113</td>
<td>1</td>
</tr>
<tr>
<td colspan="3">(Estimated number of AC by me)</td>
<td>800 (wrong)</td>
<td>500 (wrong)</td>
<td>70 (FAIL)</td>
<td>90 (ok)</td>
<td>5 (wrong)</td>
</tr>
<tr>
<td>2</td>
<td>4016</td>
<td>2028</td>
<td>1355</td>
<t...

, then we can perform topological sort on that wcc, and we can make a "chain"
(see the image below) using, 1. If a wcc in $G_1$ does not have cycles, then we can perform topological sort
on that wcc, and we

Tutorial of Codeforces Round #286 (Div. 2)

Tutorial of Codeforces Round #286 (Div. 1)

22.

Toplogical Sort help needed Usually, topological sort is implemented like
~~~~~
void dfs(int x) {
vis[x] = true;
for(int u = 0; u < n; u++) {
if(!vis[u] && graph[x][u] == 1) {
dfs(u);
}
}
order.push_back(x);
}
~~~~~
And then printed in reverse order
But if I implement this way
~~~~~
void dfs(int x) {
order.push_back(x);
vis[x] = true;
for(int u = 0; u < n; u++) {
if(!vis[u] && graph[x][u] == 1) {
dfs(u);
}
}
}
~~~~~
And print in same order.
Can someone provide me a test case where 2nd approach will fail

Toplogical Sort help needed, Usually, topological sort is implemented like

23.

Solutions for Codeforces Beta Round #74 <p><b>A div2</b>. In this problem you can <span id="result_box" class="short_text" lang="en"><span title="Нажмите, чтобы увидеть альтернативный перевод" class="hps">simulate the</span> <span title="Нажмите, чтобы увидеть альтернативный перевод" class="hps">process. You can consider all minutes and in </span></span><span id="result_box" class="short_text" lang="en"><span title="Нажмите, чтобы увидеть альтернативный перевод" class="hps">dependence by a color of a current cablecar decrease size of </span></span>corresponding group of students $G$ by<span id="result_box" class="short_text" lang="en"><span title="Нажмите, чтобы увидеть альтернативный перевод" class="hps"></span></span> $min(|G|,2)$, where $|G|$ is size of the group. After that you should determine the first minute $t$ in that all three groups of students will be empty. So $t+30$ is an answer. This solution works in $O(r+g+b)$.<br>[cut]<br>Also there is $O(1)$ solution. It is following formula: $ans = max(3[(R+1)/2] + 27, 3[...

are relationship of pack()-method. This graph is acyclic. Next, you should do
topological sort of nodes. Sizes, of edges from node i to node j. Topological sort can be done by any stupid
method. For example, you can, should do topological sort of nodes. Sizes of widgets should be calculated in
the obtained order

Tutorial of Codeforces Beta Round #74 (Div. 1 Only)

Announcement of Codeforces Beta Round #74 (Div. 2 Only)

24.

Topological Sort with Fixed Indices The goal is to create a topological sorting except some vertices need to have specific indices in the final ordering. Is there a nice, fast way to do this?

Topological Sort with Fixed Indices, The goal is to create a topological sorting except some vertices need to have
specific indices

25.

Basic Graph Theory <p class="MsoNormal"><span style="font-size: 12.0pt;line-height: 115.0%;font-family: "Times New Roman" , serif;color: black;">Graph Algorithms is
a most interesting portion of algorithm design at now. This is actually a
category named Graph Theory. Graph theory is the study of </span><a href="http://en.wikipedia.org/wiki/Graph_%28mathematics%29" title="Graph (mathematics)"><span style="font-size: 12.0pt;line-height: 115.0%;font-family: "Times New Roman" , serif;color: black;text-decoration: none;">graphs</span></a><span style="font-size: 12.0pt;line-height: 115.0%;font-family: "Times New Roman" , serif;color: black;">, mathematical structures used to model pair
wise relations between objects from a certain collection. A "graph"
in this context refers to a collection of </span><a href="http://en.wikipedia.org/wiki/Vertex_%28graph_theory%29" title="Vertex (graph theory)"><span style="font-size: 12.0pt;line-height: 115.0%;font-family: "Times Ne...

New Roman" , serif;">Topological Sorting:, New Roman" , serif;color: black;">Depth First Search, Breadth First Search,
Topological Sorting, New Roman" , serif;color: black;">The graph shown to the left has many valid
topological sorts, to sort the graph according to its nodes. A topological sort or topological
ordering of a, ; //print the topological sort

26.

Topological Sort Problem can someone explain more for this problem ([problem:510C])?
I read editorial but I didn't get that
Thanks for your help

Topological Sort Problem

27.

More Basic / Specific Algorithmic Problems Possibility? This is a blog post about possibly creating a new category of “problems” if one were to so call them on Codeforces, with the category being very standard problems requiring one specific data structure or idea. Now before you respond as to why one would want such a useless or simplistic thing, I think there are several useful scenarios. In particular sometimes right now I find myself in a workflow where I would like to try a particular concept, for instance topological sorting, max flow, range minimum queries, union find, or any other algorithms / data structures like that. Right now on Codeforces to do so one has to find a problem that uses such an idea, however of course the problem will have other extraneous ideas / tricks thrown in which one also has to code. And then the other thing is that for some concepts, such as maximum flow and even more advanced topics there are no simple problems that use it, they are all Div1 D and E problems which is quite intimidating.
What I sort of...

implementation. For instance problem called Topological Sorting, which would
ask a user tosort, where I would like to try a particular concept, for instance topological
sorting, max flow, range, . For instance problem called Topological Sorting, which would ask a user to
sort a graph

28.

a O(n^2) solution for SRM517D1_600pt <div><a href="http://community.topcoder.com/stat?c=problem_statement&pm=11537">http://community.topcoder.com/stat?c=problem_statement&pm=11537</a><br /></div><div>I just reduce this problem to another:</div><div>Given the relations(larger than or less than) of permutations, find out how many permutation satisfy the relations.</div><div>(D-f[i]>f[i+1],I-for f[i]<f[i+1])</div><div>if the relation is 'DD',then there is only one permutation satisfies the relation:3 2 1.</div><div>if the relation is 'DI',then there is two permutations satisfy the relation:3 1 2,2 1 3.</div><div><br /></div><div>if i-th relation is D,assign a direct edge from i to i+1.</div><div>if i-th relation is I,assign a direct edge from i+1 to i.</div><div>(DI - 1->2<-3,DD - 1->2->3)</div><div>then the ans is the number of topological sorts of this graph.</div><div>A friend told me he solved this problem use a n^2 dp:</div><div>dp[i][j] is the number of ways which I have decided the i-th numbe...

then the ans is the number of topological sorts of this graph.

29.

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...

First, let's solve the case of acyclic graph. Any acyclic graph has topological
sort: vertices
, , let's solve the case of acyclic graph. Any acyclic graph has topological sort
: vertices order

30.

Some Doubts Hello All,
I have some questions as doubts:
1) How can we solve problem E (The secret code) in http://codeforces.com/gym/100371 Any hints?
2) I am given an sorted array of 1000 elements, where each element can be in the range [0, 20000]. We need to consider all subsequences on the array. For every subsequence, it's power is defined as the sum of all the elements in it. We are given 1000 queries of the form "x" where i need to print the xth smallest value of the power of any subsequence of the array. Here "x" is in the range of [1, min(2^n, 10000)].
For example:
Let the array be [1, 2, 100]. Then the power of subsequences sorted order are [0, 1, 2, 3, 100, 101, 102, 103]. If the query is x = 3, I need to print 2.
3) How can we solve this problem https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=2334
My approach to this problem- First of all if the graph contains a directed cycle, then the answer is 0, as a trivial case. Otherwi...

nothing. In rest of the cases, I try to find the number of topological sorts
on graph in set 1 and 2, . In such a case, I just add nothing. In rest of the cases, I try to find the
number oftopological

31.

quantity of topological sorting Hello, Сodeforces. How I can count the quantity of topological sorting in O(2^n*n)?

quantity of topological sorting

32.

Help in this topological sort problem Can any one help in this problem.I tried to solve it by finding in degree edges but getting WA
problem link: [Uva-10305](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1246)
my solution : [here](https://ideone.com/tOLieT)

Help in this topological sort problem

33.

April Fools Day Contest 2014: editorial Unfortunately, the most anybody could solve was 7 problems out of 9 total. 1289 participants solved at least one problem — this is less than the last year's numbers, but not bad either. Anyways, the key point is the total quantity of fun the people had!
#### [problem:409A]
The Most Intellectually Challenging Game In The World turned out to be the famous rock-paper-scissors. One could deduce this from the examples — ok, the rock () didn't look itself, but paper [] and especially scissors 8< looked really lifelike!
Team competition is organized like this: players are split into pairs, with one player of each team in each pair, and pairs play against each other (the first line of input has "moves" of first team's players, the second line — of second team's players). The team which scores more individual victories wins.
By the way, the game is not so trivial as it looks -
[cut]
there are big tomes written about the strategies, game ethics and organizing club...

the constraints. In fact, you have to perform topological sorting. The easiest
way is to iterate infinitely, . In fact, you have to perform topological sorting. The easiest way is to
iterate infinitely through

Tutorial of April Fools Day Contest 2014

34.

Interview Question Directed Graph — Doubt Hi Everyone!
I haven't been active lately because of interviews going on. Recently I appeared for Amazon Interview for Internship and there was a problem that I still have doubts with:
<spoiler summary="Problem">
Given a dictionary of words, find the longest Chain of words
A chain is formed when a string's last character is the same as any other string's first character.
eg , {abd , csa , cdd , dxd , nmk}
Longest Chain : csa->abd->dxd
</spoiler>
`I confirmed with the interviewer that there is a formation of the cycle in this, he told me that cycle formation is possible and whenever it happens you have to break the chain there since you don't want to repeat the same elements`
As you can see the graph is not an unweighted DAG, Hence, the problem became finding acyclic longest chain in a directed cyclic graph.
I wasn't able to come with a clear solution (O(n)) because it didn't feel right that how I can take care of cases with a cycle using maybe topological sort? ...

care of cases with a cycle using maybe topological sort? So I wanted to ask
what is the best, )) because it didn't feel right that how I can take care of cases with a cycle
using maybetopological sort

35.

DFS topologic sor. can someone help solve this ? In this exercise you should write a function top_order (G) that uses depth-first search to determine a topological sorting of a simple directed graph, if one exists. The graph should be given as a list of objects of the Node type. Here every node object has as attributes
- a list of successors of all nodes directly accessible from this node,
- a string name and
- a string color, which is set to "white" on initialization.
It can be assumed that all nodes have different names.
Input A list G of node objects is transferred that have a
directed graph (G).
Output If G has a topological sorting, the name values of the nodes are sorted topologically as a list [v1 ,. . . , vn] returned. Otherwise the list [-1] is returned.
Sample calls
1 >>> n = Node ()
2 >>> m = Node ()
3 >>> n. name = ”source”
4 >>> m. Name = ”table”
5 >>> n. co l o r = m. co l o r = ”whi te”
6 >>> n. s u c c e s s o r s = [m]
7 >>> m. S u c c e s s o r s = []
8 >>> G = [m, n]
9 >>> t o p o r d e r (G)
...

to determine a topological sorting of a simple directed graph, if one exists.
The graph should be given

36.

getting WA need help (lighoj1390 - Weight Comparison) (Category: Cycles, Topological Sorting, Strongly Connected Component) problem link: http://www.lightoj.com/volume_showproblem.php?problem=1390
my code: http://pastebin.com/gZmFux20
verdict : WA
My idea:
did a topo sort to find an order then ran a dfs and marked cross edges and removed them. What did i miss !!!

getting WA need help (lighoj1390 - Weight Comparison) (Category: Cycles,
Topological Sorting, ://pastebin.com/gZmFux20 verdict : WA My idea: did a topo sort to find an order
then ran a dfs and marked

37.

ACPC Arab Collegiate Programming Contest 2018 Editorial Hello,
Since the editorial posted for the ACPC 2018 is rather complicated (no offense), I decided to write my own tutorial with much simpler solutions. There are two problems missing, and, hopefully, they will be available soon. Hope you like it!
[problem:101991A]
<spoiler summary="Hint">
A tree has all its edges as bridges (initially $ \relax N-1 $ bridges).
</spoiler>
<spoiler summary="Hint">
Joining the end-points of a simple path with length $ \relax P $ edges, removes $ \relax P $ bridges from the tree (resulting in $ \relax N-1-P $ bridges).
</spoiler>
<spoiler summary="Tutorial">
Initially, all edges of the given tree are bridges since removing any of them disconnects the graph. So, we start with $ \relax N-1 $ bridges. Joining the end-points of a simple path with length $ \relax P $ edges, removes $ \relax P $ bridges from the tree (resulting in $ \relax N-1-P $ bridges). Since we want the resulting graph to have the number of bridges in $ \relax [L, R] $,...

level values can be done using regular $ \relax BFS $ (note the topological
sorting) on the nodes, the topological sorting) on the nodes. In the worst case, the number of nodes
in the trie will be equal

38.

A DAG Problem A was thinking about a DAG problem. It goes as follows:
You are given a directed acyclic graph with **N** nodes and **M** edges. Every vertex has a number associated with it, let us call it **A[i]**. The power of every vertex is defined as the sum of values written on every vertex reachable from it. We are given **Q** queries. In each query we need to find the power of a given vertex.
For example, Let N = 5, M = 5 and the value of A = {2, 3, 1, 4, 2}. (Assume 1-based indexing). Let the edges be {(2, 1), (3, 1), (4, 2), (4, 3), (3, 5)}, where **(x, y)** means there is directed edge from **x** to **y**.
So, querying for vertex 4, gives a answer of (2 + 3 + 1 + 4 + 2) = 12, as every vertex is reachable from it, while for vertex 3, it gives answer as (2 + 3 + 2) = 7 as only {1, 3, 5} are reachable from it.
The brute force solution is to perform dfs/bfs in every query. If possible, can you please provide an efficient algorithm for this. (I was thinking about some kind of preco...

an efficient algorithm for this. (I was thinking about some kind of
precomputation usingtopological, of precomputation using topological sort, but ended but added some values more
than once.) Thank you.

39.

MLE Ghost Bug EDIT: Solved.
In this problem: [problem:510C], I get MLE on test case 12. This is strange as I did not allocate that much space.
My solution: https://pastebin.com/LHY3RiAZ
Data Structures:
- 2-D Vector of ints
- Stack of ints
- Vector of bools to check already visited nodes
Functions:
- DFS for topological sort, sorted vertices put in stack
- DFS for cycle checking
Is there a memory leak or something? I can't tell.
Thanks, Brad.

: - DFS for topological sort, sorted vertices put in stack - DFS for cycle
checking, Functions: - DFS for topological sort, sorted vertices put in stack - DFS for
cycle checking

40.

All the good tutorials found for Competitive Programming Here is the list of some of the good tutorials written by codeforces users :-
**C++**
- [C++ Tricks](http://codeforces.com/blog/entry/15643) by [user:Swift,2018-01-22]
- [C++ STL: map and set](http://codeforces.com/blog/entry/9702) by [user:adamant,2018-01-24]
- [C++ STL: Policy based data structures](http://codeforces.com/blog/entry/11080) by [user:adamant,2018-03-05]
- [Competitive C++ Manifesto: A Style Guide](https://codeforces.com/blog/entry/64218) by [user:Swift,2019-03-04]
- [Catching silly mistakes with GCC](https://codeforces.com/blog/entry/15547) by [user:andreyv,2019-03-04]
- [About a general reader / writer for STL-Structures,](https://codeforces.com/blog/entry/71075) by [user:Arturgo,2020-12-20]
- [Blowing up unordered_map, and how to stop getting hacked on it](https://codeforces.com/blog/entry/62393) by [user:neal,2020-12-20]
- [C++ tips and tricks](https://codeforces.com/bl...

) by [user:YoyOyoYOy000y000,2020-12-20] - [[Insight] Number of Topological
Orderings of a Directed Tree](https

41.

My review about Codeforces Round #131 (Div. 2) [problem:214A]<br/>
The first glimpse to the problem statement shows me that if m or n get their maximum value which in this case is 1000, then maximum value for a or b would be 1000 to satisfy the equation. So I must check all possible values for a(0...1000) and all values for b(0...1000), and count the pairs (a, b) such that satisfy the given equation.
<br/>
[problem:214B]<br/>
After reading the problem statement, you can find out that the necessary and sufficient condition so that we can find a number which is divisible by 2, 3 and 5 is that there exists one 0 in the input, cause at least we can build 0. Then as I want to maximize the final result, I like all the input digits appear in the output, unless where it breaks the rule for divisibility of 3. (Which numbers are divisible by 3? Those which addition of their digits is divisible by 3.) So I have a variable sum which is the summation of the input digits, here we face 3 total cases: <br/>
1. sum is divisible by 3 : ev...

a topological sort. Each part of the game is a node in this graph. One of the
algorithms to find atopological, statement it surely has a topological sort. Each part of the game is a node in
this graph. One

42.

Topcoder SRM 524 Review <p>This was a pretty good SRM for me, tantalizingly close to red now. I'll talk about the easy (decent) and medium (really cool), but I didn't have time to take a look at the hard.</p><h3><a href="http://community.topcoder.com/stat?c=problem_statement&pm=11607&rd=14549">Easy</a> (250)</h3><div>We observe immediately that if $n$ is composite, it takes only $1$ move, so all of those cases are done. Then when $n$ is prime, we can just use $1$ and $n-1$ (which is even), so it takes $2$ moves and we're done, right? Almost! For $n = 2$, the answer is indeed $2$ because $1$ is not prime, but for $n = 3$, the answer is $3$ because $2$ is prime. Those are the only two interesting cases, so now we're really done.</div><div><br /></div><h3><a href="http://community.topcoder.com/stat?c=problem_statement&pm=11580&rd=14549">Medium</a> (500)</h3><div>This is a very nice problem in my opinion because it's not obvious where to start, but once you figure it out it's quite simple. First, ...

by running a topological sort; alternatively, notice that if there is a cycle
then there must be one, to checking for cycles. We can do this in $O(n*|C|)$ time by running a
topological sort

43.

feeling demotivated and loss of confidence!! Hello friends, i know that there are a lot of similar blogs out there but i m writing this because of a genuine concern, i have been coding for sometime now but still i m unable to think beyond a certain level, however hard i try to, i don't know what to do, during holidays,i used to code for fun but since the holidays ended i do not feel like coding anymore, because so much time is wasted in daily chores and when i see people solving good questions i feel even more demotivated, i dont know what to do and i think i have forgotten whatever i learnt during holidays, i really want to code and increase my level and my lost confidence(which i gained during holidays) so guys plz help, for eg i m sure that i could have thought educational round 14 D question if i were the same person as during the holidays but i couldn't today, i lost even more confidence(i was trying to think topological sort or dsu or something but i was simply sorting), i just want to know a method to gain my lost confiden...

the holidays but i couldn't today, i lost even more confidence(i was trying to
thinktopological sort

44.

Algorithms Live! Episode 27 [http://algorithms-live.blogspot.com/2017/07/episode-27-topological-sort-and.html](http://algorithms-live.blogspot.com/2017/07/episode-27-topological-sort-and.html)

[http://algorithms-live.blogspot.com/2017/07/episode-27-topological-sort
-and.html](http

45.

[Need Help] Order statistics in rooted trees Hello!
I am solving a problem where a rooted tree with N vertices is given, each vertex has a value V <= 10^9, and i have to answer M queries. Each of the queries has the format (V,K), and i have to answer which is the K-th smallest value in the subtree rooted in vertex V. The limits for N,M are 10^5.
My current approach solves almost every instance of the problem (O(N log N) average) but fails when the tree degenerates to a linked list (O(N^2 log N) worst case). I store every query so i can answer all them after i run my algorithm. I process the tree from the leaves up to the root using topological sort, and when i am processing some vertex, i merge the leaves' subtrees values using heapsort (found it to be faster than mergesort, but still slow if the tree is a linked list), and answer every query related to this vertex. After every vertex has been processed, i iterate over the answer array and print the results.
Can anyone help me with a better approach, or point some proper...

using topological sort, and when i am processing some vertex, i merge the
leaves' subtrees values using, topological sort, and when i am processing some vertex, i merge the leaves'
subtrees values using heapsort

46.

Problem with segment tree Hi
I am currently trying to solve my first problem with segment tree.
Link to the problem:[http://www.hackerearth.com/tracks/pledge-2015-medium/xor-in-tree-1/](http://www.hackerearth.com/tracks/pledge-2015-medium/xor-in-tree-1/)
I couldn't understand the segment tree implementation in context to this problem which is present in the editorial in the problem setter's solution.
What does T[i] store here?
For the second query, why
int res = path_xor[u] ^ path_xor[v] ^ ST.get_xor(pos[u]) ^ ST.get_xor(pos[v]) ^ a[c];
and not
int res = ST.get_xor(pos[u]) ^ ST.get_xor(pos[v]) ^ a[c]; for the second query?
Currently, I could only understand that the tree is first ordered so that it becomes inline ie topological sort.Now the segment tree works on this topologically sorted tree.

topological sort.Now the segment tree works on this topologically sorted tree.

47.

Algorithms: Design and Analysis, Part 1 <br>
[![ ](https://d2wvvaown1ul17.cloudfront.net/site-static/pages/home/template/logo-light.svg)<br>](https://www.coursera.org/course/algo)
[![ ](https://www.coursera.org//maestro/api/course/971469/university_logo)](https://www.coursera.org/course/algo)
<br>
Algorithms: Design and Analysis, Part 1<br>
by _Tim Roughgarden_ <br><br>
I think this course will be very useful and this is the right position to post this post.<br>
This course started already ( _from short period of time_ )
So you still have a chance to join and see First week lectures and submit Assignments.
<br>
**FYI** ,I will start after writing this post.<br>
This course is part #1 and I think it contains most of Algorithms you need to be good at competitions<br>
**you can check what you will learn in [Syllabus](https://class.coursera.org/algo-005/wiki/Syllabus)** <br>
but to summarize you will learn Algorithm Analysis,D&C,Sorting & Searching,BFS,DF...

,DFS,SCC,Topological Sort,Dijkstra,Heaps , Hash Tables,BST,... and more
**Students who

48.

New on codeforces Hey there,
I am new on codeforces and I wanna train, therefore I might represent my country in the upcoming ACM or even ICPC.
I felt like there is a gap between the B and C problems difficulty, most contests I viewed, problems numbered A ,B were very easy, however problems C, D, & so on were very difficult. I may think that this is the point I cannot pass , because I want to train on medium difficulty problems , what do you suggest? codeforces!
UPD1 I have improved a lot since last year! It was accomplished by studying many algorithms such as in Graph(dfs, bfs, dijkstra, topological sort) and in divide and conquer such as (dynamic programming, binary search) and data structure ( segment tree, trie, prim, BIT..). you can search Youtube for good tutorials for these algorithms/data structures. even though problems div1D div1E... still are very difficult.

such as in Graph(dfs, bfs, dijkstra, topological sort) and in divide and
conquer such as (dynamic

49.

CodeCraft-17 and Codeforces Round #391 (Div. 1 + Div. 2, combined) Editorial [757A — Gotta Catch Em' All!](http://www.codeforces.com/contest/757/problem/A)
------------------
**Author:** [user:tanujkhattar,2017-01-13]
**Testers:** [user:r.arora,2017-01-13] [user:born2rule,2017-01-13]
**Expected complexity**: $\mathcal{O}(n)$
**Main idea**: Maintain counts of required characters.
Since we are allowed to permute the string in any order to find the maximum occurences of the string "Bulbasaur", we simply keep the count of the letters 'B', 'u', 'l', 'b', 'a', 's', 'r'. Now the string "Bulbasaur" contains 1 'B', 2'u', 1 'l', 2'a', 1 's', 1'r' and 1 'b', thus the answer to the problem is Min(count('B'), count('b'), count('s'), count('r'), count('l'), count('a')/2, count('u')/2). You can maintain the counts using an array.
**Corner Cases:**
1. Neglecting 'B' and while calculating the answer considering count('b')/2.
2. Considering a letter more than once ( 'a' and 'u' ).
<spoiler summ...

of merge sort. For a comparison between 2 vectors $v_1$ and $v_2$, we cover at
least $min(v_1.size

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/03/2021 01:14:58 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|