On Tuesday, April 26, 2016 at 3:06:30 AM UTC+8, Aakash Chaudhary wrote: > Call the function like so: > > int inputArray[18] = {3,3,4,4,4,2, 3,1,3,2,1,4, 7,3,1,6,4,1}; > int totalWater = GetWaterLevel(3, 6, inputArray);
Your program does not work for the input below. int inputArray[16] = {2,2,2,2, 2,1,1,2, 2,1,1,2, 2,2,2,2}; int totalWater = GetWaterLevel(4, 4, inputArray); It recurses indefinitely, ending up with a SIGSEGV. (I know why it crashes, but it's better for you to find out yourself.) On Wednesday, April 27, 2016 at 6:31:32 AM UTC+8, john.smith wrote: > Dijkstra's shortest path algorithm is the way to go, with a fringe of cells > kept in a priority queue. WC Leung's answer is exactly right. Was my complexity analysis right? I still have doubts. > > For an exam question in about 1980, even when you have recently attended an > algorithms course, I still think it quite hard. If the exam asks you to write the code on paper with a time limit, then I think it's merely to make you humble. Nowadays we have C++ and std::priority_queue, so the question is already a bit easier. At 1980s you need to code the data structures yourself. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/4012a01e-52b6-4099-be72-058cf1931847%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.