| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
http://www.spoj.com/SPOJ/problems/ABCPATH/
Consider the above problem which can possibly have a maximum of 2500 letters.
It is a dp on graphs problem,solvable by dfs.
But I had this doubt
Let us consider using say ** dfs only** and not using any sort of DP. What is then the worst case time complexity of the dfs-solution. Expressed in terms of number of steps/letters traversed on the graph.
Solution with only dfs will work in O(h2·w2) time. Simple memorization will speed up it to O(h·w).
I understood with Memoization ,it would take O(h.w) steps.
How do you claim the only dfs complexity=O(h^2w^2)??Note that maximum path length=26=max(h)/2=max(w/2)
Like if there are 2 paths A1-B1-C-D-E and A2-B2-C-D-E ,(A1,A2 are As at different places)
traversing them by memoization would be (2)+(2)+(3) = 7 steps
whereas in case of ONLY DFS it would be (5)+(5) = 10 steps.
So How do You Find a tight bound on maximum number of steps without DP.
-Thanks
It's an asymtotic estimate. If u wanna to count maximum number of steps, I can't count it strictly. But can consider that it's about
. In such test:
I guess when dreamplay says about only dfs — he means full search without any pruning and memoization.
One can see that such solution works in O(2^(h + w)) on such case:
Here for most of paths for almost every cell on a path you'll have to check 2 possible moves.
I thought that DFS means at least information about visited vertices. And what you are talking about it's a brute. Isn't me right?
Actually, I guess it doesn't really matter, because we don't know what exactly author wants. But we described both cases, so we're fine anyway.
Thanks Lebron and Wackloner.
Yeah I meant the Lebron`s way.
Considering your pattern , also since I would stop at Z, and h<=50,w<=50 I get no. of dfs calls on A to be ~50.
Since for every A it would take O(2^26) thus giving O(50*2^26).
right?