Most Lucky String

Hard
0/120
Average time to solve is 45m
profile
Contributed by
3 upvotes
Asked in companies
Webarch ClubAmdocs

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3 2 2
AAB BBD ABC
AABABCBBD
0 2
1 2
4 3 1
AAA BBD CCD BBC
BFC
1 2
0 3
1 3
Sample Output 1 :
valid
valid
Explanation for Sample Input 1 :
For the first test case : 
Mr. X can start his journey at City-0, then go to City-2 and then end his journey at City-1. The special string will be "AABABCBBD" which is exactly same as the lucky string.

For the second test case :
Mr. X should visit City-3 only, as the special string in this case differs by the lucky string at only one place.
Sample Input 2 :
2
3 3 2
ABC BBD ARQ
ABDABD
1 2
0 2
0 1
2 1 1
AAB BBA
AAA
1 0
Sample Output 2 :
valid
valid
Explanation for Sample Input 2 :
For the first test case : 
Mr. X should follow the path City-0 => City-1.

For the second test case:
Mr. X should visit City-1 only.
Hint

Try to think of generating all the possible order of cities that Mr. X should visit. 

Approaches (3)
Recursive 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: 

  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.
Time Complexity

O(N^K), where N is the number of cities and K is the number of days Mr. X will stay at Ninjaland.

 

In the worst case, when all cities are directly connected to each other, we are making N - 1 recursive calls for each day. Therefore, for K days, we will be calling the recursive function N^K times. Hence, the overall time complexity is O(N^K).

Space Complexity

O(K*(N^K)), where N is the number of cities and K is the number of days Mr. X will stay at Ninjaland.

 

In the worst case, when all cities are directly connected to each other, there are N^K possible order of cities, and each path is of length K. Hence, the overall space complexity is O(K*(N^K)).

Code Solution
(100% EXP penalty)
Most Lucky String
Full screen
Console