I googled "XYZZY" and found a link to a site: http://www.algorithmist.com. This site is great, it is an ACM problem wiki like ours, but instead of code solutions, it describes how to do them algorithmically. And what do you know, it has an article on XYZZY. http://www.algorithmist.com/index.php/UVa_10557 So we were on the right track. It says use a varient of floyd warshall, but it looks more like Dijkstra's because there is a single source. Luckily once again, this is precisely what we are studying in algorithms class right now, so I can ask Seigel about it tomorrow in class. hooray! -Alex
- There's a problem with this solution
- Assume you have only one path from source to destination with a net change in energy of greater than -100. But then assume that the first room you enter on this path has -101 is it's energy, but the next room has +102. The shortest path (ie, path with highest energy change) would be found to be this path, but in fact you'd die right off the bat. So it's impossible.
- Now assume the same graph, except one other independent path is changed so that it's net delta E is above -100, but below that of the previously described path. Also, there are no points along this path where you'd end up below 0. This path would not be discovered by Floyd-Warshall, but is the only viable path.
- I think this is the case (along with positive cycles) where they're supposed to trip you up. I still think it's DFS with Dynamic Programming.
- Hjfreyer 10:12, 28 March 2007 (EDT)
Say any given path will have a change-in-energy-so-far that stays within the range [r1,r2]. So the energy change never goes below r1, nor above r2. What you want to do is find the path from S to D with the greatest r1. If that path has r1 greater than -100, it's winnable. Now just to figure it out algorithmically. Hjfreyer 10:13, 28 March 2007 (EDT)