Most Lucky String

Posted: 30 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

Mr. X is planning to visit Ninja Land. Ninja Land has 'N' cities numbered from 0 to 'N-1' and 'M' bidirectional roads. Each road connects two of the 'N' cities, and no two cities have multiple roads between them. All the 'N' cities have a certain 3 letter code given in the array 'ARR'. Mr. X will stay at Ninja land for exactly 'K' days, and he does not like to stay in the same city for two consecutive days. Therefore, he needs to change his city every day of his stay. He also has a special string that is initially empty. Mr. X has a habit that whenever he visits a city, he appends the code of that city to his special string.

Mr. X has a lucky string 'S' of length '3*K'. Mr. X wants to plan his stay in such a manner that the number of places where the final special string differs from the lucky string is the minimum possible. Your task is to find any such order of cities that Mr. X should visit satisfying the above conditions.

Input Format :
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains three space-separated integers, 'N', 'M' and 'K', denoting the number of cities, the number of bidirectional roads, and the number of cities that Mr. X will visit, respectively. 

The second line of each test case contains 'N' space-separated strings denoting the elements of the array 'ARR'.

The third line of each test contains the special string 'S'.

The next 'M' lines of each test case contain the description of the 'M' roads.
The 'i'th' line contains two space-separated integers, 'City1', 'City2'. 'City1' and 'City2' denote the two cities that are connected by the 'i'th' road.
Output Format :
For each test case, the checker will print "valid" if the returned order of cities results in a string that differs from the lucky string 'S' at the minimum possible places. Otherwise, the checker will print "invalid".
Print the output of each test case in a new line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
2 <= N <= 1000
1 <= M  <= min(1000,(N*(N-1))/2)
1 <= K <= 100
|ARR[i]| = 3 
|S| = 3*K 
0 <= City1, City2 <= N-1

Every city is reachable from every other city, any two cities are directly connected by at most one road and all the input strings contain uppercase English letters only.

Where 'T' denotes the number of test cases, 'N' denotes the number of cities, 'M' denotes the number of roads, 'K' denotes the number of cities that Mr. X will visit, ARR[i] denotes the 'i'th' element of the array 'ARR', 'S' denotes the lucky string, 'City1' and 'City2' denotes the two cities that are connected by the 'i'th' road, .

Time Limit : 1 sec
Approach 1

The idea is to use a recursive approach to generate all the possible orders of cities that Mr. X should visit and select the best path. The recursive idea is very clear that if Mr. X visits any city on the i'th day, then he can go to any of the cities connected to that city on the (i+1)'th day. Using this idea, we can generate all the possible order of cities Mr. X can visit. After generating the corresponding special string for a particular path, we will count the number of places the generated string differs with the lucky string. In the end, we will select the path for which the generated string differs with the lucky string at the least possible places.

 

Steps: 

  1. Let adj be the adjacency list of the given graph.
  2. Let minDifference be a variable that stores the minimum number of places the generated string differs with the lucky string. Initialize it as INT_MAX.
  3. Let ans be an array of size K that stores the path that Mr. X should follow.
  4. We will define a function generateOrders(i, j, currentDifference, currentOrder) to generate all orders if we go through City i on the j'th day. The variable currentDifference stores the number of places the current path differs, and currentOrder stores the order of cities in the current path.
    • Iterate from l = 0 to 2
      • If arr[i][l] is not equal to S[3*j+l], then increase currentDifference by 1.
    • Add the index i to the array currentOrder. 
    • If j equals K - 1, then
      • If currentDifference is smaller than minDifference, then set currentDifference as min difference, and update ans as currentOrder.
    • Otherwise
      • Iterate through the adjacency list of city - i
        • Let neighbour be the current city.
        • Call the function generateOrders(neighbour, j+1, currentDifference, currentOrder).
  5. Iterate from i = 0 to N - 1
    • Initialize currentDifference as 0, and currentOrder as an empty array.
    • Call generateOrders(i, 0, currentDifference, currentOrder).
  6. Return the array ans.
Try Problem