Last Updated: 30 Mar, 2021

Most Lucky String

Hard

Asked in companies

Solve now

Problem statement

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

Solve now

Approaches

01 Approach

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:

Let adj be the adjacency list of the given graph.
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.
Let ans be an array of size K that stores the path that Mr. X should follow.
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).
Iterate from i = 0 to N - 1
- Initialize currentDifference as 0, and currentOrder as an empty array.
- Call generateOrders(i, 0, currentDifference, currentOrder).
Return the array ans.

Solve now

02 Approach

In the previous approach, the function generateOrder(i, j, currentDifference, currentOrder) is recursively being calculated several times for the same values. So, here we can use the technique of memoization to optimize the working of the previous approach. We will create a 2D Matrix to store all the previously computed values so that no value is being calculated multiple times.

Steps:

Let adj be the adjacency list of the given graph.
We will define two 2-D arrays having N and K columns. The first array, minChanges, will be used to store the number of changes from the lucky string, minChanges[i][j] stores the minimum possible changes from the special string possible if we visit i'th city on the j'th day. Note that we are storing all the changes done from the j'th day to the final day. Initialize all its elements as INT_MAX. The second array, optimalOrder, stores the city that should be visited on the next day, which we will use to generate the best path after finding the minimum difference possible that can be achieved. Initialize all its elements as -1.
We will define a function findMinDifference(i, j) to find the minimum number of differences we can get if we visit the City - i on j'th day.
- If minChanges[i][j] is not equal to INT_MAX, then we will return minChanges[i][j] as we have already calculated it.
- Set the variable currentChanges as 0.
- Iterate from l = 0 to 2
  - If ARR[i][l] is not equal to S[3*j + l], then increase currentChanges by 1.
- If j equals K - 1 then, we will return currentChanges. This serves as the base case of the recursive function.
- Otherwise,
  - Iterate through the adjacency list of the city - i
    - Let neighbour be the current city.
    - Call the function findMinDifference(neighbour, j+1). Let currDifference be the returned value.
    - If currDifference + currentChanges is smaller than minChanges[i][j], then
      - Set minChanges[i][j] as currDifference + currentChanges.
      - Update optimalOrder[i][j] as neighbour.
  - Return minChanges[i][j].
Initialize start as -1 and minTotalChanges as INT_MAX.
Iterate from i = 0 to N - 1
- Call findMinDifference(i, 0).Let currTotalChanges be the returned value.
- If currTotalChanges is smaller than minTotalChanges, then
  - Set minTotalChanges as currTotalChanges.
  - Set start as i.
Let ans be the array of size K that stores the order in which Mr. X should visit cities.
Let dayCount be a variable to store the count of the current day. Initialize it as 0.
While dayCount is less than K, then
- Set ans[dayCount] as start.
- Set start as optimalOrder[start][dayCount].
- Increase dayCount by 1.
Return the array ans

Solve now

03 Approach

In the first approach, the function generateOrder recursively generates all the possible paths, which has many overlapping subproblems. i.e. a recursive function computes the same sub-problems again and again. So we can use Dynamic Programming to overcome the overlapping subproblems.

Steps:

We will define two 2-D arrays having N and K columns. The first array, minDifference, will be used to store the DP states, minDifference[i][j] stores the minimum possible difference from the special string possible if we visit i'th city on the j'th day. Initialize all its elements as INT_MAX. The second array, optimalOrder, stores the city that should be visited on the previous day, which we will use to generate the best path after finding the minimum difference possible that can be achieved. Initialize all its elements as -1.
Iterate from i = 0 to N - 1
- Set minDifference[i][0] as 0.
- Iterate from l = 0 to 2
  - If ARR[i][l] is not equal to S[l], then increase minDifference[i][0] by 1.
Iterate from i = 1 to K - 1
- Iterate through the edge list,
  - Let firstCity and secondCity be the two cities connected by the current edge.
  - Set the two variables firstCost and secondCost as 0 each.
  - Iterate from l = 0 to 2
    - If ARR[firstCity][l] is not equal to S[3*i + l], then increase firstCost by 1.
    - If ARR[secondCity][l] is not equal to S[3*i + l], then increase secondCost by 1.
  - If minDifference[firstCity][i] is greater than minDifference[secondCity][i-1] + firstCost, then
    - Set minDifference[firstCity][i] as minDifference[secondCity][i-1] + firstCost.
    - Update optimalOrder[firstCity][i] as secondCity.
  - If minDifference[secondCity][i] is greater than minDifference[firstCity][i-1] + secondCost, then
    - Set minDifference[secondCity][i] as minDifference[firstCity][i-1] + secondCost.
    - Update optimalOrder[secondCity][i] as firstCity.
Let start be the index of the row having the minimum value in the last column in the array minDifference. This is the index of the city that Mr. X should end his journey.
Let ans be the array of size K that stores the order in which Mr. X should visit cities.
Let dayCount be a variable to store the count of the current day. Initialize it as K - 1.
While dayCount is greater than equal to 0, then
- Set ans[dayCount] as start.
- Set start as optimalOrder[start][dayCount].
- Decrease dayCount by 1.
Return the array ans.

Solve now