Timeline for Solving road trip problem in linear time
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 20, 2015 at 21:41 | history | tweeted | twitter.com/#!/StackCompSci/status/579035066359287808 | ||
| Mar 20, 2015 at 10:40 | comment | added | David Richerby | @Raphael $k$ is a number in the input but it's bounded by $n$, the total length of the road. So Yuval's correct: it is $O(n^2)$. | |
| Mar 20, 2015 at 9:51 | answer | added | Tom van der Zanden | timeline score: 6 | |
| Mar 20, 2015 at 7:55 | comment | added | greybeard | Keeping a standard min-queue of $k$ pairs $(tripcost, city)$ should cut this to $O(nlog k)$. Someone please surprise me with an $O(n)$ solution. | |
| Mar 20, 2015 at 7:00 | comment | added | Raphael | @YuvalFilmus Ah, a prime case where abuse of notation renders a sentence absolutely meaningless. ^^ | |
| Mar 20, 2015 at 6:59 | comment | added | Yuval Filmus | @Raphael No, I did mean $O(n^2)$. We want a better upper bound. We don't care about lower bounds here. | |
| Mar 20, 2015 at 6:58 | comment | added | Raphael | @YuvalFilmus means to use $\Theta$ there. I don't see how even $O(n^2)$ is correct, though; $k$ is a number so $\Theta(nk)$ is pseudopolynomial, far away from linear time. | |
| Mar 20, 2015 at 6:57 | history | edited | Raphael |
edited tags
|
|
| Mar 20, 2015 at 6:26 | comment | added | Yuval Filmus | You can try other popular paradigms such as greedy and divide and conquer. | |
| Mar 20, 2015 at 3:58 | comment | added | Dave | The exercise does suggest that it is achievable in $O(n)$ time. However, I'm struggling to see how it can be done. | |
| Mar 20, 2015 at 3:28 | comment | added | Yuval Filmus | Do you have more than an intuition? Does the exercise call for a better running time? Otherwise, I see no reason why you could improve on $O(n^2)$ substantially. | |
| Mar 20, 2015 at 3:27 | comment | added | Yuval Filmus | Since $k$ is part of the input, the complexity is actually $O(n^2)$. | |
| Mar 20, 2015 at 2:34 | history | asked | Dave | CC BY-SA 3.0 |