Fixee
Reputation
5,873
Top tag
Next privilege 10,000 Rep.
Access moderator tools
6 22 44
Impact
~260k people reached

# 491 Actions

 May1 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? May1 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$. May1 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$? May1 answered Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?) May1 revised Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?) Clarifications May1 suggested approved edit on Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?) May1 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. Apr30 revised Decryption Problem added 2 characters in body Apr30 answered probability of at least one person having a gem of type $n$, etc. Apr28 answered Simple or maybe not so simple probabilistic question Apr28 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/… Apr26 revised Calculating the highest possible damage achievable using 6 items from a pool of ~25 added 130 characters in body Apr26 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! Apr26 revised Calculating the highest possible damage achievable using 6 items from a pool of ~25 Allow duplicate combos in the code example Apr26 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. Apr26 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. Apr26 revised Calculating the highest possible damage achievable using 6 items from a pool of ~25 add some code Apr26 answered Calculating the highest possible damage achievable using 6 items from a pool of ~25 Apr26 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.) Apr26 asked Computing the integral of $e^{-x^2}$ over the entire line