Reputation
5,958
Top tag
Next privilege 10,000 Rep.
Access moderator tools
Badges
6 22 44
Impact
~267k people reached

May
1
comment Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?)
@Amir: This depends now on how the problem is given to you: if $F$ is given as a set of markings on $E$, then you're already done! If $F$ is given as a list of pointers to $E$, then you can do lookups in $O(1)$. If $F$ is given as a separate list of edges, then you have to search through $E$ for a match; how long this takes depends on the data structures for $E$ and $F$. If $G$ is given as an adjacency matrix, you can look up edges in $O(1)$. If given as an adjacency list, then it takes longer and we run into problems. Did your homework specify any of these details?
May
1
comment Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?)
@Amir: Also, there is no need to remove any edges from $E$. First, mark each edge that is in $F$. Now run Kosaraju's algorithm and each time an edge is found in an SCC, check to see if it has the $F$ label. If it does, you know some cycle uses an edge from $F$.
May
1
comment Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?)
@Amir: Kosaraju's algorithm, cited in my answer above, gives a way label each edge in $E$ with a component number telling you what SCC each edge lives in. This immediately gives you the number of components (and more). Now, if any edge of $F$ belongs in an SCC, then you know that there exists a cycle with at least one edge from $F$. Wasn't that your question? Or do you need to find a cycle composed entirely from edges in $F$?
May
1
answered Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?)
May
1
revised Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?)
Clarifications
May
1
suggested approved edit on Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?)
May
1
comment Decryption Problem
@Brandon: Hah! Ok, you got me. Cryptographers create, cryptanalysts break, and cryptologists do both. The main conference in our field is called Advances in Cryptology, but I rarely use that term it forums like this one because it's not known to lay audiences. But yeah, cryptanalysts was the proper word.
Apr
30
revised Decryption Problem
added 2 characters in body
Apr
30
answered probability of at least one person having a gem of type $n$, etc.
Apr
28
answered Simple or maybe not so simple probabilistic question
Apr
28
comment Calculating the highest possible damage achievable using 6 items from a pool of ~25
@Shawn: Yuval used the standard method to count combinations with repetitions. See en.wikipedia.org/wiki/…
Apr
26
revised Calculating the highest possible damage achievable using 6 items from a pool of ~25
added 130 characters in body
Apr
26
comment Calculating the highest possible damage achievable using 6 items from a pool of ~25
@Shawn: Just test the cost in the inner loop and include the item-set only if the cost is under the budget. By the way, the folks around here are very helpful and friendly, but to be honest I think your question would find a better home on stackoverflow or programmers.SE. Cheers!
Apr
26
revised Calculating the highest possible damage achievable using 6 items from a pool of ~25
Allow duplicate combos in the code example
Apr
26
comment Calculating the highest possible damage achievable using 6 items from a pool of ~25
@Shawn: if you want to allow a,a,a,a,a,a then start each for loop at the value before it (rather than the value + 1). I edited my code above to do this. It increases the number of total loops to 593,775 from 177,100.
Apr
26
comment Calculating the highest possible damage achievable using 6 items from a pool of ~25
I was assuming that you have a set of helm, shoulder, bracer, glove, chest, and leg items and that you couldn't equip a given item other than in its proper slot. If you want to avoid repetitions, use the code above which will give you the 177,100 unique sets of 6 items taken from 25.
Apr
26
revised Calculating the highest possible damage achievable using 6 items from a pool of ~25
add some code
Apr
26
answered Calculating the highest possible damage achievable using 6 items from a pool of ~25
Apr
26
comment Computing the integral of $e^{-x^2}$ over the entire line
@Arturo & Ross: both links give the same proof... which is indeed quite slick. Cheers. (I would delete my question now, but it already has an answer, so this is disallowed.)
Apr
26
asked Computing the integral of $e^{-x^2}$ over the entire line