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

Полный текст и комментарии »

Codeforces Round #119 — Editorial ### Problem [189A --- Cut Ribbon](http://www.codeforces.com/problemset/problem/189/A) The problem is to maximize _x+y+z_ subject to _ax+by+cz=n_. Constraints are low, so simply iterate over two variables (say _x_ and _y_) and find the third variable (if any) from the second equation. Find the maximum over all feasible solutions. Other approaches: Use dynamic programming with each state being the remainder of ribbon. Select the next piece to be _a_, _b_ or _c_. ### Problem [189B --- Counting Rhombi](http://www.codeforces.com/problemset/problem/189/B) Observe that lots of rhombi have the same shape, but are in different locations. What uniquely determines the shape of a rhombus? Its width and its height. Is it possible to build a rhombus with every width and every height such that the vertices of the rhombus are in integer points? [cut] No, it is possible only if the width and the height are both even. How many places we can put a rhombus of width _w0_ and height ...

Полный текст и комментарии »

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

Полный текст и комментарии »

-O2 can optimize floyd! Hi!<br> I was trying to solve probem E from the last contest ([problem:542E]) and I needed to solve all pairs shortest path problem. With $n$ BFSs, It would be done in $O(nm)$ but I'm too lazy to implement it! I saw 3 second time limit, so i used floyd-warshal and Bang... It just accepted in 1.7 second! [submission:11022079] <br> I tested my code on my machine without `-O2` with a simple 1000 vertex connected graph and it takes 15 seconds until my program answers, and with `-O2` it just takes 1.5 second! <br> I wrote another non-optimizable program with $n^3$ running time (You can see it [here](http://paste.ubuntu.com/11011189/)) and with $n$ = 1000 it runs in 12 seconds on my machine. <br> So obviously `-O2` can optimize floyd! I wonder how it's possible?!<br> <br> **P.S.** As [user:I_love_Tanya_Romanova,2015-05-07] said, my second example is nonsense! :D <br>Anyway, could anyone explain how my solution is optimized?

Полный текст и комментарии »