Timeline for Can the gold mine problem be solved using divide-and-conquer?
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 13, 2016 at 23:13 | vote | accept | NmdMystery | ||
| Oct 13, 2016 at 23:13 | vote | accept | NmdMystery | ||
| Oct 13, 2016 at 23:13 | |||||
| Oct 13, 2016 at 23:13 | vote | accept | NmdMystery | ||
| Oct 13, 2016 at 23:13 | |||||
| Oct 13, 2016 at 23:13 | answer | added | NmdMystery | timeline score: 0 | |
| Oct 8, 2016 at 23:19 | vote | accept | NmdMystery | ||
| Oct 13, 2016 at 23:13 | |||||
| Oct 8, 2016 at 14:51 | answer | added | amon | timeline score: 1 | |
| Oct 7, 2016 at 23:49 | history | edited | NmdMystery | CC BY-SA 3.0 |
edited body
|
| Oct 7, 2016 at 23:49 | comment | added | NmdMystery | @TannerSwett Sorry I should have specified - m = n. | |
| Oct 7, 2016 at 23:48 | comment | added | NmdMystery | @PeterTaylor Yes, additional space, and the grid is read-only (otherwise you're technically making use of O(n^2) space). | |
| Oct 7, 2016 at 23:47 | comment | added | NmdMystery | @WinstonEwert My exact problem is slightly different - I'm using a well known problem as an example where the same principles apply - but I want to know if it can be done with divide and conquer, specifically. I figured out my own problem, but I'm not sure if the same solution applies here so I'll leave the question open. | |
| Oct 7, 2016 at 23:06 | comment | added | Sophie Swett | When you say O(n), does n mean the width of the input grid or the total number of cells? | |
| Oct 7, 2016 at 21:23 | comment | added | Peter Taylor | By O(n) space, do you mean O(n) additional space on top of the Theta(mn) space required to hold the original grid? And should answers assume that the grid is read-only? | |
| Oct 7, 2016 at 19:45 | comment | added | Winston Ewert | Do you really need to avoid dynamic programming, or do you just need to avoid the n^2 space requirement? | |
| Oct 7, 2016 at 19:14 | comment | added | 8bittree | A few observations: If all cells have a >0 value, then moving diagonally is never a good idea and all best paths will always end at the top right. If all cells are >=0, then diagonal movement might not hurt in some cases, and there may be many equivalent best paths that end short of the top right. If cells can have negative values, then diagonal moves may be essential and the best path(s) could end anywhere, even at the bottom left. Interestingly, the >0 and >=0 observations do not hold in the version in your link. | |
| Oct 7, 2016 at 18:31 | review | First posts | |||
| Oct 15, 2016 at 4:22 | |||||
| Oct 7, 2016 at 18:31 | history | asked | NmdMystery | CC BY-SA 3.0 |