PalindromePath
SRM 677 · 2015-11-03 · by cgy4ever
SRM 677 · 2015-11-03 · by cgy4ever · Dynamic Programming, Graph Theory
Problem Statement
Problem Statement
You are given an undirected graph with n nodes, labeled 0 through n-1.
You are given the description of its edges in int[] s a and b and in the String c.
For each valid i, the vertices a[i] and b[i] are connected by an edge, and the character c[i] is the label of that edge.
A walk in the graph is any sequence of consecutive edges. (In other words, a walk is a path that may visit the same vertex and also use the same edge multiple times.) The length of a walk is the number of edges it contains. The label of a walk is the concatenation of labels of edges it contains, in order.
A palindrome is a string that reads the same forwards and backwards. Some palindromes: "a", "abba", "racecar", "steponnopets".
We are interested in walks that go from node 0 to node 1 and have a palindromic label. Return the length of the shortest such walk. If there is no such walk, return -1 instead.
A walk in the graph is any sequence of consecutive edges. (In other words, a walk is a path that may visit the same vertex and also use the same edge multiple times.) The length of a walk is the number of edges it contains. The label of a walk is the concatenation of labels of edges it contains, in order.
A palindrome is a string that reads the same forwards and backwards. Some palindromes: "a", "abba", "racecar", "steponnopets".
We are interested in walks that go from node 0 to node 1 and have a palindromic label. Return the length of the shortest such walk. If there is no such walk, return -1 instead.
Constraints
- n will be between 2 and 20, inclusive.
- a will contain between 1 and n*(n-1)/2 elements, inclusive.
- a, b and c will contain the same number of elements.
- Each element in a will be between 0 and n-1, inclusive.
- Each element in b will be between 0 and n-1, inclusive.
- Each character in c will be a lowercase English letter ('a'-'z').
- For each valid i, a[i] != b[i].
- If i!=j then {a[i], b[i]} != {a[j], b[j]}.
Examples
0)
5
{2,2,0,3,4}
{0,1,3,4,1}
"abxyx"
Returns: 3
The shortest walk between 0 and 1 is 0-2-1. However, the label of this walk is "ab" which is not a palindrome. The shortest walk that has a palindromic label is 0-3-4-1.
1)
5
{2,2,0,3,4}
{0,1,3,4,1}
"abxyz"
Returns: -1
This time there is no such path.
2)
7
{0,0,3,4,5,6}
{2,3,4,5,6,1}
"abaaaa"
Returns: 9
Note that sometimes you need to use an edge more than once: the optimal solution is 0-2-0-2-0-3-4-5-6-1.
3)
6
{0,0,3,4,5}
{2,3,4,5,1}
"abaaa"
Returns: -1
4)
2
{0}
{1}
"x"
Returns: 1
Submissions are judged against all 84 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PalindromePath with a public method int shortestLength(int n, vector<int> a, vector<int> b, string c) · 84 test cases · 2 s / 256 MB per case