aajjbb's blog

Palindromic Paths
By aajjbb, 11 years ago, In English

Hello.

I'm trying to solve Palindromic Paths Link. Given a graph with letters in the edges, find longest and smallest palindrome from vertex 0 to vertex N — 1. My current solution based on a backtracked dfs easily exceed the time limits, do someone know a faster way to find it ?

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Think about DP solution

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Do you have any state in mind ? I can't think of way to build a palindrome with lower states. I managed to think of a do[current_node][previous_node], but I don't know a way to keep track of ('I know inserting such a letter, I'll end up with a palindrome'). I don't know whether the explanation of my point was clear.

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

      Well, what about this problem? say we have two disconnected DAGs (G1, G2) and two nodes x & y (where x belongs to G1, y belongs to G2) and we want to find the longest common path (edges is labeled with a letters) starting from x & y.. easy one, right?

      Back to our problem, what if we only have one graph and also two starting nodes (0, n-1) and we need to make simultaneously steps such that we take two edges with the same letter until they meet at the same node? that's exactly what we need!

      Overall running time is O(pow(n, 4))

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

        Hi, I finally came up with a dp solution, the states are clear, but I'm still confused by now Wrong Answer responses. I haven't found any test case to break my solution, but I've found something more curious, for a test case:

        3
*XX
X*X
XX*

        My solution prints "ZZ" as it seems to be the biggest palindromic path, but I found a solution which gets accepted that returns "*" which is obviously an inconsistent output. Can you find a possible test case which breaks my code or prove me that an "*" answer to a valid test case is valid ? Thanks

        My Solution (WA)

        Weird behavior solution in mentioned test case (AC)

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          Printing '*' is not a valid answer, here's some test cases that your program failed on it

          Input

          AC Output

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

            Thank you so much, but do you know it's now clear that there are issues with Live Archive tests. I'm still working on fix my solution, do you know some other online judge with this problem with consistent tests ?

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

          Can you explain how is the states? Thanks before hand

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

I finally solved this problem, thank you so much, I appreciate your help. By the way, I recommend this problem to anyone who's looking for better knowledge on dynamic programming with strings.

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

    Please answer my post above. Thanks

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

      What's your doubt at all ? Mostafa.Gabriel was pretty clear in his explanation. By the way, Imagine a state, [leftmost city][rightmost city], Starting from a state [0][N-1], you can move on cities if the letter on path from the leftmost to another one is the same as a path from the rightmost to another one. I think you can go further now.

      → Reply