Timeline for Visiting points on a number line while minimizing a cost not related to distance
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 11, 2013 at 17:24 | comment | added | Slater Victoroff | Ohwait, misunderstood problem, rethinking. | |
| Mar 11, 2013 at 17:23 | comment | added | Barron W. | It's actually 19 + (19 + 19 + 64) ..., because you have to factor in the time it takes you go from -19 to 64. The actual sum is 19 + (19 + 19 + 64) + (19 + 19 + 64 + 5) + (19 + 19 + 64 + 5 + 131) = 466 | |
| Mar 11, 2013 at 17:20 | comment | added | Slater Victoroff | I think you've done some optimization calculations wrong unless I misunderstand the problem. [-19, 64, 69, -62] is the optimal solution with a cost of 321. [-19, -62, 64, 69] has a cost of 338. (19+(64+19)+(69+19)+(69+62))=321. (19+62+(64+62)+(69+62))=338 | |
| Mar 11, 2013 at 4:48 | comment | added | Barron W. | It gets [-19, 64, 69, -62 ] wrong. The optimal order is [-19, -62, 64, 69] = 462. The greedy algorithm gives [-19, 64, 49, -62] = 466 | |
| Mar 11, 2013 at 3:57 | comment | added | Slater Victoroff | I updated the description to be a bit more explicit. Let me know if it still doesn't work. | |
| Mar 11, 2013 at 3:56 | history | edited | Slater Victoroff | CC BY-SA 3.0 | added 715 characters in body |
| Mar 11, 2013 at 3:52 | comment | added | Barron W. | I'm pretty sure I implemented it exactly as said though.. Weird.. | |
| Mar 11, 2013 at 3:49 | comment | added | Slater Victoroff | I'm fairly certain you've incorrectly implemented the algorithm I explained, or perhaps I was simply not clear enough. My algorithm returns a correct result in both these cases :/ It predicted that the answer for the first example should be [-18,43,63,-82,-98], is that not correct? | |
| Mar 10, 2013 at 19:43 | comment | added | Barron W. | Also cases like [-10,-11, 10,20,30,40,50,60,70]. The correct and only solution is to collect all the negative ones then collect the positive ones. For an answer of 455. | |
| Mar 10, 2013 at 16:29 | comment | added | Barron W. | [43, -18, -98, -82, 63] | |
| Mar 10, 2013 at 15:36 | comment | added | Barron W. | There was a simple test case where this failed. I'll try to find it, but it was with N = 4 or 5. | |
| Mar 10, 2013 at 14:08 | comment | added | Slater Victoroff | When does this not work? | |
| Mar 10, 2013 at 1:44 | history | post merged (destination) | |||
| Mar 10, 2013 at 1:43 | history | migrated | from stackoverflow.com (revisions) | ||
| Mar 9, 2013 at 19:00 | comment | added | Barron W. | This doesn't always work. Maybe you could sort the coords and then do a search where the state contains a range [i..j] (which signifies which range you've visited) and the cost and the current time. | |
| Mar 9, 2013 at 5:58 | history | answered | Slater Victoroff | CC BY-SA 3.0 |