Dynamic Programming : Timus Online Judge 1172 Ship Routes

Question

I have been stuck on this problem from a long time. It must have a dynamic programming solution as it has been tagged as "dynammic programming". Please suggest an approach.

Question Link

Abridged problem statement:

There are 3 islands having N cities on each of them. There is a path from every city on an island to every city on another island, ie. there is no path connecting cities on the same island. Find the number of ways of visiting all the 3*N cities. Note that 2 trips are identical if the successions of the 3*N cities are identical or if the succession of the 3*N cities of the first trip is the same as the succession of the 3*N cities of the 2nd trip, read backwards (for instance, if every island had 1 city, numbered according to the island's number, the trips 1-2-3-1 and 1-3-2-1 would be identical).

Constraints:

1 ≤ N ≤ 30

Sample Input/Output:

For N=2, answer = 16.

Answer 1

This is just my idea:

First, we can solve the problem if we can solve two subproblems

• Assume that you need to generate a string with length 3*N made only from 1 , 2 or 3 , count how many ways we can create this string, with the condition that there is no 2 consecutive occurrences of 1, 2 or 3, and for each type of character, there should be N of them in the string. You can solve this using DP

• Secondly, from all the string created, removed the first character, because of the condition that string can be read equally backward and forward, so each string will be counted twice, except palindrome. so , we need to count the number of palindrome for those 3*N - 1 string. This can be solved by DP

And, now, we can replace each position of 1,2 or 3 in the string with one city in island 1, 2 or 3 and there is (N!)^3 way to do that for each string , and we have the answer