Given an integer K and a matrix of size t x t. construct a string s consisting of first t lowercase english letters such that the total cost of s is K

user_13403510 0
Viewed 309

I'm solving this problem and stuck halfway through, looking for help and a better method to tackle such a problem:

problem:

Given an integer K and a matrix of size t x t. we have to construct a string s consisting of the first t lowercase English letters such that the total cost of s is exactly K. it is guaranteed that there exists at least one string that satisfies given conditions. Among all possible string s which is lexicographically smallest.

Specifically the cost of having the ith character followed by jth character of the English alphabet is equal to cost[i][j].

For example, the cost of having 'a' followed by 'a' is denoted by cost[0][0] and the cost of having 'b' followed by 'c' is denoted by cost[1][3].

The total cost of a string is the total cost of two consecutive characters in s. for matrix cost is

 [1 2] 

 [3 4],

and the string is "abba", then we have

  • the cost of having 'a' followed by 'b' is is cost[0][1]=2.
  • the cost of having 'b' followed by 'b' is is `cost0=4.
  • the cost of having 'b' followed by 'a' is cost0=3.

In total, the cost of the string "abba" is 2+4+3=9.

Example: consider, for example, K is 3,t is 2, the cost matrix is

[2 1]
[3 4]

There are two strings that its total cost is 3. Those strings are:

  • "aab"
  • "ba"

our answer will be "aab" as it is lexicographically smallest.

my approach

I tried to find and store all those combinations of i, j such that it sums up to desired value k or is individual equals k. for above example

v={
   {2,1},
   {3,4}
  }

k = 3

and v[0][0] + v[0][1] = 3 & v[1][0] = 3 . I tried to store the pairs in an array like this std::vector<std::vector<std::pair<int, int>>>. and based on it i will create all possible strings and will store in the set and it will give me the strings in lexicographical order.

i stucked by writing this much code:

#include<iostream>
#include<vector>
int main(){
    using namespace std;
    vector<vector<int>>v={{2,1},{3,4}};
    vector<pair<int,int>>k;
    int size=v.size();
    for(size_t i=0;i<size;i++){
        for(size_t j=0;j<size;j++){
            if(v[i][j]==3){
                k.push_back(make_pair(i,j));
            }     
        }
    }
}

please help me how such a problem can be tackled, Thank you. My code can only find the individual [i,j] pairs that can be equal to desired K. I don't have idea to collect multiple [i,j] pairs which sum's to desired value and it also appears my approach is totally naive and based on brute force. Looking for better perception to solve the problems and implement it in the code. Thank you.

vector data-structures stl algorithm c++
2 Answers

In your implementation, you would probably need another vector of vectors of pairs to explore all your candidates. Also another vector for updating the current cost of each candidate as it builds up. Following this approach, things start to get a bit messy (IMO).

A more clean and understandable option (IMO again) could be to approach the problem with recursivity:

#include <iostream>
#include <vector>
#define K 3

using namespace std;

string exploreCandidate(int currentCost, string currentString, vector<vector<int>> &v)
{
    if (currentCost == K)
        return currentString;

    int size = v.size();
    int lastChar = (int)currentString.back() - 97;  // get ASCII code
    for (size_t j = 0; j < size; j++)
    {
        int nextTotalCost = currentCost + v[lastChar][j];
        if (nextTotalCost > K)
            continue;

        string nextString = currentString + (char)(97 + j); // get ASCII char
        string exploredString = exploreCandidate(nextTotalCost, nextString, v);
        if (exploredString != "00") // It is a valid path
            return exploredString;
    }

    return "00";
}

int main()
{
    vector<vector<int>> v = {{2, 1}, {3, 4}};

    int size = v.size();
    string initialString = "00"; // reserve first two positions
    for (size_t i = 0; i < size; i++)
    {
        for (size_t j = 0; j < size; j++)
        {
            initialString[0] = (char)(97 + i);
            initialString[1] = (char)(97 + j);
            string exploredString = exploreCandidate(v[i][j], initialString, v);
            if (exploredString != "00") { // It is a valid path
                cout << exploredString << endl;
                return 0;
            }
        }
    }
}

Let us begin from the main function:
We define our matrix and iterate over it. For each position, we define the corresponding sequence. Notice that we can use indices to get the respective character of the English alphabet, knowing that in ASCII code a=97, b=98... Having this initial sequence, we can explore candidates recursively, which lead us to the exploreCandidate recursive function.

First, we want to make sure that the current cost is not the value we are looking for. If it is, we leave immediately without even evaluating the following iterations for candidates. We want to do this because we are looking for the lexicographically smallest element, and we are not asked to provide information about all the candidates.
If the cost condition is not satisfied (cost < K), we need to continue exploring our candidate, but not for the whole matrix but only for the row corresponding to the last character. Then we can encounter two scenarios:

  • The cost condition is met (cost = K): if at some point of recursivity the cost is equal to our value K, then the string is a valid one, and since it will be the first one we encounter, we want to return it and finish the execution.
  • The cost is not valid (cost > K): If the current cost is greater than K, then we need to abort this branch and see if other branches are luckier. Returning a boolean would be nice, but since we want to output a string (or maybe not, depending on the statement), an option could be to return a string and use "00" as our "false" value, allowing us to know whether the cost condition has been met. Other options could be returning a boolean and using an output parameter (passed by reference) to contain the output string.

EDIT: The provided code assumes positive non-zero costs. If some costs were to be zero you could encounter infinite recursivity, so you would need to add more constraints in your recursive function.

user_143848320

This is a backtracking problem. General approach is :

a) Start with the "smallest" letter for e.g. 'a' and then recurse on all the available letters. If you find a string that sums to K then you have the answer because that will be the lexicographically smallest as we are finding it from smallest to largest letter.

b) If not found in 'a' move to the next letter.

Recurse/backtrack can be done as:

  • Start with a letter and the original value of K
  • explore for every j = 0 to t and reducing K by cost[i][j]
  • if K == 0 you found your string.
  • if K < 0 then that path is not possible, so remove the last letter in the string, try other paths.

Pseudocode :

string find_smallest() {
  for (int i = 0; i < t; i++) {
     s = (char)(i+97)
     bool value = recurse(i,t,K,s)
     if ( value ) return s;
     s = ""
  }
  return ""
}

bool recurse(int i, int t, int K, string s) {
   if ( K < 0 ) {
      return false;
   }
   if ( K == 0 ) {
      return true;
   }
   for ( int j = 0; j < t; j++ ) {
      s += (char)(j+97);
      bool v = recurse(j, t, K-cost[i][j], s);
      if ( v ) return true;
      s -= (char)(j+97);
   }
   return false;
}
user_14103030
Related