Farhan wrote: > Guys, > > I was just trying to solve the problem "Mountain Village" in acm > problemset site. I figured out a way to solve it but it turned out to > be extremely inefficient. It exceeded the time limit. Can anyone give > me an idea about how to solve it with better technique and better > timing.
You didn't say what the time limit was, but this seems fairly good: Try using each square as a "source" square (O(N^2)) of the village. Expand the village by going to the lowest neighbor of the village that is not lower than the source. Update the village-neighbors (O(log k)). Give up and go to the next "source" square when - - The village has grown to size k. (O(k)) or - The village has as much elevation change as the best "source" found so far or - A neighbor square is at the same elevation as "source" and has previously been used as "source". - There is no neighbor as high as the source. Total cost for a single k value is O(N*N*k*log k), and extra working storage is O(k). Some heuristics when only looking for a few k values: - Use "source-quality" at one k to order your "try each square as source" for another value of k. Most helpful when k/N/N is small. - Sort the elevations into Elev[N*N]. First try source squares at elevation E[i], where E[i+k]-E[i] is minimized. Most helpful when k/N/N is large. Not helpful when log(N) is bigger than k log(k). If you use kn*N*N extra memory, where kn is the number of k values you need to solve for, you can solve all of your problems as a side-effect of solving your biggest k. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
