Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

 
 
 
 

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

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

Results

 
 
 
 
1.
By DarthKnight, 5 years ago, In English,
Algorithm Gym :: Graph Algorithms Welcome to the new episode of [user:PrinceOfPersia,2015-01-31] presents: Fun with algorithms ;) You can find all the definitions here in the book "Introduction to graph theory", Douglas.B West. [cut] Important graph algorithms : DFS --- The most useful graph algorithms are search algorithms. DFS (Depth First Search) is one of them. While running DFS, we assign colors to the vertices (initially white). Algorithm itself is really simple : ~~~~~ dfs (v): color[v] = gray for u in adj[v]: if color[u] == white then dfs(u) color[v] = black ~~~~~ Black color here is not used, but you can use it sometimes. Time complexity : $O(n + m)$. #### DFS tree DFS tree is a rooted tree that is built like this : ~~~~~ let T be a new tree dfs (v): color[v] = gray for u in adj[v]: if color[u] == white then dfs(u) and par[u] = v (in T) ...
Algorithm Gym :: Graph Algorithms, (but if there is a cycle with negative weight, then this problem will be NP)., : adj[u]) //adj[v][i] = pair(vertex, weight) if(d[p.first] > d[u] + p.second) d[p.first, : adj[v]){ //adj[v][i] = pair(vertex, weight) int u = p.first, w = p.second; d[u] = min(d[u], w); } } } ~~~~~, ;) You can find all the definitions here in the book "Introduction to graph theory", Douglas.B West, attention that you can't have edges with negative weight., the nearest vertex to $S$, in $S$ (distance of $v$ from $S = \min_{u \in S}( weight(u,v))$ where $weight(i,j, ()); for(auto p : adj[u]) //adj[v][i] = pair(vertex, weight) if(d[p.first] > d[u] + p.second, In this algorithm, first we sort the edges in ascending order of their weight in an array of edges., ]) continue; mark[u] = true; for(auto p : adj[u]) //adj[v][i] = pair(vertex, weight) if(d, ~~~~~ Kruskal() solve all edges in ascending order of their weight in an array e ans = 0

Read more »

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

 
 
 
 
2.
By MiFaFaOvO, history, 19 months ago, In English,
A problem collection (Spoiler Alert) SPOILER ALERT : If you didn't solve the problems in NEERC and you want to enjoy the problems, please don't read. <spoiler summary="Spoiler"> It looks there are few problems about general graph matching in the community. And there are a few teams who solved problem B in NEERC both online and onsite. However, the reduction from maximum cost perfection matching to this problem is simple to me. So I want to share some problems for practice. You can find the template [here](http://uoj.ac/problem/81/statistics) and [here](http://uoj.ac/problem/79/statistics). The [shortest code](http://uoj.ac/submission/282287) of the maximum cost matching problem is about 5.7k. There is a simple way to find the cardinality of the maximum matching, which is half of the rank of the Tutte matrix. We can use Gaussian elimination to compute the rank of a matrix. By the way, if the maximum cost is no more than $W$, we can also find the maximum cost matching by Tutte matrix and polynomial interp...
three vertices. In a weighted graph, the weight of a cycle cover is the sum of the weights of all its, . In a weighted graph, the weight of a cycle cover is the sum of the weights of all its edges. Find, 2. Given an undirected weighted graph $G$, find a minimum weight subset $E$ such that each vertex, 4. Given an undirected positive weighted graph $G$, find the shortest simple path from $s$ to $t, 7. Two matching. Given an undirected weighted graph $G$, find a minimum weight subset $E

Read more »

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

 
 
 
 
3.
By re_eVVorld, 11 days ago, In English,
ICPC Graph Mining Challenge solution Hi, fellow programmer :) I want to describe ideas that I used during [contest:1378]. #### First, how to get more than 600k score? For 600k score we can just implement what [this](https://arxiv.org/pdf/0803.0476.pdf) article says. Lets start with each cluster having only one vertex. **(1)** Then do the following thing until converge: choose random vertex and move it to one of the adjacent vertices cluster if it makes result better. **(2)** Now compress each cluster to one vertex and make new graph with weighted edges, then do everything like in **(1)** but now you are making clusters of clusters. I think image in article above explains it quite good. So, do **(1)** once and **(2)** until converge. Basically, that's it. <spoiler summary="features"> In my case "until converge" means "do _const_ iterations" (about 10kk-40kk iterations for **(1)**, 100k-3kk iterations for **(2)** and reapeat **(2)** 5-10 times). Not sure if it is all that important but: - if there are sever...
ICPC Graph Mining Challenge solution, and make new graph with weighted edges, then do everything like in **(1)** but now you are making, new graph with weighted edges, then do everything like in **(1)** but now you are making clusters

Read more »

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

 
 
 
 
4.
By ICPCNews1, 4 weeks ago, In English,
2020 ICPC Graph Mining Challenge — Powered by Huawei: Battle of the Connected Brains [<img src="/predownloaded/aa/57/aa577c257884a5ae68792513c31d9f64fd7bff5f.png" align="right" style="height: 300px; margin: 10px 30px 20px;" alt="text"/>](https://challenge.icpc.global/) **UPD:** You can predownload tests as an encrypted zip-archive by the links https://test1.codeforces.com/icpc-challenge-2020-tests.zip or https://test4.codeforces.com/icpc-challenge-2020-tests.zip (~80MB). The password is `64e00d81811bbc463e1e636af`. Hello everyone! <a href="https://u.icpc.global/" style="font-size: 15.0px;padding: 8.0px 14.0px;background-color: rgb(207, 56, 34);color: white;">Live broadcast</a> Announcing the **ICPC Graph Mining Challenge**, Powered by Huawei and brought to you by [ICPC U](https://u.icpc.global/). Graphs are a powerful mechanism for representing many aspects of our daily lives, from mobile call routing to disease tracking. Answering various graph-related questions enables solutions to some of the most challenging, modern problems. The ICPC Challenge prese...
2020 ICPC Graph Mining Challenge — Powered by Huawei: Battle of the Connected Brains, broadcast Announcing the **ICPC Graph Mining Challenge**, Powered by Huawei and brought to you, -decoration: none;font-size: 18.0px;background-color: rgb(207, 56, 34);color: white;font-weight: bold;padding

Read more »

Announcement of ICPC Challenge 2020
 
 
 
 
  • Vote: I like it
  • +408
  • Vote: I do not like it

 
 
 
 
5.
By Arpa, history, 3 years ago, In English,
Graph saving methods Hi. ## Introduction. We have a graph, we want to save it (and maybe run DFS on it for example); simple? Yes, but I want to show different methods for this, you can choose any of them depending on problem. ### Adjacency matrix. Simple, if graph is not weighted, save in $G[v][u]$ if there is an edge between $v$ and $u$ or not. If graph is weighted, if there is an edge between $v$ and $u$ save it’s weight in $G[v][u]$, save $-1$ otherwise (if weight can be negative, use $inf$ instead of $-1$). Memory usage : $\mathcal{O}(n ^ 2)$.<br>Overall time complexity : $\mathcal{O}(n ^ 2)$ (for running dfs). <spoiler summary="Code here"> ~~~~~ // God & me #include <bits/stdc++.h> using namespace std; const int maxn = 1e3 + 17; int n, m; bool G[maxn][maxn], mark[maxn]; void dfs(int v){ if(mark[v]) return ; mark[v] = 1; for(int u = 0; u < n; u++) if(G[v][u]) dfs(u); } int main(){ ios::sync_with_stdio(0), cin.tie(0); cin >> n >> m; ...
Graph saving methods, about edges, i.e. change weight, delete edge). Keep index of edges related to each vertex in its, for each edge just save it in related vectors. Use pair (or another struct) for savingweighted graph, on problem. ### Adjacency matrix. Simple, if graph is not weighted, save in $G[v][u, **Example:** Consider you need to change weight of edges online, this is simple using index keeping, If graph is weighted, if there is an edge between $v$ and $u$ save it’s weight in $G[v][u]$, save, Simple, if graph is not weighted, save in $G[v][u]$ if there is an edge between $v$ and $u$ or not.

Read more »

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

 
 
 
 
6.
By ATSTNG, history, 11 months ago, In English,
[Tutorial] Matroid intersection in simple words **[This article is also available in [Russian](https://codeforces.com/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...
on edges of some undirected graph. Set of edges is independent if it does not contain a cycle

Read more »

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

 
 
 
 
7.
By arham_doshi, history, 2 weeks ago, In English,
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(...
cses graph session editorial(incomplete), distance from end of node till n and add weight/2. may be the concept involved here , p.cost + edge weight in the heap. now just print ans array complexity o(nmk).[more about, -graph/). we try to color all vertex greedily if vertex is not visited color it white

Read more »

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

 
 
 
 
8.
By Peace_789, history, 5 weeks ago, In English,
Negative Cycle in Directed weigthed graph Hello everyone... First of all sorry but I am writing the blog on same doubt again because there was some issues with code in last blog. So , recently I was solving this problem ... <spoiler summary="Problem statement"> You are given a directed weighted graph, and your task is to find out if it contains a negative cycle, and also give an example of such a cycle. </spoiler> I am aware of solving this problem using **Bellman Ford's Algorithm** , But I am trying another approach which is giving me WA in 1 Test Case (total 13 is there) . So , Can anyone point out whether this approach is correct or not ... and If it is correct then suggest me some modification else give some counter examples where this code might fail. <spoiler summary="Code"> ~~~~~ #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define mod 1000000007 #define check exit(0) #define nl cout<<endl; #define inp 30000 #define ordered_set...
Negative Cycle in Directed weigthed graph, You are given a directed weighted graph, and your task, summary="Problem statement"> You are given a directed weighted graph, and your task is to find out, with // minimum weight, { ll tmp = weight[n]-weight[c.first] + c.second; //weight of cycle, vector> g[inp]; vector weight(inp,0);, void dfs(ll n,ll tot) { vis1[n]=true; weight[n]=tot;

Read more »

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

 
 
 
 
9.
By himanshujaju, history, 4 years ago, In English,
Faster Dijkstra on Special Graphs [Tutorial] You can read the latex formatted pdf [here](https://www.dropbox.com/s/03wjbvhhvqcsz3c/fast-dijkstra.pdf?dl=0). ### Pre Requisites Dijkstra's algorithm ### Motivation Problem You are given a weighted graph $G$ with $V$ vertices and $E$ edges. Find the shortest path from a given source $S$ to all the vertices, given that all the edges have weight $W$ $\in $ $\{X,Y\}$ where $X,Y>=0$ ![ ](http://codeforces.com/predownloaded/40/aa/40aaed570e7e7cdad063751868a0993e60d2b693.png) ### Naive Solution Most people when given this question would solve it using Dijkstra's algorithm which can solve this efficiently in $O(E*logV)$ (Let's not take Fibonacci heap implementation into consideration now). It turns out that this solution, though it will work in most cases well under the time, can be improved further to a linear time algorithm. Before moving into the next section, try to think about how you could optimise Dijkstra's algorithm. ( **Hint :** There are only two possible values...
a weighted graph $G$ with $V$ vertices and $E$ edges. Find the shortest path from a given source $S, from $u$ to $v$ has a weight $X$ then push $v$ to the queue $QX$, else push it on the queue $QY, travelled an edge with weight X, we can subtract this quantity from both the distances. Thus, $dist, ### Motivation Problem You are given a weighted graph $G$ with $V$ vertices and $E$ edges. Find, . ( **Hint :** There are only two possible values of the edge weight.)

Read more »

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

 
 
 
 
10.
By luciocf, 13 months ago, In English,
Shortest Cycle in Weighted Graph I was thinking about this problem for quite a while but couldn't solve it. The statement is the following: Given an undirected and weighted simple graph with $N$ vertices and $M$ edges, find the cost (sum of weights in edges) of its shortest cycle, that is, the one with least cost. Repeated edges are not allowed in the cycle. **Note**: It is assumed the graph has at least one cycle. **Constraints**: $1 \leq N \leq 10^4$, $1 \leq M \leq 10^5$ $0 \leq W_i \leq 100$, where $W_i$ is the weight of the ith edge. The problem can be found here: https://dunjudge.me/analysis/problems/697/. Can anyone help me solve it?
Shortest Cycle in Weighted Graph, is the following: Given an undirected and weighted simple graph with $N$ vertices and $M$ edges, find, $0 \leq W_i \leq 100$, where $W_i$ is the weight of the ith edge., **Note**: It is assumed the graph has at least one cycle., Given an undirected and weighted simple graph with $N$ vertices and $M$ edges, find the cost (sum

Read more »

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

 
 
 
 
11.
By Peace_789, history, 5 weeks ago, In English,
Negative Cycle in Directed weigthed graph Hello Everyone ... Today I was solving this problem ... **Problem statement** : You are given a directed weighted graph, and your task is to find out if it contains a negative cycle, and also give an example of such a cycle. I am aware of solving this problem using **Bellman Ford's Algorithm** , But I am trying another approach which is giving me WA in 1 Test Case (total 13 is there) . So , Can anyone point out whether this approach is correct or not ... and If it is correct then suggest me some modification otherwise give some counter examples where this code might fail. <spoiler summary="code"> ~~~~~ #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define mod 1000000007 #define check exit(0) #define nl cout<<endl; #define inp 30000 #define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> #define ll long long int #define trace(x) cerr<<#x<<" : "<<x<<endl; #...
Negative Cycle in Directed weigthed graph, a directed weighted graph, and your task is to find out if it contains a negative cycle, and also, { ll tmp = weight[n]-weight[c.first] + c.second; if(tmp<0, Today I was solving this problem ... **Problem statement** : You are given a directedweighted, vector weight(inp,0);, void dfs(ll n,ll tot) { vis1[n]=true; weight[n]=tot;

Read more »

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

 
 
 
 
12.
By himanshujaju, history, 5 years ago, In English,
0-1 BFS [Tutorial] [Link To PDF version (Latex Formatted)](https://www.dropbox.com/s/sgzwlmsmx5rrrug/0-1%20BFS.pdf?dl=0) **Topic :** 0-1 BFS **Pre Requisites :** Basics of Graph Theory , BFS , Shortest Path **Problem :** You have a **graph G** with **V vertices** and **E edges**. The graph is a weighted graph but the weights have a contraint that they can only be 0 or 1. Write an efficient code to calculate shortest path from a given source. **Solution :** **Naive Solution &mdash; Dijkstra's Algorithm.** This has a complexity of O(E + VlogV) in its best implementation. You might try heuristics , but the worst case remains the same. At this point you maybe thinking about how you could optimise Dijkstra or why do I write such an efficient algorithm as the naive solution? Ok , so firstly the efficient solution isn't an optimisation of Dijkstra. Secondly , this is provided as the naive solution because almost everyone would code this up the first time they see such a question , assuming ...
**Problem :** You have a **graph G** with **V vertices** and **E edges**. The graph is a weighted, of execution of BFS when you are at an arbitrary vertex "u" having edges with weight 0 and 1. Similar, You have a **graph G** with **V vertices** and **E edges**. The graph is a weighted graph

Read more »

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

 
 
 
 
13.
By MuratKhayrulin, history, 5 years ago, In English,
A simple tool for graph vizualization Hi there! I've made a [simple tool for graph vizualization](http://mxwell.github.io/draw-graph/), that might be helpful in problems solving. The idea was to make something that could be used as easy as just copy-paste from input examples into the tool. It's built on top of Google's Image Charts. Though service is [deprecated](https://developers.google.com/chart/image/?hl=en) currently, it works fine. Thanks to Google. **How to use**: one of common ways to represent a graph is edges, described on separate lines with their endpoints and possibly some label (weight, cost, etc). So all you need is to input these lines into the text area and press the button. Try it with these lines: ``` 1 3 10 2 4 11 5 4 10 3 5 12 1 6 10 6 5 12 ``` Is that easy? You can also: - comment out some lines with `#`; - set checkbox to ignore the first line, that usually contains number of nodes or some other data; - not show labels; - plot a directed graph; - **UPD** share link ...
A simple tool for graph vizualization, **How to use**: one of common ways to represent a graph is edges, described on separate lines, Hi there! I've made a [simple tool for graph vizualization](http://mxwell.github.io/draw-graph

Read more »

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

 
 
 
 
14.
By Ripatti, 10 years ago, translation, In English,
A little bit of classics: dynamic programming over subsets and paths in graphs <i>Author thanks </i><a href="../../../profile/adamax" title="Капитан adamax" class="rated-user user-yellow">adamax</a><i> <span class="short_text" id="result_box"><span style="" title="">for translation this article into English.</span></span></i><br><br><b>Introduction</b><br>After <a href="http://codeforces.ru/blog/entry/331">Codeforces Beta Round #11</a> several participants expressed a wish to read something about problems similar to <a href="http://codeforces.ru/contest/11/problem/D">problem D</a> of that round. The author of this article, for the purpose of helping them, tried searching for such information, but to his surprise couldn't find anything on the Internet. It is not known whether the search was not thorough or there's really nothing out there, but (just in case) the author decided to write his own article on this topic.<br><br>In some sense this article may be regarded as a tutorial for the <a href="http://codeforces.ru/contest/11/problem/D">problem D</a> from Beta R...
time and memory and therefore can be used only if the graph is very small - typically 20 vertices, 1. Search for the shortest Hamiltonian walk Let the graph $G=(V,E)$ have $n$ vertices

Read more »

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

 
 
 
 
15.
By RomeoFantastik, history, 4 months ago, In English,
Breadth First Search (BFS) #### _**In what context does this work?**_ As you probably know, there are two types of graphs in terms of their edges: 1. Graphs with unweighted edges (the cost of traversing/processing/... each edge is 1) 2. Graphs with weighted edges (each edge has a particular cost to be traversed/removed/processed/... particular not necessary unique) There are a couple of classic problems on graphs, but one of the most approached one is to find the **shortest path between some node(we call it the source node) and all the other nodes**. You are going to see this problem in a lot of different formats: - Could be shortest path from a set of nodes to some specific node => which is obviously exactly the same - You can have some "obstacles"(or "bad nodes" or "bad cells") => which is exactly the same but you are not going to include those nodes in your graph/algorithm. - You can have some forbidden actions(for example, you are not allowed to move from some node to another if thei...
/... each edge is 1) 2. Graphs with weighted edges (each edge has a particular cost to be traversed, 2. Graphs with weighted edges (each edge has a particular cost to be traversed/removed/processed

Read more »

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

 
 
 
 
16.
By md.ashif313, history, 3 years ago, In English,
Shortest path in weighted graph with maximum edge limit I'm trying to find efficient algorithm for finding shortest path in weighted(Positive/Negative) graph with maximum edge limit. For example, in the graph below if we demand the shortest path from A to C with restriction the path can contain at most two edges. It would be A->B->C and total cost 5 (Which is greater than A->D->E->C) ![Weighted graph without negative edge.](/predownloaded/39/50/395082f3ae61c189441f0831cd91e8687df6e66b.png) I think when the graph is (directed or undirected) has no negative edge, we can use Dijkstra with little modification, such that we will keep the number of edges in the currently discovered shortest path from source to currently used vertex for relaxation. Is my idea OK? Or there is much better something? And how can we solve the similar problem when the graph(directed) consists of negative edges(but no negative cycle)?
Shortest path in weighted graph with maximum edge limit, (Which is greater than A->D->E->C) ![Weighted graph without negative edge.](/predownloaded/39/50, ![Weighted graph without negative edge.](/predownloaded/39/50, And how can we solve the similar problem when the graph(directed) consists of negative edges, For example, in the graph below if we demand the shortest path from A to C with restriction, I think when the graph is (directed or undirected) has no negative edge, we can use Dijkstra, I'm trying to find efficient algorithm for finding shortest path in weighted (Positive/Negative

Read more »

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

 
 
 
 
17.
By zscoder, history, 2 months ago, In English,
[Tutorial] Generating Functions in Competitive Programming (Part 2) Welcome to Part 2 of my tutorial on generating functions. The [first part](https://codeforces.com/blog/entry/77468) focused on introducing generating functions to those without any background in generating functions. In this post, I will demonstrate a few applications of generating functions in CP problems. Let us start with some relatively straightforward examples. Note: Unless stated otherwise, all computations are done modulo a convenient prime (usually $998244353$). Also, $[n]$ denotes the set $\\{1,2,...,n\\}$. ### Blatant Applications in Counting Problems **Problem.** [AGC 005 Problem F](https://atcoder.jp/contests/agc005/tasks/agc005_f) You have a tree $T$ with $n$ vertices. For a subset $S$ of vertices, let $f(S)$ denote the minimum number of vertices in a subtree of $T$ which contains all vertices in $S$. For all $1 \le k \le n$, find the sum of $f(S)$ over all subsets $S$ with $|S| = k$. Constraints: $n \le 2 \cdot 10^{5}$. <spoiler summary="Solution"> First, ...
/problem/438/E) You have a set of positive integers $C = \\{c_1, c_2, ..., c_{n}\\}$. A vertex-weighted, The idea is to relate $b(n)$ with $c(n)$. Suppose we have a labelled connected graph on $n

Read more »

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

 
 
 
 
18.
By gen, 7 years ago, translation, In English,
Codeforces Round #200 Tutorial #### [problem:344A] By the definition each block consists of a number of consequent and equally oriented dominoes. That means that in places where adjacent dominoes are not oriented equally, one block ends and another block starts. So, if there are $x$ such places, the answer is equal to $x+1$. Solution complexity: $O(n)$. Problem author: [user:gen,2013-09-15]. **Bonus:** The problem was created a day before the contest and filled in the last part of a physically flavoured DivII complect. :] #### [problem:344B] First solution. First, the sum $a+b+c$ should be even, since each bond adds 2 to the sum. Now let $x$, $y$, $z$ be the number of bonds between 1st and 2nd, 2nd and 3rd, 3rd and 1st atoms, accordingly. So we have to solve the system $x+z=a$, $y+x=b$, $z+y=c$. Now observe that the solution to the system is the length of the tangents on the triangle with sides of length $a$, $b$, $c$ to its inscribed circle, and are equal to $\frac{b+c-a}{2}$, $\frac{c+a-b}{2}$, $\fr...
) tree data structure. For a given weighted graph the tree has the following properties:, Surprisingly, such a tree exists for any weighted graph, and can be built in $O(n\cdot maxFlow

Read more »

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

 
 
 
 
19.
By felipeblassioli, history, 5 years ago, In English,
Python: Dict based graph VS list based graph , short comparison. I've written this in response to this [comment](http://codeforces.com/blog/entry/21027?#comment-257336) when I was solving a different [problem](http://codeforces.com/blog/entry/21027). Summary: You got weight: - Lookup time (in graph traversals) - str to int conversion -> reading the graph - int to str conversion -> output the graph ___ Take this [problem](http://acm.timus.ru/problem.aspx?num=1671) for example, it has an awfully big input and also a big output. (for big I mean ~10^5 ints) We have more than 200000 numbers. (when N=10^5 and M=10^5) I`ve used an EC2 small machine to do the timings and they were quite close to the timus judge's output. EC2 seems slower than timus. Here's some timings for the input with max N and M: Using a list for the graph (int indexed): ~~~~~ from sys import stdin from itertools import izip, islice tkns = iter(map(int, stdin.read().split())) n,m = int(tkns.next()), int(tkns.next()) graph = [[] for i in xrange...
Python: Dict based graph VS list based graph , short comparison., : You got weight: - Lookup time (in graph traversals) - str to int conversion -> reading, Summary: You got weight:

Read more »

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

 
 
 
 
20.
By Zlobober, history, 5 years ago, In English,
Checkers with testlib.h Introduction ------------ Checker is a program that should be written when task allows more than one correct solution. Although it seems that it is very easy to write checker, there are lots of important technical details that are easy to forget if you don't use a special library like testlib.h. A common convention is that a checker should be a program taking three command-line arguments: the testdata filename, the participant output filename and the jury answer filename. Checker should read the contents of the input, output and answer, decide whether participant answer is correct (and optimal being compared to the jury's answer if there can be unoptimal answer in this task) and return one of several pre-defined verdicts: | Verdict | testlib macro | meaning | |---------|---------------|---------| | Ok | `_ok` | The output is correct, follows the output format and represents an optimal answer (if applicable in this problem). | | Wrong Answer | `_wa` | The output is wrong or...
**Problem statement** You are given a connected undirected weighted graph witn $n$ vertices and $m, : **Problem statement** You are given a connected undirected weighted graph witn $n$ vertices and $m

Read more »

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

 
 
 
 
21.
By noobinho, history, 2 years ago, In English,
Graph problem I'm trying to do this problem: http://acm.timus.ru/problem.aspx?space=1&num=1416. It consists in a simple, undirected and weighted graph for which is demanded to calculate the second minimum total cost: a cost of a configuration (different than the minimum-spanning-tree) which connects all vertex and has the smallest cost not less than the cost given by the minimum-spanning-tree. If there isn't such a configuration it's demanded to indicate that. I did the following code: https://ideone.com/e.js/y4CcBz. It generates the minimum-spanning-tree with Kruskal and tries to eliminate the edges of this tree one by one from the bigger to the smallest. For each edge eliminated, it tries to connect the edges that weren't in the minimum-spanning-tree, one by one, from the bigger to the smallest, and verifies with a DFS if the resulting graph has only one connected component. If so, it stops. Else, it reconnects the edge of the minimum-spanning-tree and goes to the next iteration. Since my appr...
Graph problem, in a simple, undirected and weighted graph for which is demanded to calculate the second minimum total

Read more »

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

 
 
 
 
22.
By _maverick, history, 5 years ago, In English,
Interview Question — An interesting Graph problem I got this question in one of my interviews. Let me state the problem statement clearly, "You're given an undirected weighted graph consisting of N nodes and E edges and all the weights are unique ( meaning no weights will have duplicates ). Note the graph may also be disconnected ( there could be more than one component in your graph ). The nodes in the graph are labelled starting from 1 to N." Now you're given an operation that you could perform which is, cut( u , v ) , where u is the label of one node and v is the label of another node and u < v . what this operation returns as result for the given u and v is that it takes the minimum weighted edge adds its value to result and then removes it from graph and then checks whether u and v are disconnected if they are disconnected it stops and returns the result. If the u and v are still connected by some means then it checks for the next minimum weighted edge in the graph and adds its value to the existing result value and remov...
Interview Question — An interesting Graph problem, for the next minimum weighted edge in the graph and adds its value to the existing result value and removes, given an undirected weighted graph consisting of N nodes and E edges and all the weights are unique, "You're given an undirected weighted graph consisting of N nodes and E edges and all the weights

Read more »

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

 
 
 
 
23.
By Geothermal, history, 11 months ago, In English,
AtCoder Beginner Contest 137 English Solutions Although AtCoder seems to be getting back to posting English editorials, I'm continuing to release some myself in case having the extra explanations helps some people. (Sidenote: Some of the provided submissions come from after the contest itself, because I had to leave midway through, before I got the chance to debug my E or write my F.) --- #A &mdash; +-X Just use your language's max function. As $A$ and $B$ are small, we don't need to worry about integer overflow. Runtime: $O(1).$ [Click here for my submission.](https://atcoder.jp/contests/abc137/submissions/6802607) --- #B &mdash; One Clue Let's try to find the minimum and maximum values in the answer. It's fairly easy to see that all integers between them will also be in the set. To find the minimum possible position of a black stone, we place $K$ black stones such that $X$ is at the maximum position. Then, the minimum position will thus be $X-K+1$, as we have $K-1$ black stones to the left of $X$....
$. Afterwards, we have a weighted directed graph (possibly with both positive and negative weights, Afterwards, we have a weighted directed graph (possibly with both positive and negative weights

Read more »

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

 
 
 
 
24.
By skywalkert, history, 13 months ago, In English,
2018 CMUT BeihangU Contest, Editorial This editorial corresponds to [contest:102114] (stage 5), which was held on Aug 6th, 2018. Moreover, this problem set was also used as Jingzhe Tang Contest 1 in Petrozavodsk Winter Camp on Jan 30th, 2019. **This post is now finished**, in which I try to elaborate on notes, solutions and maybe some data generating. Alternatively, you can refer to [an old published material](https://drive.google.com/file/d/1CFumWbNLTUEywkVDNF-LKT3SzYd1r15L/view), though I think the old English version did not explain something clearly. --- [problem:102114A] This problem requires to calculate $s$-$t$ min cut between any two vertices on a weighted cactus graph having $n$ vertices, denoted by $\mathrm{flow}(s, t)$. You need to report $\sum_{s < t}{(s \oplus t \oplus \mathrm{flow}(s, t))}$. $n \leq 10^5$, $\sum{n} \leq 10^6$, weights are $\leq 10^9$. Try to find some features of this graph. <spoiler summary="solution"> By contradiction, we can prove that for an undirected graph, each ed...
This problem requires to calculate $s$-$t$ min cut between any two vertices on a weighted cactus

Read more »

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

 
 
 
 
25.
By MiFaFaOvO, history, 3 months ago, In English,
A problem collection of ODE and differential technique ##A problem collection of ODE and differential technique *This problem might be well-known in some countries, but how do other countries learn about such problems if nobody poses them.* For those who are interested in well-known problems in China. Thank [user:Elegia,2020-04-23] and [user:djq_cpp,2020-04-23] for developing this technique. Thank [user:tEMMIE.w.,2020-04-23] for reviewing this article. ####[Chain Reaction](http://uoj.ac/problem/50) in UOJ Round 3 By [user:vfleaking,2020-04-23] **Statement** ​ You are given a set $A$, you need to compute $g_{i} = \frac{1}{2} \sum_{j,k}{i-1 \choose j}{i-1-j \choose k} g_jg_k$ where $i-1-j-k \in A$. **Solution** ​ Let the EGF of $g$ be $x(t)$ and EGF of $A$ be $a(t)$. Thus $x'(t)=\frac{1}{2} a(t) x^2(t)+1$. We can solve this equation by D&C and FFT in $O(n\log^2 n)$. But there is a <s>slower</s> solution in $O(n\log n)$. ​ For a polynomial equation $f(x(t))=0$, we can use the Newton's method to solve it. If we find ...
of this problem: We define the weight of a sequence $a_1, a_2, \dots, a_k$ as $\prod_{i=1}^k (a_i+i)$. You

Read more »

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

 
 
 
 
26.
By felipeblassioli, history, 5 years ago, In English,
Can we use Floyd-Warshall to find the minimum weight non-trivial cycle in a graph? Can we modify Floyd-Warshall and have dist[u][u] = shortest distance from u to itself? Floyd-Warshall is initialized with dist[u][u] = 0 , can we do dist[u][u] = INF and run a default implementation of Floyd-Warshall hoping that dist[u][u] is the shortest distance from u to u? (i.e the minimum weight cycle)? Does this works for both directed and undirected graphs? I'm taking for a default implementation something like wikipedia: let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each vertex v 3 dist[v][v] ← 0 4 for each edge (u,v) 5 dist[u][v] ← w(u,v) // the weight of the edge (u,v) 6 for k from 1 to |V| 7 for i from 1 to |V| 8 for j from 1 to |V| 9 if dist[i][j] > dist[i][k] + dist[k][j] 10 dist[i][j] ← dist[i][k] + dist[k][j] 11 end if ___ Apparently it works for directed graphs. Is there a way to modify Floyd-Warshall and find the...
Can we use Floyd-Warshall to find the minimum weight non-trivial cycle in a graph?, the minimum weight cycle)?, the minimum weight cycle?, undirected graph is a tree, there are no cycles right? Suppose there is a edge (u,v) whoseweight, ) // the weight of the edge (u,v) 6 for k from 1 to |V| 7 for i from 1 to |V| 8 for j from, If your undirected graph is a tree, there are no cycles right? Suppose there is a edge (u,v) whose, So dist[u][u] = 2. But the distance from u to itself cant be 2, because the graph has no cycles

Read more »

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

 
 
 
 
27.
By moinul.shaon, 5 years ago, In English,
Junior Programming Camp BUET 2016 -Day2 contest Shortest Path & Game Theory editorial (Only for beginners) Contest Link: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=103450#overview This editorial was written by [user:atrista,2016-01-07]. I am just posting in CF. **Problem A:** Problem summary: Given a $n*m$ grid $G$, we have to go from top-left corner to bottom right corner where the cost of stepping to cell $(i,j)$ is denoted by $G[i][j]$ which is always positive. Solution: We can use straight-forward Dijkstra for this problem. Simple Dijkstra with starting node $(0,0)$ with initial cost of $G[0][0]$ and ended on $(n-1,m-1)$ will do the job. One of the participant, moudud99's code: http://paste.ubuntu.com/14416006/ **Problem B:** Problem Summary: Given a list of walls and doors, we have to find shortest path from $cell (0,0)$ to a $cell (x,y)$ where cost is corresponded to number of doors we have to pass through out the path. Solution: The main issue in the problem is certainly graph construction. We are given a list...
Summary: Given a weighted graph G, where weight can be negative, we have to find out, Problem Summary: Given a weighted graph G, where weight can be negative, we have to find out

Read more »

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

 
 
 
 
28.
By Endagorion, 8 years ago, translation, In English,
Radius/diameter of non-weighted graph Hi, Codeforces. Could anybody kindly tell me something about fast calculating radius and/or diameter of non-weighted undirected graph (definitions can be found [here] (http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Distance)) ? Fast = faster, than in O(MN) (breadth-first searches from each vertex). Any results are welcome: probabilistic, good in average, good for sparse graphs, etc. Thanks.
Radius/diameter of non-weighted graph, and/or diameter of non-weighted undirected graph (definitions can be found [here] (http://en.wikipedia.org/wiki, -weighted undirected graph (definitions can be found [here] (http://en.wikipedia.org/wiki

Read more »

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

 
 
 
 
29.
By zscoder, history, 4 years ago, In English,
Codeforces Round #372 Editorial We hope everyone enjoyed the problems. Here is the editorial for the problems. I tried to make it more detailed but there might be some parts that might not be explained clearly. [Div. 2 A &mdash; Crazy Computer](http://codeforces.com/contest/716/problem/A) ------------------ Prerequisites : None This is a straightforward implementation problem. Iterate through the times in order, keeping track of when is the last time a word is typed, keeping a counter for the number of words appearing on the screen. Increment the counter by $1$ whenever you process a new time. Whenever the difference between the time for two consecutive words is greater than $c$, reset the counter to $0$. After that, increment it by $1$. Time Complexity : $O(n)$, since the times are already sorted. <spoiler summary="Code (O(n))"> ~~~~~ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #def...
Next, we replace the edges with $0$ weight with weight $1$. Clearly, among all the possible graphs

Read more »

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

 
 
 
 
30.
By fack, history, 4 days ago, In English,
weight assignment on vertices in weighted graph Suppose I have a weighted graph with equal positive weight (let it be K) on each edge. Now I want to count the number of ways to assign weights to vertices SUCH THAT if there is an edge between X and Y then max(W[X], W[Y])=K where W[X] means assigned weight to vertex X. can someone solve it in better than O(2^n). Anyone could help me with LCM constrainsts. Please DM Thanks
weight assignment on vertices in weighted graph, Suppose I have a weighted graph with equal positive weight (let it be K) on each edge. Now I want

Read more »

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

 
 
 
 
31.
By dcordb, history, 3 years ago, In English,
An interesting graph problem Hi. This problem is from a Mexican Training Camp of this year, you can find it [here](http://matcomgrader.com/problem/9249/impartiendo-conferencias/) (spanish only). The following is the abridged statement: Given a undirected, simple and weighted graph with $N$ nodes and $M$ edges you should select a set of exactly $N$ edges (you throw away the other $M - N$ edges) and direct each of them, such that the sum of weights will be maximum, with the restriction that each node must have out-degree equal to 1 in this new directed graph; or say that there is not solution. Constraints: - $3 \leq N \leq 10000$ - $3 \leq M \leq 50000$ - The weight of edges is between $-10^5$ and $10^5$ Example: ~~~~~ 4 6 1 2 1 1 3 -2 2 3 4 1 4 -8 2 4 16 3 4 -32 ~~~~~ In this case the answer is 19, you can direct edges the following way: - 4 to 2 (weight = 16) - 2 to 1 (weight = 1) - 1 to 3 (weight = -2) - 3 to 2 (weight = 4) I thought about flow but is no...
An interesting graph problem, statement: Given a undirected, simple and weighted graph with $N$ nodes and $M$ edges you should, - 1 to 3 (weight = -2), - 2 to 1 (weight = 1), - 3 to 2 (weight = 4), - 4 to 2 (weight = 16), - The weight of edges is between $-10^5$ and $10^5$, Given a undirected, simple and weighted graph with $N$ nodes and $M$ edges you should select a set

Read more »

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

 
 
 
 
32.
By ICPCNews1, history, 3 weeks ago, In English,
2020 ICPC Graph Mining Challenge: one additional week <img src="/predownloaded/2b/2d/2b2daa03cf569b52a7650513465deed63a775945.png" align="right" style="height: 250px; margin: 10px 30px 20px;" alt="text"/> UPDATED Dear participants! Congratulations on joining the [ICPC 2020 Graph Mining Challenge](https://challenge.icpc.global/) powered by Huawei! All were truly amazed by the participation and quality of the solutions. Congratulations to all of the winners! You will be contacted soon about your prizes. The competition was so fierce that ICPC U and Huawei have decided to keep the fun going by <u>starting a **new**, one-week challenge</u> with all new prizes. The problem and graphs are the same, so you can build on your previous success. <u>All are encouraged to participate in this challenge.</u> You may only win one prize from the entire ICPC Graph Mining Challenge events (all combined). If you place in multiple challenges, you will be able to pick the prize you prefer. <center style="margin: 2.5em;"> <a href="https:/...
2020 ICPC Graph Mining Challenge: one additional week, ! Congratulations on joining the [ICPC 2020 Graph Mining Challenge](https://challenge.icpc.global/) powered, -decoration: none;font-size: 18.0px;background-color: rgb(207, 56, 34);color: white;font-weight: bold;padding

Read more »

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

 
 
 
 
33.
By low_, history, 12 months ago, In English,
HCW '19 Team Round Editorial This is an editorial blog for [contest:102279]. Any further question can be asked in the comments, I'll try to answer all the questions. Please, do not private message or email me, your question could be the same as others', and I really hate to answer one question multiple times. >:( [problem:102279A] ------------------ Author: [user:low_,2019-07-22]. <spoiler summary="Tutorial"> To solve the problem, you'll only need to note that in $(N+1)$-th turn: Seo moved through exactly $(N+1)*V_s$ property, that is exactly $V_s$ full round of the board, so that he end up in $1$ afterwards. The same happens with B21 and Lowie. After that, the game keeps repeating itself. We can conclude that: if there isn't any event of one paying other in the first $3*(N+1)$ turns, it will never happen, so we can output $3000000000$. Otherwise, we can find the first event of it by brute force in $O(3*(N+1))$ time complexity. Maximum time complexity: $O(3*(N+1))$. </spoiler> [problem:102279B]...
Initially, create a weighted directed graph with $n$ vertices ($n, : [user:b21quocbao,2019-07-28] Initially, create a weighted directed graph

Read more »

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

 
 
 
 
34.
By trunghieu11, history, 5 years ago, In English,
Can we use Map of Map for storing weighted graph? As I know one of ways for storing a weighted graph is using Adjacency List but cons of this solution is when we want to get weight of a pair vertex this will cost O(n) by looping the adjacency vertex. So I have a solution to improve that by using Map<NodeID, Map<NodeID, Weight>> then when we want to get weight of a pair vertex, for example (1, 2) we just call Node[1].get(Node[2]), this only cost O(1). Is this correct? I'm using Java so can it have a risk?
Can we use Map of Map for storing weighted graph?, As I know one of ways for storing a weighted graph is using Adjacency List but cons, So I have a solution to improve that by using MapWeight>> then when we want

Read more »

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

 
 
 
 
35.
By Fefer_Ivan, 6 years ago, In English,
Zepto Code Rush 2014 — solutions A-D ## [problem:436A] Tutorial author: [user:Fefer_Ivan,2014-06-15] In this problem types of eaten candies must alternate. It means that the type of first eaten candy dictated the types of all the following candies. There are only two possible types so we should consider each type as a type of first eaten candy separatelly and then pick the most optimal. So, what if Om Nom wants to eat a candy of type $t$ and can jump up to $h$? It is obvious that best option is to eat a candy with maximal mass among all the candies he can eat at this time. ## [problem:436B] Tutorial author: [user:Fefer_Ivan,2014-06-15] Let us number columns with integers from $0$ from left to right and rows from $0$ from top to bottom. In the cell $(x, y)$ at the time $t$ only four spiders can be at this cell: * Spider, which is moving left and started at $(x, y + t)$. * Spider, which is moving right and started at $(x, y - t)$. * Spider, which is moving up and started at $(x + t, y)$. * Spider,...
consider a weighted undirected graph with $k + 1$ vertex. Label the vertices with numbers from $0, Let's consider a weighted undirected graph with $k + 1$ vertex. Label the vertices with numbers

Read more »

Tutorial of Zepto Code Rush 2014
 
 
 
 
  • Vote: I like it
  • +117
  • Vote: I do not like it

 
 
 
 
36.
By MiptLited, 11 months ago, translation, In English,
Travel to Singapore for the ICPC international programming workshop **Discover Singapore 2019** organized **by Moscow Workshops ICPC** and the **National University of Singapore** with support of Acronis and SIT will take place in the unique city-state of Singapore located on the islands in the South-East Asia, from 21 to 28 of September, 2019. ![ ](/predownloaded/39/74/3974cd615c136cedf1e9f8796ad11cde4cded7dd.jpg) The accommodation for participants will be organized in the hostel "Yo:HA Evans" in twin and triple rooms not far from the Botanical Garden which is included in the UNESCO World Heritage List. ![ ](/predownloaded/36/c6/36c61024a681e375dde9b4c9d307351d86e218bf.jpg) ![ ](/predownloaded/6e/ca/6eca9ae6d5a8cd818266f8e3d4b7e3ce695106c3.jpg) On the day off participants can visit the **“Universal Studios Singapore”** park — the Asian biggest theme park that features 28 rides, shows, and attractions in seven themed zones. ![ ](/predownloaded/7b/59/7b593ff2ac600cd3579f8ef7b2a0c166c1cfeb0e.jpg) ![ ](/predownloaded/58/2d/582d1c2d453e8...
and advanced algorithms and data structures: finding shortest paths in weighted graphs, segment trees, finding, contains basic and advanced algorithms and data structures: finding shortest paths inweighted

Read more »

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

 
 
 
 
37.
By Endagorion, 6 years ago, In English,
Codeforces Round #265 Editorial I'll upload my example solutions and will post links to them as soon as it becomes possible. Some of the problems editorials contain an additional challenge which is apparently harder to comprehend than the original problem. Feel free to share and discuss your ideas in the comments. =) [problem:465A] If we add 1 to a number, its binary representation changes in a simple way: all the least significant $1$'s change to $0$'s, and the single following $0$ changes to $1$. It suffices to find the length of largest suffix which contains only $1$'s, suppose its length is $l$. Then the answer is $l+1$ except for the case when all the string consists of $1$, when the answer is $l$. It is amusing that div1E problem is concerned with addition of 1 to a binary integer as well. =) [problem:465B] Optimal strategy is as follows: for every segment of consecutive $1$'s open the first letter in segment, scroll until the last letter in segment, if there are more unread letters left, retu...
This seems to be a simple graph exercise, but the problem is with enormous weights of paths which

Read more »

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

 
 
 
 
38.
By MiFaFaOvO, 6 years ago, In English,
Codeforces Round #268 Editorial I'll upload my example solutions and will post links to them as soon as it becomes possible. All the problems in Div 1 don't have the unique solution. I list several solutions to each problems. There are also some interesting bonus problems. I can't solve some of them yet :( If you have interesting ideas, feel free to share and discuss your ideas in the comments. :) My English is poor, so if there are some mistakes or something you can't understand, you can also discuss it in the comments. [problem:469A] [I Wanna Be the Guy](http://kayin.moe/iwbtg/downloads.php) is an interesting game. I strongly recommend it to you. The problem itself is easy. Just check if all the levels could be passed by Little X or Little Y. [submission:7894174] [problem:469B] This problem is not hard. Just iterator over all possible $t$, and check if the schedule of Little X and Little Z will overlap. [submission:7894252] **Bonus:** 1. $p,q\leq 50, l,r\leq 10^9$ 2. $p,q,l,r\leq 1...
$. The degree of every node is at most $2$. So this graph consists of a lot of chains and cycles, Construct a undirected graph $G$ with $2n$ vertices $v_1, v_2, \dots, v_{2n}$, where the edge

Read more »

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

 
 
 
 
39.
By Serega, 7 years ago, translation, In English,
Codeforces Round #193 (Div. 2) — Tutorial Any suggestions, remarks and information about mistakes are welcomed. If you can improve the quality of this tutorial, please write me a private message :) **[problem:332A]** Since $n \ge 4$, one Vasya’s turn does not affect his other turns. Consequently, you should find just the number of positions (0-indexed) in the given string, which indexes are multiples of $n$ and before which there are at least three same symbols. Asymptotics of the solution &mdash; $O(|s|)$ [Code](http://pastebin.com/hn4wzXj0) **[problem:332B]** Let’s build the array of partial sums, which will permit to find the sum in any segment of the array in $O(1)$. Let's iterate through the number $a$ (the left edge of the leftmost segment) in descending order. Now we need to find among segments of length $k$, starting from position which index is greater than or equal to $a+k$, a segment with the maximum sum. Since we search $a$ in descending order, we can maintain this segment during the transition fr...
version of this post): if $k \ge 3$, only complete graph containing $k+1$ vertices satisfies, ://pastebin.com/CzB1v72v) **[problem:332D]** In the problem is given the weighted undirected graph, In the problem is given the weighted undirected graph without loops and multiple edges satisfying

Read more »

Tutorial of Practise Contest #04
 
 
 
 
  • Vote: I like it
  • +40
  • Vote: I do not like it

 
 
 
 
40.
By JKeeJ1e30, 9 years ago, translation, In English,
Enumeration of vertex pairs which are connected by a path of infinitesimal weight. <p><span style="font-family: verdana , arial , sans-serif;font-size: 13.0px;text-align: left;background-color: rgb(255,255,255);">Thanks for translation by </span><a class="rated-user user-blue" href="http://codeforces.ru/profile/RodionGork" style="font-family: arial;text-decoration: none;font-weight: bold;color: rgb(0,0,204);font-size: 11.0px;text-align: center;background-color: rgb(248,248,248);" title="Expert RodionGork">RodionGork</a></p><p><span style="font-family: verdana , arial , sans-serif;font-size: 13.0px;text-align: left;background-color: rgb(255,255,255);">Problem statement:</span><br style="font-family: verdana , arial , sans-serif;font-size: 13.0px;text-align: left;background-color: rgb(255,255,255);" /><span style="font-family: verdana , arial , sans-serif;font-size: 13.0px;text-align: left;background-color: rgb(255,255,255);">Given an oriented graph with N vertices and M edges we are to find all vertex pairs for which exists a path of infinitesimal weight.</span> <br /...
Enumeration of vertex pairs which are connected by a path of infinitesimal weight., (255,255,255);">Given an oriented graph with N vertices and M edges we are to find all vertex pairs, -weight: bold;color: rgb(0,0,204);font-size: 11.0px;text-align: center;background-color: rgb(248,248,248, ;background-color: rgb(255,255,255);">Step 1. Build condensation of the graph. 

Read more »

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

 
 
 
 
41.
By MedoN11, history, 4 years ago, In English,
Find the Shortest cycle for each vertex in a graph? Hello CodeForces! Recently, I was participating in a gym contest, and came across a very interesting graph problem. For each vertice of given undirected weighted graph calculate the length of shortest simple cycle, which contains this vertice. The graph does not contain self loops or multiple edges. Here it is : http://codeforces.com/problemset/gymProblem/100917/F After the contest, I did some googling, but I can only find re-search papers discussing very complex algorithms, I'm pretty sure the author did not intend these solutions. My solution is as follows : Let's say edge e connect vertices u and v. Remove edge e from the graph, then re-run dijikstra from u to v. If there exists a path, then there exists a simple cycle containing both u, and v. Repeat for each edge, and minimise over the shortest cycle for each node. The idea really makes sense, and the problem is the time limit verdict, how can I solve this problem more efficiently? Please keep i...
Find the Shortest cycle for each vertex in a graph?, interesting graph problem. For each vertice of given undirected weighted graph calculate the length, For each vertice of given undirected weighted graph calculate the length of shortest simple cycle

Read more »

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

 
 
 
 
42.
By Newtech66, 21 month(s) ago, In English,
Graph theory problem: Node Deletion >bumping this post for first and last time because I never got an answer There is an intruder in your system who wishes to steal as much information as he can. Your system can be represented as an **undirected** graph, with each node having an information value (IV). Now, you were terribly unprepared for this. Your only option is to **delete nodes**. You have time enough to delete **at most 2 nodes**. Luckily, the algorithm of the intruder has a flaw. **It cannot visit a previously visited node.** It steals the information of whatever node it visits. Assuming that the algorithm always tries to maximize the IV it can get, give the maximum possible IV you can save. **Note**: Formally the algorithm seeks the path of maximum weight. The sum of the weights of the unvisited nodes is what you have saved. The weights of the deleted nodes are unavailable to both you and the algorithm. When a node is deleted, all paths connected to it are also removed. **A variant**: Now you are given t...
Graph theory problem: Node Deletion, as an **undirected** graph, with each node having an information value (IV). Now, you were terribly, **Note**: Formally the algorithm seeks the path of maximum weight. The sum of the weights

Read more »

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

 
 
 
 
43.
By pimenta, history, 3 years ago, In English,
Two versions of the offline square root decomposition for dynamic minimum spanning tree ### Introduction It's been around 18 months since dynamic minimum spanning tree first crossed my way and yesterday I've finally understood the offline square root decomposition for this problem. I think this solution is somehow explained [here](http://codeforces.com/blog/entry/16967), but I also think it can be explained in a better way. This is the goal of this post. I'll explain how to solve two versions of the problem. ### Acknowledgments I'd like to thank [user:thiagocarvp,2017-02-25] for explaining me the solution to the first version and [user:victoragnez,2017-02-25] for explaining me the solution to the second version. ### First version #### Problem statement First, you're given a connected graph with $n$ vertices and $m$ weighted edges. And then a sequence of $q$ new edges is added to the graph. For each of these $q$ new edges, output the weight of a minimum spanning tree considering only this and the previous edges. For example, take $V = \{1,2\}$, $E = \{(\{...
$. The graph $M_i' = M_i \setminus B_i$ is a minimum spanning forest with at most $\sqrt{q}$ components, , you're given a connected graph with $n$ vertices and $m$ weighted edges. And then a sequence of $q, Again, you're first given a connected graph with $n$ vertices and $m$ weighted edges. This time, First, you're given a connected graph with $n$ vertices and $m$ weighted edges. And then a sequence

Read more »

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

 
 
 
 
44.
By Rahul_Bhateja, history, 23 months ago, In English,
Shortest path in a weighted graph(if many then lexicographically smallest) How to find the shortest path in a weighted graph(**if many then lexicographically smallest**) using Dijkstra? [cut] - I am getting WA on 2 test cases - Problem link :[Your text to link here...](http://www.hackerearth.com/submission/18786014) - Although this can be solved using BFS, but I want to know do when the graph is weighted?
Shortest path in a weighted graph(if many then lexicographically smallest), How to find the shortest path in a weighted graph(**if many then lexicographically smallest

Read more »

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

 
 
 
 
45.
By Hohol, 8 years ago, translation, In English,
Codeforces Round #124 — editorial [problem:197A] If first player can't make first move (table is too small and plate doesn't fit it, i.e. $2r > min(a,b)$), second player wins. Else first player wins. Winning strategy for first player: place first plate to the center of table. After that he symmetrically reflects moves of second player with respect to center of table. If second player has move, first player has symmetrical move, too. If not, first player won. [problem:197B] From math lessons we know, that only higher degrees of polinomials matter in this problem. 1. If denominator degree is larger than numenator degree, answer is "0/1". 2. If numenator degree is larger, answer is infinity. But what is sign of this infinity? To get it consider signs of highest degree factors of polinomials. If they are same, answer is positive infinity, else --- negative infinity. 3. If degrees of numenator and denominator are equal, answer is $\frac{a_0}{b_0}$. To get irreducible fraction, you should divide this numbers b...
, it will be published soon. [problem:196E] First of all, we can note that if eachgraph vertex is portal, First of all, we can note that if each graph vertex is portal, the answer will be a sum of all, ])$ of weight $d[i] + w(i,j) + d[j]$ for every edge $(i,j)$ of weight $w(i,j)$ from originalgraph and run

Read more »

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

 
 
 
 
46.
By tweety, history, 4 years ago, In English,
Cool tricks using Matrix Exponential <p>I'm going to share with you some cool applications of matrix exponential that I learned recently.</p> #### Application 1: Counting the number of ways for reaching a vertex <p>You are given an unweighted directed graph (may contain multiple edges) containing N vertices (1 <= N <= 200) and an integer b (1 <= b <= 10^9). You are also given Q queries (1 <= Q <= 10^5). For each query you are given two vertices u and v and you have to find the number of ways for reaching vertex v starting from u after exactly b steps. (A step is passing through an edge. Each edge may be passed multiple number of times).</p> <h5>Solution</h5> <p>Let M1 be a matrix where M1[i][j] equals the number of edges connecting vertex i to vertex j. Let M2 be M1 raised to the power of b (M1^b). Now for any pair u and v, the number of ways for reaching vertex v starting from u after b steps is M2[u][v].</p> <p>Practice problem: <a href="http://codeforces.com/contest/621/problem/E">621E</a> <br><br><br> #...
You are given a weighted graph containing N vertices (1 <= N <= 200) and an integer b (1 <= b , an unweighted directed graph (may contain multiple edges) containing N vertices (1 <= N <= 200

Read more »

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

 
 
 
 
47.
By Erfan.aa, 6 years ago, In English,
Codeforces Round #261 Editorial ### [problem:459A] Four vertices of a square with side length $a$ (and sides parallel to coordinate axis) are in this form: $(x_{0}, y_{0})$, $(x_{0} + a, y_{0})$, $(x_{0}, y_{0} + a)$, $(x_{0} + a, y_{0} + a)$. Two vertices are given, calculate the two others (and check the ranges). Total complexity : $O(1)$ Sample solution: [7495194](http://codeforces.com/contest/459/submission/7495194) ### [problem:459B] If all numbers are equal then answer will be $n * (n - 1) / 2$, otherwise the answer will be $cnt_{1} * cnt_{2}$, where $cnt_{1}$ is the number of our maximum elements and $cnt_{2}$ is the number of our minimum elements. Total complexity : $O(n)$ Sample solution: [7495202](http://codeforces.com/contest/459/submission/7495202) ### [problem:459C] For each student consider a sequence of $d$ elements from $1$ to $k$ that shows the bus number which is taken by this student on each day. Obviously, there are $k^d$ different sequence at all, so if $n ...
$. In the mentioned method, when you're adding a directed edge $xy$ to the graph , set $dp[y]$ value to $max(dp[y, First of all consider a graph with $n$ vertices and no edges, then just sort the given edges, ] In this problem, a directed graph is given and we have to find the length of a _longest strictly-increasing

Read more »

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

 
 
 
 
48.
By star569, 5 years ago, In English,
Variants of IOI Graph Algorithms Hi Codeforces, I'm going to IOI this year and I'm currently preparing for it. My teammates have recommended this site to me and I have registered here today. This site looks great so far :) Anyway, back to the original topic. As graph theory is an important component in IOI, I'm currently preparing hard for it. I know that direct implementations of the standard graph algorithms will not be tested in IOI, so I'm trying to think of variations and applications of some standard algorithms. I have thought of these so far for MST and Dijkstra. - MST + Find number of unique MST + Find MST that doesn't use a certain edge/certain edges + Minimum Spanning Forest + Second best spanning tree - Dijkstra + Find number of shortest paths + Find shortest path with minimum/maximum/certain number of edges for a weighted graph + Find shortest path that passes through a certain vertex/certain vertices/a certain edge/certain edges + Second best shortest path I would really appreciat...
Variants of IOI Graph Algorithms, number of edges for a weighted graph + Find shortest path that passes through a certain vertex/certain, /certain number of edges for a weighted graph + Find shortest path that passes through a certain vertex

Read more »

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

 
 
 
 
49.
By Dalisyron, history, 4 years ago, In English,
A problem about weighted graphs **Problem** : Given a weighted directed graph with both negative and positive edges, Find a path from vertex 1 to n, in which minimum subpath weight(starting from vertex 1) is maximum. I can't think of any graph algorithm that can help me solve this problem, so any suggestions are appreciated. N<=500
A problem about weighted graphs, **Problem** : Given a weighted directed graph with both negative and positive edges, Find a path, Given a weighted directed graph with both negative and positive edges, Find a path from vertex 1, I can't think of any graph algorithm that can help me solve this problem, so any suggestions

Read more »

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

 
 
 
 
50.
By Peregrine_Falcon, 2 years ago, In English,
Need help about UVA 1494 — Qin Shi Huang's National Road System [Problem Link](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4240) [My code link](https://ideone.com/IyfujT) My idea: *I made a graph providing connection to every node to all other nodes. *Distance = sqrt( (x1 &mdash; x2 )^2 + ( y1 &mdash; y2 )^2 ) *Ran MST( Minimum Spanning Tree ) & saved the summation of costs. *Made a graph from the MST. *Made a Sparse Table using the MST graph & also saved the weight of maximum weighted edge for the paths. *Then I tried to make a magical road between every possible node & searched for possible maximum ( A/B ) value, for delete a edge, I took help of the LCA for finding the maximum weighted edge between the path of currently two working nodes. ***I've been trying this problem for several days, but can't find any problem. Please help If anyone have free time. Thanks in advance. UPDATE: Got Accepted. { The Mistake was in Minimum Spanning Tree. Thank you....
*Made a Sparse Table using the MST graph & also saved the weight of maximum weighted edge, . *Made a graph from the MST. *Made a Sparse Table using the MST graph & also saved theweight

Read more »

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

 
 
 
 
51.
By Learner99, history, 23 months ago, In English,
Find number of MST in given Graph. Given an undirected weighted graph. How to find the total number of minimum spanning tree for that given graph. Number of nodes <= 10. No parallel edges. I found a similar problem here: [https://www.spoj.com/problems/MSTS/](https://www.spoj.com/problems/MSTS/) I don't want answer mod 31011 as asked in above Spoj Problem. I want the exact number of ways. (Though I don't know the solution of the Spoj problem either.) Can someone please help me in solving this question? Thanks in advance. Happy Coding :)
Find number of MST in given Graph., Given an undirected weighted graph. How to find the total number of minimum spanning tree

Read more »

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

 
 
 
 
52.
By ghost016, 9 years ago, In English,
Help in Weighted Bipartite Matching <p>Hello all,<br><br>i have learned that for converting Bipartite graph to Maxflow, i need to introduce two vertices, super-source and super-sink and each edge will be assigned a capacity of "1" from the super-source to the vertices in one partition and to the super-sink from the vertices of another partition, and then apply the maxflow algorithm, where the maxflow is the max-matching. My question however is that is this system can be applied to the <b>weighted</b> <b>bipartite graph, </b>for finding the maximum weight of the graph ?? if not then is there any other method how i can reduce the weighted bipartite graph to maxflow problem. Hope to get some reply.<br><br>Thanking You<br>Ghost016</p>
Help in Weighted Bipartite Matching, question however is that is this system can be applied to the weighted bipartitegraph, , weight of the graph ?? if not then is there any other method how i can reduce theweighted bipartite

Read more »

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

 
 
 
 
53.
By M.Mahdi, 4 years ago, In English,
Codeforces Round #360 Editorial [+ Challenges!] Hi again! If you notice typos or errors, please send a private message. ### [688A: Opponents](http://codeforces.com/contest/688/problem/A) #### Solution Let's find out for each row of the given matrix if it is completely consisting of _ones_ or not. Make another array $canWin$, and set $canWin_i$ equal to one if the $i$-th row consists at least one _zero_. Then the problem is to find the maximum subsegment of $canWin$ array, consisting only ones. It can be solved by finding for each element of $canWin$, the closest zero to it from left. The complexity of this solution is $O(nd)$, but the limits allow you to solve the problem in $O(nd^2)$ by iterating over all possible subsegments and check if each one of them is full of _ones_ or not. <spoiler summary="C++ code"> ~~~~~ // . .. ... .... ..... be name khoda ..... .... ... .. . \\ #include <bits/stdc++.h> using namespace std; inline int in() { int x; scanf("%d", &x); return x; } const int N = 202; int ...
one by one to the graph in decreasing order of their weights. The answer is weight of the first edge, . (Graph will be bipartite after adding these edges.) The answer will be weight of the next edge. (We, . The answer is weight of the first edge, which makes an odd cycle in the graph . Now show

Read more »

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

 
 
 
 
54.
By sravanbansal08081998, history, 2 weeks ago, In English,
Doubt in Cycle Basis of graph Hello Everyone! https://codeforces.com/contest/845/problem/G The problem says that we are given a weighted connected graph in which path length is defined as xor of all weights on the path. We are given two vertices and need to find shortest path length. In the solution, we are calculating cycle basis of graph. For this we first make a spanning tree of the graph. Let's assume we have an empty set S. Then we take all the non-spanning edges of the graph one by one and find the cycle which this edge is making with only the spanning edges and include this cycle in our set S . The claim is that every set of cycles in the graph is a subset of this set S (We can also reduce S to its basis). I am unable to get this claim.[It is wrong claim as stated in the comments.] Can somebody give me a proof of this of how is it including every cycle that exists in the graph Can we also represent every closed walk in the graph using the subset of set S? Thank You
Doubt in Cycle Basis of graph, are given a weighted connected graph in which path length is defined as xor of all weights on the path, The problem says that we are given a weighted connected graph in which path length is defined

Read more »

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

 
 
 
 
55.
By pratikmoona, 9 years ago, In English,
How to find the Vertex Cover of a Vertex-Weighted bipartite graph? <p>I recently learnt about Konig's theorem which states that finding the vertex cover in a bipartite graph is equivalent to finding the maximal matching.</p><div><a>Konig's Theorem</a>&nbsp;:&nbsp;<a>http://www.google.co.in/search?q=konig's+theorem</a></div><div><a><br /></a></div><div>It's simple to edit the hungarian algorithm or any other matching algorithm if it is an unweighted graph. But how do I do the same when it is a &quot;Vertex-Weighted&quot; graph?</div>
How to find the Vertex Cover of a Vertex-Weighted bipartite graph?, if it is an unweighted graph. But how do I do the same when it is a "Vertex- Weighted" graph?, in a bipartite graph is equivalent to finding the maximal matching., . But how do I do the same when it is a "Vertex-Weighted" graph?

Read more »

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

 
 
 
 
56.
By ben_dover, history, 5 months ago, In English,
Storing Adjacency List with Edge Weight For storing an adjacency list with edge weights, the (apparently) standard way is to store a vector of vector of pairs (vertex end, weight). I realized recently that it is possible to store the adjacency list as for an unweighted graph and store the edge weights separately (in a map or unordered map). [user:noedne,2020-02-23] pointed out that storing the weight in the adjacency list is more organized. In theory by storing the edge weights separately we can reuse algorithms for unweighted graphs that take the unweighted adjacency list. Which do you think is better?
Storing Adjacency List with Edge Weight, of vector of pairs (vertex end, weight). I realized recently that it is possible to store

Read more »

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

 
 
 
 
57.
By AakashHanda, history, 17 months ago, In English,
Editorial for Shortest Path Constrained from CodeNation Hiring Test I decided to write this blog, as a lot of people were requesting for the editorial of `Shortest Path Constrained` problem from CodeNation Hiring Test, held on 26th January, 2019 Problem ================== ### Statement There is a weighted undirected graph with $N$ nodes and $M$ edges. You are also given $X$ different sets of nodes &mdash; $S_1$ to $S_x$. You have to give the shortest possible distance between a start node &mdash; $a$ and a destination node &mdash; $b$, along a path following the following rule: For all $i<j$, before visiting a node in $S_j$, you must visit all the nodes in $S_i$. The distance is defined as sum of weights of edges along the path traversed. Note :- 1. The path must contain all the nodes in union of $S_i$ for all $1 \leq i \leq X$ 2. $S_i \cap S_j = \phi$ for all $1 \leq i$, $j \leq X$ and $i \neq j$. 3. The path may go through any node, including $a$ and $b$, more than once. The constraint is that it must end at $b$ ### Constraints -...
================== ### Statement There is a weighted undirected graph with $N$ nodes and $M$ edges. You, Problem ================== ### Statement There is a weighted undirected graph with $N$ nodes

Read more »

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

 
 
 
 
58.
By Hd7, history, 10 months ago, In English,
Find all vertices in negative cycle or reachable from it in Directed Graph. I have solved [UVa-10499 Traffic](https://uva.onlinejudge.org/external/104/10449.pdf). The problem ask to find out all shortest path from vertex 1, if vertices are affected by negative cycle, it means the shortest path become undefined and we print `?`. I solved it with Bellman-Ford algorithm and it passed but I feel my approach is incorrect and I found a counter-example. My approach: In the nth-relaxation, if vertices are shorten, I assign shortest path to them equal $-\infty$. ``` for(auto e:edges){ int u, v, w; tie(u, v, w) = e; if (d[u]+w < d[v]) { d[v] = -INF; } } ``` My fully solution: https://ideone.com/TfuoGz For example, I have this graph and edges are stored in this order, the weight of edges represent the edges. [![bb3122de4c63ab3df272.md.jpg](https://www.imageupload.net/upload-image/2019/09/29/bb3122de4c63ab3df272.md.jpg)](https://www.imageupload.net/image/qBbd) and in the n-th relaxation, I am just able to assign $-\inf...
Find all vertices in negative cycle or reachable from it in Directed Graph., this graph and edges are stored in this order, the weight of edges represent the edges

Read more »

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

 
 
 
 
59.
By Um_nik, 21 month(s) ago, In English,
How to read problem statements But [user:Um_nik,2018-10-26], we all know how to read, we have our whooping 2 month of experience! Oh, my sweet summer child, my experiments show that many people with kinda cool achievements like medals on ROI don't know how to read statements. But don't worry, I'll teach you. Well, probably you won't understand anything, because you didn't try to understand anything in your life, you expect all hard work to be done for you by someone else. Let's start! Basic rules ================== - The result of reading the statement is usually pure math model. If story helps to build correct understanding, you can keep it, but still try to discard as many unnecessary details as possible. - Imagine you want to tell the problem to someone else. What parts you want to tell? (According to my PM, this rule won't help you). - Shorter = better. - Simpler = better. - Limitations are part of problem statement. Especially small limitations, because for small data you can try all the possib...
be spanning for some graph? For example, let's build a graph in which weight of an edge is a distance *on tree

Read more »

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

 
 
 
 
60.
By atomicemc2, history, 4 years ago, In English,
Given a directed weighted graph with self loops ,find the list of nodes that are exactly k dist from a given node x? Each edge in the graph has weight of 1,The graph may have cycles ,if a node has self loop it can be any distance from itself from 0 to infinity , depending on the no. of time we take the self loop. We ll be asked multiple queries on a given graph of the form (distance , source) and the o/p is the list of nodes that are exactly at the given distance starting from the source vertex. Constraints 1<=Nodes<=500 1<queries<=500 1<=distance<=10^9 I have a feeling ,there would be many repeated computations as the no. of nodes are small,but i am not able to figure out how do i reduce the problem in smaller problems. What is the efficient way to do this? I have solved the problem using bfs, but the constraint on distance is in order of 10^9 ,hence bfs is slow. I have also tried using matrix exponentiation but its too slow ,for the given constraints. The problem has a time limit of 1 sec.
Given a directed weighted graph with self loops ,find the list of nodes that are exactly k dist, Each edge in the graph has weight of 1,The graph may have cycles ,if a node has self loop it can, We ll be asked multiple queries on a given graph of the form (distance , source) and the o/p

Read more »

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

 
 
 
 
61.
By awang01999, history, 9 months ago, In English,
XOR minimum graph path Given a graph G = (V, E) with 1 <= N <= 100000 vertices and 1 <= M <= 100000 edges, how can I compute the minimum weighted path from vertex 1 to vertex N, where "weight" is defined as the exclusive bitwise XOR of all the edge weights? For example if there is a graph with four vertices (call them 1, 2, 3) and 2 edges: one edge from 1 to 2 with weight 26, another edge from 2 to 3 with weight 18, then there's only one path from 1 to 3, so answer is 26 XOR 18 = 8. I don't think most SSSP algorithms work here because XOR does not satisfy the triangle inequality. I was wondering whether anyone knows how to approach this problem.
XOR minimum graph path, compute the minimum weighted path from vertex 1 to vertex N, where "weight" is defined as the exclusive, For example if there is a graph with four vertices (call them 1, 2, 3) and 2 edges: one edge from 1

Read more »

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

 
 
 
 
62.
By skavurskaa, history, 4 years ago, In English,
Min weight perfect matching on complete bipartite graph? Problem statement: Given a complete bipartite graph $K_{N,N}$ with weights $W_{uv}$ assigned to each edge $uv$, find a perfect matching with minimal sum of edge weights among all perfect matchings. Is there any easy to code polynomial algorithm for this problem? I know an easy way to solve it using subset dp in $O(N^{2} 2^N)$, and i also think that it is possible to modify the Hungarian Algorithm to solve this problem. But is there any easier algorithm considering it is always a complete bipartite graph? I don't care too much about the time complexity as long as it is polynomial. Thanks in advance!
Min weight perfect matching on complete bipartite graph?, bipartite graph? I don't care too much about the time complexity as long as it is polynomial., Problem statement: Given a complete bipartite graph $K_{N,N}$ with weights $W_{uv}$ assigned

Read more »

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

 
 
 
 
63.
By gamegame, history, 2 years ago, In English,
Need Help on Bipartite Matching problem with 2 types of weight I have seen a problem about bipartite matching on a special weighted graph and i would like to know the solution. The graph is similar to [problem:875F] where nodes in one sides have at most 2 neighbours and the weight of these two edges are the same. However, each edge has 2 weights Ai and Bi, and the total weight is (sum of A)*(sum of B). The task is to find a maximum matching with highest total weight. N<=10000 and A,B<=30 where N is the number of nodes. Could someone give hints/solutions about this problem? Million thanks!
Need Help on Bipartite Matching problem with 2 types of weight, I have seen a problem about bipartite matching on a special weighted graph and i would like to know

Read more »

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

 
 
 
 
64.
By .o., 6 years ago, In English,
An unusual and great task with shortest paths Hi, everyone! 2014 World Cup Brasil has started, and I was looking for interesting problems. I found a nice IOI-style problem from [Japanese Olympiad In Informatics 2014](http://www.ioi-jp.org/camp/2014/2014-sp-tasks/index.html) (this is not the online contest!). If you know how to read Japanese, you can find the problem "Kanji Shiritori" from [the statement file](http://www.ioi-jp.org/camp/2014/2014-sp-tasks/2014-sp-d4.pdf). Here is the translation of the problem, powered by Google Translation and me :D --- You are given a weighted directed graph. The graph consists of $N$ ($2 \le N \le 300$) vertices and $M$ ($1 \le M \le N \times (N-1)$) edges, and there are no loops or multiple edges in this graph. The vertices are numbered by integers from $0$ to $N-1$, and the edges are numbered by integers from $0$ to $M-1$. The $i$-th edge goes from vertex $A_{i}$ to vertex $B_{i}$, and the weight of this edge is $C_{i}$. ($0 \le A_{i} < N, 0 \le B_{i} < N, A_{i} \neq B_{i}, 1 \le C_{...
Translation and me :D --- You are given a weighted directed graph. The graph consists of $N$ ($2 \le, Both Anna and Bruno are given the whole graph and the description of the queries. (Of course, those, You are given a weighted directed graph. The graph consists of $N$ ($2 \le N \le 300$) vertices

Read more »

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

 
 
 
 
65.
By prince_of_crows, history, 2 years ago, In English,
I need help to prove a classical graph problem about strongly connected components. I have come to read [this](https://stackoverflow.com/questions/14305236/minimal-addition-to-strongly-connected-graph) stackoverflow post. It basically asks this-`I have a set of nodes and set of directed edges between them. The edges have no weight. How can I found minimal number of edges which has to be added to make the graph strongly connected?` [This](https://stackoverflow.com/a/14318315) answer gives a solution to this problem It's a really classical graph problem. 1. Run algorithm like Tarjan-SCC algorithm to find all SCCs. Consider each SCC as a new vertice, link a edge between these new vertices according to the origin graph, we can get a new graph. Obviously, the new graph is a Directed Acyclic Graph(DAG). 2. In the DAG, find all vertices whose in-degree is 0, we define them {X}; find all vertices whose out-degree is 0, we define them {Y}. 3. If DAG has only one vertice, the answer is 0; otherwise, the answer is max(|X|, |Y|). I am not been able to pr...
I need help to prove a classical graph problem about strongly connected components., -to-strongly-connected-graph) stackoverflow post. It basically asks this-`I have a set of nodes and set

Read more »

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

 
 
 
 
66.
By darkshadows, 4 years ago, In English,
[GYM] 2016 CodeCraft IIIT Hyderabad Tutorial ### [problem:100889A] Given an array of integers, find a permutation of the array to maximize the sum $\sum_{i=1}^{\frac{N}{2}} A_{n-i+1} - A_i$. If we observe the formula closely we see that we have to calculate $\sum_{i=1}^{\frac{N}{2}} A_{n-i+1} - \sum_{i=1}^{\frac{N}{2}} A_i = \sum_{i=\frac{N}{2} + 1}^{N} A_{i} - \sum_{i=1}^{\frac{N}{2}} A_i$. If the array is of odd length, we can simply skip the middle element. This can be maximized by putting the large numbers in the right half, and the small numbers in the left half. One good way to do this is to simply sort the array in ascending order. Complexity: $O(N \textrm{log} N)$. Code: http://ideone.com/nJddvt ### [problem:100889B] Given an array $A$, make it palindromic using minimum merging operations. In one merging operation two adjacent elements can be replaced by their sum. To make an array a palindromic we can simply apply merging operations $n-1$ times where $n$ is the size of array. In that case,si...
**: Given an undirected weighted graph of $n$ nodes, $m$ edges and a non-negative integer $k$, you

Read more »

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

 
 
 
 
67.
By YouKn0wWho, 7 months ago, In English,
[Editorial]Contest Based on SUST Intra University Programming Contest 2019 [A. Perfect Points](https://toph.co/p/perfect-points) Author: [user:YouKn0wWho,2019-12-20] <spoiler summary="Tutorial"> Here $$y=m(c+1)+c: \; c \geq 1 $$ $$ \rightarrow y \mod (c+1) = c: \; c \geq 1 $$ $$ \rightarrow y \mod c = c-1: \; c \geq 2 $$ $$ \rightarrow (y+1) \mod c = 0: \; c \geq 2 $$ Note that $m \geq 1$, so $(y+1) > c$. So we can say that $ (y+1) \; is \; composite: \; y \geq 1$ So $K^{th}$ value of $y$ is ($K^{th}$ composite number $-1$ ). How can we find it given that $K \leq 10^9$? <spoiler summary="Hint"> - [Prime Counting Function](https://codeforces.com/blog/entry/57826?fbclid=IwAR084Ea_mN7LFqr-LLooQrtJQ8jiN5g7W3PvA1_JnHuVOsHrj0DH4UIKqTo#comment-414818) - Binary Search </spoiler> </spoiler> <spoiler summary="Solution"> ~~~~~ #include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define pll pair<ll,ll> #define eb emplace_back #define ll long long #define nl '\n' #define deb(x) cerr<<#x" = "<<x<<nl #define i...
So we need to find the sum of the cost of all possible spanning trees in a completegraph where

Read more »

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

 
 
 
 
68.
By BanazadehAria, history, 13 months ago, In English,
Best way get the shortest path in an undirected graph with dp. Hi, What is the best way to get the shortest path from vertex a to b in a weighted undirected graph? I have done this but can we do better than O(|V|)? ~~~~~ map<int,list<pair<int,int> > > adjList; void addEdge(int u,int v,int weight){ adjList[u].pb(mp(v,weight)); adjList[v].pb(mp(u,weight)); } void FindShortestPath(int u,int v){ int dp[n]; dp[u]=0; map<int,bool> visited; queue<int> q;q.push(u);visited[u]=true; while(!q.empty()){ int now = q.front();q.pop(); for(auto neight : adjList[now]){ dp[neight.first] = min(dp[neight.first],dp[now]+neight.second); if(!visited[neight.first]){ q.push(neight.first);visited[neight.first]=true; } } }cout << dp[v]; } ~~~~~
Best way get the shortest path in an undirected graph with dp., Hi, What is the best way to get the shortest path from vertex a to b in a weighted undirected graph, void addEdge(int u,int v,int weight){ adjList[u].pb(mp(v,weight)); adjList[v].pb(mp(u

Read more »

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

 
 
 
 
69.
By mohammedehab2002, history, 3 years ago, In English,
Codeforces round #396 editorial [problem:766A] If the strings are the same, Any subsequence of $a$ is indeed a subsequence of $b$ so the answer is "-1", Otherwise the longer string can't be a subsequence of the other (If they are equal in length and aren't the same, No one can be a subsequence of the other) so the answer is maximum of their lengths. Code : http://pastebin.com/aJbeTTjw Time complexity : $O(|a|+|b|)$. Problem author : me. Solution author : me. Testers : me and [user:mahmoudbadawy,2017-02-07]. [problem:766B] #### First solution :- Let $x$, $y$ and $z$ be the lengths of 3 line segments such that $x \le y \le z$, If they can't form a non-degenerate triangle, Line segments of lengths $x-1$, $y$ and $z$ or $x$, $y$ and $z+1$ can't form a non-degenerate triangle, So we don't need to try all the combinations, If we try $y$ as the middle one, We need to try the maximum $x$ that is less than or equal to $y$ and the minimum $z$ that is greater than or equal to $y$, The easiest way to do so...
a graph containing the words, For every relation in the input add a new edge with theweight of $0, Let's build a graph containing the words, For every relation in the input add a new edge

Read more »

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

 
 
 
 
70.
By STommydx, history, 2 years ago, In English,
Codeforces Round #457 (Div. 2) Editorial I would like to take this opportunity to express my deepest apology to all of you who take your own precious time to participate in this unrated round. Also, apologies to [user:gritukan,2018-01-19] who really helped a lot in preparing the round and [user:MikeMirzayanov,2018-01-19] who helped to host the round, I did not do a good job in managing the round. As the main author of this round, I'm undoubtedly responsible for the mistake that not writing a brute force solution to test the correctness of the intended solution. It is my responsibility to make sure everything is right before the round starts. I am really sorry that the round must be unrated to ensure fairness to all contestants. I hope all of you can learn something from the contest. Do not claim a greedy solution absolutely correct (like me :C) unless you have proved it. On the bright side, I'm really glad that some of you found problem D and E interesting as said in some comments in the announcement blog post. I admit tha...
Recall that a path graph is also a tree! If we join $(i, i+1)$ for all $1 \leq i < n$, the shortest

Read more »

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

 
 
 
 
71.
By _smhx, history, 9 months ago, In English,
Matchings and Cycle Decompositions First blog post! I want to write about a cool problem that appeared on the UKIEPC 2019 contest. Here is the statement: You are a realtor in charge of buying and selling homes for $n \leq 100$ families. In total, there are $m \leq n(n-1)$ offers, with the $i$'th offer being family $a_i$ would like to buy family $b_i$'s home for $c_i$ dollars ($a_i \neq b_i$). In addition, the pair $(a_i, b_i)$ will occur at most once in the input. The families agree that they will all purchase simultaneously, or stay in their original home. You earn a fixed commission of 5% on each purchase. How can you select a subset of purchases such that nobody ends up homeless and you maximise your earnings? This problem is equivalent to the following: Given a weighted directed graph, decompose the graph into vertex disjoint cycles with maximum edge sum. Specifically, the vertices are the $n$ families, and the edges are from $a_i$ to $b_i$ with weight $c_i$. Your earnings are then just 5% of this sum. ...
This problem is equivalent to the following: Given a weighted directed graph, decompose thegraph

Read more »

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

 
 
 
 
72.
By GodSpeed98, history, 20 months ago, In English,
Need help in an interesting Graph Problem. I am stuck on this problem. [https://www.codechef.com/problems/IOPC16K](https://www.codechef.com/problems/IOPC16K) Problem Statement: Find out what will be the new shortest path if one of the edge on the original shortest path is removed.Find for all of the edges in shortest path path(Given Unique original shortest path). Constraints: no. of edges <= 1e5 no. of nodes <= 1e5 weights of edges <= 1e9 I Looked at some of the AC solutions but could not get the Idea. So if somebody can share the Idea to solve the problem it would be very Helpful! (I think its on some Algorithmic Paper).
Need help in an interesting Graph Problem.

Read more »

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

 
 
 
 
73.
By qwerty29, history, 5 months ago, In English,
Help! Shortest Path Problem on CSES [Shortest Routes 1 on cses](https://cses.fi/problemset/task/1671/http://). Question: Basically print all the distances from node 1 to all other nodes. We can assume that such a path to all other nodes exists. The path connecting the nodes is directed and weighted. My Approach: 1) do dfs and keep updating the node's distance (initialized to LLONG_MAX at the start of search). 2) if the distance to reach a node is greater than the existing distance (previously calculated) then we don't continue the search from that node. 3) sort the edges for each node so that we choose the smallest edge every time. My Doubt: 1) I am getting TLE for some cases. I wanted to know whether this approach is slow in general or there is some corner case that I am missing, which is getting my code to run in circles. 2) (according to me this should run My Code: ~~~~~ #include <bits/stdc++.h> #define all(v) (v).begin(),(v).end() #define f first #define s second us...
other nodes exists. The path connecting the nodes is directed and weighted. My Approach: 1

Read more »

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

 
 
 
 
74.
By hackerbaba, history, 3 months ago, In English,
Implementation of some ds for graphs Hello again. I am newbie learning graphs, currently doing it in c++ and there are multiple opinions everywhere as to what should be used to implement the (min heap) structure(currently looking into Dijkstra's algo). 1. Should it be PRIORITY QUEUE or MULTISET or SET.? 2. How should the weighted graph be represented in the adjacency list? Currently I started doing a ```vector<pair<int, int> >``` with the node as the first element and the weight as the second. Is it right or something else has to be added? Any other good practices for graphs are appreciated.
into Dijkstra's algo). 1. Should it be PRIORITY QUEUE or MULTISET or SET.? 2. How should theweighted

Read more »

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

 
 
 
 
75.
By Gerald, 9 years ago, translation, In English,
Codeforces Round #101 (Div. 2) Разбор Задач. <p</p><div style="text-align: center;"><span style="color: rgb(34,34,34);font-family: arial , sans-serif;font-size: 13.0px;text-align: left;background-color: rgb(255,255,255);">[[problem:141A]]</span> <br /></div><div style="text-align: justify;"><span style="color: rgb(34,34,34);font-family: Arial , sans-serif;font-size: 13.0px;">It was enough for solving this problem to calculate for each letter: $a_c$ - amount of occurrences of letter $c$ in first and second strings in input, $b_c$ - amount of occurrences of letter $c$ in third string in input. If $\forall c : a_c = b_c$ the answer is &quot;YES&quot; else &quot;NO&quot;.</span> <br /></div><div style="text-align: justify;"><br /></div><div style="text-align: center;"><span style="color: rgb(34,34,34);font-family: arial , sans-serif;font-size: 13.0px;text-align: left;background-color: rgb(255,255,255);">[[problem:141B]]</span>  <br /></div><div style="text-align: justify;"><span style="color: rgb(34,34,34);font-family: Arial , sans-s...
;">Let's generate the weighted directed

Read more »

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

 
 
 
 
76.
By andreyv, 8 years ago, translation, In English,
Codeforces Round #142 Problem Analysis ### [Div. 2 A — Dragons](/contest/230/problem/A) Observe that if Kirito fights a dragon whose strength is less than Kirito's strength, then Kirito does not lose anything — in fact, he even gains a nonnegative strength increase. Taking note of this, let's for each step choose some dragon whose strength is less than Kirito's current strength, and fight it. After performing some amount of these steps we'll eventually end up in one of these two situations: either all dragons are slain (then the answer is "YES"), or only dragons whose strength is not less than Kirito's strength remain (then the answer is "NO"). On each step we can choose a suitable dragon to fight either by searching through all dragons or by sorting the dragons by strength in non-descending order in advance. The complexity of the solution is $O(n^2)$ or $O(n\log n)$. Sample solution: http://pastie.org/4897164 [cut]   ### [Div. 2 B — T-primes](/contest/230/problem/B) It can be shown that only squares of prime nu...
of the initial complete graph that pass through the same vertices, assign a weight: for each pair of edges

Read more »

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

 
 
 
 
77.
By prodipdatta7, 3 months ago, In English,
Need help in graph theory problem!!! Given a connected undirected weighted graph of **n (<= 15)** nodes and **m(<= 1000)** edges.<br> Every edge is assigned a positive integer which is the length of the edge.<br> In this graph i need to make the degree of every node even by adding some fake edges between nodes. <br> The cost of adding a fake edge is the length shortest path between this nodes in the initial graph. <br> It is obvious that i can use floyd warshall algorithm to compute the shotest path between every pair of nodes. < br> How can I add fake edges with minimum cost ? <br> Actually this is needed as a sub-problem of another problem i'm trying to solve but can't afford an efficient way.<br> link: [1086 &mdash; Jogging Trails](http://lightoj.com/volume_showproblem.php?problem=1086) Your any kind of help will be cordially accepted. <br> Thanks.
Need help in graph theory problem!!!, Given a connected undirected weighted graph of **n (<= 15)** nodes and **m(<= 1000)** edges.

Read more »

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

 
 
 
 
78.
By cjchirag7, 5 weeks ago, In English,
Editorial of Virtual Farewell IIT (ISM) Dhanbad Here, we present you the Editorial for the [Virtual Farewell IIT (ISM)](https://codeforces.com/contestInvitation/a52c365430f69a8f04d28eafb2cad804d392072c). I hope you enjoyed the contest !! [A. Farewell or Best Wishes](https://codeforces.com/gym/102625/problem/A) ----------------- **Author :** [user:chefpr7,2020-06-21] <spoiler summary="Tutorial"> Firstly, if the office is located anywhere in the path of the auto, then their plan will always fail, i.e if $X=1$ or $Y=M$ then best wishes are on the way. Otherwise, the auto can meet the agents only in the cells ($1$, $Y$) or ($X$, $M$). The time needed to reach these cells can be obtained in $O$($1$). Agent A initially headed North reaches the cell ($1$, $Y$) at time $t$ = $Y$-$1$ and after that it comes back at intervals of $2*(N-1)$. So all we need to do is check whether the time taken by the auto to reach any of the two cells is a term in the arithmetic progression of time taken by an agent to reach that cell. If we ch...
edge may not be in one of the connected components of the graph constructed so far. Thus, that offices are nodes, passages are edges, and security levels are weights of the edges. Also, ourgraph

Read more »

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

 
 
 
 
79.
By MostafaAbdullah, history, 4 years ago, In English,
Graph problems debugging tools Hello **Codeforces** community, I'm presenting to you two tools tool that I have created that may help you debug graph problems. The first one is a **graph drawing tool**, where you can draw the graph and then generate its test case, this may be helpful when you need to write your own test cases for your graph problems, and need to easily visualize and edit them. [Link to graph drawing tool](http://mostafa-abdullah.github.io/graph/) The second one is a **random test case generator**, where you can generate huge test cases according to certain conditions (like weighted vs unweighted, directed vs undirected..etc). [Link to random case tool](http://mostafa-abdullah.github.io/graph/random-case.html) Feedback is appreciated. Thank you.
Graph problems debugging tools, according to certain conditions (like weighted vs unweighted, directed vs undirected..etc)., that may help you debug graph problems. The first one is a **graph drawing tool**, where you can draw

Read more »

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

 
 
 
 
80.
By kxx_monica, history, 2 months ago, In English,
find the shortest distance between the source node and destination node in an undirected weighted graph with obstacles The obstacle nodes can be any node between 1 to n( max vertices). If no path is possible then -1 otherwise the length between the source and destination.
find the shortest distance between the source node and destination node in an undirectedweighted

Read more »

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