Partially Correct


#1

I’ve got partially correct answer but don’t know why because test case inputs are not opened
I’ve just got following messages:

  • Wrong Answer. Your program’s output doesn’t match the expected output. You can try testing your code with custom input and try putting debug statements in your code.

  • Your code might be failing for larger test-cases

How can I find what’s the problem and debug it?

typedef unordered_map<string, pair<int, int>> memoType;

pair<int, int> cut(int start, int end, vector<int>& points, memoType& M) {
    string key = to_string(start) + "_" + to_string(end);

    auto pos1 = M.find(key);
    if (pos1 != M.end()) {
        return pos1->second;
    }

    pair<int, int> min(INT_MAX, 0);

    int size = end - start;
    for (int i = 0; i < (int)points.size(); i++) {
        if (points[i] <= start) continue;
        if (points[i] >= end) break;

        auto rc1 = cut(start, points[i], points, M);
        auto rc2 = cut(points[i], end, points, M);

        if (min.first > size + rc1.first + rc2.first) {
            min.first = size + rc1.first + rc2.first;
            min.second = points[i];
        }
    }
    
    if (min.first == INT_MAX) return make_pair(0, 0);

    M[key] = min;

    return min;
}

vector<int> buildSeq(memoType& M, int start, int end) {
    vector<int> res;
    string key = to_string(start) + "_" + to_string(end);
    auto pos1 = M.find(key);

    if (pos1 != M.end()) {
        int P = pos1->second.second;
        res.push_back(P);

        vector<int> rc1 = buildSeq(M, start, P);
        vector<int> rc2 = buildSeq(M, P, end);

        res.insert(res.end(), rc1.begin(), rc1.end());
        res.insert(res.end(), rc2.begin(), rc2.end());

        return res;
    }

    return vector<int>();
}

vector<int> Solution::rodCut(int A, vector<int> &B) {
    if (B.empty()) return vector<int>();

    memoType M;
    auto res = cut(0, A, B, M);

    return buildSeq(M, 0, A);
}

#2

Integer is overflowing for you, use unsigned long long to store cost.


#3

Thank you!.
I’ve passed all the tests.