Fixee
Reputation
6,328
Top tag
Next privilege 10,000 Rep.
Access moderator tools
 May 2 answered Modulo arithmetic with big numbers? May 1 comment Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?) @Amir: I highly doubt that this level of detail was intended by the instructor who assigned this problem. Even in the case that $G$ is an adjacency list and $F$ is an unsort edge list, you can still get within the time bounds: simply convert the adjacency list to an adjacency matrix using $O(|V|+|E|)$ time (but $O(|V|^2)$ space!). Then your lookups are $O(1)$. 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