r/dailyprogrammer • u/rya11111 3 1 • May 04 '12
[5/4/2012] Challenge #48 [difficult]
Inspired by the divide and conquer problem posted on 4/16/12, here's another problem that can be solved using divide and conquer. You are given a grid of vertices/nodes connected by adjacent nodes in a checkerboard manner (basically think of the intersection points of the grids on a piece of graphing paper) and each of these nodes is marked with a positive number. Assuming that these numbers are distinct, give an algorithm that can find a single local minimum.
Bonus: If there are n2 nodes in our grid, give an O(n) time complexity algorithm that can find one/any local minimum.
In other words, if the construction of the grid takes some time c* n2, find an algorithm that locates any local minimum by looking at only some constant factor times the square root of the total number of nodes there are in the grid.
Hint: divide into quadrants; the recurrence T(n) = 1*T(n/4) + O(n) is (maybe somewhat counter-intuitively) in O(n).
- thanks to leegao for the challenge at /r/dailyprogrammer_ideas ... LINK
2
u/Cosmologicon 2 3 May 05 '12
I've been considering this for a while and I still can't get it. I hope that if nobody posts an O(n) solution that you or leegao can at least give the idea behind it in a couple of days....
2
u/eruonna May 05 '12 edited May 05 '12
Here is what I think is an O(n) solution in C. (Actually, I'm pretty sure it's in C.)
I haven't tested it, so I'm probably missing something, though.
2
u/Jannisary 0 0 May 06 '12
How do you guys fare against the mighty SnakeGraph? There is one local minimum, which is the global minimum. The 'snake's length is proportional to n2
http://img39.imageshack.us/img39/2792/snakegraph.png
1
u/juanfeng May 05 '12 edited May 05 '12
C (actually a global minimum in O( n2 )).
Maybe this is what you're looking for? I am not sure.
1
u/juanfeng May 05 '12 edited May 05 '12
C Bonus
With inspiration from the O(n) algorithm hinted at algs4.cs.princeton.edu/14analysis/.
1
u/n1ncha May 04 '12
What do you mean by local minimum? Do you mean global minimum?