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 ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Think about DP solution
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.
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))
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:
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)
Printing '*' is not a valid answer, here's some test cases that your program failed on it
Input
AC Output
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 ?
1244 — Palindromic paths
Can you explain how is the states? Thanks before hand
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.
Please answer my post above. Thanks
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.