dreamplay's blog

Doubt in ABC path.
By dreamplay, 9 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Solution with only dfs will work in O(h2·w2) time. Simple memorization will speed up it to O(h·w).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    • 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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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:

      .......
CCCCCCC
BBBBBBB
AAAAAAA
BBBBBBB
CCCCCCC
.......
      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        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:

        ABCDE...
BCDEF...
CDEFG...
DEFGH...
........

        Here for most of paths for almost every cell on a path you'll have to check 2 possible moves.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it -7 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Thanks Lebron and Wackloner.

            Yeah I meant the Lebron`s way.

            → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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?

          → Reply