How can I generate path according to lexicograpical ordering for this solution structure? (expect that it should be doable with this structure)


  • 0
    E

    I wrote the following code during the contest time duration. It uses cost[k] to store the best cost from index 1 to K+1, and uses DP (top-down, in the form of recursion with memoization using cost[] vector). The 'best' and 'bestj' variables in findPath are used to store the best cost when comparing among the i-1, i-2,...i-B for an index i.

    This program doesn't seem to produce path output for the lexicographical ordering rule, and gives wrong answer for the following case.

    Input:[0,0,0,0,0,0]
    3
    Output:[1,3,6]
    Expected:[1,2,3,4,5,6]
    

    Can someone explain how I can make this work for the lexicographical ordering rule? Most explanations in this forum have DP[K] storing the cost for K+1... to N the index, so that doesn't directly apply. How can I make the way this solution is constructed produce also path per the lexicographical ordering?

    class Solution {
    public:
        vector<int> cheapestJump(vector<int>& A, int B) {
            vector<int> path;
            vector<int> cost(A.size(), INT_MAX);
            path.emplace_back(1);
            cost[0] = A[0];
            findPath(A, B, cost, path, A.size()-1);
    
            if (A[A.size()-1] != -1) 
                path.emplace_back(A.size());
            else 
                path.clear();
            return path;
        }
        
        void findPath(vector<int>& A, int B, vector<int>& cost, vector<int>&path, int idx) {
            if (idx == 0) return;
            int best = INT_MAX;
            int bestj = -1;
            for (int i=1; i<=B && idx-i >=0 && A[idx] != -1; i++) {
                int j = idx-i;
                if (A[j] == -1) continue;
                if (cost[j] == INT_MAX) {
                    findPath(A, B, cost, path, j);
                    path.pop_back();
                }
                if (cost[j] == INT_MAX) {
                    A[j] = -1;
                    continue;
                }
                int tmp = cost[j] + A[idx];
             
                if (tmp <= best) {
                    best = tmp;
                    bestj = j;
                }
            }
            cout << idx << " ::: " << best << " ::: " << bestj << endl;
            if (bestj != -1) {
                cost[idx]= best;
                path.emplace_back(bestj+1);
            }
            else 
                A[idx] = -1;
        }
        
        
    };
    

  • 0
    V

    @edaengineer said in How can I generate path according to lexicograpical ordering for this solution structure? (expect that it should be doable with this structure):

    o that doesn't dir

    I had the same issue as well, I couldn't find a way, let me know once you do.


  • 0

    @venkata-sai-krishn same issue here for this test case. Would love to know how you solved it. Thanks!


  • 0

    Hey @edaengineer same issue here.
    I was wondering whether we are wrong to " store the best cost from index 1 to K+1"?
    Still stuck in this question, love to hear your advice ! Thanks!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.